基于模块度优化的加权复杂网络社团发现算法分析

西南科技大学学报

Journal of Southwest University of Science and Technology

Vol.31 No. 4

Dec. 2016

基于模块度优化的加权复杂网络社团发现算法分析

杨春明王玉金

(西南科技大学计算机科学与技术学院四川绵阳621010)

摘要:社团结构是复杂网络的一种重要拓扑结构。针对加权复杂网络中的社团发现问题，在8个不同领域、不同规 模的真实数据集上，从模块度、强/弱社团、聚集系数3个评估指标分析了基于模块度优化的GN算法、FN算法、 CNM算法和BGLL算法在加权复杂网络社团发现的效果。研究结果表明，上述3个评估指标在加权复杂网络上的

划分结果不能始终保持一致，基于优化模块度的算法更倾向于找到复杂网络中比较粗糙的社团结构,而不是精准的 社团结构，其算法的泛化能力有待加强。

关键词:加权复杂网络社团发现模块度聚集系数中图分类号:TP301.6

文献标志码:A

文章编号= 1671 -8755(2016)04 - 0084 - 06

The Community Discovery Algorithm Analysis on Weight Complex

Network based on Modularity Optimization

YANG Chunming, WANG Yujing

(School of Computer Science and Technology, Southwest University of Science

and Technology, Mianyang 621010, Sichuan, China)Abstract： Community structure is an important topology of complex networks. Aiming at the community discovery problem of weight complex networks, this paper analyzes modularity optimization algorithm of GN, FN, CNM, BGLL form modularity, strong/weak community, clustering coefficient evaluation in 8 different domains and different sizes of real - world datasets. The result shows that the existing criterions encounter difficulties in evaluating the weighted community with complex structure, and these algorithms are more likely to find crude community structure in complex networks, rather than precise community structure. The generalization of the algorithm still needs to be strengthened.Key words：Weight complex network； Community discovery； modularity； clustering coefficient

现实中大量的复杂系统通常可用网络来描述， 如互联网络、社交网络、科学家合作网络、病毒传播 网络等，这些抽象出来的复杂网络通常具有小世 界[1]及无标度特性[2]。复杂网络的一个重要结构 特征是网络的社团（community)结构[3]，又称为群 (group)或簇（cluster),社团内部节点连接紧密，社 团间连接相对稀疏，社团内部节点都具有比较相近 的属性[4]。

收稿日期=2013-12-23

第一作者简介:杨春明（1980—），男,副教授，硕士, CCF会员（18297M),研究方向为算法设计，知识工程,E - Mail: yangchurnning® swust.

edu.cn

复杂网络的社团发现研究主要用于理解网络的 拓扑结构、挖掘网络的潜在意义及预测网络行为等。

对无权复杂网络社团发现，主要有谱聚类方法[5]、 KL( Kemighan - Lin)算法[6]、GN ( Girvon - Newman) 相对与无权网络,有权网络中包含了更多的网 络信息，更能反映实际情况。如论文合作者网络中 作者共同发表论文的数量反映了作者之前的紧密程

算法、FN算法[7]、CNM算法[8]、BGLL算法[9]等。

第4期杨春明,等:基于模块度优化的加权复杂网络社团发现算法分析

85

度;人与人接触的频度越高病毒在两者间传播的可 能性越大。网络中边的权值反映了节点间连接的强 度，在社团结构中，社团内边的平均权值更大，连接 紧密，而社团间连边的平均权值较小，连接相对稀疏。

加权复杂网络的复杂性远高于无权网络，社团 划分结果的评价指标也有了较大变化。目前的研究 大多针对无权网络的社团发现[1°]，已有一些研究进 行了单一算法对特定数据集的分析[11]、多种加权复 杂网络算法的综述[3]以及在多个指标下利用模拟 数据和小规模真实数据的对比分析[12]，但在较大规 模的真实数据集及社团的层次结构特征上的加权复 杂网络社团发现算法还缺乏较全面的实验比较。对 此，本文在不同领域、不同规模大小的8个真实数据 集上分析社团评估指标中的模块度、强弱社团及层 次特征,在加权复杂网络上对基于模块度优化的算 法进行实验比较分析。

1加权复杂网络社团发现算法分析

目前的社团发现算法主要针对无权网络，在加

权网络上，通常考虑边的权值信息，对无权网络的社 团发现算法进行改进。常见的算法有基于图分割思

想的谱聚类算法、KL算法和基于模块度优化的GN 算法、FN算法、CNM算法、BGLL算法等。

1.1基于图分割的算法

谱聚类和KL算法将社团划分视为图分割问 题。谱聚类算法[5]将图分割问题中求解最小“截” 问题转化为求解带约束的二次型优化问题,利用矩 阵分析技术求拉普拉斯矩阵第二小特征值对应的特 征向量问题，从而根据特征向量将网络进行递归划 分。该方法需要预先知道社团的数量，以便定义递 归终止条件，X才具有n节点的网络，该方法的时间复 杂度为〇(〃3)。

KL算法[6]的优化目标是极小化簇间连接数目 与簇内连接数目之差。KL算法在每次迭代过程中 产生、评价、选择候选解，直到从当前解出发找不到 更好的候选解为止。该算法的解往往是局部最优, 而不是全局最优，算法对初始解非常敏感，时间复杂 度是〇(m2),其中表示网络节点个数，t表示算法 停止时的迭代次数。该算法也需要预先知道网络中 社团的数量。

1.2基于模块度优化的算法

模块度优化算法是以模块度函数（P函数）为 目标的社团划分方法。

GN算法[7]将社团划分视为分裂过程,开始将 网络整体看作一个社团，通过逐步移除当前边介数 最大的边来划分出独立的子图。该算法以模块度作 为其评价指标,即在移除边的同时计算移除边后网 络的模块度值，算法执行过程中最大模块度值 对应的网络划分状态即是最终社团划分结果。在加 权复杂网络中,边介数定义为原始定义下的边介数 除以边的权值所得到的值。对于有《个节点/n条

边的加权复杂网络，GN算法中计算每条边的边介 数的算法时间复杂度为，而算法总共需要进 行m次移除边的操作,每次都需要重新计算网络中 每条边的边介数，所以该算法的最终时间复杂度为0 ( nm

2 ) 〇

FN算法[7]是对GN算法的加速,是一种凝聚算 法，开始时将每个节点看作一个社团，计算合并每两 个社团后的模块度值增益,选取使C值增益增加 最多或减少最少的两个社团合并成一个社团，直至 整个网络合并为一个社团为止。对于加权网络，定 义向量a,其

元

素

，即社团i内部节点与

所有社团连边的权值之和占网络所有边权之和的比 例。合并两个社团的模块度(?值增益计算公式：

=2(^ -〇；〇7)

对于有《个节点m条边的加权复杂网络 算法在执行过程中更新矩阵等数据的最坏时间复杂

度为0(n)。算法每一步的最坏时间复杂度为 〇( +肌），最多n -1次社团合并操作，算法的最终时 间复杂度为〇( (n +m)n)，对于稀疏矩阵为0(n2)。

CNM算法[8]是对FN算法时间复杂度的改进, 通过使用堆来构造模块度增量矩阵从而达到快速定 位当前应合并的两个社团的目的。该算法执行过程 依然是一个聚集过程,初始时将每个节点看作一个 社团，同样以模块度值作为评价指标。对于有灯 个点m条边的加权复杂网络。由于CNM算法采用 了堆来构造模块度增量矩阵,所以在每次更新矩阵 时复杂度为〇(l〇g«),而在每次决策合并的两个社 团时只需要常数时间〇( 1 )，算法最多执行n - 1次 社团合并操作，最终算法针对稀疏网络的时间复杂 度为 O(mlogra)。

86

西南科技大学学报

第31卷

BGLL[9]是一种重叠社团发现算法，每次迭代分 为两个阶段。第一阶段将每个节点看作单独的社 团，考虑将每个节点i移除出其当前所在的社团，移 入其邻居节点所在的社团C。第二个阶段将根据 第一个阶段的结果构造一个新的网络，即将第一步 中划分出的各社团各自看作一个节点，社团内部边 的权重之和作为新节点的自环权重,相应的社团与 其他社团所有连边的权重之和作为新节点之间边的 权重值。

BGLL算法提出的模块度增益计算公式简易， 以及算法执行过程中社团数目在前几次迭代中急剧 减少，在针对稀疏网络时有接近线性的时间复杂度。 执行速度快是BGLL算法的一个非常大的优势，使 BGLL算法能在较短的时间消耗下处理上千万甚至 上亿节点的复杂网络,同时该算法还能保持良好的 社团划分效果。

综上所述，上述6种算法的特点如表1所示。

表1算法特点比较

Table 1 Algorithm features

算法复杂度

社团数量重叠社团

谱聚类〇(n3)

已知否KL0(tn2)

已知否GN0(nmz)未知否FN0( (n +m)n)

未知否CNMO(mlogn)

未知否BGLL

〇{n)

未知

是

2加权复杂网络社团划分评估指标

复杂网络的社团划分需要有效的评价指标对社

团划分的过程进行指导，并对社团划分结果的效果 进行衡量。对无权复杂网络，常见的评估指标有:模

sense and in a weak sense)

块度（modularity)、强/弱社团（community in a strongefficient) clustering co­

〇

2.1模块度指标

模块度函数（⑴

其中％表示节点j与节点y连边的权重^为网络中

边的权值之和表示与节点i所连接边的权值总

和,C;表示节点！;；所在的社团，C;与C;相同时, s(Ci，Cy) =1,否则为〇。值取值越接近1,社团结 构越明显，实际网络中发现强/弱社团[14]是对于加权网络G的子图F,定 义^ (>0为子图F内部节点A与子图^内其他节点 连边的权值之和,为子图F内部节点％与非子 图F内部节点连边的权值之和。若子图F满足下 述条件则其为强社团：

S；n(F) >sr(V), yi^v

(2)

若子图F满足下述条件则其为弱社团：

⑴

> Z/广⑴

⑶

茹果针对某网 1各的社团划分结果中满足强/弱 社团定义的社团小于等于1个，则可判断该网络不 具备社团结构或划分结果不正确。因强社团结构同 时也是弱社团结构，因此可以通过弱社团结构总数 占所有划分的社团结构数量的比例来从一定程度上 衡量社团划分效果。2.3聚集系数

聚集系数[15]反映了网络中各节点的邻居节点 间的平均紧密程度，用来刻画网络节点的局部聚集 程度，也可以用其衡量网络整体或其子社团的聚集 程度。对于加权网络，聚集系数定义为：

Ci1 „ W- + W L = S.ik.-l

) § 為

⑷

其中，％表示节点％与&间连边的权值A表示所 有与节点K相连的边的权值之和。

可通过计算每个节点的聚类系数进一步求整个 网络的平均聚类系数来体现网络整体的聚集情况, 同样可以针对网络中的每个社团分别求其聚类系数 来衡量社团聚集程度。一般网络节点间连接越紧 密，连接强度越高则聚类系数越大。

3实验及分析

为了分析加权复杂网络上社团划分算法的特

点，实验时获取了 8个来自不同领域、规模不一的真 实加权网络数据集。由于真实的网络中社团数量未 知，且存在层叠社团的特征，因此实验中选择基于模 块度优化的GN算法、FN算法、CNM算法和BGLL

第4期杨春明,等:基于模块度优化的加权复杂网络社团发现算法分析

87

算法进行实验，在运行时间、模块度、强弱社团、聚集 系数上进行对比分析。

3.1数据集分析

CELE( Celegansneural)为秀丽线虫神经网络的 加权复杂网络。A - ph, C - mat, H - th 为 1995 至 1999 年间 www. arxiv. org上天体物理学、凝聚态、髙能物理3 个研究领域的科学家合作网络，合作的次数作为边 的权值。Cros( cross - domain)为 1990 至 2005 年间 5 个

表2

领域(数据挖掘、医学信息学、计算机理论、可视化、 数据库)科学家发表论文的情况，合作的次数作为 边的权值。

G - au为aminer. org上的论文作者与作者之间 的合作关系构成，合作的次数作为边的权值。NDac 为 www. imdb. com 上的 127 823 部电影参 演信息，同时参演一部电影的次数作为边权的权值。NDw为nd. edu网站上网页间的跳转关系，可 由同一个页面跳转的页面数量作为边权的权值。 上述数据及的统计特征如表2所示。

数据集统计情况

Table 2 Statistics of datasets

网络CELEA - phC - matH-thCrosG - auNDacNDw

N

29716 70616 7268 36124 4455 114392 400325 729

M2 359

121 25147 59415 75161 67617 16815 038 0835 487 065

7.485 315.112 95.852 74.139 65.292 06.723 978.688 333.901 6

L

1.337 92.212 61.749 11.527 60.763 03.611 5

-0.833 6

C

0.726 60.665 050.638 00.48560.711 00.307 90.780 00.898 9

表2中W为节点数,M为边数，< A >为平均 度，i为平均路径长度，C为平均聚集系数。从表2 可以看出,8个数据集的平均路径长度都较小（小于 4)，同时又有较高的聚类系数，这印证了真实复杂 网络几乎都能够满足小世界特性。表中表示 运行时间大于6 S还未得到结果。

表3

GN2 min 58 s

-------

3.2算法运行时间分析

从表3可以看出，BGLL算法执行时间最短，这 与概算法中模块度增益函数及迭代次数有关，这也

使得BGLL算法可以处理较大规模的图片问题。

算法针对各数据集的耗时

Table 3 Hme consunqitloii of algorithm for different datasets

网络 CELE A _ ph C - mat H-th Cros G - au NDac NDw

FN81 ms1 h 53 min 15 s1 h 53 min 37 s14 min 21 s5 h 57 min 9 s3 min 34 s

--CNM15 ms8 s 261 ms3 s 340 ms1 s 422 ms6 s 44 ms1 s 40 ms8 h 21 min1 h 47 min

BGLL2 2 ms 139 ms 98 ms 68 ms 145 ms 37 ms36 s 326 ms13 s 465 ms

3.3模块度指标分析

从表4的结果可看出，每个数据集的社团划分 结果基本都具有明显的社团结构,GN算法与其他3 个算法所得出的结果在模块度指标上出人较大,FN

算法与CNM算法所得到的社团划分结果的模块度 指标数据相差无几，这与CNM算法是基于FN算法 进行时间复杂度优化而来的特点保持一致,BGLL 算法在所有的数据集上表现最好。

88

表4

西南科技大学学报

社团划分结果模块度统计数据

第31卷

BGLL算法中给的A到i4分别表示4个层次的重 叠社团。从数据可以看出，所有算法的社团划分结 果中弱社团的数目都大于1,这说明这些加权复杂 网络都具有社团结构。GN算法的结果中社团数目 相比其他算法多，但弱社团数目相差无几，这与GN 算法的分裂过程特性有较大关系。在规模较大数据 集的社团划分结果中有较多既不属于强社团也不属 于弱社团的社团结构，其中相当部分社团结构都是 离群点，表明在真实复杂网络中，离群点现象比较正 常。此外，从BGLL算法的划分结果可以看出该算 法在第一层与第二层社团层次结构时社团数目急剧 减少，说明在真实复杂网络中层次越高，社团聚类的 可能性越低。

BGLL0.486 70.762 10.873 30.870 10.903 90.761 50.718 90.932 7

Table 4 Statistics of different object modules

网络CELEA - phC — matH-thCrosG - auNDacNDw

GN0.360 7

-------

FN0.471 40.745 40.869 20.868 70.896 90.758 4

--

CNM0.465 20.745 30. 868 90.868 40.896 80.756 50.672 10.913 6

3.4强/弱社团指标分析

表5给出了每个算法在各数据集中的强社团、 弱社团和其他社团的数量（强/弱/其他），其中

表5

强弱社团划分结果

Table 5 Division results of strong and weak communities

rn

CELEA - phC - matH-thCrosG - auNDacNDw

0/6/50------—

BGLL

k

1/4/1193/108/786421/204/643408/170/8152 213/64/1 13655/30/44

3/7/27456/962/1 692819/1 208/1 770710/754/1 1942 746/1 096/2 326293/345/189

h

0/5/1193/341/806429/614/677425/360/8202 317/272/1 137

56/54/44

[3-190/121/785419/246/643405/180/8152 168/70/113635/27/441 998/125/10 1815 414/150/2 024

1/3/0193/110/786421/205/643408/170/8152 214/64/1 13657/30/44

-—

u

-190/104/785419/202/643405/165/8152 163/50/1 13633/26/441 997/114/10 1815 400/132/2 024

763/15 0462 077/350/10 1832 628/90/10 2104 575/2

6 276/102/2 02411 647/3 112/4 5085 715/349/2 025

3.5聚类系数指标统计数据

表6给出了各算法社团划分结果中社团的聚类系 数的均值，平均社团聚类系数越高，说明所划分出来的

社团结构越紧密。从数据中可以看出M与CNM的平 均社团聚类系数相差无几,BGLL所划分的社团结构层

表6

次越高,聚类系数越大，这与聚类系数能够反映网络聚 集程度的特性保持一致。而GN算法得出社团划分结 果的聚集系数相对不理想,通过对GN算法所获得的社 团划分数据分析，其原因是该社团划分结果中有相当 数量的社团结构仅由一^节点构成。

社团平均聚类系

Table 6 Community average clusters

网络CELEA - phC - matH-thCrosG - auNDacNDw

GN0.760 1

-------

FN6.494 62.261 62.423 70.931 01.438 94.320 0

--

CNM4.3322.266 22.426 20.931 01.439 64.384 91.622 62.376 2

BGLL

L,

1.530 00. 854 50. 822 40.463 80.761 40.832 91.094 51.199 7

h

4.750 51.903 41.842 20.829 11.339 83.872 01.679 72.486 1

^3-2.253 92.365 20.935 61.460 25.431 51.710 72.627 9

h

-2.287 12.440 10.945 51.471 85.586 71.711 92.638 1

第4期杨春明,等:基于模块度优化的加权复杂网络社团发现算法分析

89

4

结论

通过8个来自不同领域、规模不一的真实加权

复杂网络社团划分结果分析，可以看出文中的4种 社团发现算法都能够在一定程度上挖掘出其中的社 团结构,但划分出来的社团数量与真实情况存在较 大出人。因此,合理的定义社团内部与社团外部的 关系是社团划分结果优劣的关键，真实复杂网络中 往往存在大量的噪音，影响社团发现的过程,降低社 团发现的准确度。如何根据网络的特征，诠释合理 的社团定义，去除网络噪音将是此后的研究重点 之一'〇

在模块度，强/弱社团，聚类系数3个评价指标 上,从针对CELE的划分结果中可以发现，FN与 CNM的结果的模块度值相差无几，BGLL稍大于 二者。但聚类系数上FN与CNM平均聚类系数相 差较大，BGLL的平均聚类系数位于两者之间。而 在其他数据集的社团划分结果上各统计指标对划分 效果的衡量又能基本保持一致。由此可看出，各评 估指标在针对相同的社团划分结果上并不能始终保 持一致的判断，评价指标是指导社团发现过程、衡量 社团发现效果的重要参数，如何优化现有评价指标 或者找到新的评价指标对加权复杂网络的社团划分 结果进行更加有效的衡量也将是此后研究的重点 之^'〇

本文讨论的加权复杂网络社团发现算法都是基 于模块度优化的算法，这类算法的共同特点是都是 以最大化模块度值或者最大化局部模块度值 增益为目标，具有一定的贪婪特性，因此在算法决策 时可能错过指向真实社团结构但并非局部最优值的 方向，从而导致算法的最终结果存在偏差。从实验 结果中也可看出即便是针对社团结构清晰的加权复 杂网络，比如跨领域科学家合作网Cr〇s,社团划分结 果依然存在大量的未被正确划分的节点，并且最终 得到的社团数量与实际偏差较大，这表明对于大规 模复杂网络，基于优化模块度(?值的算法通常更倾 向于找到复杂网络中比较粗糖的社团结构,而不是 精准的社团结构。

参考文献

[1 ] WATIS D J, STROGATZ S H. Collective dynamics of small -

world networks[J]. Nature, 1998 , 393(6684) ： 440 - 442.[2] BARABASI A, ALBERT R. Emergence of scaling in ran­

dom networks [ J ]. Science, 1999 , 286 ( 5439 )： 509-512.

[3] 李晓佳，张鹏，狄增如，等.复杂网络中的社团结构[J].

复杂系统与复杂性科学，2008(3): 19 - 42.[4]

ZOLLMAN K J. The communication structure of episte- mic communities [ J ]. Philosophy of Science, 2015 , 74(5): 574 -587.

[5] HUANG L, LI R, CHEN H, et al. Detecting network com­

munities using regularized spectral clustering algorithm[ J]. Artificial Intelligence Review, 2014, 41(4) ： 579 -594.[6]

VIEIRA V D, XAVIER C R, EBECKEN N F, et al. Performance evaluation of modularity based community detection algorithms in large scale networks [ J ]. Mathe­matical Problems in Engineering, 2014.

[7] MEJ N. Fast algorithm for detecting community structure in

networks [J]. Physical Review E, 2004 , 69(6): 066133.[8]

CLAUSET A, NEWMAN MEJ, MOORE C. Finding community structure in very large networks [ J ] . Physical Review E, 2004, 70(6) ： 66111.

[9] BLONDEL V, GUILLAUME J, LAMBIOTIE R, et al. Fast

unfolding of community hierarchies in large networks [ J ]. ArXiv, 2008.

[l〇]杨博，刘大有，金弟，等.复杂网络聚类方法[J].软

件学报，2009, 20(1): 54 - 66.[11]

田柳，狄增如，姚虹.权重分布对加权网络效率的影

响[J] •物理学报，2011, 60(2): 803 - 808.

[12] 吕天阳，谢文艳，郑纬民，等.加权复杂网络社团的评

价指标及其发现算法分析[J]•物理学报，2012, 61 (21)： 145 - 154.

[13] NEWMAN MEJ. Communities, modules and large -

scale structure in networks[ J]. Nature Physics, 2012, 8 (1) ： 25 -31.

[14] CAFIER S, CAPOROSSI G, HANSEN P, et al. Finding

communities in networks in the strong and almost - strong sense[J]. Physical Review E, 2012.85(4) ：52 -58.[15] SONG Y, UU J, YU Z, et al. Multifractal analysis of

weighted networks by a modified sandbox algorithm [ J ]. Scientific Reports, 2015,(5) ： 17628.