复杂网络中的社团结构

2008年9月

复杂系统与复杂性科学　

COMPLEXSYSTEMSANDCOMPLEXITYSCIENCE

Vol.5No.3Sep.

2008

文章编号:1672-3813(2008)03-0019-24

复杂网络中的社团结构

李晓佳,张　鹏,狄增如,樊　瑛

(北京师范大学管理学院系统科学系,北京100875)

摘要:对复杂网络社团结构问题进行了综述。介绍了无权无向网络中社团结构的

定义、探索社团结构的算法及算法的评价标准和检验网络。重点总结与类比了具

有代表性的算法及其在检验网络上得到的结果,并依据这些结果和评价标准对算法进行了评述。部分地概括了原有算法在加权无向网络中的推广方法。最后对部分社团结构算法的特点进行了横向的比较,对社团结构与网络功能的研究进行简略介绍,并对社团结构研究的发展做出展望。

关键词:复杂网络;社团结构;聚类中图分类号:N94文献标识码:A

CommunityStructureinComplexNetworksLIXiao2jia,ZHANGPeng,DIZeng2ru,FANYing

(DepartmentofSystemsScience,SchoolofManagement,BeijingNormalUniversity,Beijing100875,China)

Abstract:Communitystructureexistswidelyinmostofactualsystemsandnetworks.Investigationon

communitystructureisanimportantwaytounderstandboththestructureandfunctionofnetworks.Inthispaper,wereviewmainresultsinthestudyofcommunitystructureincomplexnetworks.Firstly,wefocusontheunweightedandundirectednetworks.Definitionsofcommunitystructureandalgorithmsthatdetectcommunitiesareintroduced.Meanwhilesomemeasurementsondetectingalgorithmsandclassicalnet2worksarelisted.Theemphasisofourworkisevaluatingalgorithmsusingmeasurementsandtheresultsforclassicalnetworks.Secondlyweextendstudytoweightedandundirectednetworks.Finally,thecom2parisonofsomealgorithmsandabriefintroductiontotherelationshipbetweencommunitystructureandnetworkfunctionaregiven,andprospectofstudyoncommunitystructureinthefutureisoutlined.Keywords:complexnetworks;communitystructure;clustering

1　引言

近些年来,复杂网络逐渐成为受人关注的研究领域,越来越多的科研工作者投身其中,使得新思想新成

[1-6]

果不断涌现。在此过程中,新的研究方向也被开拓出来,网络结构的社团划分就是其中之一。通过近几年的发展,在这一方向上已经积累了一些优秀的思想和成果,有必要对其进行全面系统的整理,为今后的发展提供帮助和借鉴。

收稿日期:2008-01-23

基金项目:国家自然科学基金(70771011)

作者简介:李晓佳(1984-),女,江苏人,硕士研究生,主要研究方向为系统工程及复杂网络。

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学·20·2008年9月

网络由大量顶点(或称为节点)和连接顶点的边组成。许多实际系统都可以从网络的角度进行刻画,例

[7-8][9][10-11]

如:Internet网、万维网、食物链、人际交往关系等等。用网络对实际系统进行抽象时,系统中的个体对应网络中的顶点,个体间的相互关系对应网络中的边,从而这些系统都可以表现为由点和边构成的图。这种抽象过滤了系统纷繁复杂的背景信息,只保留了系统的基本结构,有助于对系统内在共同特征和性质的研究。

近年来对众多实际网络的研究发现,它们存在一个共同的特征,称之为网络中的社团结构。它是指网络

[12]

中的顶点可以分成组,组内顶点间的连接比较稠密,组间顶点的连接比较稀疏,如图1。社团结构在实际

[13]

系统中有着重要的意义:在人际关系网中,社团可能基于人的职业、年龄等因素形成;在引文网中,不同社

[14-16]

团可能代表了不同的研究领域;在万维网中,不同社团可能表示了不同主题的主页;在新陈代谢网、神经网中,社团可能反映了功能单位;在食物链网中,社团可能反映了生态系统中的子系统。在网络性质和功能的研究中,社团结构也有显著的表现。例如:在网络动力学的研究中,当外加能量处于较低水平时同一社

[17]

团的个体就能达到同步状态;在网络演化的研究中,相同社团内的个体可能最终连接在一起。总之,对网络中社团结构的研究是了解整个网络结构和功能的重要途径。

本文着重关注网络社团结构研究中以下4方面问题:1)社团结构的定义;2)探索社团结构的算法;3)划分方法的检验与评价;4)社团结构及划分算法在加权网上的推广。

在这里不过多涉及社团结构与网络功能之间的关系。因此本文的基本结构为:第2节介绍社团结构的各种定义,以及社团结构的描述方法。

第3节在概括介绍一种社团结构划分思路的基础图1　社团结构网络示意图[22]上,讨论社团结构划分方法的评价标准,包括算法

复杂度及一些作为检验工具的人造网和实际网,

并进一步介绍划分结果的比较方法。第4节具体介绍各种社团结构的划分算法,及应用于经典网络的划分结果。第5节将上述讨论推广到加权网,展现权重对网络社团结构划分的影响。最后对社团结构划分问题进行总结与展望。

2　社团结构的定义与模块化函数

2.1　社团结构的定义

关于网络中的社团结构目前还没有被广泛认可的唯一的定义,较为常用的是基于相对连接频数的定义:网络中的顶点可以分成组,组内连接稠密而组间连接稀疏。这一定义中提到的“稠密”和“稀疏”都没有明确的判断标准,所以在探索网络社团结构的过程中不便使用。因此人们试图给出一些定量化的定义,如提

[18-19]

出了强社团和弱社团的定义。强社团的定义为:子图V中任何一个顶点与V内部顶点连接的度大于其

[18-19]

与V外部顶点连接的度。弱社团的定义为:子图V中所有顶点与V内部顶点的度之和大于V中所有顶点

[24]

与V外部顶点连接的度之和。此外,还有比强社团更为严格的社团定义———LS集,一个LS集是一个由顶点构成的集合,它的任何真子集与该集合内部的连边都比与该集和外部的连边多。

[21]

另一类定义则是以连通性为标准定义社团,称之为派系。一个派系是指由3个或3个以上的顶点组成的全连通子图,即任何两点之间都直接相连。这是要求最强的一种定义,它可以通过弱化连接条件进行拓展,形成n-派系。例如:2-派系是指子图中的任意两个顶点不必直接相连,但最多通过一个中介点就能够连通。3-派系是指子图中的任意两个顶点,最多通过两个中介点就能连通。随着n值的增加,n-派系的要求越来越弱。这种定义允许社团间存在重叠性。所谓重叠性是指单个顶点并非仅仅属于一个社团,而是可以同时属于多个社团。社团与社团由这些有重叠归属的顶点相连。有重叠的社团结构问题有研究的价值,因为在

[21]

[12,22]

第5卷第3期　　李晓佳,等:复杂网络中的社团结构·21·

实际系统中,个体往往同时具有多个群体的属性。

除上述提到的社团定义以外,还有多种其他定义方式,文献[24]进行了更为详细的介绍。本文重点关注于可以完全分离的社团结构问题,并采用较为常用的基于相对连接频数的社团结构定义。2.2　社团结构的定量描述———模块化Q函数

在探索网络社团结构的过程中,描述性的定义无法直接应用。因此Girvan和Newman定义了模块化函数,定量地描述网络中的社团,衡量网络社团结构的划分。所谓模块化是指网络中连接社团结构内部顶点的边所占的比例与另外一个随机网络中连接社团结构内部顶点的边所占比例的期望值相减得到的差值。这个随机网络的构造方法为:保持每个顶点的社团属性不变,顶点间的边根据顶点的度随机连接。如果社团结构划分得好,则社团内部连接的稠密程度应高于随机连接网络的期望水平。用Q函数定量描述社团划分的模块化水平。

假设网络已经被划分出社团结构,ci为顶点i所属的社团,则网络中社团内部连边所占比例可以表示成

[25]

6

ij

Aij(ci,cj)

6

ij

Aij

=

12m6

ij

δ(ci,cj)Aij

其中,Aij为网络连接矩阵中的元素,如果i,j两点有边相连则Aij=1,否则等于0;δ(ci,cj)为δ函数,即ci=cj时值等于1,否则等于0;m=在连边的可能性为

kikj

126

ij

Aij为网络中边的数目。在社团结构固定,边随机连接的网络中,i,j两点存

[26]2m

,ki为顶点i的度。所以Q函数的表达式Q=

为12m6

ij

Aij-

kikj2mδ(ci,cj)

Q函数还有另一种表达方法[25]

。如果网络被划分为n个社团,那么定义n×n的对称矩阵e。其中的元素

eij表示连接社团i与社团j中的顶点的边占所有边的比例。这个矩阵的迹Tre=

6

i

eii表示网络中所有连接社

团内部顶点的边占总边数的比例。定义行(或列)的加总值ai=

6

i

eij,表示所有连接了社团i中的顶点的边

占总边数的比例。由eij和ai的定义可知eij=aiaj。从而,Q函数可以表达为

Q=

2

6

i

(eii-ai)=Tre-‖e‖

2

2

22

其中,“‖e‖”为矩阵e的模,即e中元素的加总。

[23]

同时,Q函数还可以表达为

Q=

v=1

6

n

lvL

-

dv

22L其中,lv为社团V中内部连边的数目,dv为社团V的总度值,L为网络中的总边数。

如果社团内部顶点间的边没有随机连接得到的边多,则Q函数的值为负数。相反,当Q函数的值接近1时,表明相应的社团结构划分得很好。实际应用中,Q的最大值一般在013～017的范围内,更大的

[25]

值很少出现。在社团结构的划分过程中,计算每一种划分所对应的Q值,即模块化值,并找出数值尖峰所对应的划分(通常会有一两个),这就是最好或最接近期望的社团结构划分方式(图2)。

　　图2　不同社团结构划分对应不同模块化函数值[25]

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学·22·2008年9月

模块化Q函数自提出以来得到了广泛的认可,不但完善了一些旧有的探索社团结构的算法,而且发展了

[23]

众多以Q函数为目标函数的新算法。然而,最近有些科研工作者对Q函数的有效性提出了质疑。他们指出,根据模块化的定义,包含lv条内部连边且总度值为dv的子图V满足

lvL-dv

2L2

>0,则这个子图便可视为

一个社团。但在最大化Q函数的过程中,若这种社团内部连边的数目小于2L,即使社团间的连接十分稀疏,它们也会被合并成一个大社团。因此Q函数最大值所确定的社团,可能是多个满足模块化社团定义的小社团的结合。

3　社团划分思路及社团划分的相关问题

3.1　社团划分思路

按照复杂网络中社团形成的过程,网络中社团结构的划分思路大体可以分成4类:凝聚过程、分裂过程、搜索过程和其他过程。

凝聚过程是以顶点为基础,通过逐步凝结形成社团。其主要步骤为:1)设定某种标准可以衡量社团与社团之间的距离或相似度;2)将网络中的每一个顶点视为一个社团,所以网络中有多少顶点就有多少初始社团,并且每个社团只包含一个顶点;3)根据设定的衡量标准,计算社团与社团间的距离或相似度,并将距离最近的社团或相似度最高的社团合并在一起形成新的社团;4)重新计算每对社团间的距离或相似度;5)不断重复合并及重新计算的步骤,直到所有顶点都聚集成一个社团。整个过程可以用一个倒立的树状图表示,如图3。第4节将介绍的层次算法就是一个典型的例子。图3　树状图[22]

分裂过程则相反,它首先将网络中的所有顶点都视为一大社团,通过逐步分割这个大社团形成小社团。其主要步骤为:1)设定某种衡量顶点间密切程度或边对网络结构影响程度的指标;2)按照一定标准进行断边;3)不断重复计算和断边的过程,网络将被划分成一个个越来越小的连通社团,这些连通社团就是对应某一阶段的社团;4)全部过程以每个顶点被独立地分成一个社团为终点。整个过程可以用一个直立的树状图表示,过程方向与凝聚过程相反。其代表之一就是第4节中将介绍的GN算法。

搜索过程不拘泥于统一的凝结或分裂,而是建立一个逐步优化目标的探索过程,社团结构直接由最后的优化结果给出。搜索的方法可以应用成型的算法,Potts模型算法中就应用了模拟退火算法进行搜索。

其他过程包含不归属于上述3个过程中的其他社团形成过程。如第4节将介绍的谱分析算法。

第5卷第3期　　李晓佳,等:复杂网络中的社团结构·23·

3.2　划分方法的复杂度研究

由于各种划分方法在判断标准,优化思路、搜索步骤等方面的不同,每种划分算法都有其自身的复杂度。

复杂度往往与被研究网络的顶点数目、边的数目、层次的数目、社团的数目有关。划分方法的复杂度越高划分所需的时间越长。对于较小的网络,划分方法所需时间的长短不会产生本质的影响。然而由于受到计算机技术的制约,一种划分方法的复杂度决定该划分方法能否运用于大规模的网络。可见,算法复杂度既是判断划分方法速度的标准,又是判断划分方法适用范围的标准。复杂度越小的划分方法,划分的速度越快,适用的网络规模越大。因此,构造复杂度低的算法,是科研工作者的目标之一。算法复杂度的具体分析方法将在算法介绍中作简单讨论。

3.3　检验划分方法的经典网络

检验划分方法的网络有两大类:人造网和实际网。之所以要构建人造网,是因为人造网的结构可以人为给定,在分析之前就拥有较多的已知信息,从而可以用来检验划分方法的有效性及正确率。另外,人造网的参数可以调控,从而可以研究划分方法的适用范围,以及划分正确率与参数的联系。常用的人造网是由128个

[12]

顶点构成的网络,这128个顶点被平均分成4份,形成4个社团,每个社团包含32个顶点。顶点之间相互独立的随机连边,如果两顶点属于一个社团,则以概率pin相连,如果两点属于不同的社团,则以概率pout相连。pin和pout的取值,保证每个顶点的度的期望值为16。记Zin为顶点与社团内部顶点连边数目的期望值,Zout为顶点与社团外顶点连边数目的期望值,从而Zin+Zout=16。Zout越小,说明顶点与社团外顶点的连边越少,网络的社团结构越明显;Zout越大,说明顶点与社团外顶点的连边越多,网络越混乱,社团结构越不明显。对于Zout值大的网络还能够基本正确对网络进行划分的方法,在实际应用中适用范围更广,价值更大。众多方法的实践表明,当Zout的取值在一定范围内时,其值对顶点划分正确率没有影响,并且正确率都保持在100%,然而当Zout的取值超过这一临界值之后,网络中顶点被正确划分的比率与Zout的取值呈现负相关关系,即Zout越大,顶点被正确划分的比例越低。

人造网的检验在一定程度上反映了划分方法的有效性。然而,由于人们感兴趣的问题大多是实际网络,所以需要用实际网络对划分方法进行再检验。选择用作检验的实际网络时,首先要保证构建网络的数据是方便易得的;其次要保证网络有实际的意义,从而可以判断社团划分的结果是否具有可解释性;另外为了方便划分方法间的比较,宜采用已被广泛使用的实际网络。以下介绍几个常用的实际网络,方便对第4节所介绍的划分方法进行比较。

[12]

空手道俱乐部网:20世纪70年代初,WayneZachary观察了美国大学空手道俱乐部成员间的人际关系,并依据俱乐部成员间平时的交往状况建立了一个网络。这个网络包含34个顶点,代表了俱乐部成员;包含了78条边,代表他们之间的人际关系。由于突发的原因,俱乐部管理者与俱乐部主要教师之间针对是否提高收费这一问题产生了激烈的争论,并最终导致俱乐部分裂成两部分。图4为空手道俱乐部网,其中方形顶点代表归于俱乐部管理者(1号顶点)的成员,圆形顶点代表归于俱乐部主要教师(33号顶点)的成员。

科学家合作网:科学家之间合作的表现方式是广泛的,如文章的合作、引用、致谢。这里介绍3

[26]

个科学家合作网:1)物理学家合作网,它是收集了arxiv.org网上的关注于物理研究的科学家的文章,并据此构建的科学家合作网。其中顶点表示发表过文章的科学家,如果两位科学家共同发表过文章就将他们用边连接起来;2)桑塔菲研究所科学家合作网,是收集了1999年、2000年研究所内271位科学家的合作情况构建的网络,其

[12]

图4　空手道俱乐部人际关系[25]

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学·24·2008年9月

中的顶点是桑塔菲研究所内的科学家,如果他们合作发表过文章,就将他们用边连接起来;3)经济物理学家

[27]

合作网,收集了经济物理学主页(www.econophysics.org)上发表的文章、PhysicaA发表的经济物理学文章、ISI(www.isi.knowledge.com)上发表的文章,根据文章的合作、引用、致谢建立经济物理学者之间的关系。

[12]

类似的还有根据美国大学橄榄球队2000年一个赛季的赛程建立的网络,其中顶点代表大学的橄榄球队,共有115支大学橄榄球队,连边表示两队之间进行了常规赛,这一赛季共包含616场常规赛;根据Linda

[28]

Wolfe收集的猴子3个月的活动数据,通过猴子之间相互刷毛的关系抽象出的网络,其中16个顶点代表16只猴子,若两只猴子相互刷毛则用边连接起来,共有69条边。在这些实际网络中,除了空手道俱乐部网和美国大学橄榄球比赛网有可以判断划分准确性的已知社团结构,其他网络并没有这样的标准,因此用来判断划分方法优劣的标准是划分结果是否具有可解释性。虽然这样的判断标准是不严谨的,然而社团结构划分的主要对象正是这样未知结果的网络,因此结果更具解释性的划分算法更有价值。3.4　划分结果的比较方法

不同的算法往往会将同一网络划分出不同的社团结构。对于社团结构已知的网络,划分结果与网络真实社团的比较可以得到划分方法的准确性;对于社团结构未知的网络,多种划分方法所得结果间的比较同样可以加深对各种算法的理解及对网络的了解。划分结果的比较方法主要有3种。

[12]

3.4.1　正确划分率比较法

这种方法多用在社团结构已知的网络研究中,比较对象是划分得到的社团结构与网络实际的社团结构。具体方法是在划分得到的所有社团中,找到能够被真实社团结构中的任一社团所包含的规模最大的社团。并以此社团为标准,顶点数超过此标准的社团中的顶点都被视为错误划分了,小于此标准的社团,则只将不在真实社团中的顶点视为错误划分。以128个顶点的人造经典网为例,如果划分得到的3个社团,其中两个社团与真实的社团完全相同,第3个社团由另外两个真实社团组成,则正确划分的比例是50%。这种方法过于严厉,会将一些人们主观认为被正确划分的顶点归于错误划分。然而,这种比较方法的应用十分广泛,大多数研究者在研究经典人造网时使用它。3.4.2　共同信息比较法

[29]

DanonL等人将文献[30-31]介绍的标准共同信息的衡量引入到社团结构的比较中来,并认为这种方法较之3.4.1中介绍的方法更具判别力。具体过程为:首先定义一个混乱矩阵N,其中行为真实的社团,列为划分得出的社团。矩阵N中的元素Nij为既在真实社团i中出现又在划分出的社团j中出现的顶点的个数。基于信息理论得到的两种社团结构A,B的相似程度为

-2

I(A,B)=

66

i=1

cAcB

Nijlog+

j=1

NijNNi.N.jN.jlogN.jN6

cA

Ni.logi=1

Ni.N6

cB

j=1

其中,真实社团的个数用cA表示,划分所得结果中的社团个数用cB表示,Ni.为Nij的第i行的加总,N.j为Nij的第j列的加总。

如果划分结果与真实的社团结构完全一致,则I(A,B)达到最大值1;当划分结果与真实社团结构没有任何重叠时I(A,B)达到最小值0。可见,I(A,B)值越大说明社团划分的准确性越高。采用这种比较方法衡量3.3节中提到的人造网的例子,得到划分的正确率为01858,比原来的结果更加符合人们的感受。3.4.3　D函数比较法

[32]

两种划分结果差异性可以分解成社团对之间差异的总和,D函数法就是采用这一思路讨论两种划分结果间的差异性。划分得到的社团可以视为集合,网络划分的结果就是一组集合,社团间的差异表现为集合中的不同元素。设A,B是任意两个集合,定义A∩B为两个集合的相似度,而(A∩B)∪(A∩B)(A和B的全空间是A∪B)是两个集合的相异度。从而,集合A,B标准化后的相似度(s)和相异度(d)为

第5卷第3期　　李晓佳,等:复杂网络中的社团结构·25·

s=d=

A∩BA∪B

(A∩B)∪(A∩B)A∪B

两种划分结果就是两组不同的社团,对它们进行比较时有多种配对的方法,这里采用的比较规则为:1)建立不同划分得到的两组社团之间的匹配关系:将两个集合组中的集合进行对比,相似度最大的两个集合组成一对,然后根据相似度排序把各个集合配对。若两组集合所包含的集合数目不相等,则多出的集合与空集配对。

2)根据配对,计算每对集合的相异度。

3)综合每对集合的相异性,得到两种划分的相异度的数值:

D=

6dXYk

其中,XY为配对的集合,k为集合对的总数。

D函数的取值范围是[0,1],取值为1表示两种划分完全不同,取值为0表示两种划分完全相同,可见取值越大说明两种划分之间的差异越大。用这种方法考察上述两小节中的例子,得到两种划分的相似度或者说划分的正确率为01625,介于前两种指标之间。

4　社团划分的具体算法

随着关注网络社团结构问题的科研工作者不断增加,众多划分网络社团结构的算法被设计出来。根据不同的标准,这些算法可以被分成不同的种类。例如:根据第3节提到的社团结构的形成过程,算法可以分为凝聚算法、分裂算法,搜索算法及其他算法4大类。从算法的物理背景上考虑,又可以将其分为基于网络拓扑结构的算法,基于网络动力学的算法,基于Q函数优化的算法及其他算法。在本节中将根据这一分类,对其中的几种算法分别予以具体介绍。4.1　基于网络拓扑结构的算法

这类算法的特点在于关注网络连通形成的拓扑结构,并应用拓扑结构的特性刻画顶点和连边,划分网络中的社团。应用这类算法时往往并不需要额外的信息。4.1.1　谱分析思想的算法

[33-34]

谱分析早在20世纪70年代就已经有所发展,到90年代变得普及。它的主要思想是通过对连接矩

[35]

阵形成的拉普拉斯矩阵或标准矩阵的特征值、特征向量的分析,挖掘网络中的社团结构。以标准矩阵的分

[36]-1

析为例,具体介绍这种算法。所谓标准矩阵N,是由网络的连接矩阵A和一个对角矩阵的逆矩阵K构成的,N=KA。对角矩阵K中的元素是每个顶点的度值kii=

-1

6

S

aij,S为网络中顶点的个数。由于标准矩阵行

j=1

的标准化,标准矩阵总有最大的特征值等于1,以及与之对应的特征向量(1,1,1……)。在对社团化明显的网络如图5的分析中发现,如果网络自然呈现m个社团,则标准矩阵N就有m-1个十分接近1的特征值,而其余的特征值则有较大的距离。这m-1个特征值中,最大的特征值所对应的特征向量有一个特性:在同一个社团中的顶点所对应的值较为接近。因此,特征向量元素的值呈现阶梯状分布,如图6所示,并且阶梯的级数与社团的个数相匹配。

这种方法对社团结构比较清晰的网络十分有效,然而实际网络的社团结构往往并非这般显著。在由众多顶点构成的连接混乱的网络中,社团间的过渡是平滑的,第一大非平庸特征值对应的特征向量中的元素没有呈现明显的阶梯状分布,取而代之的是几乎光滑的曲线。可见,仅仅参考这一指标无法进行社团结构的划分。因此需要对上述方法进行拓展,使之适用范围更广。

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学·26·2008年9月

谱分析法根据特征值、特征向量对顶点进行划分的过程可以理解为:依据特征值设立众多的标准,并根据这些标准对顶点进行划分。根据平庸特征值1,无法对顶点做出任何的区分;对于社团结构明显的网络,只需要采用最大的非平庸特征值,就可对顶点进行划分,而对于混乱的网络仅用这一个标准无法实现。划分混乱的网络,需要综合考虑多个标准,即同时考虑多个特征值对应的特征向量。其依据是同属一个社团的顶点在各个标准上都更为相近。通过对两个顶点在各个标准下取值的综合考察,得到它们的紧密程度,用以表明它们同属于一个社团的倾向

[36]

。i,j两顶点间的紧密程度表示为rij=〈xixj〉-〈xi〉〈xj〉

2222

[(〈xi〉-〈xi〉)(〈xj〉-〈xj〉)]

其中,〈xi〉为几个较大的特征值所对应的特征向量中顶点i对应的元素的平均值。虽然多考虑一些特征值会使精确性有所提高,但是由于过多的特征值和特征向量的计算会大大提高计算量。

同样的方法也可以对拉普拉斯矩阵进行分析。差别在于,拉普拉斯矩阵总存在平庸的特征值0,考察的标准是大于0的最小的特征值及其对应的特征向量。

这类方法对于社团结构显著的网络是高效的,然而对于规模大连接混乱的网络却没有明显的优势。因为对于大规模的网络而言,求特征值和特征向量的计算相当复杂耗时。并且即便得到两顶点间的紧密程度rij,也需要人为的设定标准,判断它们是否归为一类。从而,使得划分的结果在很大程度上受到了人为因素的影响。

4.1.2　层次聚类算法

层次聚类法在社会科学中被广泛应用

[37-38]

,其核心思想是:由距离最近、相似度最高的社团开始合并,

直到所有元素都归于一个社团为止。可见这算法的核心在于对距离及相似度的定义。针对复杂网络社团划分

问题,已有一些距离和相似度的定义。点与点之间的距离可以定义为两点间的最短路径,它们的相似度定义为最短路径的倒数。这样最短路径近的顶点相似度较高,最短路径远的顶点相似度较低。一种较为科学的方法则是用结构等价的程度来衡量两顶点的相似度。结构等价的概念在1971年由Lorrain和White引入社会网络。如果一个顶点与网络中其余顶点的连接方式和另一顶点与网络中其余顶点的连接方式完全相同,则这两个顶点结构等价。例如在人际关系网中,如果两个人的朋友完全相同,则这两个人结构等价。Burt首次引入欧几里德距离衡量结构等价,顶点i,j之间的欧几里德距离为

Dij=

S

k=1,k≠i,j

6

(aik-ajk)

2

其中,aik为连接矩阵中的元素,表示顶点i与顶点k的连接状况。如果i,j两点结构完全等价,则它们的连接矩阵完全相同,所以它们的距离Dij等于0。网络中的每一对顶点都可以计算出距离,然后按照凝聚思想划分社团结构。首先选择距离最小的归为一个社团,在进一步的凝聚过程中,由于每个社团所包含的元素不再唯一,

第5卷第3期　　李晓佳,等:复杂网络中的社团结构·27·

因此要定义包含多个元素的社团间的距离。常用的方法有3种:1)最短距离法,两个社团的距离等于两个社

团间所有顶点对的距离中最短的值;2)最长距离法,两个社团的距离等于两个社团间所有顶点对的距离中最长的值;3)平均距离法,两个社团的距离等于两个社团间所有顶点对距离的平均值。任意选取一种定义将凝聚步骤进行下去都可以将网络中顶点间的关系用树状图表示出来,并且可以通过Q函数确定最优的社团划分。4.1.3　GN算法

。

由网络中社团的定义可知,所谓社团就是指其内部顶点的连接稠密,而与其他社团内的顶点连接稀疏。这就意味着社团与社团之间联系的通道比较少,从一个社团到另一个社团至少要通过这些通道中的一条。如果能找到这些重要的通道,并将它们移除,那么网络就自然而然地分出了社团。Girvan和Newman提出用边介数

Girvan和Newman提出的分裂算法已经成为探索网络社团结构的一种经典算法,简称GN算法

[12,22,25]

来标记每条边对网络连通性的影响。某条边的边介数是指网络中通过这条边的最短路径的数目。两顶点间的最短路径在无权网中为连接该顶点对的边数最少的路径。由此定义可知,社团间连边的边介数比较大,因为社团间顶点对的最短路径必然通过它们;而社团内部边的边介数则比较小。这种算法的具体过程是:1)计算网络中各条边的边介数;2)找出边介数最大的边,并将它移除(如果最大边介数的边不唯一,那么既可以随机挑选一条边断开也可以将这些边同时断开);3)重新计算网络中剩余各条边的边介数;4)重复第2)、3)步,直到网络中所有的边都被移除。

算法中包括了重复计算边介数值的环节是十分必要的。因为当断开边介数值最大边后,网络结构发生了变化,原有的数值已经不能代表断边后网络的结构,各条边的边介数需要重新计算。举一个形象的例子:假如网络中有两个社团,它们之间只有两条边相连。起初其中一条边的边介数最大,而另外一条边介数较小,则第一条边被断开。如果不重新计算各条边的边介数,那么第二条边依据其原有边介数值可能不会被立即断开。如果重现计算各条边的边介数,那么第二条边的边介数可能成为最大值,会被立即断开。这显然会对社团结构的划分产生重大的影响。

GN算法分析网络的整个过程也可以用树状图表示,网络的最优划分要通过Q函数进行判断。对于由n个顶点m条边构成的网络,按照广度优先的法则,计算某个顶点到其他所有顶点的最短路径对网络中每条边边介数的贡献最多耗时O(m),由于网络中共有n个顶点,所以计算网络中每条边的边介数总共耗时O(m),又因为每次断边后需要重新计算每条边的边介数,因此总体上讲这种算法的复杂度为O(nm);

3

对于稀疏网,算法的复杂度为O(n)。复杂度较高是GN算法的显著缺点。

应用GN算法分析人造经典网络,得到的结果如图9所示。当Zout小于等于6时,有90%以上的顶点被正确划分;Zout继续增加时,正确划分的比例迅速下降,当Zout等于8时,正确划分的比较仅为30%左右。所以GN算法不适用于较为混乱的网络。对空手道俱乐部人际关系网的划分,GN算法的准确率很高,仅有标号为3的顶点被划分到错误的社团。结果的树状图及与之对应的Q函数变化如图7所示。用GN算法对物理学家合作网的最大连通社团进行研究。科学家之间的合作关系如图8a所示,其中每一个矩形代表一位科学家。分析的结

图7　GN算法得到的空手道俱乐部社团结构划

分的树状图及对应的模块化函数值[25]

2

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学·28·2008年9月

果是:当网络划分成13个社团时,Q=0172±0102为峰值。用图8b形象地表示出来,其中圆形代表社团,圆形的大小代表包含的科学家的多少;连边表示社团间的合作关系,边的粗细代表合作的密切程度。划分出的社团具有可解释性,如处于中心位置的社团所包含的科学家基本来自西欧国家。

　　矩形表示科学家,连边表示合作关系圆形代表社团,圆形的大小代表包含的科学家的多少;连边表示社团间的合作关系,边的粗细代表合作的密切程度　　a网络示意图b社团划分结果

图8　科学家合作关系网[25]

4.1.4　边集聚系数法GN算法的核心概念最短路径边介数由网络的全局结构决定,Radicchi等人提出基于网络局部结构的边

集聚系数的定义

[18]

,并以此寻找社团间的连边。一条边的边集聚系数定义为网络中包含该边的实际三角形

数目与包括该边的所有三角形的数目之比。其中包含该边的所有三角形包括实际三角形和潜在三角形。i,j两顶点间连边的边集聚系数为

C

()

(3)

i,j

zi,j

=

min[(ki-1),(kj-1)]

(3)

3

其中,zi,j为包含该边的实际三角形个数,min[(ki-1),(kj-1)]为包含该边的所有三角形数目。由于社团

内部顶点间的连接比较稠密,所以处于社团内部的连边被较多的实际三角形所包含;而社团间的连边被较少的实际三角形包含,甚至不被任何实际三角形包含。因此根据边集聚系数可以挖掘网络中社团间的连边。然而当包含某边的实际三角形个数zi,j=0时,无论构成这条边的两个顶点的度ki,kj为何值,Ci,j都等于0,无法反映出结构的差异。为克服这一缺陷,对原式做微小的调整:

C

(3)

i,j

(3)

(3)

zi,j+1

=

min[(ki-1),(kj-1)]

(3)

边集聚系数的定义可以进一步推广到更大的环,如考虑网络中的四边形、五边形……,从而边集聚系数的通式为

C

(g)

(g)

i,j

=

zi,j

(g)

+1

(g)i,j

(g)

s

其中,g为研究包含边的g边形,zi,j为包含该边的实际g边形的个数,si,j为包含该边的所有g边形个数。

算法的具体过程为:1)确定研究环的种类(三角形、四边形……);2)根据定义计算每条边的边集聚系数,断开边集聚系数最小的边;3)重复计算和断边的操作,直到网络中所有的边都被断开为止。该算法的复

2

杂度大致为O(m),比GN算法有显著的降低。然而,这种方法的局限在于只能分析包含环的网络。以三角形

第5卷第3期　　李晓佳,等:复杂网络中的社团结构·29·

为例:该方法对于包含三角形较多的社会网络有着良好的效果,但对于非社会网的效果则较差。

4.1.5　信息集中性算法

[39-40]

Latora,Marchion等为方便分析非连通图的通讯效率提出了信息效率的概念。并进一步提出了信

[41]

息集中性的概念,用以衡量网络中边的重要性。网络中两顶点i,j之间信息传递的效率εij等于它们最短路径dij的倒数。整个网络的信息传递效率E[G]等于所有顶点对信息传递效率的平均值:

E[G]=

i≠j∈G

6

εij

=

1n(n-1)n(n-1)i≠j∈Gdij

6

1其中,G为整个网络,n为网络中顶点的数目。若顶点i,j之间不连通,即dij=+∞,则它们之间的信息传递效率等于0。网络边k的信息集中性定义为由于k边的移除导致的网络整体信息传递效率的相对变化:

E[G]-E[G′ΔEk]

Ck==,k=1,…,m

E

E[G]

其中,m为网络中包含的边的数目,G′Fortunato将这k为将G网中k边移除后形成的包含m-1条边的新网。些概念引入到划分社团结构的问题之中。信息集中性越高的边对网络连通性的影响越大,而社团间的连

边往往对网络的连通性有着重要的影响,因此考虑使用信息集中性探索网络中社团间的连边。算法的具体过程为:首先计算每条边的信息集中性;然后将信息集中性最高的边移除;重新计算网络的信息传递效率;重复以上的过程直到网络中所有的边都被断开为止;最终使用Q函数判断最优的社团结构划分。

应用这种算法分析经典人造网,得到的结果如图9所示,表明该算法适用的网络的混乱程度与GN算法所能适用的网络的混乱程度相当,只有微小的优势。然而对于众多实际网络,该算法的分析结果并不令人满意。问题在于总是在划分初期就产生孤立的顶点,致使得到的社团结构与实际情况的拟合程度不高或结果的可解释性不强。例如:对空手道俱乐部网络,该算法首先分离出两个由单点构成的社团。通过分析发现,最先被分离的孤立点通常处于网络的边缘如图10中的k点,因为当网络没有明显社团结构时,移除与该点相连的边会导致网络传递效率的较大变化,分析结果树状图如图11。信息集中性算法有这一显著缺陷,并且它的复

4

杂度较高为O(n),所以较之其他算法它没有显著的优势。

[42]

4.2　基于网络动力学的算法4.2.1　Potts模型算法

JorgReichardt和StefanBornholdt将物理学的Potts模型引入到确定网络社团最优划分的问题之

中

[43-44]

。网络中的顶点与模型中的粒子相对应,并对模型的哈密顿量进行修正。当修正后的哈密顿量处于基

态时,具有相同自旋值的粒子归为一个社团,从而得到网络的最优划分。可见,问题的关键在于根据划分社团结构这一目标,修正哈密顿量。修正的依据是网络社团内部连接稠密,社团间连接稀疏的性质。因此得出4项

标准:1)对连接社团内部顶点的边进行奖励;2)对社团内部可以连接却没有连接的边进行处罚;3)对连接

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学·30·2008年9月

社团间顶点的边进行处罚;4)对社团间可以连接却没有连接的边进行奖励。由这4项标准得到的修正哈密顿量为

H({σ})=-+

66

aijAijδ(σi,σj)+

internallinks

i≠j

6

bij(1-Aij)δ(σi,σj)　　　　　　internalnonlinks

i≠j

cijAij[1-δ(σi,σj)]-externallinks

i≠j

6

dij(1-Aij)[1-δ(σi,σj)]externalnonlinks

i≠j

其中,i,j为网络中的任意两个顶点;Aij为连接矩阵中的元素,如果i,j两点有边相连则Aij=1,否则等于0;σi,σj在原模型中表示粒子的自旋值,在这里表示i,j顶点所属的社团的编号;δ为一函数,当σi=σj即i,j两顶点属于一个社团时,δ(σi,σj)=1,否则等于0;

aij,bij,cij,dij分别为奖励和惩罚的力度。值得指出的

是,因为目标是使得哈密顿量最小,所以这里奖励的部分为负号,惩罚的部分为正号。以表达式中的第一项为例:如果顶点i,j属于同一社团即δ(σi,σj)=1,且它们之间有边相连即Aij=1,则以aij的力度进行奖励,遍历所有不同的顶点对并取和,从而得到由于社团内顶点相连对哈密顿量的贡献。如果两顶点间是否有边相连对哈密顿量影响力度相同,那么有aij=cij,bij=dij,从而将4个参量压缩成2个。进一步,需要找出一个适当的参量将aij,bij共同表示出来。一个显见的参数为pij,它为顶点i,j间存在边的可能性。从而aij,bij可以表达为aij=1-γpij,bij=γpij,其中γ为aij,bij对pij的依赖程度。用顶点间存在边的可能性作为参数是合理的,例如:若i,j两顶点间存在边的可能性pij比较小,则

图11　信息集中性算法得到的空手道俱乐部社团结

构划分的树状图及对应的模块化函数值[42]

aij比较大,当i,j间存在边时,得到的奖励就比较大。进而,修正后的哈密顿量表示为:H({σ})=-

6

(Aij-

i≠j

γpij)δ(σi,σj)。使得哈密顿量最小的网络社团划分是最优划分。

两顶点间存在边的可能性可以在应用时自行选择,常用的取法有两种。第一种方法是选择一个固定p值,即任意两顶点i,j之间存在边的可能性pij都等于p,这是最简便的方法。第二种方法要考虑网络的分布,若两顶点的度值都比较大,则它们之间存在连边的可能性就比较大,即任意两顶点i,j之间存在边的可能性表示为pij=

kikj

,其中ki,kj分别为顶点i,j的度值,M为网络中的总边数。2M

确定目标函数后,可以采用模拟退火算法进行搜索。假设网络中的顶点初始有q种自旋态,该算法的具体过程为:

1)给定系统一个初始温度,网络中每个顶点都被赋予一个从q个自旋态中随机选择的状态。2)随机挑选一个顶点改变它的自旋态。

3)如果新状态产生的系统修正的哈密顿量的变化值ΔH=Hnew-Hold<0,那么该顶点就接受这个新的

ΔH),也接受这个新的自自旋态;如果ΔH=Hnew-Hold>0,则在(0,1)间随机选择一个数ε,若ε1T

,否则保持原有状态。

4)回到第2)步,遍历网络中的所有顶点。

5)降低系统温度,重复以上所有操作。当系统温度接近0时,停止计算。根据此时每个顶点所处的自旋

第5卷第3期　　李晓佳,等:复杂网络中的社团结构·31·

态,对它们进行社团划分。

这种算法的复杂度与计算停止的温度有密切的关系。

在文献[44]中,JorgReichardt和StefanBornholdt指出,采用第2种p的选择方式并且令γ=1时,哈密顿量与Q函数有负相关关系:Q=-4.2.2　随机行走

1M

H({σ})。此时最小化哈密顿量与最大化Q函数值是等价的。

随机行走算法建立在层次算法之上,其特别之处在于用随机行走粒子的跃迁行为定义顶点间的距离

[45-47]

。假设网络上有一个可以任意跳跃到其邻居位置上的粒子,它每一步跳跃都只与其当时所处的位置

Aij

,其中Aij为连接矩阵中的元素,d(i)为顶点i的度。从而得到顶点间的一步转移概率d(i)

t

t

有关,而与之前的状态没有关系,即一系列跳跃形成一个马尔科夫链。在每一步中,由顶点i跳跃到其邻居顶点j的概率为Pij=

矩阵P。由顶点间的一步转移概率矩阵可以得出顶点间的t步转移概率矩阵P,其中的元素Pij为由顶点i通过t步转移到顶点j的概率。这里的顶点j可以是网络中的任何顶点,不局限于顶点i的邻居顶点。如果两个顶点同属于一个社团,那么分别从两个顶点透视整个网络得到的结果应该相近,即如果顶点i和顶点j在同一社团,则对于任意顶点k有P󰂕P。两顶点结构等价的程度由距离rij衡量,rij=t

ik

tjk

t

Sk=1t

6(Pik-Pjk)

。因为这

d(k)

tt2

个值依赖t的取值,所以也可以表示成rij。t值的选取不宜过大,因为当t趋于无穷时Pij只与顶点j的度有关,而与顶点i无关。应用这种距离也可以将网络梳理成树状图的形式,并应用Q函数得到最优的社团结构。4.2.3　电流算法

F.Wu和B.A.Huberman将网络类比成电路,形成一种算法

[48]

。其主要思想是:将网络中的边视为阻值

相等的电阻,在两顶点i,j上施加一个固定的电压,比如顶点i的电势为1,顶点j的电势为0,从而整个网络就成为了一个电路,每个顶点上都会有相应的电势值,进而按照电势值划分顶点的社团。同属一个社团的顶点,其电势值应当比较接近,而与其他社团顶点的电势值相差较多。

顶点电势的计算应用基尔霍夫等式,它是指流入顶点的电流净值为0。若顶点i有n个与它相连的顶点,则根据基尔霍夫等式,流入i点的净电流为

k=1

6

n

Ik=

k=1

6

n

Vk-Vi

R

=0

其中,Ik为由顶点k流向顶点i的电流,Vk为顶点k的电势,R为每条边的阻值。从而顶点i的电势可以表示为

Vi=

1n

k=1

6

n

Vk。即每一顶点的电势等于其所有邻居的电势的平均值。

一般的想法是用谱分析法计算各个顶点的电势值,然而这种方法消耗的时间比较长。F.Wu和B.A.Huberman推荐了一种复杂度为线性的算法。在拥有N个顶点的网络中,首先将i,j两点的电势设定,如Vi=1,Vj=0,其余顶点的电势也赋予初始值0;然后按照上式更新除i,j外每个顶点的电势,称这一过程为一轮;

多次重复这一过程,在一定精度上可以得到电势值的稳定解。其精确度并不取决于网络的规模,而是由重复的次数决定的。得到每个顶点的电势值后,通过设立划分标准,得到顶点的社团归属。通常选择基本将顶点等分的电势值最大跳跃处作为两社团的划分标准。

因为i,j两点分别被赋予1,0两个电势值,其他顶点的电势则介于1和0之间,这就意味着i,j两点一定不会在同一社团当中。在不了解网络的前提下,如何确定两个不在同一社团中的顶点,成为需要解决的问题。在同一社团中由于连接稠密,所以两点之间的距离通常比较近,而社团间顶点的距离相对比较远。因此距离越大的顶点属于不同社团的可能性越大。根据这一特点,只需找出距离相对较远的顶点施加电压就基本上可以保证算法的正确性。通过统计发现,只要不选择相邻的两个顶点,社团划分的正确率便会大大提高。因此,另一种解决方法便是对比多次排除相邻两点的随机选择电极得到的社团划分的结果,确定顶点的归属,进而

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学·32·2008年9月

划分网络社团。

这种算法虽然可以推广到多个社团的划分,然而更适合于网络两社团的划分问题。F.Wu和B.A.Huberman将这一算法运用到空手道俱乐部网,第1次将电极安放于顶点1和顶点34处,第2次将电极安放在顶点16和顶点17处,第3次将电极安放顶点12和顶点26处,第4次将电极安放在顶点32和顶点33处。得到的结果如图12所示,可见第1,2,3次当电极安放在不同社团的顶点间时,划分的结果很好;而第4次将电极安放在同一社团的顶点之间,社团没有被正确划分。4.3　优化Q函数算法4.3.1　Newman贪婪算法

[49]

这类算法的共同之处在于都是以最大化Q函数值为目标,区别在于最大化的途径不同。Newman贪婪算法的过程为:

1)初始时将网络中的每1个顶点都视为1个社团,每个社团内只有1个顶点。即如果网络中共有n个顶点,则初始有n个社团。

2)两两合并社团,并计算社团合并所产生的Q值的变化量:

ΔQ=eij+eji-2aiaj=2(eij-aiaj)选择使得Q值增加最大(或减少最小)的方式进行合并。需要指出的是,如果两个社团间不存在任何连边,那么它们的合并不能对Q值产生正向的影响。因此在计算Q值变化时,只需考虑存在连边的社团对。当网络中包含m条边时,这步算法的复

　　　线状虚线和点状虚线表示顶点的实际社团属性,杂度为O(m)。社团合并后必然对e矩阵产生影响

　　　实线表示按照顶点基本等分电压最大跳跃处社团的划分值(e矩阵的含义参见Q函数的第2种表达式),因此

　　图12　电流算法分析空手道俱乐部网[48]

将合并的两个社团所对应的行和列相加,对eij进行更新。这一步的复杂度为O(n)。因此这一步最多耗时O(m=n)。

3)重复步骤2)的操作,不断对社团进行合并,直到所有顶点被凝聚到一个社团中为止。这样的操作最

多进行n-1次。

2

因此,这种算法总体的复杂度为O((m+n)n),对于稀疏网则为O(n)。这种方法将网络中的社团用树状图的形式表现,使得Q函数值最大的社团划分方式就是网络的最优划分。这种方法可以直接推广到加权网的分析,只需在初始对eij赋值时用权重替代无权网中的0、1赋值,并且这种推广不会改变算法的复杂度。

应用Newman贪婪算法分析人造经典网络,即2.3小节介绍的包含128个顶点的网络。随着Zout值逐渐增大,顶点被正确划分的比例在不断减少,如图13所示。图13中横坐标为Zout值,纵坐标为被正确划分的顶点的比例。当Zout比较小时顶点的划分完全正确,即便当Zout=6时,顶点被正确划分的比例也大于90%。但当Zout=8即顶点有一半的边与社团外的顶点相连时,正确划分的比例很低,所以这种方法不适宜过于混乱的网络。

应用Newman贪婪算法分析空手道俱乐部网,Q函数的峰值为01381,其对应的网络树状图为图14。它将网络平均分成两个社团,每个社团包含17个成员,除10号成员被划分错误外,其他所有成员的划分都与实际结果相同。

这种方法的突出优势在于复杂度较低,因此适用于规模较大的网络。已经用它对包含5万多个顶点的物理学家合作网进行了分析。在相同硬件设备上,这种算法所消耗的时间显著少于GN算法所消耗的时间。Q函数的峰值为01713,对应的结果包含600余个社团。其中有4个大社团,它们包含的顶点占所用顶点的77%,

第5卷第3期　　李晓佳,等:复杂网络中的社团结构·33·

并且这4个社团具有良好的解释性,它们与研究领域有着密切的联系,一个社团对应天体物理学,一个社团

对应高能物理学,两个社团对应凝聚态物理学。

图13　贪婪算法和GN算法

划分正确率检验图[49]

图14　贪婪算法划分空手道俱　　　　　　

乐部网络的树状图[49]

4.3.2　改进的贪婪算法

Clauset等人对Newman的贪婪算法进行了改进

2

[72]

,采用堆的数据结构来存储和运算Q函数,使得算法

的复杂度进一步降低为O(nlogn),接近线性复杂度。Clauset贪婪算法的核心是建立了存储模块化增加量的矩阵ΔQ,通过对这个矩阵元素的更新得到Q值最大的社团划分方式。由于合并没有边相连的社团不会产生Q值的正向变化,因此只需要存储有边相连的社团的信息,这样既节省了存储空间又缩短了运算时间。这种算法应用到3种数据结构:1)存储模块化增加量的稀疏矩阵ΔQ,其中的元素只包含存在边相连的社团对。并且矩阵的每一行都以平衡二叉树的方式存储;2)最大堆H,其中储存了ΔQ矩阵中每一行的最大元素,以及这个元素对应的两个社团的编号;3)一个辅助向量a。

方法的具体过程:

1)将网络中的每一个顶点都视为一个社团。在这种前提下,如果顶点i,j有边相连则eij=1/2m(m为网络中边的数目),否则为0;而ai=ki/2m。初始化ΔQ矩阵:

ΔQij=1/2m-kikj/(2m)0

2

如果i,j间有边相连

其他

由初始化的ΔQ矩阵可以得到每行的最大元素,从而构成最大堆H。

2)最大堆H中找出最大的ΔQij,合并与之对应的社团i,j,合并后的社团标记为j。更新矩阵ΔQ、最大堆

H、及辅助向量a,具体方法为:

(1)对于矩阵ΔQ,移除第i行和第j列,更新第j行和第i列的元素:如果社团k与社团i,j都相连,则

ΔQ′ΔQik+ΔQjk;如果社团k只与社团i相连而与社团j不相连,则ΔQj′Qik-2ajak;如果社团k只与社jk=k=Δ团j相连而与社团i不相连,则ΔQ′Qjk-2aiak。jk=Δ

(2)根据更新后的ΔQ′,更新最大堆H。

(3)辅助向量a的更新:a′j=aj+ai　ai=0。

3)重复2),直到所有的顶点都归为一个社团为止。

这种计算过程使得Q函数有唯一的峰值,因为当最大的Q值增量成为负值后,所有的Q值增量便都为负值,Q函数的值只能逐渐减小。由此可知,只要最大的ΔQij由正值变成负值,就不需要再继续合并社团。因为此时的Q函数值最大,所以其对应的社团划分就是最优的划分方式。

这种贪婪算法比Newman贪婪算法在复杂度方面有显著的降低,因此适用范围进一步拓宽,可以分析规模更为巨大的网络。应用这种方法分析包含40多万个顶点200多万条边的由Amazon.com网上书店网页连

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学·34·2008年9月

接关系构成的网络,得到的结果具有良好的解释性。4.3.3　极值优化算法

[50]

极值优化算法的思想类似于生物系统演化中的断续平衡问题,之后用于离散和连续的NPC问[51-52]题,解决如图分割,伊辛模型,原子最优团簇结构等问题。Duch和Arenas将该思想引入网络社团结构

[53]

划分问题当中,以最大化Q函数为目标,判断网络中的连边是否被断开。首先定义极值优化算法中的局部变量,它被定义为在一种社团划分下顶点i对总体Q函数值的贡献,表达式为

qi=κr(i)-kiar(i)

其中,κr(i)为社团r中的顶点i与社团r内的顶点构成连边的数目,ki为顶点i的度,ar(i)为至少一端在顶点i所属的r社团中的边的比例。若用m表示网络中的总边数,则全局变量Q与局部变量qi的关系为Q=

(1/2m)

6

i

qi。因为Q函数的取值范围为[-1,1],所以对qi进行标准化,使其取值范围与Q函数相同,从而

得到更为合理的变量,表示顶点i对Q函数的贡献:

λi=

qiki

=

κr(i)

ki

-ar(i)

λi越大表明顶点i对Q函数的贡献越大,λi越小表明顶点i对Q函数的贡献越小。针对最大化Q函数这一目标而言,λi也反映出顶点i归于r社团的适合性,λi值小说明顶点被归于r社团不太合适。根据这一理解,极值优化算法的具体过程为:

1)任意将网络中的顶点分成等大的两部分,每部分中相互连通的顶点形成一个社团,从而形成一个初始的社团结构。如图15a分别用圆圈和方形代表随机分成的两部分,图15b表示这种任意等分得到的初始社团结构,其中一种灰度代表一个社团。可见,初始的等分并不将网络划分成等大的两个社团。

2)根据社团结构计算每个顶点的适合度λi,并将适合度最低的顶点归入另外一部份中去(如从初始的圆圈变为方形),这可能使得社团结构发生巨大的变化。计算新社团结构的Q函数值,并按照新的社团结构重新计算每个顶点的适合度。

3)重复2)过程,直到得到最大的Q函数值为止。断开两部分之间的所有连边,从而将网络划分成了两个社团,即由圆圈和方形代表的两个社团,如图15c中的左图。

4)对得到的社团递归地重复上述1)～3)操作,当Q函数值不能被进一步增大时,就得到了网络社团的最优划分。如图15c所示,逐步将网络划分成4个社团。

　　　　　　图15　EO算法的划分过程示意图[53]　　图16　EO算法和GN算法划分正确率检验图[53]

上述方法可能导致搜索陷入局部极值,因此用τ-EO方法进行改进。每个顶点被选到的概率为:P(q)∝-τq。其中q值为顶点按照适合度排列的序号,τ～1+1/ln(N)与网络的规模有关。

本方法的基本思想是:逐步达到最优划分。首先以将网络划分成两个社团为目标,并以顶点的适合度值判别需要调整的顶点,通过调整顶点的属性,达到将网络划分成两个社团的最优划分;再逐步增加社团数目,

第5卷第3期　　李晓佳,等:复杂网络中的社团结构·35·

并分别达到对应社团数的最优划分;直到Q值不能被进一步提高为止,便确定了最优社团数目及对应的划分方法。

应用极值优化算法对经典人造网进行分析,顶点划分正确率与Zout取值的关系如图16所示。当Zout小于等于6时,顶点划分的正确率都为100%;当Zout等于8时,划分的正确率仍有80%;但Zout进一步增大时,划分的正确率迅速下降,当Zout等于10时,正确率仅为40%。由此可知,若社团间的连边平均占所有连边50%或以下,极值优化算法都能较好地进行分析,说明此算法也适用于混乱的网络。这种算法的复杂度为

O(nlogn)。推广到加权网时,只需相应调整成加权网中的Q函数。

2

4.4　其他算法

有些研究者对已有的算法进行适当的综合,提出了一些新的算法,例如:Newman将Q函数与谱分析算法相结合

[54-55]

。JosepMP等人将随机行走思想、贪婪算法和Q函数相结合

[57]

[59]

[56]

,张世华等人将谱分析法、模糊

[58]

聚类法和Q函数相结合等等;有的学者通过网络演化的思想对社团结构进行分析

;有的学者则通过视

[60-61]

觉大致分析网络社团结构。另外,有些研究者通过挖掘网络的局部信息,划分社团结构。这种算法可

以运用于网络全局信息无法得到的问题,且得到的结果与基于全局信息的方法相近。下面具体介绍Newman提出的综合法及ClausetA提出的基于局部信息的方法。4.4.1　Q函数与谱分析算法的结合

Newman将Q函数与谱分析算法相结合,建立Q函数矩阵并根据Q函数矩阵的特征值特征问题的解划分网络中的社团。

假设含有n个顶点的网络包含两个社团,如果顶点i属于第一个社团,则si=1,如顶点i属于第二个社团,则si=-1。Aij表示i,j之间连接边的条数,由Aij组成的矩阵为连接矩阵。ki,kj为顶点的度,m=

i,j之间连边的期望值为kikj/2m。因此模块化表示为

Q=

126

i

ki,

14m6

i,j

Aij-

kikj2msisj=

1T

sBs4m

kikj其中,s是由si组成的向量。

定义一个新的矩阵B,称为模块化矩阵,其中包含的元素为Bij=Aij-2m

。这个矩阵各行各列元素相加

之和为0,所以这个矩阵一定有特征向量(1,1,1…)以及与之对应的特征值0,与拉普拉斯矩阵相同。用矩阵

B的标准化特征向量ui的线性组合表示向量s:s=

Q=

6

n

aiui。进而模块化函数可以表示成

i=1

6

i

aiuiB

T

6

j

ajuj=

6

n

(ui·s)βi

T2

i=1

其中β假设特征i是矩阵B对应特征向量ui的特征值,原式中常数1/4m不影响后续的计算,因此先不考虑。

T2

ββ值按照递减次序排列β1≥2≥…≥n,那么最大化Q的方法就是选择适当的(ui·s),使其中的大值与特

征值中的大值相对应。如果对s没有限制,只需使s与模块化矩阵的最大特征向量u1成比例就可以达到目的。然而事实上s中的元素si只能取1或-1,无法做到与u1成比例。那么只能尽可能使s与u1成平行关系:当u1中的元素ui大于0时,对应的si等于1;当u1中的元素ui小于0时,对应的si等于-1。至此就将网络划分出了两个社团结构。

众多的实际应用证明这种方法的优越性。它在有效划分社团结构的同时,还提供了十分有用的网络信息。向量u1中元素的数值表示出了该顶点属于某个社团结构的强度,某顶点对应值为0或接近0,表示它在两个社团结构的边界线上。

这种算法并非只能将网络划分成两个社团结构。将其拓展到划分多个社团结构的思路是重复上述划分成两个社团结构的过程。需要注意的是,在第1次社团结构划分完毕后,不要将网络中两个社团结构间的连

(1)

(1)

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学·36·2008年9月

边删除。因为边的删除会导致Q函数中度值的变化,从而使得最大化的目标不是初始目标。正确的做法是定

(g)

义子图模块化矩阵,如果子图中有ng个顶点,那么其模块化矩阵B就是ng×ng的矩阵。模块化矩阵的元素

Bij

(g)

=Aij-

kikj2m

-δij[ki

(g)

-ki

dg2m

],其中ki

T

(g)

为顶点i在子图g中的度,dg为子图中各顶点的度(在整个网络

中的度)的总和。子图的模块化Qg=sBs的值是重复划分对原有模块化值的增加。重复划分何时为止?这种算法有明确的标准:如果子图的任何划分都不能增加网络的模块化,或得不到正的Qg,那么就无需进一步的划分。

总体上这种方法可以概括如下:首先计算模块化矩阵的最大特征值和特征向量,根据这个向量的符号将网络中的顶点划分成两部分,然后对每部分重复上述过程。如果某次划分对总体模块化值没有贡献或贡献为负数,就取消这个划分,将这部分视为不可进一步划分的子图。当整个网络完全由不可划分子图组成时,就得到了社团结构划分的结果。4.4.2　基于局部信息的方法

以上具体介绍的探索网络社团结构的算法都要求在进行分析前了解网络的整体结构。然而,这一要求对于规模巨大且动态性强的网络是难以实现的,例如万维网。因此有学者提出了基于局部信息的探索网络社团

[60]

结构的方法。这里具体介绍ClausetA提出的方法。

网络社团结构划分问题可以转化为对某个刻画网络社团结构函数的优化问题,如4.3小节介绍的算法,都以Q函数为优化目标。当缺乏全局信息时,目标函数应当独立于全局性质。由于Q函数依赖网络中的总边数,因此不能作为基于局部信息划分社团结构的目标函数,需要设立新的仅依赖于部分连接的局域模块函数。

考虑一个网络G,假设只了解其中一部分C的全部信息。那么就必然存在一部分U,只知道这些顶点与C内部顶点的连接状况,而不知道这些顶点的全部信息。进一步假设获得更多关于G的信息的唯一方法是访问U中的顶点vi,获得它的全部连接状况,这样vi成为C内的顶点,同时可能有一些初始时完全不了解的顶点加入U部分中。对于这类仅仅了解部分信息的网络,定义局部连接矩阵为

Aij=(g)

1,　顶点i,j间存在连接且任意一个顶点属于C0,　其他

若将C视为G的一个局部模块,对于这种划分的一个简便衡量方式是C内部连边占总体已知连边的比例,表示为

6

ijξ(i,j)Aij

6ij

Aij

=

12m

36

ij

ξ(i,j)。Aij其中m

3

=

126

ij

Aij为局部连接矩阵中的总边数,当顶点i,j都属

于C时,ξ(i,j)等于1,否则等于0。当C内部连边众多并且与G中未知部分连接较少时,该值便会较大。依据该标准,当C≥U时,将C视为局部模块的划分总是好的。

C中有这样一些顶点,它们至少有一条边与U内的顶点相

连。它们构成了C的边界B,如图17所示。边界的连接矩阵表示为

Bij=

1,　顶点i,j间存在连接且任意一个顶点属于B0,　其他

对边界清晰度的衡量标准应当独立于边界所包围的社团的规

图17　边界B含义的形象表明[60]模。直观上,划分恰当的社团其边界应当比较明显,即边界与网

络未知部分的连边少而与社团内顶点的连边多,如图17所示。因此,定义局部模块衡量标准R为

R=

6

ij

δ(i,j)Bij

6ij

Bij

=

IT

第5卷第3期　　李晓佳,等:复杂网络中的社团结构·37·

其中,当vi∈B,vj∈C或vj∈B,vi∈C时,δ(i,j)等于1,否则等于0,T为至少有一端属于B的边的数目,I为两端都不属于U的边的数目。

因为衡量局部模块的标准是针对单一模块,所以网络中的社团是逐一划分出来的。算法的具体过程是:1)给定已知信息的顶点v0作为某一社团的源顶点。令v0=C,与之相连的顶点构成U。2)将使U值增大最多(或减小最少)的邻居顶点加入到C中。3)向U中加入新增的顶点,更新R值。

4)重复2)、3)操作,直到达到指定次数k或完成了全体连通的部分。

ClausetA将该方法应用于经典人工网和亚马逊购物网。结果显示,其分析经典人工网的能力与基于全

局信息的GN算法、边集聚系数算法及Newman贪婪算法相近;并能够从亚马逊网中摘录出一些性质完全不同的物品社团。

5　加权网上的社团结构问题

以往的研究大多都是建立在无权无向网的基础之上,然而随着复杂网络研究的深入,人们发现现实系统构成的网络其连接总是有权重中的,并不是非是既否的关系。因此富含权重的网络才能反映出系统的本质。网络的权重对社团划分产生影响,也成为值得探讨的问题。5.1　加权网

实际系统形成的网络往往包含权重关系,这一事实已经得到广泛认同,比如在人际关系网中,人与人的关系并非完全相同,有些人是推心置腹的朋友,而有些人只是泛泛之交;在科学家合作关系网中,科学家之间合作的密切程度也存在很大的差异,有些是经常合作,有些仅仅合作过一次。边的权重刻画了这些差异。较之无权网的抽象方式而言,加权网的抽象方式更大限度上保留了系统的信息。

网络权重的增加使得在讨论网络中社团时不能仅仅考虑连接强度,必须将边上的权重考虑进来。因此定量描述社团结构的模块化Q函数应当包含边的权重

Q

w

[62]

。含权重的Q函数表达为

TiTj=

12T6

ij

wij-

2Tj

δ(ci,cj)

wij,T=

其中,wij为顶点i,j间连边的权重,Ti为顶点i的点权,Ti=和,ci为顶点i所属的社团。5.2　算法推广

6126

ij

wij为网络中所有连边的权重之

针对探索网络社团结构的研究,网络权重的引入会影响到网络社团的定义。但权重的引入并不会改变探索网络社团结构的主要思路,只需要在细节之处作适当的调整,反映出加权网的特性即可。在谱分析算法和Potts模型算法中,用权重矩阵替代连接矩阵;凝聚思想和分裂思想都与距离和相似度的定义有紧密的联系,

因此采用这种思想的算法要在定义距离和相似度时添加边的权重的影响;优化算法的推广更为简便,只需将优化目标替换为含权重的Q函数。以下详细介绍GN算法和EO算法在加权网上的推广。

GN算法在加权网络上推广的关键在于如何计算加权网中的边介数

[62]

。边介数的定义是不变的,区别在

于顶点间距离的定义。一种显而易见的方法就是将距离看作权重的倒数,从而两个顶点连接边的权重越大,它们之间的距离也就越近,这与人们的直观感受是相符合的。然而进一步研究会发现这种方法是不可取的。两点间权重越大,它们连线的距离就越短,就有越多的最短路径通过它们的连线,因此它们连线的最短路径边介数就越大,从而它们的连线就越早被移除。这就意味着连接越紧关系越密切的会被越早地断开,与聚类的初衷完全相反。

正确的方法是将加权网转化为无权多图。加权网是用边的权重代表点与点之间的紧密程度;而在无权多图中每条边的权重都是相同的,点与点之间的紧密程度是由边的个数表示的。如图18,它们的连接矩阵是相同的。

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学·38·2008年9月

权重为n的边与n条权重为1的平行边等价,加权网和无权多图可以相互替代。GN法运用于无权多图,与运用于与之相应的普通无权网相比,任意两点间的最短路径是不变的,然而由于重复边的存在,边介数的值发生了变化。如果两顶点间有两条边,则每条边的边介数是原值的一半;如果两顶点间有三条边,则每条边的边介数是原值的三分之一……随后找出边介数最大的边将其断开,重新计算边介数,断开边介数最大的边,并重复此过程,便可划分出网络的社团结构。选择最优划分时,只需采用包含权重的Q函数即可。

将EO算法推广到加权网

[63]

时,用含权的Q函数代替Q函数作为全局目标。并将Q函数改写为

Q

w

ww

=

6

r

(err-(ar))

w

ww2

其中,err=12T

w

w

12T6

ij

δ(ci,r)δ(cj,r)为连接r社团内部顶点的连边的权重之和占总权重的比例,arwij

w

=

6

i

Tiδ(ci,r)为社团r内所有顶点的权重之和所占的比例。局部变量,即每个顶点对Q的贡献变为:

w

qi=Tr(i)-Tiar(i)。其中Tr(i)表示如果顶点i属于r社团,则其与r社团内顶点构成连边的权重的总和,Ti为

顶点i的点权。将局部变量对全局变量的贡献标准化,得到顶点属于某个社团的适合度λi=

ar(i)。具体优化过程与无权网EO算法相同。

w

w

qi

w

Ti

=

Tr(i)Ti

-

5.3　权重对社团结构的影响

权重的引入会对网络社团结构产生多大的影响?一些学者以GN算法、Potts模型算法和EO算法在加权

[63]

网中的推广为工具,对此进行了研究。将经典人造网进行拓展,使其成为一个加权网,winter表示与社团外顶点连边的权重,wintra表示与社团内顶点连边的权重。在顶点度值固定的情况下,检验权重变化对社团划分正确率的影响。如图19,其中顶点向内部与向外部连边的平均数都等于8,即〈zin〉=〈zout〉=8,连边的总权重给定〈winter〉+〈wintra〉=2,但分布逐渐变化,竖轴为顶点被划分正确的比例。

第4节具体介绍算法时大都进行了经典人造网的检验,当〈zin〉=〈zout〉=8时,除EO算法的准确率还能达到80%以外,其他算法准确率较低。然而加入权重后可以发现,各种算法的准确性都有所提高,当边权主要集中在每部连边上时,社团结构仍能被较为准确地划分出来。可见,权重的引入会对网络社团结构的划分产生较大影响。

图18　对应相同连接矩阵的加权网和无权多图[62]图19　权重变化导致的社团结构划分正确率的变化[63]

6　总结与展望

本文对复杂网络社团结构研究的成果进行归纳,讨论了网络中社团的定义,着重介绍了有代表性的探索

第5卷第3期　　李晓佳,等:复杂网络中的社团结构·39·

网络社团结构的算法及网络社团结构的相关问题,并关注了权重对网络社团结构的影响。

纵观众多划分网络中社团结构的算法,有些算法的准确率比较高,有些算法的复杂度比较低,有些算法可以处理比较混乱的网络,而有些算法只能应用于具有特定结构的网络。为了对算法特点有更为深刻的认

[29,64]

识,一些科研工作者对部分算法进行了横向的比较。这里对文章第4部分重点介绍的算法进行小结:谱分析思想的算法适用于社团结构显著的网络,且由于求特征值和特征向量的计算复杂耗时,不适合分析规模大的网络;层次距离算法的分析能力严重依赖于顶点间相似度及社团间相似度的定义;GN算法精确性高,即算法包含的随机因素少,但它的复杂度高且不适宜用于混乱的网络;边集聚系数法较之GN算法,复杂度有显著降低,但只能应用于簇系数比较大的网络;信息集中性算法复杂度高,不能应用于分析混乱的网络,且易在划分初期产生孤立点;Potts模型算法中划分社团的操作采用模拟退火算法,因此该算法的复杂度与系统降温速度及中止温度关系密切;随机行走算法建立在层次算法的基础上,其特点与层次算法相仿;电流算法更适合于将网络划分成两个社团的问题;Newman贪婪算法较之GN算法复杂度有显著降低,但依然不适宜分析过于混乱的网络;改进的贪婪算法进一步降低了复杂度,使之接近于线性复杂度,因此可以分析规模较为巨大的网络,但分析混乱网络的能力没有提高;极值优化算法的复杂度较之GN算法有显著下降,且适用于连接混乱的网络;Q函数与谱分析相结合的算法在有效划分网络社团结构的同时,更细致地提供了顶点属于某个社团的倾向;基于局部信息的方法适用于不了解全局信息的大规模网络。综上所述,已有的社团结构划分方法各具特色,仍有发展的空间。因此,发展划分复杂网络社团结构的算法依然是值得关注的方向。而且,针对一个具体的网络,如何高效选取精确性和准确性高,复杂度低的算法也是需要解决的问题。

网络社团结构与网络功能间的联系也是一个有价值的研究方向。Oh.E等学者在酵母网和Internet网

[65]

两个社团结构差异明显的无标度网络上研究了Kuramoto改良模型的同步问题。结果表明,社团间的连接状况对同步具有影响:当社团间的连接分散时同步过渡陡峭,达到全局同步;当社团间的连接集中时同步过渡平滑,达到社团内部的同步。Park等学者为了探索社团结构对网络同步的影响,构建并研究了社团间

[66]

连接方式不同的多个网络。他们发现社团间的随机连接和长程连接能够增强网络的同步能力,而社团内部顶点间的连接对网络同步能力的影响不大。因此他们认为在社会网络中实现全局同步的策略是建立和强

[67]

化远距离社团间的连接。严钢等学者应用SIRS传染病模型探讨了网络社团结构对集群同步的影响。他们应用Q函数衡量网络的社团结构水平,提出一种生成不同Q值网络的方法。对这些生成网的研究发现,Q值小的网络有强同步能力,该结论与Donetti.L等人的结论一致。周涛等学者也提出了一种社团结构强度可变的无标度网络增长模型,并用社团间连边数目与社团内部连边数目的比值衡量社团结构的强度。基于这种网络对Kuramoto模型相同步的研究发现,在一定的社团强度之内,网络的同步能力低于社团间没有连接的网络;而社团强度超出某一域值后,社团结构对网络同步能力的影响便会消失;社团强度介于两个特

[69][70-71]

殊值之间时,社团结构越强网络的全局同步能力越弱。另外,有的研究中还发现网络中拥有相同功能的顶点往往被归于同一个社团。这些研究结果不但指出了探索划分社团结构算法的新思路,而且丰富了网络社团结构的意义。

有向网中社团结构的研究有着广泛的空间,如何定义和划分有向网中的社团结构,有向网中的环型结构与集团结构的关系,以及如何探索有向网中的层次问题(如食物链网络中的植食性动物层和肉食性动物层)都是值得关注的问题。另外,复杂网络社团结构问题的研究也可以推广到包含两类顶点的二分网。用二分网描述系统的优势在于:减少了描述过程中的信息损失,保留了更多的系统信息。并且众多的实际系统往往具有二分性,例如图书借阅系统,包含读者和图书这两类主体。对二分网社团结构的研究不但需要重新定义社团结构的概念,还需要开发两类顶点协同考虑的搜索算法,使得两类顶点被同时划分出社团结构。

复杂网络社团结构分析在实际问题中还没有得到广泛的应用,仅仅涉及Internet网、科学家合作网等领域,但其在大脑系统、生物系统、经济系统、管理系统等领域的应用可能会揭示出以往方法未发掘的信息。不仅如此,网络社团结构对实际问题还有着指导意义。因此,社团结构对分析解决实际问题的价值需要进一步的探讨。

[68]

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学·40·2008年9月

参考文献:

[1]NewmanMEJ.Thestructureandfunctionofcomplexnetworks[J].SIAMReview,2003,45(2):167-256.[2]吴金闪,狄增如.从统计物理看复杂网络研究[J].物理学进展,2004,24(1):18-45.

WuJinshan,DiZengru.Complexnetworksinstatisticalphysics[J].ProgressinPhysics,2004,24(1):18-45.[3]汪秉宏,周涛,何大韧.统计物理与复杂系统研究最近发展趋势分析[J].中国基础科学,2005,7(3):37-43.

WangBinghong,ZhouTao,HeDaren.Thetrendofrecentresearchonstatisticalphysicsandcomplexsystems[J].ChinaBasicScience,2005,7(3):37-43.

[4]周涛,柏文洁,汪秉宏,等.复杂网络研究概述[J].物理,2005,34(1):31-36.

ZhouTao,BaiWenjie,WangBinghong,etal.Abriefreviewofcomplexnetworks[J].Physics,2005,34(1):31-36.[5]方锦清,汪小帆,郑志刚,等.一门崭新的交叉科学:网络科学(上)[J].物理学进展,2007,27(3):239-343.

FangJinqing,WangXiaofan,ZhengZhigang,etal.Newinterdisciplinaryscience:networkscience(I)[J].ProgressinPhys2ics,2007,27(3):239-343

[6]方锦清,汪小帆,郑志刚,等.一门崭新的交叉科学:网络科学(下)[J].物理学进展,2007,27(4):361-448.

FangJinqing,WangXiaofan,ZhengZhigang,etal.Newinterdisciplinaryscience:networkscience(II)[J].ProgressinPhys2ics,2007,27(4):361-448.

[7]AlbertR,JeongH,BarabasiA2L.Diameteroftheworld2wideweb[J].Nature,1999,401(6749):130-131.[8]AndreiB,RaviK,FarzinM,etal.GraphstructureintheWeb[J].CompuerNetworks,2000,33:309-320.[9]WilliamsRJ,MartinezND.Simplerulesyieldcomplexfoodwebs[J].Nature,2000,404(6774):180-183.

[10]AmaralLAN,ScalaA,BarthelemyM,etal.Classesofsmall2worldnetworks[J].ProcNatlAcadSciUSA,2000,97(21):

11149-11152.

[11]GleiserP,DanonL.Communitystructureinjazz[J].AdvancesinComplexSystem,2003,6(4):565-573.

[12]GirvanM,NewmanMEJ.Communitystructureinsocialandbiologicalnetworks[J].ProcNatlAcadSciUSA,2002,99:

7821-7826.

[13]RednerS.Howpopularisyourpaper?Anempiricalstudyofthecitationdistribution[J].EurPhysJB,1998,4:131-134.[14]GibsonD,KleinbergJ,RaghavanP.Inferringwebcommunitiesfromlinktopology[C].Proceedingsofthe9thACMConference

onHypertextandHypermedia.Pittsburgh:ACMPress,1998:225-234.

[15]FlakeGW,LawrenceSR,GilesCL,etal.Self2organizationandidentificationofwebcommunities[J].

2002,35(3):66-71.

[16]AdamicAL,AdarE.Friendsandneighborsontheweb[J].SocialNetworks,2003,25(3):211-230.

[17]ArenasA,Diaz2GuileraA,Perez2VicenteCJ.Synchronizationrevealstopologicalscalesincomplexnetworks[J].PhysRev

Lett,2006,96(11):114102.

[18]RadicchiF,CastellanoC,CecconiF,etal.Definingandidentifyingcommunitiesinnetworks[J].ProcNatlAcadSciUSA,

2004,101:2658-2663.

[19]CastellanoC,RadicchiF.Self2containedalgorithmstodetectcommunitiesinnetworks[J].EurPhysJB,2004,38:311-319.[20]解亻刍,汪小帆.复杂网络中的社团结构分析算法研究综述[J].复杂系统与复杂性科学,2005,2(3):1-12.

XieZhou,WangXiaofan.Anoverviewofalgorithmsforanalyzingcommunitystructureincomplexnetworks[J].ComplexSys2temsandComplexityScience,2005,2(3):1-12.

[21]PallaG,DernyiI,FarkasI,etal.Uncoveringtheoverlappingcommunitystructureofcomplexnetworksinnatureandsociety

[J].Nature,2005,435(7043):814-818.

[22]NewmanMEJ.Detectingcommunitystructureinnetworks[J].EurPhysJB,2004,38:321-330.

[23]FortunatoS,BarthelemyM.Resolutionlimitincommunitydetection[J].ProcNatlAcadSciUSA,2007,104:36-41.[24]WassermanS,FaustK.SocialNetworkAnalysis[M].Cambridge,UK:CambridgeUnivPress,1994.

[25]NewmanMEJ,GirvanM.Findingandevaluatingcommunitystructureinnetworks[J].PhysRevE,2004,69(2):026113.[26]ParkJandNewmanMEJ.TheoriginofdegreecorrelationsintheInternetandothernetworks[J].PhysRevE,2003,68(2):

026112.

IEEEComputer,

第5卷第3期　　李晓佳,等:复杂网络中的社团结构·41·

[27]LiMH,FanY,ChenJW,etal.Weightednetworksofscientificcommunication:themeasurementandtopologicalroleof

weight[J].PhysicaA,2005,350:643-656.

[28]SadeDS.Sociometricsofmacacamulattalingkagesandcliquesingroomingmatrices[J].FoliaPrimatol,1972,18:196-223.[29]DanonL,GuileraA,DuchJ,etal.Comparingcommunitystructureidentification[J].JStatMech,2005,P09008.

[30]KunchevaLI,HadjitodorovST.Usingdiversityinclusterensembles[C].2004IEEEInternationalConferenceSystems,Man

andCybernetics,2004,2:1214-1219.

[31]FredALN,JainAK.Robustdataclustering[C].ProceedingofIEEEComputerSocietyConferenceonComputerVisionand

PatternRecognition,Madison,USA,IEEE,2003,2:128-133.

[32]ZhangP,LiMH,WuJS,etal.Theanalysisanddissimilaritycomparisonofcommunitystructure[J].PhysicaA,2006,367:

577-585.

[33]HallKM.Anr2dimensionalquadraticplacementalgorithm[J].ManagementScience,1970,17:219-229.[34]FiedlerM.Algebraicconnectivityofgraphs[J].CzechMathJ,1973,23(98):298-305.

[35]PothenA,SimonH,LiouK2P.Partitioningsparsematriceswitheigenvectorsofgraphs[J].SIAMJMatrixAnalAppl,1990,

11(3):430-452.

[36]CapocciA,ServedioVDP,CaldarelliG,etal.Detectingcommunitiesinlargenetworks[J].PhysicaA,2005,352:669-676.

[37]BoccalettiS,LatoraV,MorenoY,etal.Complexnetworks:structureanddynamics[J].PhysRep,2006,424:175-308.[38]ScottJ.SocialNetworkAnalysis:AHandbook[M].2nded.London:SagePublications,2002.[39]LatoraV,MarchionM.Efficientbehaviorofsmall2worldnetworks[J].PhysRevLett,2001,87:198701.

[40]LatoraV,MarchioriM.Economicsmall2worldbehaviorinweightednetworks[J].EurPhysJB,2003,32:249-263.[41]LatoraV,MarchioriM.Ameasureofcentralitybasedonthenetworkefficiency[DB/OL].[2007-12-18].http://arxiv.org/

abs/cond2mat/0402050.

[42]FortunatoS,LatoraV,MarchioriM.Methodtofindcommunitystructuresbasedoninformationcentrality[J].PhyRevE,

2004,70(5):056104.

[43]ReichardtJ,BomholdtS.DetectingfuzzycommunitystructuresincomplexnetworkswithaPottsmodel[J].PhysRevLett,

2004,93(21):218701.

[44]ReichardtJ,BomholdtS.Statisticalmechanicsofcommunitydetection[J].PhysRevE,2006,74(1):016110.[45]ZhouHJ.NetworklandscapefromaBrownianparticle’sperspective[J].PhysRevE,2003,67(4):041908.[46]ZhouHJ.Distance,dissimilarityindex,andnetworkcommunitystructure[J].PhysRevE,2003,67(6):061901.[47]PonsP,LatapyM.Computingcommunitiesinlargenetworksusingrandomwalks[J].LNCS2005,3733:284-293.[48]WuF,HubermanBA.Findingcommunitiesinlineartime:aphysicsapproach[J].EurPhysJB,2004,38:331-338.[49]NewmanMEJ.Fastalgorithmfordetectingcommunitystructureinnetworks[J].PhysRevE,2004,69(6):066133.[50]BakP,SneppenK.Punctuatedequilibriumandcriticalityinasimplemodelofevolution[J].PhysRevLett,1993,71:4083-4086.

[51]BoettcherS,PercusAG.Optimizationwithextremaldynamics[J].PhysRevLett,2001,86:5211-5214.

[52]ZhouT,BaiWJ,ChenLJ,etal.ContinuousextremaloptimizationforLennard2Jonesclusters[J].PhysRevE,2005,72(1):

016702.

[53]DuchJ,ArenasA.Communitydetectionincomplexnetworksusingextremaloptimization[J].PhysRevE,2005,72(2):

027104.

[54]NewmanMEJ.Modularityandcommunitystructureinnetworks[J].ProcNatlAcadSciUSA,2006,103:8577-8582.[55]NewmanMEJ.Findingcommunitystructureinnetworksusingtheeigenvectorsofmatrices[J].PhysRevE,2006,74(3):

036104.

[56]JosepMP,JavierB,JordiD.Clusteringalgorithmfordeterminingcommunitystructureinlargenetworks[J].PhysRevE,

2006,74(1):016107.

[57]ZhangSH,WangRS,ZhangXS.Identificationofoverlappingcommunitystructureincomplexnetworksusingfuzzyc2means

clustering[J].PhysicaA,2007,374(1):483-490.

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学·42·2008年9月

[58]YangB.Self2organizingnetworkevolvingmodelforminingnetworkcommunitystructure[J].LNCS2006,4093:404-415.[59]YangSZ,LuoSW,LiJY.Anovelvisualclusteringalgorithmforfindingcommunityincomplexnetwork[J].LNCS2006,

4093:396-403.

[60]ClausetA.Findinglocalcommunitystructureinnetworks[J].PhysRevE,2005,72(2):026132.[61]BagrowJP,BolltEM.Localmethodfordetectingcommunities[J].PhysRevE,2005,72(4):046108.[62]NewmanMEJ.Analysisofweightednetworks[J].PhysRevE,2004,70(5):056131.

[63]FanY,LiMH,ZhangP,etal.Accuracyandprecisionofmethodsforcommunityidentificationinweightednetworks[J].

PhysicaA,2007,377(1):363-372.

[64]MikaG,MichaelH,AnnaL.Comparisonandvalidationofcommunitystructuresincomplexnetworks[J].PhysicaA,2006,

367:559-576.

[65]OhE,RhoK,HongH,etal.Modularsynchronizationincomplexnetworks[J].PhysRevE,2005,72(4):047101.[66]ParkK,LaiYC,GupteS,etal.Synchronizationincomplexnetworkswithamodularstructure[J].Chaos,2006,16:015105.[67]YanG,FuZQ,RenJ,etal.Collectivesynchronizationinducedbyepidemicdynamicsoncomplexnetworkswithcommunities

[J].PhysRevE,2007,75(1):016108.

[68]DonettiL,HurtadoPI,MunozMA.Entanglednetworks,synchronization,andoptimalnetworktopology[J].PhysRevLett,

2005,95(18):188701.

[69]ZhouT,ZhaoM,ChenGR.Phasesynchronizationonscale2freenetworkswithcommunitystructure[J].PhysLettA,2007,

368:431-434.

[70]ZhouCS,ZemanovaL,ZamoraG,etal.Hierarchicalorganizationunveiledbyfunctionalconnectivityincomplexbrainnet2

works[J].PhysRevLett,2006,97(23):238103.

[71]ZemanovaL,ZhouCS,KurthsJ.Structuralandfunctionalclustersofcomplexbrainnetworks[J].PhysicaD,2006,224:

202-212.

[72]ClausetA,NewmanMEJ,MooreC.Findingcommunitystructureinverylargenetworks[J].PhysRevE,2004,70(6):

066111.