《基于Fast-Newman算法的网络社团结构分解》由会员分享，可在线阅读，更多相关《基于Fast-Newman算法的网络社团结构分解（23页珍藏版）》请在金锄头文库上搜索。
1、B007青岛科技大学第八届“校长杯”数学知识竞赛暨2013年全国研究生、大学生数学建模竞赛选拔赛评 阅 专 用 页评阅记录：评阅人评分备注目录一摘 要2二问题的提出4三问题的分析5四基本理论与算法思想64.1复杂网络的基本概念与性质64.1.1真实网络的图表示64.1.2度分布64.1.3网络的平均最短路径和顶点的介数64.1.4网络的簇系数74.2复杂网络社团结构定义74.3 GN算法与Fast-Newman算法84.3.1 GN算法84.3.2 Fast-Newman算法9五建模过程115.1问题一115.1.1第一题第1个网络115.1.2第一题第2个网络135.2.3第一题第3个网络1
2、45.2 问题215六模型的评价与改进15七参考文献16青岛科技大学第八届“校长杯”数学知识竞赛暨2013年全国研究生、大学生数学建模竞赛选拔赛题 目 基于Fast-Newman算法的网络社团结构分解 一摘 要社团结构是复杂网络的一个极其重要的特性，网络社团结构分解在生物学、计算机科学和社会学等多个领域都具有很重要的意义。复杂网络通常会呈现出社团结构特性，如何在实际网络中高效地发现社团结构是近年来复杂网络的研究热点之一。近年来，针对不同类型的大规模复杂网络，提出了很多寻找社团结构的算法。本模型基于贪婪算法的思想，根据Newman在GN算法上改进优化的一种凝聚算法Fast-Newman算法，对问
3、题中的多种复杂网络进行了社团结构分解，建立一种针对复杂网络社团分解的标准化方法，取得了不错的效果。最后，还分析了本算法的优缺点，提出了如何改进准确度。关键词：复杂网络 社团结构 分解 凝聚算法GN算法 Fast-Newman算法Decomposition of Network Community Structure Based on the Fast - Newman Algorithm AbstractCommunity structure is a very important property of complex networksDetecting communities in net
4、works is of great importance in biology，computer science，sociology and so onCommunity structure exists in many real networksHow to find such communities effectively is one of focuses of many recent researches in the branch of complex networksIn recent years，a lot of community discovery algorithms ha
5、ve been proposed aiming at different kinds of large scale complex networksIn this paper, we based on greedy algorithm,According to a condensation algorithm which Newman in designed.the GN algorithm on optimization-Fast Newman algorithm.We decomposition a variety of complex network community structur
6、e in problems, good results have been achieved.Key words: complex network；community structure; GN Algorithm; Fast-Newman Algorithm二问题的提出 随着小世界网络模型和无标度网络模型的提出，国内外掀起了研究复杂网络的热潮。复杂网络的研究以系统的观点来看待真实系统，如Internet网络、电力网、新陈代谢网络等。复杂网络通常会呈现出社区结构特性，如何在实际网络中高效地发现社团结构是近年来复杂网络的研究热点之一。近年来，人们提出了许多算法来寻找复杂网络中的社团结构。然而，当
7、网络的规模过于庞大时，寻找整个网络的全局社团结构的计算量是极大的。另外，在很多情况下关心的并不是整个网络的社团结构，而是网络中某一部分的社团结构。比如，通常只关心社会网络中某个人所在的社团的结构，或者是万维网中某个网站所在社团的局部拓扑结构。在这种情况下，就不希望消耗过多的时间来寻找全部的社团结构。 揭示网络的社团结构，对于深入了解网络结构与分析网络特性是很重要的。如社会网络中的社团代表根据兴趣和背景而形成的真实的社会团体；引文网络中的社团代表针对同一主题的相关论文；万维网中的社团就是讨论相关主题的若干网站；而生物化学网络或者电子电路中的网络社团可以是某一类功能单元。发现这些网络中的社团有助于
8、我们更加有效的理解和开发这些网络。 尽管复杂网络的社团发现问题得到了大量的研究，但还存在一些尚未解决的基本问题，如社团概念虽然大量使用，但却缺少严格的数学定义；大多数社团发现算法虽然性能优越，但所需计算量却很大。这说明复杂网络中社团发现的研究还需要付出大量的努力。 三问题的分析由题意可知，本题的目的就是建立一种模型，将复杂网络中社团进行分解。在复杂网络社团结构划分的研究中，社团结构划分算法所要划分的网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络(网络中边的权值为正实数)；另一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分网络中社团结构的算法相应分为两
9、大类，而对于第一类网络又提出了许多不同的社团结构划分算法，划分第一类网络社团的传统算法可分为两大类，第一类是基于图论的算法，比如KL算法、谱平分法、随机游走算法和派系过滤法等；第二类是层次聚类算法，比如基于相似度度量的凝聚算法和基于边介数度量的分裂算法等。2001年，Girvan和Newman提出了一种基于边介数的分裂算法，简称GN算法。该算法的基本思想是不断地从网络中移除介数最大的边。边介数定义为网络中经过每条边的最短路径数目，该算法的复杂度非常高。2004年，Newman提出一种基于贪婪法思想的凝聚算法，并称这种算法为Fast-Newman算法。该算法是在使得模块度不断增加的基础上进行，即
10、每次合并沿着使模块度增多最大和减小最少的方向进行。算法总的复杂度为，对于稀疏网络则为，其中n为网络中结点的个数，m为网络中边的条数。在本题中，我们选择了更为先进的Fast-Newman算法，通过把所给网络进行数据化处理，在MATLAB上实现了复杂网络的社团分解。四基本理论与算法思想4.1复杂网络的基本概念与性质4.1.1真实网络的图表示 首先，简单介绍有关图的定义和基本概念。图可以表示为集合，表示图的顶点集合，表示网络的顶点总数，代表边集合，表示总边数，如果，则图是无向图，否则为有向图。当网络是无向无权网络时，邻接矩阵是一个对称矩阵，表示图中顶点之间的连接关系。如果顶点之间有连接，则：否则。当
11、网络是有向图时，邻接矩阵是非对称的矩阵：当网络是加权网络时，中的非元素代表边的权重。4.1.2度分布 度分布是描述网络性质的一个重要统计量。结点的度定义为与结点连接的边的数目。度分布定义为随机地选择一个结点，度为的概率，或者等价地描述为网络中度为后的结点数占网络结点总数的比例。当然，对于有向网络，其度分布还可细致地分为网络的入度分布（in-degree distribution）和出度分布(out-degree distribution)。4.1.3网络的平均最短路径和顶点的介数网络的平均最短距离(average path length)定义为网络中任意一对结点之间的最短距离的平均值，数学表达
12、式为：其中为结点之间的最短路径的长度。所有结点间的最短路径长度的最大值称为网络半径(network diameter)。 网络中不相邻的结点和之间的路径主要依赖于连接结点和的路径上所经过的结点，如果某个结点被其它许多路径经过，则表示该结点在网络中很重要。定量地描某个结点在网络中的影响力或重要性可以用顶点的介数(node betweeness)来衡量，这一定义最早由Freeman在1977年提出。顶点的介数定义为： 其中表示结点、之间的最短路径的个数，表示结点、之间的最短路径中经过结点的个数。4.1.4网络的簇系数 网络的簇系数(clustering coefficient)是衡量网络集团化程度
13、的重要参数，是一个局部特征量。结点的簇系数定义为结点的邻接点之间实际存在的边数与所有可能的边数的比值，数学表达为： 其中，表示结点的度，表示结点的邻接点之间实际存在的边数。网络的簇系数定义为对所有结点的簇系数做和求平均： 许多真实网络具有较大的簇系数和较小的平均最短距离。这里“较大的簇系数指真实网络的簇系数远远大于相同规模的随机网络的簇系数。“较小的平均最短距离指平均最短距离随网络规模的增加呈对数或者更小增长。4.2复杂网络社团结构定义 近几年来，复杂网络的研究正处于蓬勃发展的阶段，其思想已经充斥到科学和社会的每一个角落。随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有
14、一个共同性质社团结构。也就是说，网络是由若干个“群(Group)或“团(Cluster)构成的。每个群内的结点之间的连接非常紧密，而群之间的连接却相对比较稀疏，如图3.2所示。图中的网络包含三个社团，分别对应图中三个虚线圆圈包围的部分。在这些社团内部，结点之间的联系非常紧密，而社团之间的联系就稀疏得多。一般而言，社团可以包含模块、类、群和组等各种含义。例如，万维网可以看成是由大量网站社团组成，其中同一个社团内部的各个网站所讨论的都是一些有共同兴趣的话题。类似地，在生物网络或者电路网络中，同样可以将各个结点根据其不同的性质划分为不同的社团。揭示网络中的社团结构，对于了解网络结构与分析网络特性具有
15、极为重要的意义。社团结构分析在生物学、物理学、计算机图形学和社会学中都有广泛的应用。图3.24.3 GN算法与Fast-Newman算法4.3.1 GN算法 GN算法是最典型的分裂算法。它的基本思想是通过不断地从网络中移除介数(Betweenness)最大的边将整个网络分解为各个社团。其中，边介数定义为网络中经过该边的最短路径的数目。它为区分一个社团的内部边和连接社团之间的边提供了一种有效的度量标准。GN算法的基本流程如下： 步骤1计算网络中所有边的介数； 步骤2找到介数最高的边并将它从网络中移除； 重复步骤1和2，直到每个结点就是一个退化的社团为止。 GN算法弥补了一些传统算法的不足，但是，在不知道社团数目的情况下，GN算法也不知道这种分解要进行到哪
