基于局部聚合的复杂网络自动聚簇算法

汤 蓉，唐常杰，徐开阔，杨 宁

(1. 成都信息工程学院计算机学院 成都 610225; 2. 四川大学计算机学院 成都 610065)

现实世界中的诸多系统均可建模为复杂网络(complex network)，如：WWW万维网、人际关系网、流行病传播网等。系统中的实体(entity)由节点(node)表示，而实体之间的关联(interaction/relation)由边(edge)表示，节点集和边集构成了复杂网络。复杂网络的社区结构(network community/cluster structure)是描述复杂网络拓扑结构的重要特性之一，具有社区内部节点连接紧密而社区之间连接相对疏松的特点[1]。随着计算机技术的发展，可得到的数据规模越来越大，从规模巨大的网络数据中发现社区结构从而挖掘网络中隐藏的规律已变得越来越重要。

迄今为止，研究者们提出了诸多不同的发现社区结构的方法[1-6]，如：文献[5]提出的快速启发式算法，文献[6]提出的基于子图相似度的贪婪聚簇算法等，其中大部分为全局聚簇(global clustering)算法。很多文献中使用的快速随机递归搜索算法(fast stochastic and recursive search algorithm)[3-4,7-8]，根据特定的全局模块性，如：Q函数(modularity)[2]和网络最短描述长度(network minimum description length,NMDL)等[3-4]，利用全局信息(global information)，对所有的点和边同时展开搜索从而揭示网络社区结构，导致聚簇时间和空间消耗偏高。因全局聚簇需预先掌握网络的全局连接信息，有些还需预知簇数，使其对于动态网络和大型网络具有局限性。

文献[7]首先提出了局部簇(local cluster)和局部模块性(local modularity)的概念，并基于最大化局部模块性提出了局部聚簇(local clustering)算法[7]。随后研究者们又提出了其他局部模块性定义，包括：Outwardness(OW)[9]、 ModularityM(MM)[10]和LMetric(LMe)[11]等。因局部聚簇无需全局信息，通过计算单个簇的模块性搜索局部簇，特别适应于动态网络和大型网络的已知区域。

针对全局聚簇算法空间和时间消耗偏高的缺陷，本文基于局部聚簇提出了一种两段式(two-phase)的复杂网络自动聚簇算法(local agglomeration and iterative clustering algorithm, LAICA)。该算法分为两个阶段：局部聚合(local agglomeration)阶段和局部簇迭代聚簇(iteratively clustering of local clusters)阶段。第一阶段通过局部聚簇发现网络中局部密集的节点集，获得由局部簇构成的复杂网络局部簇结构；第二阶段通过迭代式全局聚簇网络的局部簇结构自动解析网络的最优社区结构。本文选择了4种局部模块性作为局部簇搜索的评价标准；因Q函数存在分辨极限[12]，全局模块性则采用基于信息论的网络最短描述长度—Map Equation(ME, 映射方程式)[4]。使用多个真实网络对LAICA算法进行了聚簇实验，两个阶段中不同的局部模块性和全局模块性的结合使用，使LAICA算法表现的聚簇性能不同。和其他全局聚簇算法比较，LAICA算法的聚簇无需所有节点参与，仅从一组初始节点开始发现局部簇；对局部簇的迭代聚合，使算法能够自动解析网络的社区数量，并同时精确地将节点分配至其所属社区。实验的聚簇精度(NM I值)最高达99.72%，表明LAICA是一个精确的复杂网络自动聚簇算法。

1 复杂网络聚簇基本概念

复杂网络可建模为图：X = (V，E), 其中：X为复杂网络，V为节点集，E为边集。复杂网络中局部连接紧密的节点集形成了网络的社区(community/cluster)。设X包含n个节点且分布于m个社区中，形成了X特定的社区结构：M = {M1, M2,…,Mi,…, Mm}，其中：Mi(1≤i≤m)为X的任一社区且Mi∈V。

1.1 局部簇结构模型

从单个节点出发，利用该节点的连接信息所发现的局部密集的节点集，称为复杂网络的局部簇[7]。局部簇Mi的节点集如图1所示。局部簇中所有节点构成其成员节点集(member nodes)，以Mi表示。成员节点又可分为两个子集：边界成员节点集(boundary nodes, Bi)和核心成员节点集(core nodes, Ci)，即：Mi= CiUBi，其中：边界成员节点至少存在一条边与簇外节点相连，而核心成员节点仅与簇内成员节点相连。Mi的簇外节点，如果至少存在一条边与Mi的成员节点相连，则为Mi的邻居节点，Mi的邻居节点集(shell nodes)以Si表示。连接不同节点集之间的边形成了不同的边集，包括：内边集(inlinks)、外边集(outlinks)/边界外边集(outlinks/Boutlinks)和边界内边集(boundary inlinks, Binlink)，其中：内边为连接Mi成员节点之间的边；外边(也称为边界外边)为Mi的边界成员节点与邻居节点之间的边。边界内边集和边界外边集的并集称之为边界边集，即：与边界成员节点相连的所有边的集合[11]。

图1 局部簇Mi的节点集

1.2 局部模块性

局部聚簇的基本思路如下：选择初始节点vi，以vi建立初始局部簇Mi；搜索最大化Mi局部模块性变化值的邻居节点聚合到Mi中，更新Mi的成员节点集和邻居节点集；直到Mi不再存在能改善其局部模块性的邻居节点，则停止对局部簇Mi的搜索和扩展[7]。如表1所示，以下4种不同的局部模块性：Local Modularity(LM)[7]、 ModularityM(MM)[10]、 Lmetric(LMe)[11]和Outwardness(OW)[9]，均利用社区结构中社区内连接紧密而社区间连接疏松的特点，以簇内连接与簇外连接之间的比值或差值来表示局部簇的局部模块性；但却采用局部簇的不同属性值来量化簇内连接与簇外连接。其中：LM、MM和LMe均采用簇内连接与簇外连接之间的比值表示局部模块性，但OW定义的不是局部簇Mi的模块性，而是Mi的单个邻居节点连接簇内与簇外节点的边数之差。

表1 局部模块性评价标准的定义和计算公式

2 基于局部聚合与迭代的自动聚簇

LAICA算法分为两个阶段：局部聚合阶段和局部簇迭代聚合阶段。LAICA算法引入针对网络聚簇问题的概念：子簇网络结构。

2.1 局部聚合算法

以每一个初始节点vi为首个成员建立初始局部簇Mi，然后逐步聚合最大化Mi局部模块性的邻居节点，直到Mi不再存在邻居节点能改善其局部模块性，则停止对Mi的搜索。当Mi不存在邻居节点能改善其局部模块性时，称Mi不可再扩展(un-expandable)。对于复杂网络X，如果其所有局部簇都不可再扩展或其所有节点均已聚合到局部簇中，则称X不可再扩展，此时停止搜索并输出所得到的X的局部簇网络结构，如算法1所示。

2.2 局部簇迭代合并算法

通过局部聚簇X¢到一组局部簇。所有局部簇和未被聚合到局部簇的其他节点则构成了X¢的局部簇网络结构X¢，其中每一个局部簇或节点均为X¢的聚簇单元(clustering unit)。局部簇迭代合并算法(iteratively clustering of local clusters, ICLC)通过最大化X¢的全局模块性，迭代合并(iteratively merge)X¢的聚簇单元从而搜索X的最优社区结构。

2.1.1 全局模块性

Q函数[2]已被文献广泛使用。而Map Equation是根据香农的源编码理论(source coding theorem)[14]提出的另一种全局模块性[4]。设复杂网络X包含n个节点和l条边，且其节点分布在m个簇中，M表示包含该m个簇的特定社区结构，Q函数和ME的定义和计算公式分别如下：

1) Network Modularity(Q函数)

Q函数为社区内实际连接数目与随机连接情况下社区内期望连接数目之差，如式(1)所示，式中：i表示第i个社区，lii为第i个社区的边数，di为第i个社区节点的总度数(degree)。对于特定社区结构M，Q值越大，则M的网络模块度越强：

2) Map Equation(ME, 映射方程式)

以L(M)表示社区结构M的ME值。对于无向网络，L(M)的定义如式(2)所示，式(2)中参数含义及计算公式参考文献[4]。对于特定社区结构M，L(M)的值越小，则M的网络模块度越强，能更精确描述网络的社团结构[4]。

2.1.2 局部簇迭代合并

定义每一个聚簇单元中节点的数量为聚簇单元的长度(length)。迭代聚簇的每一步，均选择X¢中长度最短的聚簇单元Umin，通过计算Umin与每一个邻居单元合并后X¢的全局模块性变化值：DME。选择最大化DME的邻居单元与Umin聚合。直到X¢的小于某一个阈值e，即：DME，则终止迭代合并，并输出所获得的社区结构，如算法2所示。

2.3 算法复杂度分析

首先分别对算法两个阶段的复杂度进行分析。设m¢为局部簇个数(m¢

1) 局部聚合算法(LAA)的复杂度

对于LAA算法，ModularityM、LMetric和LocalModularity的复杂度均为O(k2d)[7,11,13]。对于真实网络，添加新节点的时间消耗决定了局部簇搜索的复杂度为O(k)[7,11,13]。

因outwardness仅需在局部簇的邻居节点中搜索outwardness值最大的节点v，且当v聚合到局部簇时，仅v的簇外邻居节点发生变化，所以聚合时仅需更新v的簇外邻居节点的outwardness值。因为在v和每一个邻居节点之间有且仅有一条边，所以对于每一个簇外邻居节点：Δoutwardness = -2/k (k为v的邻居节点的度数)。最大化outwardness的复杂度为O(kd2log|B|)，而对于稀疏网络，则为O(k log|k|)[9]。

2) 子簇迭代合并算法(ICSC)的复杂度

ICSC算法中，每一步选择长度最小的子簇，通过计算其与每一个邻居子簇合并后网络全局模块性的变化值：ΔGlobalMod，搜索能最大化ΔglobalMod的合并单元。根据式(2)，因为是一个常量，所以，ΔGlobalMod的计算可分解为3部分：

式中：Δvalue1、Δvalue2和Δvalue3的计算分别如式(3)～(5)所示。设参与合并的两个子簇为Mj和Mk，Mj和Mk合并后产生的子簇为Mjk，根据公式，每一次合并仅需通过合并前的参数值重新计算子簇Mjk的wjk和wjkÐ。所以，每一次合并的复杂度为O(kd)。对于有k个节点的复杂网络，ICSC算法的复杂度为O(k2d)。

综上所述，LAICA算法的复杂度为O(k2d)。

3 实 验

为了验证LAICA算法的有效性和可行性，使用Zachary空手道俱乐部网络(Zachary karate club network)[15]、多学科网络(multi-discipline network)[3]和美国大学足球联盟网络(American college football network)[16]等多个真实网络进行聚簇实验。文献[17]提出范化互信息(normalized mutual information,NM I)计算聚簇所得社区结构和真实社区结构的相似程度，本文也采用NM I作为聚簇精度对LAICA算法进行了定量分析与评估。实验采用两种参数产生初始节点：并比较这两种参数设置下LAICA的聚簇精度，其中：Dn0=0时所选择的初始节点即为网络中度数最高的节点。实验所获社区结构将与文献[4]中算法所获社区结构进行比较。

3.1 Zachary空手道俱乐部网络

Zachary空手道俱乐部网络[15]由34个节点和78条边构成，其中：节点代表俱乐部成员、边代表成员之间的社会交往。因意见分歧，俱乐部分裂成以俱乐部管理者和俱乐部教练为中心的两个子俱乐部。此网络标准社区结构的ME值为4.409 3，而文献[4]中算法发现的最佳社区结构ME值为4.311 8。

表2 空手道俱乐部网络的avgNM I统计

表2统计了采用不同的局部模块性和全局模块性聚簇空手道俱乐部网络的平均NM I值(AvgNM I)。当Dn0=0时，ME和Modularity两种全局模块性中，LMe、LM和MM均分别获得了完全一致的AvgNM I值，其中：ME的AvgNM I值为0.991 6，而Modularity的AvgNM I值仅为0.342 7。当时，不同的局部模块性和全局模块性的结合所获AvgNM I值均高于90%。整体而言，在两种初始节点选择参数设置下，ME的聚簇精度高于Modularity。图2为初始节点数从12到32，4种局部模块性的AvgNM I曲线图。

图2 空手道俱乐部网络不同初始节点数的AvgNM I

3.2 多学科网络

多学科网络(multi-discipline network)[3]以节点表示期刊、边表示引用关系。如果一个期刊的某篇论文引用了另一期刊的某篇论文，则构成了两个期刊之间的一个引用关系。网络包含4个领域：multidisciplinary physics、chem istry、bioloegy和ecology，每一个领域为一个社区。每一个领域选取10个期刊共40个期刊作为节点，期刊之间的189个引用关系作为边。该网络标准社区结构的ME值是4.635 0，但文献中[4]算法发现的最佳社区结构的ME值为4.620 0。

表3 多学科网络的AvgNM I统计

表3总结了初始节点个数由15逐一增加到40，两种不同的初始节点参数设置下，算法结合不同的局部模块性和全局模块性对多学科网络聚簇的AvgNM I值。对于多学科网络数据显示，Modularity的聚簇精度高于ME。对于Modularity和ME两种全局模块性，LMe、LM和MM这3种局部模块性也分别获得了完全一致的AvgNM I值。采用ME的LAICA算法在时聚簇精度明显高于Dn0=0；而采用Modularity，则两种不同的初始节点选择策略的聚簇精度非常接近。图3为时，初始节点数从12到40时，4种局部模块性聚簇多学科网络的AvgNM I曲线。

图3 多学科网络不同初始节点数的AvgNM I

3.3 美国大学足球联盟网络

美国大学足球联盟网络(American college football network)是根据2000年秋季常规赛季的比赛计划构建[16]，以节点表示球队、边表示两个球队之间常规赛季的一场比赛。 网络共包含115个节点和613条边。115个球队分属于12个联合会(conference)，因处于同一个联合会的球队间的比赛次数要多于不同联合会的球队间的比赛次数，每一个联合会建模为一个真实网络社区。文献[4]中算法聚簇得到了一个包含10个簇的社区结构，其ME值为5.441 7。

表4 美国足球联盟网络的AvgNM I统计

表4为初始簇个数从20逐一增加到115，两种不同初始节点选择策略下，结合不同的局部模块性和全局模块性聚簇足球联盟网络聚簇的AvgNM I值。数据显示对于该网络，ME的聚簇精度高于Modularity。对于Modularity和ME两种全局模块性，LMe、LM和MM这3种局部模块性也分别获得了完全一致的AvgNM I值。使用ME的LAICA算法在两种不同的初始节点选择策略的聚簇精度明显高于

图4 美国大学足球联盟网络不同初始节点数的AvgNM I

3.4 实验结果分析

实验结果表明，LACIA算法的聚簇精度随初始局部簇个数的增加而上升。当初始簇个数与网络的节点个数完全一致时，LACIA算法等同于快速随机递归搜索算法[1,4]，即：所有节点同时参与聚簇。随着初始簇个数的增加，LACIA算法准确率升高，但计算消耗也增大。要实现准确率与计算消耗之间的折衷，需要设置合理的初始簇个数。在4种局部模块性评价标准中，OW的计算和维护相对简单，却获得了相对较好的聚簇精度。任一真实网络，在Dn0=0的初始节点选择策略下，LMe、LM和MM获得的聚簇精度完全一致，表明这3种局部模块性虽使用不同的参数量化局部簇的簇内和簇外连接数，但因其均采用簇内连接与簇外连接之间的比值来表示局部模块性，搜索局部簇时，这3种局部模块性均聚合了与局部簇内部连接最紧密的节点，导致最后获得的局部簇结构相同。

图5 真实网络度分布曲线图

3个网络节点的度分布(degree distribution)[18]如图5a～图5c所示，仅空手道俱乐部网络严格遵循幂律发布(power law)[19]，而美国大学足球联盟网络节点的度分布则完全违背幂律分布。空手道俱乐部网络的聚簇，当Dn0=0时，其平均NM I值均超过0.99，实验数据还显示，初始节点数从16递增至32，使用ME的LACIA算法均能100%准确地搜索到该网络的标准社区结构。而对于美国大学足球联盟网络，LACIA算法的聚簇精度最低。所以，对于遵循幂律分布的网络，使用ME的LACIA算法的聚簇精度最佳。

4 结论和未来工作

本文提出了基于局部聚簇的自动聚簇算法(LACIA)。LACIA算法的特点如下：1) 利用局部聚簇发现局部连接紧密的节点集，获得聚簇粒度更大且具有一定聚簇精度的局部簇网络结构，从而减少全局聚簇的计算消耗；2) 迭代合并局部簇网络的聚簇单元，自动决定网络簇数并精确分配节点。4种局部模块性评价标准：local modularity[7]、outwardness[9]、modularityM[10]和LMetric[11]，在LACIA算法中均显示出较高的聚簇能力。前3者对3个真实网络的聚簇结果基本一致，表明其聚簇能力相似。而Outwardness[9]仅考虑单个邻居节点与簇内和簇外的连接差异，计算简单，却获得了相对较高的聚簇精度。实验数据也表明，对于遵循幂律分布的网络，使用ME的LACIA算法具有最佳聚簇精度。LACIA算法聚簇多个真实网络，节点分配准确率最高达99.72%，表明该算法能精确有效地聚簇复杂网络。本文的下一步工作将对LACIA算法聚簇大型网络进行深入的探测和研究。

[1] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6):066133.

[2] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E,2004, 69(2): 026113.

[3] ROSVALL M, BERGSTROM C. An information-theoretic framework for resolving community structure in complex networks[J]. Proceedings of the National Academy of Sciences, 2007, 104(18): 7327-7331.

[4] ROSVALL M, AXELSSON D, BERGSTROM C T. The map equation[J]. Eur Phys Journal, Special Topics,2009(178): 13-23.

[5] CHEN D, FU Y, SHANG M. A fast and efficient heuristic algorithm for detecting community structures in complex networks[J]. Physica A: Statistical Mechanics and its Applications, 2009, 388(13): 2741-2749.

[6] XIANG B, CHEN E, ZHOU T. Finding community structure based on subgraph sim ilarity[J]. Studies in Computational Intelligence, 2009(207): 73-82.

[7] CLAUSET A. Finding local community structure in networks[J]. Phys Rev E, 2005(72): 026132.

[8] WAKITA K, TSURUM I T. Finding community structure in mega-scale social networks[C]//In www'07: Proceedings of the 16th International Conference on World Wide Web.Banff(CANADA). NewYork: ACM Press, 2007: 1275-1276 .

[9] BAGROW J P. Evaluating local community methods in networks[J]. Journal of Statistical Mechanics, 2008(7):05001.

[10] LUO F, WANG J Z, PROM ISLOW E. Exploring local community structures in large networks[C]//Proceedings of the 2006 IEEE/W IC/ACM International Conference on Web Intelligence. Hongkong, China: IEEE Computer Society Press, 2006.

[11] CHEN J, ZAÏANE O R, GOEBEL R. Detecting communities in social networks using local information[C]//From Sociology to Computing in Social Networks:Thoeory, Foundation and Applications. New York:SPRINGER-VERLAG W IEN, 2010(1): 197- 214.

[12] FORTUNATO S, BARTHLEMY M. Resolution lim it in community detection[J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-41.

[13] FREEMAN L. Centrality in social networks: conceptual clarification. social networks[M]. Lansanne: Elsevier sequoia S.A., 1979.

[14] SHANNON C E. A mathematical theory of communication[J]. Bell System Technical Journal, 1948(27): 379-432, 623-656.

[15] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977(33): 452-473.

[16] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.

[17] DANON L, DAZ-GUILERA A, DUCH J, et al. Comparing community structure identification[J]. Journal of Statistical Mechanics: Theory and Experiment, 2005(9): 09008.

[18] ALBERT R, BARABÁSI A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002,74(1): 47-97.

[19] BARABÁSI A L. Linked: the new science of networks[M].Cambridge, MA, USA: Perseus Publishing, 2002.

编 辑 蒋 晓