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

杨春明 王玉金

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

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

杨春明 王玉金

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

社团结构是复杂网络的一种重要拓扑结构。针对加权复杂网络中的社团发现问题，在8个不同领域、不同规模的真实数据集上，从模块度、强/弱社团、聚集系数3个评估指标分析了基于模块度优化的GN算法、FN算法、CNM算法和BGLL算法在加权复杂网络社团发现的效果。研究结果表明，上述3个评估指标在加权复杂网络上的划分结果不能始终保持一致，基于优化模块度的算法更倾向于找到复杂网络中比较粗糙的社团结构，而不是精准的社团结构，其算法的泛化能力有待加强。

加权复杂网络 社团发现 模块度 聚集系数

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

复杂网络的社团发现研究主要用于理解网络的拓扑结构、挖掘网络的潜在意义及预测网络行为等。对无权复杂网络社团发现，主要有谱聚类方法[5]、KL(Kernighan-Lin)算法[6]、GN(Girvon-Newman)算法、FN算法[7]、CNM算法[8]、BGLL算法[9]等。

相对与无权网络，有权网络中包含了更多的网络信息，更能反映实际情况。如论文合作者网络中作者共同发表论文的数量反映了作者之前的紧密程度；人与人接触的频度越高病毒在两者间传播的可能性越大。网络中边的权值反映了节点间连接的强度，在社团结构中，社团内边的平均权值更大，连接紧密，而社团间连边的平均权值较小，连接相对稀疏。

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

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

目前的社团发现算法主要针对无权网络，在加权网络上，通常考虑边的权值信息，对无权网络的社团发现算法进行改进。常见的算法有基于图分割思想的谱聚类算法、KL算法和基于模块度优化的GN算法、FN算法、CNM算法、BGLL算法等。

1.1 基于图分割的算法

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

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

1.2 基于模块度优化的算法

模块度优化算法是以模块度函数(Q函数)为目标的社团划分方法。

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

FN算法[7]是对GN算法的加速，是一种凝聚算法，开始时将每个节点看作一个社团，计算合并每两个社团后的模块度Q值增益，选取使Q值增益增加最多或减少最少的两个社团合并成一个社团，直至整个网络合并为一个社团为止。对于加权网络，定义向量α，其元素a=k∑jeij，即社团i内部节点与所有社团连边的权值之和占网络所有边权之和的比例。合并两个社团的模块度Q值增益计算公式：

ΔQ=2(eij-aiaj)

对于有n个节点m条边的加权复杂网络，FN算法在执行过程中更新矩阵等数据的最坏时间复杂度为O(n)。算法每一步的最坏时间复杂度为O(n+m)，最多n-1次社团合并操作，算法的最终时间复杂度为O((n+m)n)，对于稀疏矩阵为O(n2)。

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

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

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

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

表1 算法特点比较Table 1 Algorithm features

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

复杂网络的社团划分需要有效的评价指标对社团划分的过程进行指导，并对社团划分结果的效果进行衡量。对无权复杂网络，常见的评估指标有：模块度(modularity)、强/弱社团(community in a strong sense and in a weak sense)和聚类系数(clustering coefficient)。

2.1 模块度指标

模块度函数(Q函数)是用来衡量复杂网络社团划分质量的标准[13]，表示实际情况下社团内部连接强度与随机连接情况下的社团内两个节点连接强度的差异。对加权网络，模块度函数定义为：

(1)

其中wij表示节点i与节点j连边的权重，s为网络中边的权值之和，si表示与节点i所连接边的权值总和，ci表示节点vi所在的社团，ci与cj相同时，δ(ci,cj)=1，否则为0。Q值取值越接近1，社团结构越明显，实际网络中发现Q值大于0.3时具有较好的社团划分结果。

2.2 强/弱社团指标

(2)

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

(3)

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

2.3 聚集系数

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

(4)

其中，wij表示节点vi与vj间连边的权值，si表示所有与节点vi相连的边的权值之和。

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

3 实验及分析

为了分析加权复杂网络上社团划分算法的特点，实验时获取了8个来自不同领域、规模不一的真实加权网络数据集。由于真实的网络中社团数量未知，且存在层叠社团的特征，因此实验中选择基于模块度优化的GN算法、FN算法、CNM算法和BGLL算法进行实验，在运行时间、模块度、强弱社团、聚集系数上进行对比分析。

3.1 数据集分析

CELE(Celegansneural)为秀丽线虫神经网络的加权复杂网络。

A-ph,C-mat,H-th为1995至1999年间www.arxiv.org上天体物理学、凝聚态、高能物理3个研究领域的科学家合作网络，合作的次数作为边的权值。

Cros(cross-domain)为1990至2005年间5个领域(数据挖掘、医学信息学、计算机理论、可视化、数据库)科学家发表论文的情况，合作的次数作为边的权值。

G-au为aminer.org上的论文作者与作者之间的合作关系构成，合作的次数作为边的权值。

NDac为www.imdb.com上的127 823部电影参演信息，同时参演一部电影的次数作为边权的权值。

NDw为nd.edu网站上网页间的跳转关系，可由同一个页面跳转的页面数量作为边权的权值。

上述数据及的统计特征如表2所示。

表2 数据集统计情况Table 2 Statistics of datasets

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

3.2 算法运行时间分析

从表3可以看出，BGLL算法执行时间最短，这与概算法中模块度增益函数及迭代次数有关，这也使得BGLL算法可以处理较大规模的图片问题。

表3 算法针对各数据集的耗时Table 3 Time consumption of algorithm for different datasets

3.3 模块度指标分析

从表4的结果可看出，每个数据集的社团划分结果基本都具有明显的社团结构，GN算法与其他3个算法所得出的结果在模块度指标上出入较大，FN算法与CNM算法所得到的社团划分结果的模块度指标数据相差无几，这与CNM算法是基于FN算法进行时间复杂度优化而来的特点保持一致，BGLL算法在所有的数据集上表现最好。

表4 社团划分结果模块度统计数据Table 4 Statistics of different object modules

3.4 强/弱社团指标分析

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

3.5 聚类系数指标统计数据

表6给出了各算法社团划分结果中社团的聚类系数的均值，平均社团聚类系数越高，说明所划分出来的社团结构越紧密。从数据中可以看出FN与CNM的平均社团聚类系数相差无几，BGLL所划分的社团结构层次越高，聚类系数越大，这与聚类系数能够反映网络聚集程度的特性保持一致。而GN算法得出社团划分结果的聚集系数相对不理想，通过对GN算法所获得的社团划分数据分析，其原因是该社团划分结果中有相当数量的社团结构仅由一个节点构成。

表6 社团平均聚类系Table 6 Community average clusters

4 结论

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

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

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

[1] WATTS 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 random networks[J]. Science, 1999, 286(5439): 509-512.

[3] 李晓佳, 张鹏, 狄增如,等. 复杂网络中的社团结构[J]. 复杂系统与复杂性科学, 2008(3): 19-42.

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

[5] HUANG L, LI R, CHEN H, et al. Detecting network communities 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]. Mathematical 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 M E J, MOORE C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6): 66111.

[9] BLONDEL V, GUILLAUME J, LAMBIOTTE R, et al. Fast unfolding of community hierarchies in large networks[J]. ArXiv, 2008.

[10] 杨博, 刘大有, 金弟,等. 复杂网络聚类方法[J]. 软件学报, 2009, 20(1): 54-66.

[11] 田柳, 狄增如, 姚虹. 权重分布对加权网络效率的影响[J]. 物理学报, 2011, 60(2): 803-808.

[12] 吕天阳, 谢文艳, 郑纬民,等. 加权复杂网络社团的评价指标及其发现算法分析[J]. 物理学报, 2012, 61(21): 145-154.

[13] NEWMAN M E J. 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, LIU J, YU Z, et al. Multifractal analysis of weighted networks by a modified sandbox algorithm[J]. Scientific Reports, 2015,(5): 17628.

The Community Discovery Algorithm Analysis on Weight Complex Network based on Modularity Optimization

YANG Chunming, WANG Yujing

(SchoolofComputerScienceandTechnology,SouthwestUniversityofScienceandTechnology,Mianyang621010,Sichuan,China)

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.

Weight complex network; Community discovery; modularity; clustering coefficient

2013-12-23

杨春明(1980—),男,副教授,硕士,CCF会员(18297M)，研究方向为算法设计,知识工程，E-Mail:yangchunming@swust.edu.cn

TP301.6

A

1671-8755(2016)04-0084-06