一种新的复杂网络层次社团发现算法_图文

1、一种新的复杂网络层次社团发现算法张剑(北京邮电大学计算机学院,北京 100876摘要:网络结构广泛存在于自然界和人们的现实生活之中,近来研究表明复杂网络呈现出层次社团结构,网络中节点被分成社团,社团又可以划分成更小的社团,这些不同的层次划分从不同维度展示复杂网络的结构特性。本文针对复杂网络中的层次社团结构提出一种新的基于聚类的层次社团划分算法,该算法通过有效合并策略能对不同规模的网络进行自适应计算。人工和实际网络的试验结果均表明:该算法能得到复杂网络中合理的层次社团划分。关键词:可能性矩阵;概率矩阵;层次结构;社团发现中图分类号:TP312A Novel Algorithm for Hiera

2、rchical Community StructureDetection in Complex NetworksZHANG Jian(School of Computer Science,Beijing University of Posts and Telecommunications, Beijing 100876 Abstract: Networks have in recent years emerged as an invaluable tool for describing and quantifying complex systems in many branches of sc

3、ience. Recent studies suggest that network often exhibit hierarchical organization, where vertices divide into groups that further subdivided into groups of groups, and so forth over multiple scales. In this paper, we introduce a novel algorithm that searches for the hierarchical structure. The meth

4、od iteratively combines the similar communities with the elaborate design of community similarity and combination threshold. The experiments on artificial and real networks show that the method is able to obtain reasonable hierarchical structure solutions.Key words: similarity matrix; possibility ma

5、trix; hierarchical structure; community detection0引言随着对实际网络的拓扑结构和物理意义的深入研究,人们逐渐发现复杂网络除了典型的“无尺度”1,“小世界”2以及“高聚集系数”3等特征,现实世界中的网络还具有第四个重要特性,即:存在“社区结构”4或“社团结构”。更进一步研究发现,平面化的网络社团划分并不能掩盖实际网络结构的非平面模块结构:社团是嵌套的,小社团组成稍大社团,稍大社团反过来组成更大社团,例如大公司组织架构,生物组织功能结构等。在社团发现基础上引入层次结构,社团结构会更丰富,并能帮助分析研究人员更清楚地了解复杂系统的组织结构特征。应用于

6、生物,金融以及社会网络分析中的层次聚类算法由来已久,其基本思想就是根据结点之间的相似程度递归地将结点合并和分裂。本文所要介绍的算法是基于合并型的层次聚类算法,算法分别采用相似性矩阵和概率矩阵来衡量节点和社团间的相似性,这种具备自适应特性的社团合并策略对于人工网络和实际网络的层次社团划分都取得了满意的结果。1介绍由Girvan和Newman5提出的一种新社团发现算法-GN算法,是基于从网络中不断移除边的思想,作为一种分裂型算法,GN算法的执行过程就可以反映网络的层次结构。该算法的主要思想是:根据社团的定义,社团之间的边的数目很少,可以认为是社团之间的“瓶颈”。作者简介:张剑(1986-,男,硕士

7、,主要研究方向:复杂网络可视化与数据挖掘. E-mail: zj.cst.bupt如果从一个社团的结点到达另一个结点就必须经过至少一条这样的“瓶颈”边。因此这些边的流量与社团内部的边相比较高。如果找到这样的一些边从网络中移除就可以把网络划分为社团。Girvan 和Newman 提出的算法在很多情况下都可以取得较好的效果,但是这种算法也有两个重要的缺点,第一个是像其它算法一样这个算法也没有给出应该把网络划分为几个社团的衡量方法。该算法另一个缺点就是速度较慢。如果共移除m 条边,算法将花费O(mN的时间,最坏情况下为O(N 3 。在此之后出现了此算法的改进算法,其主要思路是在计算边介数时应用一些优

8、化模型来提高算法效率。合并层次聚类算法的一般步骤如下:1计算N 个结点两两之间的相似度; 2构造N 个成员社团C 1,C 2,C 3,C N ,每一类的高度都为0; 3找到最近的社团C i , C j ,合并C i ,C j ,社团个数减少1,以被合并的两个类的间距作为上层的高度; 4计算新生成的社团与本层中其它社团的相似度,如果满足条件算法终止,否则转到3。各种合并型聚类算法的步骤基本相同,差别在于数据之间的相似度量标准的定义和社团间距离的定义。本文所提的算法即合并型的层次聚类,算法分别采用相似性矩阵和概率矩阵来衡量节点和社团间相似性,并对算法的优劣从人工网络和实际网络分别进行实验对比,均取

9、得满意结果。2 迭代层次社团发现算法本章首先介绍算法中的相关函数定义,再介绍算法的详细实现。 (A 0111000101110011010001110000000001100001010000110 1.00.40.50.50.20.0010.0010.4 1.00.40.40.0010.20.20.50.4 1.00.50.20.0010.0010.50.40.5 1.00.20.0010.0010.20.0010.20.2 1.00.250.250.0010.20.0010.0010.25 1.00.3330.0010.20.0010.0010.250.333 1.010.0040.001

10、0.00410.250.0010.251 (B (C (D图1 (A简单网络图;(B邻接矩阵;(C相似性矩阵;(D概率矩阵如图所示,图1 (A由7个节点和10条边组成的简单网络. 考虑节点1和5间的节点相似性(N1= 2, 3, 4, N5= 2, 6, 7,相似度为0.2;(B 图A 所示网络的邻接矩阵. (C 图A 相似性矩阵. 同时也是概率矩阵000,(,0.5,(,0.001,0.25PM MAX PM i j MIN PM i j =. 第一次迭代运行结束后所得到的社团:1123123,1,2,3,4,5,6,7P C C C C C C =;(D11121212,(,0.25,(,

11、0.001,0.125.,1,2,3,4,5,6,7PM MAX PM i j MIN PM i j P C C C C =.2.1 相似性矩阵计算任意一对节点间相似性,用以构造相似性矩阵。衡量节点间相似性的办法很多,在经过大量试验后,我们选择了一个测量网络拓扑重叠的基本方法678,将其定义为两节点公有的邻接点与两节点所有的邻接点的比值。这种衡量方法是在图中较小的局部空间内衡量节点间的相似度。 1(|,(|i j ij i j N N SM i j i j N N = 在节点相似度基本上构造SM 矩阵,矩阵行列索引与节点编号一致。考虑到节点i 的度可能通过,i j K A i j =计算。|i

12、 j N N 即为第i 行和第j 行数据所构造的向量进行“与”运算; |i j N N 即为第i 行和第j 行数据所构造的向量进行“并”运算即可得。2.2 可能性矩阵在合并社团过程中,我们需要衡量社团间的连接紧密程度。这里我们引用概率矩阵来衡量社团间的连接紧密程序。在诸多方法比较之后,我们定义可能性矩阵公式如下:|11|,1,j i i j C C m n C C PM i j SM m n = 注意到分母,SM m n 的值可能为0,在实验中我们选择一个极小值(0.001来代替0.2.3 迭代层次社团发现算法IHCD算法思想沿用层次聚类思想,通过引入相似性矩阵来表示节点间连接紧密程度,用概率

13、矩阵来衡量社团间连接紧密程度,其算法主要包括以下两个基本步骤:(i 根据邻接矩阵计算相似性矩阵(ii 迭代合并连接度紧密的社团结构算法1是IHCD 的基本框架,通过每一次的迭代过程,我们都能得到一种社团划分,即相应的层次结构。概率矩阵是基于上次迭代后得到的社团划分结果以及相似性矩阵计算而来。整个过程结束的条件是所有节点处于同一社团。IHCD 算法的关键在于社团合并,在经过大量试验和对比后我们发现,采取一种自适应的方式来合并社团更有效。对于某种社团划分t P 得到的概率矩阵t PM , 合并阈值(,(,/2MAX PM i j MIN PM i j =,如果社团i 和社团j 的相似度,PM i

14、j >,算法将i 与j 合并。Algorithm 1 Main framework of IHCD-Iteration Hierarchical Community Detection1. procedure2. calculate similarity matrix SM based on the adjacent matrix A3. initialize graph partition 0P with each node is a community4. set t = 05. while (|1t P > do6. calculate possibility matrix

15、t PM based on t P and SM7. combine communities to construct partition 1t P +8. t=t+19. end while10. end procedure算法2给出了合并社团的详细描述,其过程可看作是算法1中第7行的具体操作策略。Algorithm 2 Combine Communities1. procedure2. set (,(,/2MAX PM i j MIN PM i j =3. for each community i set isCombinedi = false4. set m = 05. initiali

16、ze graph partition 0P6. for each i C in t P do7. if (isCombinedi = false do8. add i C to m C in 1t P +9. isCombinedi = true10. for j C in t P (j>ido 11. if ( isCombinedj = false and ,PM i j > do12. add j C to m C in 1t P +13. isCombinedj = true14. end if15. end for 16. m+17. end if18. end for1

17、9. end procedure合并过程截止条件是所有节点划归到同一社团。很显然我们在每次迭代过程中能得到一种社团结构划分,这种划分也构成了层次网络的每一层。为了找出有意义的层次结构,我们需要较好地设计合并策略,对值的设计可以有很多种方式,最简单的方式是将值从0到1按0.1逐级递增,将网络从不同颗粒度逐级合并。这里我们设置值选取概率矩阵所有值的中间值,即最大与最小值求平均。试验结果表明这种社团合并策略能达到最快的社团层次收敛,并且能得到有意义的层次社团结构,其它合并策略也可引用,将留作今后讨论。 3 试验为了进一步验证IHCD 实验效果,我们进行了两组试验,包括人工网络和实际网络实验,实验环境

18、:OS Windows XP, Frequency 2.40GHz and 2G RAM Pentium Processor 。3.1 人工网络实验采用的数据是由Girvan 与Newman 数据集的扩展,如图2所示。网络由1024个节点组成,所有节点被划分成64个社团,每个社团包含16个节点。在最里层社团(由16个节点组成,每个结点有K1条边与其内部结点相连,在第二层有K2条边与64个节点组成的社团相连,第三层有K3条边与256个节点所组成的第三层社团相连接,另外,每个节点有K4条边随机地与网络中其他节点相连。这样,网络的三层结构便呈现出来,如图2(A 灰度图所示:其中最里层包含64个社团(

19、图中高亮部分,次外层包含16个社团,最外层包括四个社团。通过实验我们希望IHCD 能将网络的三层结构呈现出来:最外层包含四个大社团,中间层包含16个子社团,最里层包含64个小社团。K1, K2, K3和K4分别用来控制社团度。K1值越大表明最内部社团连接越紧密,这里我们选择设置K2=K3=K4=5, K1取值范围从5到13. K1值越小,表明最内部社团结构越模糊,试验算法能否从中找出有效社团。 (A (B图2 (A三层网络结构灰度图;(B试验结果如图所示,图2(A是一个具有三层层次结构的网络灰度图。最外层的社团结构由四个均包含256个结点的社团组成,次外层由16个均包含64个节点组成的社团,最

20、里层由64个均包含16个结点组成的社团来表示。图2(B是层次网络的实验结果,图释分别表示K1-K2-K3-K4。试验结果如图2(B所示。在多数情况下,IHCD能准备地显示出三层体系结构:最内层(包含64个社团结构,次外层(包含16个社团结构,第三层(包含4个社团结构。我们同样发现:随着K1值减少,最里层节点间联系变得较为松散。因此,IHCD难以准确寻找64个社团。特别地,当K1=13时,IHCD迭代四次即可准备找出三层社团结构。当K1=5时,IHCD算法通过6次迭代过程显示出其层次结构。3.2实际网络为验证IHCD的有效性,我们使用经常使用的一个典型的网络:空手道俱乐部5(Karate 俱乐部

21、网络来进行实验,这个网络是在社会网络分析中经常用到的一个经典的具有社团结构的网络。它反应了美国一所大学中空手道俱乐部成员之间的相互关系。20世纪70年代, Zachary通过对这个网络的观察,发现该俱乐部的主管和教练之间因是否应该提高俱乐部的收费产生了分歧,结果该俱乐部形成了以主管和教练为中心的两个社团。如图3所示,结点1和结点33分别代表主管和教练,方形和圆形分别代表了以主管和教练为中心的社团。 (A(B图3 (AKarate俱乐部网络;(B北美大学足球联盟网络实验二是北美大学足球联盟网络5。其中包括115个结点,代表所有队伍,队伍间比赛用一条边相连。在该网络中,每个结点代表了北美2000年

22、橄榄球赛季的参加比赛的高校代表队,连接两个结点之间的边则表示相应的两支球队之间至少曾有过一场比赛。整个赛季被事先划分成了12个区域(conferences,每个区域平均包含有10-12支球队。被划分在同中国科技论文在线 为如图所示的 12 个社区。 一个区域内的高校之间的常规赛要明显多于区域之间的比赛， 因此， 该网络很自然地被划分 (A (B (C (D (E 图 4 (A迭代次数与相应 Q 值衡量标准间关系的结果示意图。 (B(C通过 Q 值局部最优得到的 Karate 网 络的两层结构。(D(E通过局部 Q 值最优得到的两层结构的足球网络图。 两实验在 IHCD 算法经过 7 次迭代运算

23、后结束。 我们使用较简单的方式从诸多社团划分 中选择有意义的层次社团结构。通过计算 Q 值，我们选择局部 Q 值最优解来得到有意义的 社团结构。图 4（A）显示不同次迭代划分得到的社团个数及其对应的 Q 值。对 Karate 网络 而言，在第六次迭代时得到最真实的社团划分结果（如图 4（C）所示），这两个社团从更 低粒度可被进一步划分为 5 个社团（如图 4（B）所示），同样的结果也在其他研究中被发 现59.对足球网络而言，IHCD 在第三次迭代时将其划分为 12 个社团（如图 4（D）所示。 同时，这些社团可进一步在第 6 次迭代后高粒度划分为 5 个区（如图 4（E）。对于这些 -6- 中

24、国科技论文在线 4 结论 真实网络而言， IHCD 不仅能反正网络的真实结构， 同时能发现社团间隐藏的其他真实情况。 本文给出了层次社团发现算法 IHCD 的两个主要过程。 第一阶段是计算网络相似性矩阵 并初始化各个节点自成社团，第二阶段即迭代地合并相似的社团。在经过一系列实验后，我 们设计一个简单并有效的方法来衡量社团相似并决定合并条件。 对人工网络的实验结果表明 算法可以通过少量的迭代过程准确地找到内在的层次结构， 对真实网络的实验结果表明算法 可以找到真实存在的社团结构， 并能找到其他有意义的层次结构。 算法的相应改进策略包括 设计更合理的合并策略以及相似性计算， 包括其应用于大规模网络

25、， 这些均有待在今后进一 步探讨。 参考文献 (References 1 Barabasi, A.L. and R. Albert, Emergence of scaling in random networks, in Science. Department of Physics, University of Notre Dame, Notre Dame, 1999，46556, USA. p. 509-512. 2 Watts, D.J. and S.H. Strogatz. Collective Dynamics of Small-World Networks. Nature. 1998. p. 440-422. 3 Newman, M.E.J. The structure and function of complex networks. S