（运筹学与控制论专业论文）复杂网络社区结构划分算法研究.pdf

大连理工大学硕士学位论文 摘要 随着w s 小世界网络模型和b a 无标度网络模型的提出，国内外掀起了研究复杂网络 的热潮。复杂网络的研究以系统的观点来看待真实系统，如i n t e r n e t 网络、电力网、 新陈代谢网络等。复杂网络通常会呈现出社区结构特性，如何在实际网络中高效地发现 社区结构是近年来复杂网络的研究热点之一。本文基于谱算法的思想提出了一种基于共 邻矩阵和增益函数的有效算法来划分复杂网络中的社区，并把此算法推广到了加权的复 杂网络中。主要工作如下： 1 定义了共邻矩阵和增益函数这两个概念，在此基础上提出一种有效算法来划分复杂 网络中的社区结构。其中共邻矩阵中的元素定义为结点对之间拥有相同邻居的数目。 以增益函数作为网络社区结构划分的目标函数，进一步推导出基于增益矩阵和增量 矩阵的特征值和特征向量的社区结构划分方法。最后把这种算法应用于三个常用的 实际网络数据中，并和n e w m a n 基于模块度矩阵的谱算法结果做了比较，以验证算法 的可行性和有效性。 2 重新定义了在加权网络中结点对之间拥有共同邻居的数目，把基于共邻矩阵和增益 函数的复杂网络社区划分算法推广到加权的复杂网络中。在以往许多复杂网络社区 结构划分算法中，网络中的边常被看作是无权重的，但是现实世界中存在许多加权 网络。如果忽略边的权重，仅仅把划分无权网络社区的算法应用到这些加权网络中， 将会忽略许多包含在边权重中的重要信息，从而得出不尽合理的结果。借鉴n e w m a n 把加权网络映射到无权多重图的思想，重新定义了在加权网络中结点对之间拥有共 同邻居的数目，然后将基于共邻矩阵和增益函数的算法推广到加权的网络中，并把 算法应用到计算机仿真网络和实际的加权网络数据中，验证了推广算法的可行性和 有效性。 关键词：复杂网络；社区结构；共邻矩阵；增益函数；加权网络 复杂网络社区结构划分算法研究 p a r t i t i o n i n gm e t h o d sf o rc o m m u n i t ys t r u c t u r ei nc o m p l e xn e t w o r k s a bs t r a c t i nr e c e n ty e a r s ，a st h ew ss m a l l - w o r l dn e t w o r km o d e la n db as c a l e f r e en e t w o r km o d e l w a sp r o p o s e d ，t h es t u d yo nc o m p l e xn e t w o r k si sa c h i e v i n gac l i m a xa th o m ea n da b r o a dn o w t h es t u d yo nc o m p l e xn e t w o r k st r e a t st h er e a ls y s t e m ss u c ha st h ei n t e r n e t ，e l e c t r i c i t y n e t w o r k sa n dm e t a b o l i cn e t w o r k s 、) l ，i t l lt h ev i e w p o i n to fs y s t e m s c i e n c e c o m m u n i t ys t r u c t u r e e x i s t si nm a n yr e a ln e t w o r k s h o wt of i n ds u c hc o m m u n i t i e se f f e c t i v e l yi so n eo ff o c u s e so f m a n yr e c e n tr e s e a r c h e si nt h eb r a n c ho fc o m p l e xn e t w o r k s i nt h i sa r t i c l e ，t h ea u t h o rp r o p o s e s ap a r t i t i o n a lm e t h o db a s e do nc o m m o nn e i g h b o u r sm a t r i xa n dg a i nf u n c t i o na n dg e n e r a l i z e s t h em e t h o dt ow e i g h t e dn e t w o r k s t h em a i nw o r ko ft h i sp a p e rc a nb es u m m a r i z e da s f o l l o w s ： 1 d e f i n i n gt h ec o m m o nn e i g h b o u r sm a t r i xa n dg a i nf u n c t i o n , a n dp r o p o s i n ga ne f f e c t i v e m e t h o do fa n a l y z i n gt h ec o m m u n i t ys t r u c h l r ei nc o m p l e xn e t w o r k sb a s e do nt h e s et w o c o n c e p t s t h ee l e m e n t si nc o m m o nn e i g h b o u r sm a t r i xm e a n st h en u m b e ro fc o m m o n n e i g h b o u r sb e t w e e nn o d e s w i t ht h eg a i nf u n c t i o na st h eo b j e c t i v ef u n c t i o no fa n a l y z i n g t h ec o m m u n i t ys t r u c t u r e ，w ed e r i v eap a r t i t i o nm e t h o db a s e do nt h ee i g e n v a l u e sa n d e i g e n v e c t o r so fg a i nm a t r i xa n di n c r e m e n tm a t r i x f u r t h e rm o r e ，w ea p p l yt h i sm e t h o dt o t h r e ec o m m o nr e a ln e t w o r kd a t aa n dc o m p a r et h ec o m p u t a t i o n a lr e s u l t sw i t h m o d u l a r i t y b a s e da n a l y s i s m e t h o d sp r o p o s e d b yn e w m a n c o m p u t a t i o n a l r e s u l t s d e m o n s t r a t et h a tt h ep r o p o s e dm e t h o di sf e a s i b l ea n de f f e c t i v e 2 r e d e f m i n gt h ec o m m o nn e i g h b o u r sb e t w e e nap a i ro fn o d e si nw e i g h e dn e t w o r ka n d g e n e r a l i z i n gt h ea l g o r i t h mb a s e do nc o m m o nn e i g h b o u r sm a t r i xa n dg a i nf u n c t i o nt o w e i g h t e dn e t w o r k s a l t h o u g ht h e r ea r em a n yw e i g h t e dn e t w o r ki nt h ew o r l d ，n e t w o r k s a r eu s u a l l yc o n s i d e r e dt ob eu n w e i g h t e di nl o t so fa l g o r i t h m sf o rc o m m u n i t ys t r u c t u r ei n c o m p l e xn e t w o r k c e r t a i n l yt h ea b o v ea l g o r i t h m sc a nb ea p p l i e dt os u c hn e t w o r k sb y s i m p l yi g n o r i n ge d g ew e i g h t s ，b u tt od os oi st ot h r o wa w a yu s e f u li n f o r m a t i o nc o n t a i n e d i nt h ew e i g h t s ，i n f o r m a t i o nt h a tc o u l dh e l pu st om a k eam o r ea c c u r a t ed e t e r m i n a t i o no f t h ec o m m u n i t i e s i nt h i sp a p e rw eu s et h et e c h n i q u et h a tw e i g h e dn e t w o r k sa r em a p p e d o n t om u l t i g r a p h sp r o p o s e db yn e w m a na n dr e d e f i n et h ec o m m o nn e i g h b o u r sb e t w e e na p a i ro fn o d e si nw e i g h t e dn e t w o r k t h e n ，t h ea l g o r i t h mb a s e do nc o m m o nn e i g h b o u r s m a t r i xa n dg a i nf u n c t i o ni sg e n e r a l i z e dt ow e i g h t e dn e t w o r k s f u r t h e rm o r e ，w ea p p l y t h i sm e t h o dt oac o m p u t e r - g e n e r a t e dn e t w o r ka n dar e a ls o c i a ln e t w o r k c o m p u t a t i o n a l r e s u l t sd e m o n s t r a t et h a tt h ep r o p o s e dm e t h o di sf e a s i b l ea n de f f e c t i v e 一i i 大连理工大学硕士学位论文 k e yw o r d s ：c o m p l e xn e t w o r k ；c o m m u n i t ys t r u c t u r e ；c o m m o nn e i g h b o u r sm a t r i x ； g a i nf u n c t i o n ；w e i g h t e dn e t w o r k 1 1 1 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：堡垒! 塑兰墨叠堡至查塑兰! 笪望墨塑庭 作者签名： 继塑芒：日期：4 年l 月j 鱼日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 作者签名： 导师签名： 日期：竺12 年生月鱼日 日期：4 年上月止日 大连理工大学硕士学位论文 1绪论 1 1 复杂网络研究的背景与意义 2 0 世纪9 0 年代以来，以i n t e r n e t 为代表的信息技术的迅猛发展使人类社会大步迈 入了网络时代。从i n t e r n e t 到w w w ，从大型电力网络到全球交通网络，从生物体中的 大脑到各种新陈代谢网络，从科研合作网络到各种经济、政治和社会关系网络等，可以 说；人们已经生活在一个充满着各种各样的复杂网络的世界中。人类社会的网络化是一 把“双刃剑”：它既给人类社会生产与生活带来了极大便利，提高了人类生产效率和生 活质量，但也给人类社会生活带来了一定的负面冲击，如传染病和计算机病毒的快速传 播以及大规模的停电事故等。因此，人类社会的日益网络化需要人类对各种人工和自然 的复杂网络的行为有更好的认识。长期以来，通信网络、电力网络、生物网络、社会网 络等分别是通信科学、电力科学、生命科学、社会学等不同学科的研究对象，而复杂网 络理论所要研究的则是各种看上去互不相同的复杂网络之间的共性和处理它们的普适 方法。从2 0 世纪末开始，复杂网络研究正渗透到数理学科、生命学科和工程学科等众 多不同的领域，对复杂网络的定量与定性特征的科学理解，已成为网络时代科学研究的 一个极其重要的挑战性课题心3 1 ，甚至被称为“网络的新科学( n e ws c i e n c eo f n e t w o r k s ) ”。 传统的对网络的研究最早起源于著名的欧拉七桥问题。之后的近两百年中，数学家 们一直致力于对简单的规则网络和随机网络进行抽象的数学研究。随着近年来计算机存 储能力和处理数据能力的增强，以及一些大规模系统的数据库的建立，人们重新获得了 真实网络的特征数据，发现大多数真实网络既不是规则的，也不是随机的，而是呈现一 定规律的复杂网络h 。复杂网络之所以复杂，不仅在于网络规模的巨大，网络结构的复 杂而且网络在时间、空间上都具有动态的复杂性，网络行为也具有复杂性。 许多真实系统都可以用网络的形式加以描述，一个典型的网络是由许多结点与连接 结点之间的边组成的。结点代表系统中的个体，边则表示结点之间的作用关系。如w w w 网络可以看成是网页之间通过超链接构成的网络璐3 ；i n t e r n e t 网络可以看作不同的计算 机通过光缆连接构成的网络嵋1 ：科学家合作网络可以看作不同的科学家合作关系构成的 网络盯8 1 ：基因调控网络可以看作是不同的基因通过调控与被调控关系构成的网络旧1 。 这些真实网络的普遍存在，促使来自不同学科领域的科学家共同致力于复杂网络的 研究。这些学科领域包括复杂性科学、数学、物理、生物和计算机等。复杂网络的研究 复杂网络社区结构划分算法研究 可以使人们更好地了解现实世界的复杂系统，为设计具有良好性能的网络提供依据。同 时复杂网络的理论成果将会广泛地应用到生物、计算机等各个学科领域。 复杂网络的研究大致可以描述为三个密切相关但又依次深入的方面：大量的真实网 络的实证研究，分析真实网络的统计特性：构建符合真实网络统计性质的网络演化模型， 研究网络的形成机制和内在机理：研究网络上的动力学行为，如网络的鲁棒性和同步能 力，网络的拥塞及网络上的传播行为等。 当把一个系统描述为网络的形式后，就可以通过分析网络的统计性质，如网络的度 分布，网络的簇系数，网络的平均最短距离等来描述真实网络n 叫引。大量的实证研究表 明许多真实世界的网络具有两个基本性质：小世界特性( s m a l lw o r l dc h a r a c t e r ) n 司和无 标度特性( s c a l e - f r e ec h a r a c t e r ) n 刚。小世界特性是指与相同规模的随机网络相比，该 网络具有较小的平均最短距离和较大的簇系数。1 9 6 7 年，美国哈佛大学社会心里学家 m i l g r a m 做了一个实验，在美国将一封信通过熟人找熟人的方式传递到目标者，发现平 均最短经过6 人就可到达，这就是著名的“六度分离( s i xd e g r e eo fs e p a r a t i o n ) ”现 象，它揭示了社会网络的小世界特性。而在万维网( 嗍) 中，平均只需点击1 9 次超级链 接，就可以从任意一个网页到达其它网页鄙。 大量的小世界网络的普遍存在，促使人们探讨形成这种网络的内在机理。1 9 9 8 年， 学者w a t t s 和s t r o g a t z 在规则网络中引入随机性，建立了著名的小世界网络模型( w s 小世界网络模型) n 翻，很好地描述了真实网络的小世界特性。 1 9 9 9 年，学者b a r a b a s i 和a l b e r t 通过对万维网的数据进行统计分析发现万维网的 度分布服从幂律分布，在双对数坐标系下是一条下降的直线，由于幂律分布具有标度不 变性，缺乏一个特征度值，因此称这种度分布服从幂律分布的网络为无标度网络 ( s c a l e - f r e en e t w o r k ) n 明。之后的研究表明，许多社会网络如科学家合作网络口8 1 、生 物网络中的新陈代谢网络n 刀和技术网络中的i n t e r n e t 网络3 等都是无标度网络。这些来 自不同领域的大规模系统呈现了共同的普适规律，促使人们去探索隐藏在这些表象后的 内在演化机制，从此掀起了研究复杂网络的热潮。 近年来，随着大型数据库的建立和计算机存储与运算能力的迅速提高，复杂网络的 研究进程大大加快。人们对社会系统、大型基础性设施和生物系统中大量的真实网络数 据库进行了系统的分析，寻找呈现表象的内在机制和模式，试图发现支配和影响这些复 杂系统的动力学和演化规律的内在本质。复杂网络的理论及实证研究的发展将会对网络 安全、网络控制、疾病传播的控制与防御、社会中人的行为动力学的研究和生物网络的 演化机制研究等产生重要影响。 大连理工大学硕士学位论文 1 2 复杂网络社区结构研究现状 随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有 一个共同性质，即社区结构。也就是说，整个网络是由若干个“社区 或“组构成的。 每个社区内部的结点间的连接相对非常紧密，但是各个社区之间的连接相对来说却比较 稀疏n 8 1 训。揭示网络的社区结构，对于深入了解网络结构与分析网络特性是很重要的。 如社会网络中的社区代表根据兴趣和背景而形成的真实的社会团体；引文网络中的社区 代表针对同一主题的相关论文；万维网中的社区就是讨论相关主题的若干网站u 7 一；而 生物化学网络或者电子电路中的网络社区可以是某一类功能单元幢“捌。发现这些网络中 的社区有助于我们更加有效地理解和开发这些网络。 在复杂网络社区结构划分的研究中，社区结构划分算法所要划分的网络大致可分为 两类，一类是比较常见的网络，即仅包含正联系的网络( 网络中边的权值为正实数) ；另 一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分 网络中社区结构的算法相应分为两大类，而对于第一类网络又提出了许多不同的社区结 构划分算法，划分第一类网络社区的传统算法可分为两大类，第一类是基于图论的算法， 比如k l 算法晗羽、谱平分法盼钆删、随机游走算法啪3 和派系过滤算法口7 勰3 等；第二类是层 次聚类算法，比如基于相似度度量的凝聚算法n 劬和基于边介数度量的分裂算法n 墨观制等。 最近几年从其他不同的角度又提出了许多划分第一类网络社区结构的算法，大致可划分 如下：基于电阻网络性质的算法驺、基于信息论的算法b 船、基于p c a 的算法羽和最大化 模块度们的算法州等。对于符号网络，d o r e i a n 和m r v a r 提出了一种利用局部搜索划 分符号网络社区结构的算法h ，而y a n g 等提出一种基于代理的启发式划分符号网络社 区结构的算法( f e c ) h 羽。下面简要介绍一下几种具有代表性的算法。 1 9 7 0 年，k e r n i g h a n 和l i n 提出一种试探优化法划分网络中的社区结构，简称k - l 算法。它是一种基于贪婪算法原理将网络划分为两个大小已知的社区的二分法。其基 本思想是为网络的划分引进一个增益函数q ，增益函数定义为两个社区内部的边数减去 连接两个社区之间的边数，然后寻找使q 值最大的划分方法。 1 9 9 0 年，p o t h e n 等基于图的l a p l a c e 矩阵的谱特征提出一种将网络划分为两个社 区的二分法瞻目。该算法的理论基础是不为零的特征值所对应的特征向量的各元素中，同 一个社区内的结点对应的元素是近似相等的。因此可以根据网络的l a p l a c e 矩阵的第二 小特征值将其分为两个社区。 2 0 0 1 年，g i r v a n 和n e w m a n 提出了一种基于边介数的分裂算法，简称g n 算法n 8 1 。 该算法的基本思想是不断地从网络中移除介数最大的边。边介数定义为网络中经过每条 边的最短路径数目。该算法的复杂度非常高，2 0 0 3 年t y l e r 等在g n 算法的基础上提出 复杂网络社区结构划分算法研究 了一种新的算法圆1 ，它可以显著提高计算速度，但也降低了计算的准确性。g n 算法是以 网络中的每一个结点i 为源结点，来计算它到其他结点的最短路径，并以这些最短路径 经过每条边的次数作为该边的介数。而t y l e r 等人提出，以网络中某个结点集内的结点 为源结点来计算边的介数也可以达到较好的效果。2 0 0 4 年，n e w m a n 把g n 算法推广到了 加权网络中h 副。 2 0 0 3 年，w u 和h u b e r m a n 基于电阻网络的性质提出了w _ h 算法3 ，其主要思路为将 网络中每条边想象成电阻为单位值的导线，且在网络中任意选择的两个结点上加上单位 值的电位差。w u 和h u b e r m a n 认为，如果网络可以分解成两个社区，那么电位谱在连接 两个社区的边的两端会产生一个较大的间隙。因此，首先确定电位谱的最大间隙处的某 个电位值，然后根据每个结点处的电位是否大于该值而确定结点属于哪个社区。该算法 的一个重要特点是可以用来确定包含指定结点的社区，而无须计算出所有的社区。 2 0 0 4 年，n e w m a n 提出一种基于贪婪法思想的凝聚算法n9 i ，并称这种算法为快速算 法。该算法是在使得模块度不断增加的基础上进行，即每次合并沿着使模块度增多最大 和减小最少的方向进行。算法总的复杂度为d ( ( 研+ 刀咖) ，对于稀疏网络则为o ( n 2 ) ，其中 n 为网络中结点的个数，m 为网络中边的条数。在n e w m a n 快速算法的基础上，c l a u s e t 、 n e w m a n 和m o o r e 等人采用堆的数据结构来计算和更新网络的模块度，提出了一种新的贪 婪算法，称为c n m 算法啪1 。该算法的复杂度只有o ( n l 0 9 2 刀) ，已接近线性复杂性，可用来 分析大型复杂网络数据。同样为了最大化网络的模块度，2 0 0 6 年n e w m a n 基于模块度矩 阵提出一种划分网络中社区结构的谱算法m 1 ，并于2 0 0 8 年把该算法推广到有向网络中 4 4 3 o 2 0 0 5 年，p o n s 和l a t a p y 提出一种利用随机游走划分网络社区结构的算法嘶3 ，算法 的初始条件为每个结点为一个单独的社区，然后逐步合并可使结点和它所在社区之间的 平方距离均值达到最小的两个社区。每一步都要更新社区之间的距离，其中两个结点之 间的距离对应于它们的相似度，即在一个离散的随机游走过程中，它们之间的方向转移 概率。 大多数社会网络社区结构划分算法仅适用于包含正联系的网络，而不适合符号网络 中的社区结构划分。在符号社会网络的社区结构中，不仅社区内部的正联系比较多，而 且社区之间的负联系也比较多。1 9 9 6 ，d o r e i a n 和r r v a r t 提出了一种利用局部搜索划分 符号社会网络中社区结构的算法1 。这种算法本质上是一种基于贪婪策略的算法，通过 最小化一个预定义的误差函数把网络划分为几个社区。误差函数的定义为：社区内部负 向联系和社区之间正向联系权重绝对值的和。算法的初始条件为随机的把结点划分到已 大连理工大学硕士学位论文 知数量的社区中，然后计算对于初始划分的误差函数值。为了减小误差函数的值，把结 点从一个社区移动到另外一个社区，结点的移动直到误差函数不再减少为止。算法复杂 度为d ( 迭代次数奉刀2 ) ，其中迭代次数为结点移动的次数，n 为网络中结点的个数。该算 法的缺陷为必须事先知道要划分的社区的数目且依赖于初始划分，并且该算法仅考虑到 边的符号而没有考虑边的密度。 2 0 0 7 年y a n g 等人提出了一种基于代理的启发式方法划分符号社会网络中的社区结 构，并称这种算法为f e c 算法h 羽。该算法分为两个阶段，第一个阶段为f c 阶段，即计 算其他所有结点经过一定数量的步长到达汇结点( s i n kn o d e ) 的概率；第二个阶段为定 义一个截断标准，找出汇结点所在的社区。该算法效率比较高，为o ( ，z ) ，其中n 为网络 中结点的个数，并且能给出接近最优解的解。 以上所述算法最终目的均是把网络划分为若干个相互分离的社区，但是现实中很多 网络并不存在绝对的彼此独立的社区结构，相反它们是由许多彼此重叠且相互关联的社 区构成。比如，每个人根据不同的分类方法都会属于多个不同的社区( 如学校、家庭、 不同的兴趣小组等) 。在这种情况下，很难单独的将这些社区划分出来。因此，p a l l a 等人提出了一种派系过滤算法( c li q u ep e r c o l a t i o nm e t h o d ) 来分析这种互相重叠的社 区结构3 。 尽管复杂网络的社区发现问题得到了大量的研究，但还存在一些尚未解决的基本问 题，如社区概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性 能优越，但所需计算量却很大。这说明复杂网络中社区发现的研究还需要付出大量的努 力蜘。 1 3 本文的研究内容与文章结构 本课题主要研究复杂网络中的社区结构划分。首先，针对无权的复杂网络，提出了 共邻矩阵和增益函数的概念，在此基础上提出一种有效的划分社区结构的算法。实验结 果表明该算法是可行且有效的。最后把这种算法推广到加权的复杂网络中，并把算法应 用到计算机仿真网络和实际的加权网络数据中，验证了推广算法的可行性和有效性。 综上所述，本文主要研究内容共分为两个部分：第一部分提出了一种基于共邻矩阵 和增益函数的复杂网络社区结构划分算法；第二部分把此算法推广到加权的复杂网络 中。具体内容如下： 第二章首先介绍了复杂网络的图表示、度分布、平均最短路径和社区结构等基本概 念和基本性质。然后详细介绍了几种划分复杂网络社区结构算法的基本思想和特点，包 括无权网络和加权网络中的社区结构划分算法。 复杂网络社区结构划分算法研究 第三章从社区内部结点对之间应该拥有更多的共同邻居出发，提出了基于共邻矩阵 和增益函数的复杂网络社区结构划分算法。把这种网络社区结构划分方法应用于空手道 俱乐部网络、海豚网络和政治书籍网络三个常用的实际网络数据中，并和n e w m a n 基于 模块度矩阵的谱算法结果做了比较，数值实验结果表明本文提出的方法是可行且有效 的。 第四章重新定义了在加权网络中结点对之间拥有共同邻居的数目，把基于共邻矩阵 和增益函数的复杂网络社区结构划分算法推广到加权的复杂网络中。在以往许多复杂网 络社区结构划分算法中，网络中的边常被看作是无权重的，但是现实世界中却存在许多 加权网络。如果忽略边的权重，仅仅把划分无权网络中社区结构的算法应用到加权网络 中，将会忽略许多包含在边权重中的重要信息，得出不合理的结果。借鉴n e w m a n 把加 权网络映射到无权多重图的思想，重新定义了在加权网络中结点对之间拥有共同邻居的 数目，然后将基于共邻矩阵和增益函数的算法推广到加权的网络中，并把算法应用到计 算机仿真网络和实际的加权网络数据中，验证了推广算法的可行性和有效性。 最后对全文的工作进行了总结，并对今后的工作和发展方向提出了展望。 大连理工大学硕士学位论文 2 复杂网络社区结构划分算法概述 2 1 复杂网络基本性质 2 1 1真实网络的图表示 首先，简单介绍有关图的定义和基本概念。图g 可以表示为集合，9 ) ， ，( g ) = 1 ，2 ， 表示图g 的顶点集合，n 表示网络的顶点总数， 9 ( g ) = ( ，五) ，( 之，五) ，( 名，止) ) 代表边集合，e 表示总边数，如果( f ，j ) = ( - j f ，f ) ，则图是无 向图，否则为有向图。当网络是无向无权网络时，邻接矩阵a = 概，) 是一个0 - 1 对称矩 阵，表示图中顶点之间的连接关系。如果顶点f ，歹之间有连接，则= 1 ：否则a o = 0 。 当网络是有向图时，邻接矩阵a 是非对称的0 - 1 矩阵：当网络是加权网络时，a 中的非零 元素代表边的权重。 2 1 2 度分布 度分布是描述网络性质的一个重要统计量。结点i 的度定义为与结点f 连接的边的数 目。度分布p ( j j ) 定义为随机地选择一个结点，度为k 的概率，或者等价地描述为网络中 度为后的结点数占网络结点总数的比例。当然，对于有向网络，其度分布还可细致地分 为网络的入度分布( i n - d e g r e ed i s t r i b u t i o n ) 和出度分布( o u t - d e g r e ed i s t r i b u t i o n ) 。 近年来大量的实证研究表明，许多真实网络的度分布都遵循幂律分布，数学形式 为：p ( 后) k ，其中y 一般介于2 到3 之间。幂函数在双对数坐标系下是一条下降的直 线，如w w w h 7 1 的度分布，如图2 1 b 所示。与指数函数相比，幂函数下降速度较慢，使得 网络中存在度较大的结点，通常称这些结点为集散结点( h u bn o d e ) 。研究发现除了幂 律分布，真实网络中还存在其它形式的度分布，如电力网络n 司的度分布服从指数分布， 在单对数坐标系下是一条下降的直线；也存在幂律加指数截断的度分布的网络，如电影 演员合作网络口6 1 ，如图2 1 a 所示，以及蛋白质相互作用网络。 2 1 3网络的平均最短路径和顶点的介数 网络的平均最短距离( a v e r a g ep a t hl e n g t h ) 定义为网络中任意一对结点之间的最 短距离的平均值，数学表达式为： 1 一 d = 二办 (21)n(n- 1 ) f 篇8 。 复杂网络社区结构划分算法研究 其中办为结点f ，j 之间的最短路径的长度。所有结点间的最短路径长度的最大值称为网 络半径( n e t w o r kd i a m e t e r ) 。大多数真实网络具有较小的平均最短距离，如具有1 5 3 1 2 7 个结点的万维网( w w w ) 的平均最短距离为3 1 h 钉，大肠杆菌的代谢网络的平均最短距离为 2 4 6 4 8 】。 订 埘o 矿 卫 ， 轧矿 1 l f i 矿 图2 1 不同类型的大规模网络的度分布。a ：电影演员合作网络，网络规模为 n = 2 1 2 ，2 5 0 ，( 七) = 2 8 7 8 ；b ：唧网络，网络规模为n = 3 2 5 ，7 2 9 ，( 七) = 5 4 6 。度分布的幂 指数：，一= 2 3 ，= 2 1 ，引自文 1 6 。 f i g 2 1 t h ed i s t r i b u t i o nf u n c t i o n so fe o n n e c t i v i t i e sf o rv a r i o u sl a r g en e t w o r k s a ：a c t o r c o l l a b o r a t i o ng r a p hw i t h n = 2 1 2 2 5 0n o d e sa n da v e r a g ec o n n e c t i v i t y = 2 8 7 8 b ：w w w ， n = 3 2 5 ，7 2 9 ， = 5 4 6 1 1 他d a s h e dl i n e sh a v es l o p e sa ：y 础，= 2 3 ，b ：y 删= 2 1 r e f 1 6 网络中不相邻的结点歹和k 之间的路径主要依赖于连接结点歹和k 的路径上所经过 的结点，如果某个结点被其它许多路径经过，则表示该结点在网络中很重要。定量地描 某个结点在网络中的影响力或重要性可以用顶点的介数( n o d eb e t w e e n e s s ) 来衡量，这 一定义最早由f r e e m a n 在1 9 7 7 年提出呻。顶点f 的介数置定义为： ( 2 2 ) 业 归 = 忍 大连理工大学硕士学位论文 其中拧硪表示结点j 、后之间的最短路径的个数，n j , ( i ) 表示结点j 、七之间的最短路 径中经过结点i 的个数。 2 1 4 网络的簇系数 网络的簇系数( c l u s t e r i n gc o e f f i c i e n t ) 是衡量网络集团化程度的重要参数，是一 个局部特征量。结点f 的簇系数g 定义为结点f 的邻接点之间实际存在的边数与所有可 能的边数的比值，数学表达为： c ：生一 ( 2 3 ) 。 匆( 毛- i ) 其中，毛表示结点f 的度，e ，表示结点f 的邻接点之间实际存在的边数。网络的簇系数定 义为对所有结点的簇系数做和求平均： n c = 专c ， ( 2 4 j ，一 vt - - ! 许多真实网络具有较大的簇系数和较小的平均最短距离。这里“较大的簇系数指 真实网络的簇系数远远大于相同规模的随机网络的簇系数。“较小的平均最短距离指 平均最短距离随网络规模的增加呈对数或者更小增长。 2 2 复杂网络社区结构定义 近几年来，复杂网络的研究正处于蓬勃发展的阶段，其思想已经充斥到科学和社会 的每一个角落。随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际 网络都具有一个共同性质社区结构。也就是说，网络是由若干个“群( g r o u p ) 或 “团( c l u s t e r ) 构成的。每个群内的结点之间的连接非常紧密，而群之间的连接却 相对比较稀疏n 1 ，如图2 2 所示。图中的网络包含三个社区，分别对应图中三个虚线圆 圈包围的部分。在这些社区内部，结点之间的联系非常紧密，而社区之间的联系就稀疏 得多。 一般而言，社区可以包含模块、类、群和组等各种含义。例如，万维网可以看成是 由大量网站社区组成，其中同一个社区内部的各个网站所讨论的都是一些有共同兴趣的 话题n 7 阍3 。类似地，在生物网络或者电路网络中，同样可以将各个结点根据其不同的性 质划分为不同的社区瞳h 翻。揭示网络中的社区结构，对于了解网络结构与分析网络特性 具有极为重要的意义。社区结构分析在生物学、物理学、计算机图形学和社会学中都有 广泛的应用n8 刚。 复杂网络社区结构划分算法研究 图2 2 一个小型的具有社区结构性质的网络示意图。引自文 1 。 f i g 2 2 as m a l ln e t w o r kw i t hc o m m u n i t ys t r u c t u r e r e f 1 2 3 复杂网络社区结构划分算法 网络社区结构的研究已经有很长的历史。为了能够准确有效地分析复杂网络中的社 区结构，人们提出了多种不同的社区结构划分算法，这些算法的目的是利甩尽量少的信 息得到尽量准确地网络社区结构，从而更好地分析网络中社区结构的基本特点和共同特 性。早期分析社区结构的算法，包括计算机科学中的图形分割( g r a p hp a r t i t i o n ) 和 社会学中的层次聚类( h i e r a r c h i c a lc l u s t e r i n g ) 两种晦1 嘲，前者主要包括 k e r n i g h a n - l i n 算法嘲和基于图的l a p l a c e 矩阵特征向量的谱平分法( s p e c t r a l b i s e c t i o nm e t h o d ) 幽踟；而后者则以著名的g n ( g i r v a n - n e w m a n ) 算法为代表n 驯。 2 3 1迭代二分法 计算机科学中的一个典型问题，是将一个网络分解成若干结点数基本相等的子网， 使得不同子网中的结点之间的连接数最少，称为图分割( g r a p hp a r t i t i o n i n g ) 。图分割 问题( g p p ) 可应用于并行计算机的处理器合理分配进程。实际应用中，大多数图分割方 法均基于迭代二分法：首先将图按要求分割成2 个子图，然后再分别对这2 个子图进行分 割，如此迭代下去直至获得所要求的子图个数。 我们介绍两个最具代表性的迭代二分法：一是k e r n i g h a n l i n 算法昭引，该算法使用 贪婪策略对社区内以及社区间的边数进行优化，从而达到改进网络的初始分解的目 的；另一个是基于图的l a p l a c e 矩阵的特征向量的谱二分法( s p e c t r a lb i s e c t i o n m e t h o d ) 2 4 , 2 5 】。 大连理工大学硕士学位论文 2 3 1 1k e r n i g h a n - - l i n 算法 k e r n i g h a n l i n 算法是一种试探优化法1 。它基于贪婪算法原理将网络划分为两个 规模已知的社区。其基本思想是为网络的划分引进一个增益函数q ，q 定义为两个社区 内部的边数减去连接两个社区之间的边数，然后寻找使q 值最大的划分方法。整个算法 可描述如下： 首先，将网络中的结点随机地划分为已知规模的两个社区。在此基础上，考虑所有 可能的结点对，其中每个结点对的结点分别来自两个社区。对每个结点对，计算如果交 换这两个结点的话可能得到的q 的增益q = q 交换后一绥换前，然后交换最大的q 对应的 结点对，同时记录交换以后的q 值。规定每个结点只能交换一次。重复这个交换过程， 直到某个社区内所有的结点都被交换一次为止。需要注意的是，在结点对交换的过程中， q 值并不一定总是单调增加的。不过，即使某一步的交换会使q 值有所下降，但是仍然 可能在其后的步骤中出现一个更大的q 值。当交换完毕后，便找到上述交换过程中所记 录的最大的q 值。这时对应的社区结构就认为是该网络实际的社区结构。 k e r n i g h a n l i n 算法最大的缺陷是要求事先知道两个社区的规模，否则，就很可能 不会得到正确的结果。这个缺陷使得它在实际网络分析中难以应用。而且，即使这个问 题可以得到解决，它与所有的二分算法一样，仍然面临着如何事先知道网络中的社区数 目，以及确定二分法要重复到哪一步停止的问题。 2 3 1 2 谱平分法 一个有n 个结点的无向图g 的l a p l a c e 矩阵是一个刀x 刀维的对称矩阵l 。其中，l 的对角线上的元素厶，是结点i 的度( 结点的度定义为与该结点连接的其它结点的数目) ， 而其他非对角线上的元素厶，则表示结点i 和结点j 的连接关系。如果这两个结点之间有 边连接，则厶，值为1 ，否则为0 。l 矩阵所有的行与列的和都为0 ，因此，该矩阵总有一 个特征值为o ，其对应的特征向量为l = ( 1 ，1 ，1 ) 。可以从理论上证明，不为零的特征 值所对应的特征向量的各元素中，同一个社区内的结点对应的元素是近似相等的。这就 是谱平分法的理论基础。 考虑网络社区结构的一种特殊情况：当一个网络中仅存在两个社区，此时该网络的 l a p l a c e 矩阵l 就对应了两个近似的对角矩阵块。对一个实对称矩阵而言，它的非退化 的特征值对应的特征向量总是正交的。因此，除了最小特征值0 以外，矩阵l 其他特征 值对应的特征向量总是包含正、负两种元素。这样，当网络由两个社区构成时，就可以 根据非零特征值相应的特征向量中的元素对应网络的结点进行分类。其中，所有正元素 对应的那些结点都属于同一个社区，而所有负元素对应的结点则属于另一个社区。 复杂网络社区结构划分算法研究 因此，我们可以根据网络的l a p l a c e 矩阵的第二小的特征值九将其分为两个社区。 这就是谱平分法的基本思想。当网络的确是分成两个社区时，用谱平分法可以得到非常 好的效果。但是，当网络不满足这个条件时，谱平分法的优点就不能得到充分体现。事 实上，第二小特征值厶可以作为衡量谱平分法效果的标准：它的值越小，平分的效果就 越好。九也称为图的代数连接度( a l g e b r a i cc o n n e c t i v i t y ) 。 一般情况下，计算一个聆”矩阵的全部特征向量的时间复杂度为o ( n 3 ) 。但是在大 多数情况下，实际网络的l a p l a c e 矩阵是一个稀疏矩阵，因此，可以用l a n c z o s 方法快 速计算主要的特征向量。该方法的时间复杂度大致为m ( 厶一九) ，其