[硕士论文精品]复杂网络社区结构划分算法研究

大连理工大学硕士学位论文摘要随着WS小世界网络模型和BA无标度网络模型的提出，国内外掀起了研究复杂网络的热潮。复杂网络的研究以系统的观点来看待真实系统，如INTERNET网络、电力网、新陈代谢网络等。复杂网络通常会呈现出社区结构特性，如何在实际网络中高效地发现社区结构是近年来复杂网络的研究热点之一。本文基于谱算法的思想提出了一种基于共邻矩阵和增益函数的有效算法来划分复杂网络中的社区，并把此算法推广到了加权的复杂网络中。主要工作如下1定义了共邻矩阵和增益函数这两个概念，在此基础上提出一种有效算法来划分复杂网络中的社区结构。其中共邻矩阵中的元素定义为结点对之间拥有相同邻居的数目。以增益函数作为网络社区结构划分的目标函数，进一步推导出基于增益矩阵和增量矩阵的特征值和特征向量的社区结构划分方法。最后把这种算法应用于三个常用的实际网络数据中，并和NEWMAN基于模块度矩阵的谱算法结果做了比较，以验证算法的可行性和有效性。2重新定义了在加权网络中结点对之间拥有共同邻居的数目，把基于共邻矩阵和增益函数的复杂网络社区划分算法推广到加权的复杂网络中。在以往许多复杂网络社区结构划分算法中，网络中的边常被看作是无权重的，但是现实世界中存在许多加权网络。如果忽略边的权重，仅仅把划分无权网络社区的算法应用到这些加权网络中，将会忽略许多包含在边权重中的重要信息，从而得出不尽合理的结果。借鉴NEWMAN把加权网络映射到无权多重图的思想，重新定义了在加权网络中结点对之间拥有共同邻居的数目，然后将基于共邻矩阵和增益函数的算法推广到加权的网络中，并把算法应用到计算机仿真网络和实际的加权网络数据中，验证了推广算法的可行性和有效性。关键词复杂网络；社区结构；共邻矩阵；增益函数；加权网络HTTP/INFO3DOUCOM/论坛推广复杂网络社区结构划分算法研究PARTITIONINGMETHODSFORCOMMUNITYSTRUCTUREINCOMPLEXNETWORKSABSTRACTINRECENTYEARS，ASTHEWSSMALLWORLDNETWORKMODELANDBASCALEFREENETWORKMODELWASPROPOSED，THESTUDYONCOMPLEXNETWORKSISACHIEVINGACLIMAXATHOMEANDABROADNOWTHESTUDYONCOMPLEXNETWORKSTREATSTHEREALSYSTEMSSUCHASTHEINTERNET，ELECTRICITYNETWORKSANDMETABOLICNETWORKS、L，ITLLTHEVIEWPOINTOFSYSTEMSCIENCECOMMUNITYSTRUCTUREEXISTSINMANYREALNETWORKSHOWTOFINDSUCHCOMMUNITIESEFFECTIVELYISONEOFFOCUSESOFMANYRECENTRESEARCHESINTHEBRANCHOFCOMPLEXNETWORKSINTHISARTICLE，THEAUTHORPROPOSESAPARTITIONALMETHODBASEDONCOMMONNEIGHBOURSMATRIXANDGAINFUNCTIONANDGENERALIZESTHEMETHODTOWEIGHTEDNETWORKSTHEMAINWORKOFTHISPAPERCANBESUMMARIZEDASFOLLOWS1DEFININGTHECOMMONNEIGHBOURSMATRIXANDGAINFUNCTION,ANDPROPOSINGANEFFECTIVEMETHODOFANALYZINGTHECOMMUNITYSTRUCHLREINCOMPLEXNETWORKSBASEDONTHESETWOCONCEPTSTHEELEMENTSINCOMMONNEIGHBOURSMATRIXMEANSTHENUMBEROFCOMMONNEIGHBOURSBETWEENNODESWITHTHEGAINFUNCTIONASTHEOBJECTIVEFUNCTIONOFANALYZINGTHECOMMUNITYSTRUCTURE，WEDERIVEAPARTITIONMETHODBASEDONTHEEIGENVALUESANDEIGENVECTORSOFGAINMATRIXANDINCREMENTMATRIXFURTHERMORE，WEAPPLYTHISMETHODTOTHREECOMMONREALNETWORKDATAANDCOMPARETHECOMPUTATIONALRESULTSWITHMODULARITYBASEDANALYSISMETHODSPROPOSEDBYNEWMANCOMPUTATIONALRESULTSDEMONSTRATETHATTHEPROPOSEDMETHODISFEASIBLEANDEFFECTIVE2REDEFMINGTHECOMMONNEIGHBOURSBETWEENAPAIROFNODESINWEIGHEDNETWORKANDGENERALIZINGTHEALGORITHMBASEDONCOMMONNEIGHBOURSMATRIXANDGAINFUNCTIONTOWEIGHTEDNETWORKSALTHOUGHTHEREAREMANYWEIGHTEDNETWORKINTHEWORLD，NETWORKSAREUSUALLYCONSIDEREDTOBEUNWEIGHTEDINLOTSOFALGORITHMSFORCOMMUNITYSTRUCTUREINCOMPLEXNETWORKCERTAINLYTHEABOVEALGORITHMSCANBEAPPLIEDTOSUCHNETWORKSBYSIMPLYIGNORINGEDGEWEIGHTS，BUTTODOSOISTOTHROWAWAYUSEFULINFORMATIONCONTAINEDINTHEWEIGHTS，INFORMATIONTHATCOULDHELPUSTOMAKEAMOREACCURATEDETERMINATIONOFTHECOMMUNITIESINTHISPAPERWEUSETHETECHNIQUETHATWEIGHEDNETWORKSAREMAPPEDONTOMULTIGRAPHSPROPOSEDBYNEWMANANDREDEFINETHECOMMONNEIGHBOURSBETWEENAPAIROFNODESINWEIGHTEDNETWORKTHEN，THEALGORITHMBASEDONCOMMONNEIGHBOURSMATRIXANDGAINFUNCTIONISGENERALIZEDTOWEIGHTEDNETWORKSFURTHERMORE，WEAPPLYTHISMETHODTOACOMPUTERGENERATEDNETWORKANDAREALSOCIALNETWORKCOMPUTATIONALRESULTSDEMONSTRATETHATTHEPROPOSEDMETHODISFEASIBLEANDEFFECTIVE一IIHTTP/INFO3DOUCOM/论坛推广大连理工大学硕士学位论文KEYWORDSCOMPLEXNETWORK；COMMUNITYSTRUCTURE；COMMONNEIGHBOURSMATRIX；GAINFUNCTION；WEIGHTEDNETWORK111HTTP/INFO3DOUCOM/论坛推广大连理工大学学位论文独创性声明作者郑重声明所呈交的学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。若有不实之处，本人愿意承担相关法律责任。学位论文题目堡垒塑兰墨叠堡至查塑兰笪望墨塑庭作者签名继塑芒日期4年L月J鱼日HTTP/INFO3DOUCOM/论坛推广大连理工大学硕士学位论文大连理工大学学位论文版权使用授权书本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印、或扫描等复制手段保存和汇编本学位论文。学位论文题目作者签名导师签名日期竺12年生月鱼日日期4年上月止日HTTP/INFO3DOUCOM/论坛推广大连理工大学硕士学位论文1绪论11复杂网络研究的背景与意义20世纪90年代以来，以INTERNET为代表的信息技术的迅猛发展使人类社会大步迈入了网络时代。从INTERNET到WWW，从大型电力网络到全球交通网络，从生物体中的大脑到各种新陈代谢网络，从科研合作网络到各种经济、政治和社会关系网络等，可以说；人们已经生活在一个充满着各种各样的复杂网络的世界中。人类社会的网络化是一把“双刃剑”它既给人类社会生产与生活带来了极大便利，提高了人类生产效率和生活质量，但也给人类社会生活带来了一定的负面冲击，如传染病和计算机病毒的快速传播以及大规模的停电事故等。因此，人类社会的日益网络化需要人类对各种人工和自然的复杂网络的行为有更好的认识。长期以来，通信网络、电力网络、生物网络、社会网络等分别是通信科学、电力科学、生命科学、社会学等不同学科的研究对象，而复杂网络理论所要研究的则是各种看上去互不相同的复杂网络之间的共性和处理它们的普适方法。从20世纪末开始，复杂网络研究正渗透到数理学科、生命学科和工程学科等众多不同的领域，对复杂网络的定量与定性特征的科学理解，已成为网络时代科学研究的一个极其重要的挑战性课题心31，甚至被称为“网络的新科学NEWSCIENCEOFNETWORKS”。传统的对网络的研究最早起源于著名的欧拉七桥问题。之后的近两百年中，数学家们一直致力于对简单的规则网络和随机网络进行抽象的数学研究。随着近年来计算机存储能力和处理数据能力的增强，以及一些大规模系统的数据库的建立，人们重新获得了真实网络的特征数据，发现大多数真实网络既不是规则的，也不是随机的，而是呈现一定规律的复杂网络H。复杂网络之所以复杂，不仅在于网络规模的巨大，网络结构的复杂而且网络在时间、空间上都具有动态的复杂性，网络行为也具有复杂性。许多真实系统都可以用网络的形式加以描述，一个典型的网络是由许多结点与连接结点之间的边组成的。结点代表系统中的个体，边则表示结点之间的作用关系。如WWW网络可以看成是网页之间通过超链接构成的网络璐3；INTERNET网络可以看作不同的计算机通过光缆连接构成的网络嵋1科学家合作网络可以看作不同的科学家合作关系构成的网络盯81基因调控网络可以看作是不同的基因通过调控与被调控关系构成的网络旧1。这些真实网络的普遍存在，促使来自不同学科领域的科学家共同致力于复杂网络的研究。这些学科领域包括复杂性科学、数学、物理、生物和计算机等。复杂网络的研究HTTP/INFO3DOUCOM/论坛推广复杂网络社区结构划分算法研究可以使人们更好地了解现实世界的复杂系统，为设计具有良好性能的网络提供依据。同时复杂网络的理论成果将会广泛地应用到生物、计算机等各个学科领域。复杂网络的研究大致可以描述为三个密切相关但又依次深入的方面大量的真实网络的实证研究，分析真实网络的统计特性构建符合真实网络统计性质的网络演化模型，研究网络的形成机制和内在机理研究网络上的动力学行为，如网络的鲁棒性和同步能力，网络的拥塞及网络上的传播行为等。当把一个系统描述为网络的形式后，就可以通过分析网络的统计性质，如网络的度分布，网络的簇系数，网络的平均最短距离等来描述真实网络N叫引。大量的实证研究表明许多真实世界的网络具有两个基本性质小世界特性SMALLWORLDCHARACTERN司和无标度特性SCALEFREECHARACTERN刚。小世界特性是指与相同规模的随机网络相比，该网络具有较小的平均最短距离和较大的簇系数。1967年，美国哈佛大学社会心里学家MILGRAM做了一个实验，在美国将一封信通过熟人找熟人的方式传递到目标者，发现平均最短经过6人就可到达，这就是著名的“六度分离SIXDEGREEOFSEPARATION”现象，它揭示了社会网络的小世界特性。而在万维网嗍中，平均只需点击19次超级链接，就可以从任意一个网页到达其它网页鄙。大量的小世界网络的普遍存在，促使人们探讨形成这种网络的内在机理。1998年，学者WATTS和STROGATZ在规则网络中引入随机性，建立了著名的小世界网络模型WS小世界网络模型N翻，很好地描述了真实网络的小世界特性。1999年，学者BARABASI和ALBERT通过对万维网的数据进行统计分析发现万维网的度分布服从幂律分布，在双对数坐标系下是一条下降的直线，由于幂律分布具有标度不变性，缺乏一个特征度值，因此称这种度分布服从幂律分布的网络为无标度网络SCALEFREENETWORKN明。之后的研究表明，许多社会网络如科学家合作网络口81、生物网络中的新陈代谢网络N刀和技术网络中的INTERNET网络3等都是无标度网络。这些来自不同领域的大规模系统呈现了共同的普适规律，促使人们去探索隐藏在这些表象后的内在演化机制，从此掀起了研究复杂网络的热潮。近年来，随着大型数据库的建立和计算机存储与运算能力的迅速提高，复杂网络的研究进程大大加快。人们对社会系统、大型基础性设施和生物系统中大量的真实网络数据库进行了系统的分析，寻找呈现表象的内在机制和模式，试图发现支配和影响这些复杂系统的动力学和演化规律的内在本质。复杂网络的理论及实证研究的发展将会对网络安全、网络控制、疾病传播的控制与防御、社会中人的行为动力学的研究和生物网络的演化机制研究等产生重要影响。HTTP/INFO3DOUCOM/论坛推广大连理工大学硕士学位论文12复杂网络社区结构研究现状随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有一个共同性质，即社区结构。也就是说，整个网络是由若干个“社区“或“组构成的。每个社区内部的结点间的连接相对非常紧密，但是各个社区之间的连接相对来说却比较稀疏N81训。揭示网络的社区结构，对于深入了解网络结构与分析网络特性是很重要的。如社会网络中的社区代表根据兴趣和背景而形成的真实的社会团体；引文网络中的社区代表针对同一主题的相关论文；万维网中的社区就是讨论相关主题的若干网站U7一；而生物化学网络或者电子电路中的网络社区可以是某一类功能单元幢“捌。发现这些网络中的社区有助于我们更加有效地理解和开发这些网络。在复杂网络社区结构划分的研究中，社区结构划分算法所要划分的网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络网络中边的权值为正实数；另一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分网络中社区结构的算法相应分为两大类，而对于第一类网络又提出了许多不同的社区结构划分算法，划分第一类网络社区的传统算法可分为两大类，第一类是基于图论的算法，比如KL算法晗羽、谱平分法盼钆删、随机游走算法啪3和派系过滤算法口7勰3等；第二类是层次聚类算法，比如基于相似度度量的凝聚算法N劬和基于边介数度量的分裂算法N墨观制等。最近几年从其他不同的角度又提出了许多划分第一类网络社区结构的算法，大致可划分如下基于电阻网络性质的算法驺、基于信息论的算法B船、基于PCA的算法羽和最大化模块度们的算法州等。对于符号网络，DOREIAN和MRVAR提出了一种利用局部搜索划分符号网络社区结构的算法H，而YANG等提出一种基于代理的启发式划分符号网络社区结构的算法FECH羽。下面简要介绍一下几种具有代表性的算法。1970年，KERNIGHAN和LIN提出一种试探优化法划分网络中的社区结构，简称KL算法。它是一种基于贪婪算法原理将网络划分为两个大小已知的社区的二分法。其基本思想是为网络的划分引进一个增益函数Q，增益函数定义为两个社区内部的边数减去连接两个社区之间的边数，然后寻找使Q值最大的划分方法。1990年，POTHEN等基于图的LAPLACE矩阵的谱特征提出一种将网络划分为两个社区的二分法瞻目。该算法的理论基础是不为零的特征值所对应的特征向量的各元素中，同一个社区内的结点对应的元素是近似相等的。因此可以根据网络的LAPLACE矩阵的第二小特征值将其分为两个社区。2001年，GIRVAN和NEWMAN提出了一种基于边介数的分裂算法，简称GN算法N81。该算法的基本思想是不断地从网络中移除介数最大的边。边介数定义为网络中经过每条边的最短路径数目。该算法的复杂度非常高，2003年TYLER等在GN算法的基础上提出HTTP/INFO3DOUCOM/论坛推广复杂网络社区结构划分算法研究了一种新的算法圆1，它可以显著提高计算速度，但也降低了计算的准确性。GN算法是以网络中的每一个结点I为源结点，来计算它到其他结点的最短路径，并以这些最短路径经过每条边的次数作为该边的介数。而TYLER等人提出，以网络中某个结点集内的结点为源结点来计算边的介数也可以达到较好的效果。2004年，NEWMAN把GN算法推广到了加权网络中H副。2003年，WU和HUBERMAN基于电阻网络的性质提出了W_H算法3，其主要思路为将网络中每条边想象成电阻为单位值的导线，且在网络中任意选择的两个结点上加上单位值的电位差。WU和HUBERMAN认为，如果网络可以分解成两个社区，那么电位谱在连接两个社区的边的两端会产生一个较大的间隙。因此，首先确定电位谱的最大间隙处的某个电位值，然后根据每个结点处的电位是否大于该值而确定结点属于哪个社区。该算法的一个重要特点是可以用来确定包含指定结点的社区，而无须计算出所有的社区。2004年，NEWMAN提出一种基于贪婪法思想的凝聚算法N9I，并称这种算法为快速算法。该算法是在使得模块度不断增加的基础上进行，即每次合并沿着使模块度增多最大和减小最少的方向进行。算法总的复杂度为D研刀咖，对于稀疏网络则为ON2，其中N为网络中结点的个数，M为网络中边的条数。在NEWMAN快速算法的基础上，CLAUSET、NEWMAN和MOORE等人采用堆的数据结构来计算和更新网络的模块度，提出了一种新的贪婪算法，称为CNM算法啪1。该算法的复杂度只有ONL092刀，已接近线性复杂性，可用来分析大型复杂网络数据。同样为了最大化网络的模块度，2006年NEWMAN基于模块度矩阵提出一种划分网络中社区结构的谱算法M1，并于2008年把该算法推广到有向网络中443O2005年，PONS和LATAPY提出一种利用随机游走划分网络社区结构的算法嘶3，算法的初始条件为每个结点为一个单独的社区，然后逐步合并可使结点和它所在社区之间的平方距离均值达到最小的两个社区。每一步都要更新社区之间的距离，其中两个结点之间的距离对应于它们的相似度，即在一个离散的随机游走过程中，它们之间的方向转移概率。大多数社会网络社区结构划分算法仅适用于包含正联系的网络，而不适合符号网络中的社区结构划分。在符号社会网络的社区结构中，不仅社区内部的正联系比较多，而且社区之间的负联系也比较多。1996，DOREIAN和RRVART提出了一种利用局部搜索划分符号社会网络中社区结构的算法1。这种算法本质上是一种基于贪婪策略的算法，通过最小化一个预定义的误差函数把网络划分为几个社区。误差函数的定义为社区内部负向联系和社区之间正向联系权重绝对值的和。算法的初始条件为随机的把结点划分到已HTTP/INFO3DOUCOM/论坛推广大连理工大学硕士学位论文知数量的社区中，然后计算对于初始划分的误差函数值。为了减小误差函数的值，把结点从一个社区移动到另外一个社区，结点的移动直到误差函数不再减少为止。算法复杂度为D迭代次数奉刀2，其中迭代次数为结点移动的次数，N为网络中结点的个数。该算法的缺陷为必须事先知道要划分的社区的数目且依赖于初始划分，并且该算法仅考虑到边的符号而没有考虑边的密度。2007年YANG等人提出了一种基于代理的启发式方法划分符号社会网络中的社区结构，并称这种算法为FEC算法H羽。该算法分为两个阶段，第一个阶段为FC阶段，即计算其他所有结点经过一定数量的步长到达汇结点SINKNODE的概率；第二个阶段为定义一个截断标准，找出汇结点所在的社区。该算法效率比较高，为O，Z，其中N为网络中结点的个数，并且能给出接近最优解的解。以上所述算法最终目的均是把网络划分为若干个相互分离的社区，但是现实中很多网络并不存在绝对的彼此独立的社区结构，相反它们是由许多彼此重叠且相互关联的社区构成。比如，每个人根据不同的分类方法都会属于多个不同的社区如学校、家庭、不同的兴趣小组等。在这种情况下，很难单独的将这些社区划分出来。因此，PALLA等人提出了一种派系过滤算法CLIQUEPERCOLATIONMETHOD来分析这种互相重叠的社区结构3。尽管复杂网络的社区发现问题得到了大量的研究，但还存在一些尚未解决的基本问题，如社区概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性能优越，但所需计算量却很大。这说明复杂网络中社区发现的研究还需要付出大量的努力蜘。13本文的研究内容与文章结构本课题主要研究复杂网络中的社区结构划分。首先，针对无权的复杂网络，提出了共邻矩阵和增益函数的概念，在此基础上提出一种有效的划分社区结构的算法。实验结果表明该算法是可行且有效的。最后把这种算法推广到加权的复杂网络中，并把算法应用到计算机仿真网络和实际的加权网络数据中，验证了推广算法的可行性和有效性。综上所述，本文主要研究内容共分为两个部分第一部分提出了一种基于共邻矩阵和增益函数的复杂网络社区结构划分算法；第二部分把此算法推广到加权的复杂网络中。具体内容如下第二章首先介绍了复杂网络的图表示、度分布、平均最短路径和社区结构等基本概念和基本性质。然后详细介绍了几种划分复杂网络社区结构算法的基本思想和特点，包括无权网络和加权网络中的社区结构划分算法。HTTP/INFO3DOUCOM/论坛推广复杂网络社区结构划分算法研究第三章从社区内部结点对之间应该拥有更多的共同邻居出发，提出了基于共邻矩阵和增益函数的复杂网络社区结构划分算法。把这种网络社区结构划分方法应用于空手道俱乐部网络、海豚网络和政治书籍网络三个常用的实际网络数据中，并和NEWMAN基于模块度矩阵的谱算法结果做了比较，数值实验结果表明本文提出的方法是可行且有效的。第四章重新定义了在加权网络中结点对之间拥有共同邻居的数目，把基于共邻矩阵和增益函数的复杂网络社区结构划分算法推广到加权的复杂网络中。在以往许多复杂网络社区结构划分算法中，网络中的边常被看作是无权重的，但是现实世界中却存在许多加权网络。如果忽略边的权重，仅仅把划分无权网络中社区结构的算法应用到加权网络中，将会忽略许多包含在边权重中的重要信息，得出不合理的结果。借鉴NEWMAN把加权网络映射到无权多重图的思想，重新定义了在加权网络中结点对之间拥有共同邻居的数目，然后将基于共邻矩阵和增益函数的算法推广到加权的网络中，并把算法应用到计算机仿真网络和实际的加权网络数据中，验证了推广算法的可行性和有效性。最后对全文的工作进行了总结，并对今后的工作和发展方向提出了展望。HTTP/INFO3DOUCOM/论坛推广大连理工大学硕士学位论文2复杂网络社区结构划分算法概述21复杂网络基本性质211真实网络的图表示首先，简单介绍有关图的定义和基本概念。图G可以表示为集合，9，G1，2，表示图G的顶点集合，N表示网络的顶点总数，9G，五，之，五，名，止代表边集合，E表示总边数，如果F，JJF，F，则图是无向图，否则为有向图。当网络是无向无权网络时，邻接矩阵A概，是一个01对称矩阵，表示图中顶点之间的连接关系。如果顶点F，歹之间有连接，则1否则AO0。当网络是有向图时，邻接矩阵A是非对称的01矩阵当网络是加权网络时，A中的非零元素代表边的权重。212度分布度分布是描述网络性质的一个重要统计量。结点I的度定义为与结点F连接的边的数目。度分布PJJ定义为随机地选择一个结点，度为K的概率，或者等价地描述为网络中度为后的结点数占网络结点总数的比例。当然，对于有向网络，其度分布还可细致地分为网络的入度分布INDEGREEDISTRIBUTION和出度分布OUTDEGREEDISTRIBUTION。近年来大量的实证研究表明，许多真实网络的度分布都遵循幂律分布，数学形式为P后K，其中Y一般介于2到3之间。幂函数在双对数坐标系下是一条下降的直线，如WWWH71的度分布，如图21B所示。与指数函数相比，幂函数下降速度较慢，使得网络中存在度较大的结点，通常称这些结点为集散结点HUBNODE。研究发现除了幂律分布，真实网络中还存在其它形式的度分布，如电力网络N司的度分布服从指数分布，在单对数坐标系下是一条下降的直线；也存在幂律加指数截断的度分布的网络，如电影演员合作网络口61，如图21A所示，以及蛋白质相互作用网络。213网络的平均最短路径和顶点的介数网络的平均最短距离AVERAGEPATHLENGTH定义为网络中任意一对结点之间的最短距离的平均值，数学表达式为1一D二办21NN1F篇8。HTTP/INFO3DOUCOM/论坛推广复杂网络社区结构划分算法研究其中办为结点F，J之间的最短路径的长度。所有结点间的最短路径长度的最大值称为网络半径NETWORKDIAMETER。大多数真实网络具有较小的平均最短距离，如具有153127个结点的万维网WWW的平均最短距离为31H钉，大肠杆菌的代谢网络的平均最短距离为24648】。订埘O矿卫，轧矿1LFI矿图21不同类型的大规模网络的度分布。A电影演员合作网络，网络规模为N212，250，七2878；B唧网络，网络规模为N325，729，七546。度分布的幂指数，一23，21，引自文16。FIG21THEDISTRIBUTIONFUNCTIONSOFEONNECTIVITIESFORVARIOUSLARGENETWORKSAACTORCOLLABORATIONGRAPHWITHN212250NODESANDAVERAGECONNECTIVITY2878BWWW，N325，729，54611他DASHEDLINESHAVESLOPESAY础，23，BY删21REF16网络中不相邻的结点歹和K之间的路径主要依赖于连接结点歹和K的路径上所经过的结点，如果某个结点被其它许多路径经过，则表示该结点在网络中很重要。定量地描某个结点在网络中的影响力或重要性可以用顶点的介数NODEBETWEENESS来衡量，这一定义最早由FREEMAN在1977年提出呻。顶点F的介数置定义为22业归忍HTTP/INFO3DOUCOM/论坛推广大连理工大学硕士学位论文其中拧硪表示结点J、后之间的最短路径的个数，NJ,I表示结点J、七之间的最短路径中经过结点I的个数。214网络的簇系数网络的簇系数CLUSTERINGCOEFFICIENT是衡量网络集团化程度的重要参数，是一个局部特征量。结点F的簇系数G定义为结点F的邻接点之间实际存在的边数与所有可能的边数的比值，数学表达为C生一23。匆毛I其中，毛表示结点F的度，E，表示结点F的邻接点之间实际存在的边数。网络的簇系数定义为对所有结点的簇系数做和求平均NC专C，24J，一VT许多真实网络具有较大的簇系数和较小的平均最短距离。这里“较大的簇系数指真实网络的簇系数远远大于相同规模的随机网络的簇系数。“较小的平均最短距离指平均最短距离随网络规模的增加呈对数或者更小增长。22复杂网络社区结构定义近几年来，复杂网络的研究正处于蓬勃发展的阶段，其思想已经充斥到科学和社会的每一个角落。随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有一个共同性质社区结构。也就是说，网络是由若干个“群GROUP“或“团CLUSTER构成的。每个群内的结点之间的连接非常紧密，而群之间的连接却相对比较稀疏N1，如图22所示。图中的网络包含三个社区，分别对应图中三个虚线圆圈包围的部分。在这些社区内部，结点之间的联系非常紧密，而社区之间的联系就稀疏得多。一般而言，社区可以包含模块、类、群和组等各种含义。例如，万维网可以看成是由大量网站社区组成，其中同一个社区内部的各个网站所讨论的都是一些有共同兴趣的话题N7阍3。类似地，在生物网络或者电路网络中，同样可以将各个结点根据其不同的性质划分为不同的社区瞳H翻。揭示网络中的社区结构，对于了解网络结构与分析网络特性具有极为重要的意义。社区结构分析在生物学、物理学、计算机图形学和社会学中都有广泛的应用N8刚。HTTP/INFO3DOUCOM/论坛推广复杂网络社区结构划分算法研究图22一个小型的具有社区结构性质的网络示意图。引自文1。FIG22ASMALLNETWORKWITHCOMMUNITYSTRUCTUREREF123复杂网络社区结构划分算法网络社区结构的研究已经有很长的历史。为了能够准确有效地分析复杂网络中的社区结构，人们提出了多种不同的社区结构划分算法，这些算法的目的是利甩尽量少的信息得到尽量准确地网络社区结构，从而更好地分析网络中社区结构的基本特点和共同特性。早期分析社区结构的算法，包括计算机科学中的图形分割GRAPHPARTITION和社会学中的层次聚类HIERARCHICALCLUSTERING两种晦1嘲，前者主要包括KERNIGHANLIN算法嘲和基于图的LAPLACE矩阵特征向量的谱平分法SPECTRALBISECTIONMETHOD幽踟；而后者则以著名的GNGIRVANNEWMAN算法为代表N驯。231迭代二分法计算机科学中的一个典型问题，是将一个网络分解成若干结点数基本相等的子网，使得不同子网中的结点之间的连接数最少，称为图分割GRAPHPARTITIONING。图分割问题GPP可应用于并行计算机的处理器合理分配进程。实际应用中，大多数图分割方法均基于迭代二分法首先将图按要求分割成2个子图，然后再分别对这2个子图进行分割，如此迭代下去直至获得所要求的子图个数。我们介绍两个最具代表性的迭代二分法一是KERNIGHANLIN算法昭引，该算法使用贪婪策略对社区内以及社区间的边数进行优化，从而达到改进网络的初始分解的目的；另一个是基于图的LAPLACE矩阵的特征向量的谱二分法SPECTRALBISECTIONMETHOD24,25】。HTTP/INFO3DOUCOM/论坛推广大连理工大学硕士学位论文2311KERNIGHANLIN算法KERNIGHANLIN算法是一种试探优化法1。它基于贪婪算法原理将网络划分为两个规模已知的社区。其基本思想是为网络的划分引进一个增益函数Q，Q定义为两个社区内部的边数减去连接两个社区之间的边数，然后寻找使Q值最大的划分方法。整个算法可描述如下首先，将网络中的结点随机地划分为已知规模的两个社区。在此基础上，考虑所有可能的结点对，其中每个结点对的结点分别来自两个社区。对每个结点对，计算如果交换这两个结点的话可能得到的Q的增益QQ交换后一绥换前，然后交换最大的Q对应的结点对，同时记录交换以后的Q值。规定每个结点只能交换一次。重复这个交换过程，直到某个社区内所有的结点都被交换一次为止。需要注意的是，在结点对交换的过程中，Q值并不一定总是单调增加的。不过，即使某一步的交换会使Q值有所下降，但是仍然可能在其后的步骤中出现一个更大的Q值。当交换完毕后，便找到上述交换过程中所记录的最大的Q值。这时对应的社区结构就认为是该网络实际的社区结构。KERNIGHANLIN算法最大的缺陷是要求事先知道两个社区的规模，否则，就很可能不会得到正确的结果。这个缺陷使得它在实际网络分析中难以应用。而且，即使这个问题可以得到解决，它与所有的二分算法一样，仍然面临着如何事先知道网络中的社区数目，以及确定二分法要重复到哪一步停止的问题。2312谱平分法一个有N个结点的无向图G的LAPLACE矩阵是一个刀X刀维的对称矩阵L。其中，L的对角线上的元素厶，是结点I的度结点的度定义为与该结点连接的其它结点的数目，而其他非对角线上的元素厶，则表示结点I和结点J的连接关系。如果这两个结点之间有边连接，则厶，值为1，否则为0。L矩阵所有的行与列的和都为0，因此，该矩阵总有一个特征值为O，其对应的特征向量为L1，1，1。可以从理论上证明，不为零的特征值所对应的特征向量的各元素中，同一个社区内的结点对应的元素是近似相等的。这就是谱平分法的理论基础。考虑网络社区结构的一种特殊情况当一个网络中仅存在两个社区，此时该网络的LAPLACE矩阵L就对应了两个近似的对角矩阵块。对一个实对称矩阵而言，它的非退化的特征值对应的特征向量总是正交的。因此，除了最小特征值0以外，矩阵L其他特征值对应的特征向量总是包含正、负两种元素。这样，当网络由两个社区构成时，就可以根据非零特征值相应的特征向量中的元素对应网络的结点进行分类。其中，所有正元素对应的那些结点都属于同一个社区，而所有负元素对应的结点则属于另一个社区。HTTP/INFO3DOUCOM/论坛推广复杂网络社区结构划分算法研究因此，我们可以根据网络的LAPLACE矩阵的第二小的特征值九将其分为两个社区。这就是谱平分法的基本思想。当网络的确是分成两个社区时，用谱平分法可以得到非常好的效果。但是，当网络不满足这个条件时，谱平分法的优点就不能得到充分体现。事实上，第二小特征值厶可以作为衡量谱平分法效果的标准它的值越小，平分的效果就越好。九也称为图的代数连接度ALGEBRAICCONNECTIVITY。一般情况下，计算一个聆”矩阵的全部特征向量的时间复杂度为ON3。但是在大多数情况下，实际网络的LAPLACE矩阵是一个稀疏矩阵，因此，可以用LANCZOS方法快速计算主要的特征向量。该方法的时间复杂度大致为M厶一九，其中，M表示网络中边的条数。这样，计算的速度可以得到很大程度的提高。但是，如果不能很快将九从其它特征值中分离出来，该算法就可能在一定程度上有所减慢。换句话说，当网络很明显地分成两个社区时，该算法的速度非常快，否则该算法就未必很有效。232层次聚类法层次聚类是寻找社会网络中社区结构的一类传统算法。它基于各个结点之间连接的相似性或者强度，把网络自然地划分为各个子群。根据加边或去边，该类算法又可以分为两小类凝聚方法AGGLOMERATIVEMETHOD和分裂方法DIVISIVEMETHOD嘞1。按照网络中添加或者删除边的步骤，层次聚类方法通常采用谱系图或树状图来记录算法的结果，从而描述整个网络从单个独立的子群逐步凝聚为整个网络或者从整个网络逐步分解为若干个越来越小的子群的连续过程，如图23所示，其中底部的各个圆代表了网络中的各个结点。当水平虚线从树的底端逐步上移，各结点也逐步聚合成为更大的社区。当虚线移至顶部，即表示整个网络就成为一个社区。在该树状图的任何一个位置用虚线断开，就对应着一种社区结构。HTTP/INFO3DOUCOM/论坛推广大连理工大学硕士学位论文图23分级聚类方法中记录算法结果的树状图谱系图18O底部的各个圆代表了网络中的各个结点。FIG2_3ANEX锄PLEOFASMALLHIERARCHICALCLUSTERINGTREE【捌THECIRCLESATTHEBOTTOMREPRESENTTHENODESINTHENETWORK2321分裂方法分裂方法中最典型的算法是GN方法口刚。它的基本思想是通过不断地从网络中移除介数BETWEENNESS最大的边将整个网络分解为各个社区。其中，边介数定义为网络中经过该边的最短路径的数目。它为区分一个社区的内部边和连接社区之间的边提供了一种有效的度量标准。GN算法的基本流程如下步骤1计算网络中所有边的介数；步骤2找到介数最高的边并将它从网络中移除；重复步骤1和2，直到每个结点就是一个退化的社区为止。GN算法弥补了一些传统算法的不足，但是，在不知道社区数目的情况下，GN算法也不知道这种分解要进行到哪一步终止。为解决这个问题，NEWMAN等人引进了一个衡量网络划分质量的标准模块度M1。它是基于同型混合ASSOCIATIVDMIXING来定义的。考虑某种划分形式，它将网络划分为K个社区。定义一个七XK维的对称矩阵EP。，其中元素E，表示网络中连接两个不同社区的结点的边在所有边中占的比例；这两个结点分别位于第F个社区和第，个社区。注意，在这里所说的所有的边是在原始网络中的，而不必考虑是否被社区结构算法移除。因此，该模块度的衡量标准是利用完整的网络来计算的。HTTP/INFO3DOUCOM/论坛推广复杂网络社区结构划分算法研究设矩阵中对角线上各元素之和为MYP一它给出了网络中连接某一个社区内部各结点的边在所有边的数目中所占比例。定义每行或者列中各元素之和为AIY，_YJ它表示与第I个社区中的结点相连的边在所有边中所占的比例。在此基础上，用下式来定义模块度的衡量标准QQ，一砰25上式的物理意义是网络中连接两个同种类型的结点的边即社区内部边的比例减去在同样的社区结构下任意连接这两个结点的边的比例的期望值。如果社区内部边的比例不大于任意连接时的期望值，则有Q0。一般认为，Q的最大值对应的社区结构就是网络的社区结构。Q的上限为QI，Q越接近这个值，就说明网络的社区结构越明显。实际网络中，该值通常位于O3到07之间阱1。经过NEWMAN等人的改进以后，GN算法不必依赖多余的信息来判断得到的社区结构是否具有实际意义，而是可以直接从网络的拓扑结构来进行分析。但是该算法的耗时比较大，为ON3，因此它仅仅适用于中等规模的大型网络N10000以下。为了解决这个问题，人们在GN算法的基础上提出了多种改进的算法，主要包括采用结点集的GN算法、自包含GN算法等。2321凝聚方法GN算法虽然准确度比较高，分析社区结构的效果比原有的一些算法好，但是它的算法复杂度比较大，因此仅仅局限于研究中等规模的复杂网络。现在，对于INTERNET、唧和电子邮件网络等网络的研究越来越多，面这些网络通常都包含几百万个以上的结点。在这种情况下，传统的GN算法就不能满足要求。基于这个原因，NEWMAN在GN算法的基础上提出了一种快速算法N钟NEWMANFASTALGORITHM，以下简称NF算法，它实际上是基于贪婪算法思想的一种凝聚算法，可以用于分析结点数达100万的复杂网络。NF算法如下步骤1初始化网络为N个社区，即每个结点就是一个独立社区。则在GN算法中讨论过的矩阵E中，初始的Q，和口J满足HTTP/INFO3DOUCOM/论坛推广大连理工大学硕士学位论文J肌如果结点L之间有边相连9IO其他26Q其中KI为结点I的度，M为网络中总的边数。步骤2依次合并有边相连的社区对，并计算合并后的模块度增量AQP，2A，AJ2E，A,AJ。根据贪婪算法的原理，每次合并应该沿着Q增大最多或者减小最少的方向进行，其算法复杂度为0M。每次合并以后，对相应的元素更新，并将与F、，社区相关的行和列相加，其时间复杂度为0N。因此，步骤2总的时间复杂度为OMN。步骤3重复执行步骤2，不断合并社区，直到整个网络都合并成为一个社区。最多要执行N1次合并。该算法总的算法复杂度为0MNN，对于稀疏网络则为ON2。整个算法完成后可以得到一个社区结构分解的树状图。再通过选择在不同位置断开可以得到不同的网络社区结构。在这些社区结构中，选择一个对应着局部最大Q值的，就得到最好的网络社区结构。为了进一步提高算法的速度，CLAUSET等人在NF算法的基础上，采用堆的数据结构来计算和更新网络的模块度，提出了一种新的凝聚算法嘲。该算法的复杂度只有ONL092刀1，已接近线性复杂性。233基于模块度矩阵的社区结构划分算法2006年，NEWMAN在模块度矩阵的基础上，结合谱分析的思想，提出了一种新的算法。此处仅列出两社区的划分算法，多社区划分算法可参考文献40。该算法的目的是为了让社区内部拥有尽可能多的边数。此目的可通过最大化实际网络中社区内部的边数和网络在随机相连的情况下社区内部的边数的差值来实现。但是，寻找该差值的最大值将会耗费很大的计算量，不适合大型复杂网络数据的社区划分，因此可寻找一种使差值尽可能大的方法。基于模块度矩阵的社区划分方法就是利用模块度矩阵的谱特征，使差值尽可能大的一种方法。式27中去掉等式右边的常系数项后表示在网络划分为两个社区的情形下的上述差值Q去莓名一等矿1去莓一等H。27HTTP/INFO3DOUCOM/论坛推广复杂网络社区结构划分算法研究其中肌为网络中的总边数，彳。为网络邻接矩阵中的元素，为网络在随机相连的情。2M形下，结点F与结点歹之间拥有的边数。S岛，SN7是一个标记向量，若结点F属于第一个社区，则S，1，否则S，一1。上式Q的值正好为NEWMAN提出的对网络进行二社区划分后的模块度的值嘲1。等式27可转换为如下的等价形式Q去SRBS28其中矩阵B被称为模块度矩阵，B，彳，一罟。基于模块度矩阵划分网络二社区的算法描述如下首先求得模块度矩阵B的最大特征值所对应的特征向量，然后根据此特征向量中元素的正负，把网络划分为两个社区。正的元素为一个社区，负的元素属于另一个社区。该算法的时间复杂度为ON2LOGN，其中N为网络中结点的个数。234加权网络中的社区结构划分算法以上算法所适用的网络大多数是无权网络，然而现实世界中却存在许多加权网络。网络中边的权重大小具有实际意义，比如在社会网络中边的权重可能表示人与人之间关系亲密程度的大小，因此如果忽略权重去分析加权网络将会丢失大量包含在权重中的有用信息。直接处理加权网络难以实现社区结构的划分，NEWMAN通过把加权网络转换为多重图的形式H3I，即通过把网络中结点对之间边的权重N，看作是此结点对之间有N条边相连，实现了把GN算法推广到加权网络中143。GN算法的本质是不断的移除网络中具有最大边介数的边。边的介数定义为通过该边的所有最短路径的条数。把GN算法推广到加权网络中，一个很简单的想法是在把加权网络转换的多重图中计算边的介数，然后移除拥有最大边介数的边。边的权重越大，通过该边的最短路径数目越多，被移除的概率也越大，然而边的权重代表该边所连接的结点对的亲密程度，权重越大，结点对之间的亲密程度越高，从社区结构划分的角度上来说，该边被移除的概率应该越小，所以上述算法的推广是不可行的。正确的求解加权网络中边的介数的方法应该是在忽略边的权重的情形下，计算网络中各边的介数，然后定义加权网络中边的介数为以上无权情形下求得的边的介数除以该边的权重，这样权重越大的边得到的边的介数越小，因而被移除的概率越小，符合社区结构划分的定义。HTTP/INFO3DOUCOM/论