基于Fast-Newman算法的网络社团结构分解

B007青岛科技大学第八届“校长杯”数学知识竞赛暨2013年全国研究生、大学生数学建模竞赛选拔赛评阅专用页评阅记录：评阅人评分备注1目录一．摘要.................................................................2二．问题的提出............................................................4三．问题的分析............................................................5四．基本理论与算法思想....................................................64.1复杂网络的基本概念与性质...........................................64.1.1真实网络的图表示.................................................64.1.2度分布.......................................................64.1.3网络的平均最短路径和顶点的介数...............................64.1.4网络的簇系数.................................................74.2复杂网络社团结构定义...............................................84.3GN算法与Fast-Newman算法..........................................94.3.1GN算法......................................................94.3.2Fast-Newman算法............................................10五．建模过程.............................................................115.1问题一............................................................115.1.1第一题第1个网络............................................115.1.2第一题第2个网络............................................135.2.3第一题第3个网络............................................145.2问题2............................................................15六．模型的评价与改进.....................................................16七．参考文献.............................................................172青岛科技大学第八届“校长杯”数学知识竞赛暨2013年全国研究生、大学生数学建模竞赛选拔赛题目基于Fast-Newman算法的网络社团结构分解一．摘要社团结构是复杂网络的一个极其重要的特性，网络社团结构分解在生物学、计算机科学和社会学等多个领域都具有很重要的意义。复杂网络通常会呈现出社团结构特性，如何在实际网络中高效地发现社团结构是近年来复杂网络的研究热点之一。近年来，针对不同类型的大规模复杂网络，提出了很多寻找社团结构的算法。本模型基于贪婪算法的思想，根据Newman在GN算法上改进优化的一种凝聚算法——Fast-Newman算法，对问题中的多种复杂网络进行了社团结构分解，建立一种针对复杂网络社团分解的标准化方法，取得了不错的效果。最后，还分析了本算法的优缺点，提出了如何改进准确度。关键词：复杂网络社团结构分解凝聚算法GN算法Fast-Newman算法3DecompositionofNetworkCommunityStructureBasedontheFast-NewmanAlgorithmAbstractCommunitystructureisaveryimportantpropertyofcomplexnetworks．Detectingcommunitiesinnetworksisofgreatimportanceinbiology，computerscience，sociologyandsoon．Communitystructureexistsinmanyrealnetworks．Howtofindsuchcommunitieseffectivelyisoneoffocusesofmanyrecentresearchesinthebranchofcomplexnetworks．Inrecentyears，alotofcommunitydiscoveryalgorithmshavebeenproposedaimingatdifferentkindsoflargescalecomplexnetworks．Inthispaper,webasedongreedyalgorithm,AccordingtoacondensationalgorithmwhichNewmanindesigned.theGNalgorithmonoptimization--FastNewmanalgorithm.Wedecompositionavarietyofcomplexnetworkcommunitystructureinproblems,goodresultshavebeenachieved.Keywords:complexnetwork；communitystructure;GNAlgorithm;Fast-NewmanAlgorithm4二．问题的提出随着WS小世界网络模型和BA无标度网络模型的提出，国内外掀起了研究复杂网络的热潮。复杂网络的研究以系统的观点来看待真实系统，如Internet网络、电力网、新陈代谢网络等。复杂网络通常会呈现出社区结构特性，如何在实际网络中高效地发现社团结构是近年来复杂网络的研究热点之一。近年来，人们提出了许多算法来寻找复杂网络中的社团结构。然而，当网络的规模过于庞大时，寻找整个网络的全局社团结构的计算量是极大的。另外，在很多情况下关心的并不是整个网络的社团结构，而是网络中某一部分的社团结构。比如，通常只关心社会网络中某个人所在的社团的结构，或者是万维网中某个网站所在社团的局部拓扑结构。在这种情况下，就不希望消耗过多的时间来寻找全部的社团结构。揭示网络的社团结构，对于深入了解网络结构与分析网络特性是很重要的。如社会网络中的社团代表根据兴趣和背景而形成的真实的社会团体；引文网络中的社团代表针对同一主题的相关论文；万维网中的社团就是讨论相关主题的若干网站]11[；而生物化学网络或者电子电路中的网络社团可以是某一类功能单元]13,12[。发现这些网络中的社团有助于我们更加有效的理解和开发这些网络。尽管复杂网络的社团发现问题得到了大量的研究，但还存在一些尚未解决的基本问题，如社团概念虽然大量使用，但却缺少严格的数学定义；大多数社团发现算法虽然性能优越，但所需计算量却很大。这说明复杂网络中社团发现的研究还需要付出大量的努力。5三．问题的分析由题意可知，本题的目的就是建立一种模型，将复杂网络中社团进行分解。在复杂网络社团结构划分的研究中，社团结构划分算法所要划分的网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络(网络中边的权值为正实数)；另一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分网络中社团结构的算法相应分为两大类，而对于第一类网络又提出了许多不同的社团结构划分算法，划分第一类网络社团的传统算法可分为两大类，第一类是基于图论的算法，比如K—L算法]1[、谱平分法]3,2[、随机游走算法]4[和派系过滤法]6,5[等；第二类是层次聚类算法，比如基于相似度度量的凝聚算法]7[和基于边介数度量的分裂算法]10,9,8[等。2001年，Girvan和Newman提出了一种基于边介数的分裂算法，简称GN算法]8[。该算法的基本思想是不断地从网络中移除介数最大的边。边介数定义为网络中经过每条边的最短路径数目，该算法的复杂度非常高。2004年，Newman提出一种基于贪婪法思想的凝聚算法]7[，并称这种算法为Fast-Newman算法。该算法是在使得模块度不断增加的基础上进行，即每次合并沿着使模块度增多最大和减小最少的方向进行。算法总的复杂度为))((nnmO，对于稀疏网络则为)(2nO，其中n为网络中结点的个数，m为网络中边的条数。在本题中，我们选择了更为先进的Fast-Newman算法，通过把所给网络进行数据化处理，在MATLAB上实现了复杂网络的社团分解。6四．基本理论与算法思想4.1复杂网络的基本概念与性质4.1.1真实网络的图表示首先，简单介绍有关图的定义和基本概念。图G可以表示为集合),(v，},2,1{)(nGv表示图G的顶点集合，N表示网络的顶点总数，)},(,),,(),,{()(2211EEjijijiG代表边集合，E表示总边数，如果),(),(ijji，则图是无向图，否则为有向图。当网络是无向无权网络时，邻接矩阵}{ijaA是一个10对称矩阵，表示图中顶点之间的连接关系。如果顶点ji,之间有连接，则1ija：否则0ija。当网络是有向图时，邻接矩阵A是非对称的10矩阵：当网络是加权网络时，A中的非元素代表边的权重。4.1.2度分布度分布是描述网络性质的一个重要统计量。结点i的度定义为与结点i连接的边的数目。度分布)(kp定义为随机地选择一个结点，度为k的概率，或者等价地描述为网络中度为后的结点数占网络结点总数的比例。当然，对于有向网络，其度分布还可细致地分为网络的入度分布（in-degreedistribution）和出度分布(out-degreedistribution)。4.1.3网络的平均最短路径和顶点的介数网络的平均最短距离(averagepathlength)定义为网络中任意一对结点之间的最短距离的平均值，数学表达式为：GjiijdNNd)1(17其中ijd为结点ji,之间的最短路径的长度。所有结点间的最短路径长度的最大值称为网络半径(networkdiameter)。网络中不相邻的结点j和k之间的路径主要依赖于连接结点j和k的路径上所经过的结点，如果某个结点被其它许多路径经过，则表示该结点在网络中很重要。定量地描某个结点在网络中的影响力或重要性可以用顶点的介数(nodebetweeness)来衡量，这一定义最早由Freeman在1977年提出]14[。顶点i的介数iB定义为：vkjjkjkininB,)(其中jkn表示结点j、k之间的最短路径的个数，)(injk表示结点j、k之间的最短路径中经过结点i的个数。4.1.4网络的簇系数网络的簇系数(clusteringcoefficient)是衡量网络集团化程度的重要参数，是一个局部特征量。结点i的簇系数iC定义为结点i的邻接点之间实际存在的边数与所有可能的边数的比值，数学表达为：)1(iiiikkeC其中，ik表示结点i的度，ie表示结点i的邻接点之间实际存在的边数。网络的簇系数定义为对所有结点的簇系数做和求平均：NiiCNC11许多真实网络具有较大的簇系数和较小的平均最短距离。这里“较大的簇系数’’指真实网络的簇系数远远大于相同规模的随机网络的簇系数。“较小的平均最短距离’’指平