《基于FastNewman算法的网络社团结构分解.doc》由会员分享，可在线阅读，更多相关《基于FastNewman算法的网络社团结构分解.doc（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算法弥补了一些传统算法的不足，但是，
16、在不知道社团数目的情况下，GN算法也不知道这种分解要进行到哪一步终止。为解决这个问题，Newman等人引进了一个衡量网络划分质量的标准模块度。它是基于同型混合(Associativd Mixing)来定义的。考虑某种划分形式，它将网络划分为个社团。定义一个维的对称矩阵，其中元素，表示网络中连接两个不同社团的结点的边在所有边中占的比例；这两个结点分别位于第个社区和第个社团。注意，在这里所说的所有的边是在原始网络中的，而不必考虑是否被社团结构算法移除。因此，该模块度的衡量标准是利用完整的网络来计算的。 设矩阵中对角线上各元素之和为。它给出了网络中连接某一个社团内部各结点的边在所有边的数目中所占比例
17、。定义每行(或者列)中各元素之和为它表示与第个社团中的结点相连的边在所有边中所占的比例。在此基础上，用下式来定义模块度的衡量标准： 上式的物理意义是：网络中连接两个同种类型的结点的边(即社区内部边)的比例减去在同样的社团结构下任意连接这两个结点的边的比例的期望值。如果社团内部边的比例不大于任意连接时的期望值，则有。一般认为，的最大值对应的社团结构就是网络的社团结构。的上限为，越接近这个值，就说明网络的社团结构越明显。实际网络中，该值通常位于0.3到0.7之间。经过Newman等人的改进以后，GN算法不必依赖多余的信息来判断得到的社区结构是否具有实际意义，而是可以直接从网络的拓扑结构来进行分析。
18、但是该算法的耗时比较大，为，因此它仅仅适用于中等规模的大型网络(n=10000以下)。为了解决这个问题，人们在GN算法的基础上提出了多种改进的算法，主要包括采用结点集的GN算法、自包含GN算法等。4.3.2 Fast-Newman算法 GN算法虽然准确度比较高，分析社团结构的效果比原有的一些算法好，但是它的算法复杂度比较大，因此仅仅局限于研究中等规模的复杂网络。现在，对于Internet、WWW和电子邮件网络等网络的研究越来越多，面这些网络通常都包含几百万个以上的结点。在这种情况下，传统的GN算法就不能满足要求。基于这个原因，Newman在GN算法的基础上提出了一种快速算法Fast-Newma
19、n算法，它实际上是基于贪婪算法思想的一种凝聚算法，可以用于分析结点数达100万的复杂网络。 Fast-Newman算法如下： 步骤1初始化网络为个社团，即每个结点就是一个独立社团。则在GN算法中讨论过的矩阵中，初始的和满足： 其中为结点的度，为网络中总的边数。 步骤2依次合并有边相连的社团对，并计算合并后的模块度增量 根据贪婪算法的原理，每次合并应该沿着Q增大最多或者减小最少的方向进行，其算法复杂度为。每次合并以后，对相应的元素更新，并将与社团相关的行和列相加，其时间复杂度为。因此，步骤2总的时间复杂度为。 步骤3重复执行步骤2，不断合并社团，直到整个网络都合并成为一个社团。最多要执行n-1次
20、合并。该算法总的算法复杂度为，对于稀疏网络则为。 整个算法完成后可以得到一个社区结构分解的树状图。再通过选择在不同位置断开可以得到不同的网络社区结构。在这些社区结构中，选择一个对应着局部最大值的，就得到最好的网络社区结构。五建模过程通过我们对问题的分析，我们发现，可以将问题1的三个复杂网络图，通过标号，写成类似于问题2的数据形式，这样我们只需编写一个算法程序即可一次性解决问题1与问题2。通过阅读大量文献，我们选择了Fast-Newman算法，除了它比一些传统算法外，还有在算法结束后它可以直接得到一个社团分解结构图。5.1问题一5.1.1第一题第1个网络图1观察图1，我们发现网络中标号虽然有30
21、个点，但实际只有19个点，其中又只有15个点在网络上。为了便于处理，我们对网络1上的点进行重新赋值。如图1.1图1.1 按照附件3所给数据格式，我们将图1.1的信息转化成邻接矩阵数据（见“B题：附件2.1.txt”）。我们将Fast-Newman算法编写成MATLAB程序，见附录1、2。由于16、17、18、19四点已独立于网络之外，故只需考虑点115。运行程序，得到社团分解结构图：图1.2 我们只需将原来点的标记代换回去，即可得到图1的结构分解树状图。5.1.2第一题第2个网络图2 由于网络2没有进行标记，我们利用作图软件将每个点进行标记，如图2.1：图2.1同样，我们将第2个网络的信息转化
22、成邻接矩阵（“B题：附件2.2.txt”），在MATLAB程序中更换相应数据，得到结构分解树状图2.2:图2.25.2.3第一题第3个网络 图3.1（图中点84应更正为64） 参照网络1、网络2处理步骤，我们同样得到了邻接矩阵数据（“B题：附件2.3.txt ”）。 在MATLAB程序中更换相应数据，得到结构分解树状图3.2图3.2至此，第一问三个复杂网络都进行了社团结构分解，得到了3个结构分解树状图，Fast-Newman算法程序运行速度较快。5.2 问题2对于问题2，我们观察附件3中数据，发现在第二列中出现了数字0。即表明电力网络从0开始，到4940结束，共计4941个点。为了能够生成稀疏
23、矩阵（生成稀疏矩阵要求数据都大于零），我们将附件3中所给数据每列都加1，这样我们得到了一组新的数据。然后按照问题1的处理方法，在MATLAB中进行社团结构分解，即可得到结果。由于硬件原因，问题2在MATLAB中运行时间过长。程序见附录一与程序说明文件。六模型的评价与改进 复杂网络的社团结构分析是一个非常具有挑战性和前景性的研究领域。本文介绍了复杂网络的一些基本性质，网络中社团结构的定义和研究历史及其意义，并且详细分析了寻找网络中社区结构的算法的优劣。我们通过Fast-Newman算法，对复杂网络的社团结构进行了成功的分解，并得到了树状图。本模型最主要的优点在与复杂网络的社团结构分解速度较快，尤
24、其在复杂网络节点不超过100个的时候，可以迅速直接的得到社团结构的树状图。另外在数据处理与MATLAB程序方面，给出了一套接近于标准化的社团结构分解方法，可以处理各种复杂网络的社团结构分解问题。本模型同样存在一些弊端，首先在处理大规模复杂网络的时候，对计算机硬件要求较高，得出社团结构分解的速度较慢。我们同复旦大学席裕庚教授的最新成果进行了对比，席教授在分解30个节点的复杂网络社团结构的时候大约花费了6秒钟，我们分解速度略慢。此外，我们的模型不能直接将某一社团直接分离，而是一次性显示整个网络的社团结构，这也是程序运行花费时间较长的原因之一。对于复杂网络社团结构划分方法的进一步研究可以从以下几个方
25、面考虑：(1)寻找划分大规模复杂网络社团结构的有效算法；(2)寻找快速而且更为可靠的网络多社团结构分析算法以及对划分结果的优化处理方法；(3)提升计算机CPU处理效率； (4)对不同的复杂网络，运用不同的算法模型。七参考文献1Kernighan B W，Lin SAn efficient heuristic procedure for portioning graphsJBellSystem Techni cal Journal，1970，49：2913072Fiedler MAlgebraic connectivity of graphsJCzechoslovak Mathematical
26、Journal，1973，23(98)：2983053PothenA，Simon n，Liou K PPartitioning sparse matrices with eigenvectors of graphsJSIAM Journal on Matrix hnalysiS and Applications1990，11(3)：4304524Pons P and Latapy MComputing Communities in Large Networks Using Random WalksJComputer and Information Sc iences2005，2842935Pa
27、lla G，Derenyi I，Farkas I et a1Uncovering the Overlapping Community Structure ofComplex Networks in Nature and SocietyJNature，2005 435(7043)：814-8186Palla G，Farkas I，Pollner P，Derenyi I et a1Directed network modulesJPhysNewJ，2007，1867Newman M E JFast algorithm for detecting community structure in net
28、worksJPhysicalReview E，2004，69(6)：0661338Girvan M，Newman M E JCommunity structure in social and biological networksJPNAS，2001，99(12)：7821-78269Tyler J，Wilkinson D，Huberman BEmail as spectroscopy：Automated discovery of community structure within organizationsCInternational Conference on Communitiesan
29、d Techn0109ies，2003，819610Radicchi F，Castellano C，Cecconi F et a1Defining and identifying communities in networksJEurPhys。JB，2004，101：2658266311Fell D A，Wagner AThe small world of metabolismJNature(Biotechnology，2000，(18)：1121-112212Pool l，Kochen MContacts and InfluenceJSocial Networks，1978，(1)：l-48
30、13Milgram SThe small world problemJPsychology Today，1967，(2)：60-6714Freeman LSociometryG1977，40：35-4115Gleiser P，Danon LCommunity structure in jazzJAdvances in Complex Systems，2003，6：565-57316Newman M E J，Girvan MFinding and evaluating community structure in networksJPhysical Review E，2004，69(2)：026
31、11317汪小帆，李翔，陈关荣复杂网络理论及其应用M北京：清华大学出版社，2006，162-19118王冰复杂网络的演化机制及若干动力学行为研究D大连：大连理工大学，200619郭崇惹，张亮基于PCA的复杂网络社区结构分析方法J运筹与管理，2008，17(6)，14414920王林，戴冠中复杂网络中的社区发现理论与应用J科技导报，2005，23(8)：626621张光卫，康建初，夏传良，李鹤松复杂网络集团特征研究综述J计算机科学，2006，33(10)：1-4附录一：function Z H = FastNewman(adjacent_matrix)% FastNewman算法实现社团发现%
32、该算法参见文献Fast algorithm for detecting community structure in networks(2003)% 输入% adjacent_matrix - 邻接矩阵% 输出% Z - n-1*3矩阵，第i行表示第i次合并，第1列和第2列表示合并的社团标号，第3列是合并后的模块度% H - 聚类树图的句柄u,v=textread(B题：附件2.2.txt);m=length(u);A=zeros(85);for i=1:m A(u(i),v(i)=1;endadjacent_matrix=A;n = size(adjacent_matrix,1); % 节点
33、数目max_id = n;Z = ;clusters = 1:n; zeros(1,n); 1:n; % 初始划分，第1行是节点标号，第2行是社团标号的变换，第3行是社团标号step = 1;while numel(unique(clusters(3,:) = 1 % while step n Q e a clusters = GetModularity(adjacent_matrix, clusters); k = size(e,1); % 社团数目 DeltaQs = ; for i = 1:size(e,1) for j = 1:size(e,1) if i = j DeltaQ = 2
34、*(e(i,j)-a(i)*a(j); DeltaQs = DeltaQs i;j;DeltaQ; end end end maxDeltaQ,id = max(DeltaQs(3,:); id = id(1); i = DeltaQs(1,id); j = DeltaQs(2,id); % 找出DeltaQ最大的社团对的序号 max_id = max_id + 1; c_id1 = find(clusters(2,:) = i); c_id2 = find(clusters(2,:) = j); id1 = unique(clusters(3,c_id1); id2 = unique(clu
35、sters(3,c_id2); clusters(3,c_id1) = max_id; clusters(3,c_id2) = max_id; Z = Z; id1 id2 length(c_id1 c_id2); step = step + 1;endif nargout = 2 H = dendrogram(Z,0)enddendrogram(Z,n)附录二：function Q e a out_clusters = GetModularity(adjacent_matrix, clusters)% 获取无向无权网络的某种划分的模块度% 模块度的提出和计算方法见如下文献:% Finding
36、 and evaluating community structure in network(2004)% 输入% adjacent_matrix - 网络的邻接矩阵% clusters - 网络的社团划分，第1行是节点标号，第2行是社团标号的变换，第3行是社团标号% 输出% Q - 划分的模块度% e - k*k矩阵，k是社团数目，其中元素的定义见上述文献% a - 意义见上述定义% out_clusters - 与输入含义相同uni = unique(clusters(3,:);for i = 1:length(uni) idices = find(clusters(3,:) = uni(
37、i); clusters(2,idices) = i;endm = sum(sum(adjacent_matrix)/2; % 网络的边的数目Q = 0 ;k = numel(unique(clusters(2,:); % 社团数目e = zeros(k);for i=1:k idx = find(clusters(2,:)=i); labelsi = clusters(1,idx); for j=1:k idx = find(clusters(2,:)=j); labelsj = clusters(1,idx); for ii=1:length(labelsi) vi = labelsi(ii); for jj=1:length(labelsj) vj = labelsj(jj); e(i,j) = e(i,j)+adjacent_matrix(vi,vj); end end endende = e/2;% for i=1:k% e(i,i) = e(i,i)*2;% ende = e/m;a = ;for i=1:k ai = sum(e(i,:); a = a; ai; Q = Q + e(i,i)-ai2;endout_clusters = clusters;end
