一种面向动态网络的社团检测与演化分析方法

王 菊，刘付显

(空军工程大学防空反导学院 西安 710051)

在信息和网络技术快速发展的背景下，动态网络受到越来越多的关注，例如信息交互网络、社交网络、生物网络等[1-3]。目前关于动态网络的研究主要集中在动态社团挖掘、动态子图挖掘和时序边的预测等[4]。而动态网络演化分析方法的研究，无论是在生物信息领域还是在社会和科技领域都处于初级阶段，常采用以下两类方法：1)演变社团检测；2)通过识别社团演变的关键事件来发现社团演变模式[5]。演变社团检测的主要方法是增量聚类和进化聚类，目前已有较多研究[6-9]，而如何设计高效的社团演变模式挖掘算法成为制约动态网络演化分析的瓶颈[4]。

针对上述问题，本文采用基于事件的动态网络分析架构，提出了一种面向动态网络的社团检测与演化分析方法，该方法将动态网络的时序动态性和时刻静态性用时间序列的方式进行表示，在时刻上运行基于Memetic的静态社团检测算法，在时序上运行社团演化分析算法，最终可以得到社团的动态演变轨迹，能够应用于实际动态网络的演化分析。

1 基于事件的动态网络演化分析架构

文献[10]提出了基于事件的动态网络演化分析框架，如图1所示。其中，生成的时间轴用来刻画网络的变化情况；网段抽取是用平稳的或相对多变的趋势来近似时间轴上网络的变化；图近似是对网段抽取后的结果用网络图进行表示；社团检测是发现近似动态网络某时刻所对应静态网络中的社团；社团演化分析是将不同时刻所发现的社团关联起来，得到相应的演化事件。

生成时间轴、网段抽取和图近似属于对动态网络的近似和简化，与被研究动态网络的规模有直接关系。因此，本文以该框架为基础，以社团检测和社团演化分析为研究重点，提出了一种面向动态网络的社团检测与演化分析方法。

图1 基于事件的动态网络演化分析架构

2 动态网络的社团检测与演化分析

2.1 符号说明

动态网络研究中涉及到很多与静态网络类似的概念与问题，本节首先对文中通用的概念与问题给出形式化的定义，符号说明如表1所示。

表1 符号说明

定义 1[4]动态网络。动态网络G=〈g(1),g(2),…,g(t),…〉是时间上的有序图集，其中g(t)=(V(g(t)),E(g(t)))是t时刻拓扑图。

定义 2[10]社团。社团是网络中的一种子结构，在社团内部，点之间的联系比较紧密，相比之下，这些点和社团外部点的联系则比较稀疏。

2.2 面向动态网络的社团检测与演化分析方法

采用基于事件的动态网络演化分析架构，本文提出了一种面向动态网络的社团检测与演化分析方法，该方法将动态网络的时序动态性和时刻静态性用时间序列的方式进行表示，在时刻上运行基于Memetic的静态社团检测算法，在时序上运行社团演化分析算法，最终可以得到社团的动态演变轨迹。

2.2.1 基于Memetic的静态网络社团检测算法

Memetic是一种结合遗传算法和局部搜索策略的新型智能算法，在优化问题上具有较高的搜索效率[11-14]。本文以其为基础，设计了一种具有指向性的变异策略，将变邻域搜索算法作为局部搜索算子，提出了一种基于Memetic的静态社团检测算法。

1)编码策略

对t时刻的网络快照g(t)，采用字符串编码方式。假设该快照中包含5个节点{v1,v2,v3,v4,v5}，若字符串编码的染色体为(1,2,2,1,3)，则表示{v1,v4}属于社团1，{v2,v3}属于社团2，{v5}属于社团3。

2)具有指向性的变异策略

在Memetic算法中，变异概率通常是随机取值或给定特定的值，收敛速度较慢，因此本文提出了一种具有指向性的变异策略，即计算每个个体中不同社团之间的结构相似度设置个体的变异概率其中的定义如下。

定义 3[15]结构相似度。对于t时刻的网络快照g(t)，对于任意两个社团结构相似度定义为：

采用具有指向性的变异策略可以尽量保留社团间结构相似度较小的个体，变异社团间结构相似度较大的个体，使变异朝社团内部点和外部点联系稀疏的方向进行，进而快速收敛到最优个体。

3)适应度函数

本文适应度函数使用基于相似度的模块度函数，使得网络中社团内部节点对的相似度要高于分属于不同社团的节点对相似度，其定义如下。

定义 4[15]模块度。对于t时刻的网络快照g(t)，若个体x所对应的社团集合为则其模块度函数被定义为：

4)变邻域搜索算法

变邻域搜索(variable neighborhood search,VNS)[16-18]算法是一种求解优化问题的启发式算法。本文将该算法作为局部搜索算子引入到Memetic算法中，可以在社团划分过程中通过动态地改变邻域结构来拓展搜索范围，从而使搜索过程跳出局部最优向全局最优靠近。

邻域结构集Nl(x)(l=1,2,…,lmax)的构造是VNS算法最核心的部分。本文设计了3种邻域结构，具体形式如下：

① 交换/N1(x)

随机选择第i个个体的任意两节点vm和vn(m≠n)；交换vm和vn所属社团。

② 多点交换/N2(x)

随机选择第i个个体的任意两节点vm和vn(m≠n)；交换vm和vn所属社团；重复以上两个步骤至少两次。

③ 复合交换/N3(x)

随机选择第i个个体的任意两节点vm和vn(m≠n)；随机选择第i个个体中任意两个序列p和q，p≠q≠m≠n；将vm所属社团置于p序列，将vn所属社团置于q序列。

仿真实验发现，调用VNS算法时，按照先N1(x)交换，再多点交换，最后复合交换的顺序(即l单调递增)，算法性能表现最好，因此本文仿真实验按此顺序使用这3种离散邻域结构。以下是VNS算法的详细步骤。

5)算法步骤

基于Memetic的静态网络社团检测算法的整体步骤如下所示。

2.2.2 社团演化分析算法

基于本文所定义的匹配度和社团生存周期，提出了一种社团演化分析算法。该算法通过分析不同时刻社团集合的匹配度来发现社团演变事件，从而获得社团的动态演变轨迹。

1)演变事件

演变事件用来刻画不同时刻的社团演变特征，常用演变事件的定义如下[19-21]：

① 社团生长(community survives)：在t+1时刻存在一个社团使得成立。

② 社团合并(community absorb)：在t+1时刻存在一个社团使得同时成立。

③ 社团分裂(community split)：在t+1时刻存在p个社团使得成立。

④ 社团消失(community disappear)：在t时刻存在社团中找不到社团与之对应。

⑤ 社团出生(community appear)：在t+1时刻存在社团在C(t)中找不到社团与之对应。

2)匹配度及match函数

传统的社团演化分析主要有点重合度[22]和结构相似[23]两种方法，它们的不足在于只孤立地分析点或者边，忽略了社团的整体性，因此本文通过综合考虑节点和边的相似度，定义了匹配度，如定义5。

定义 5匹配度。前后两个时刻的任意两个社团之间的匹配度定义为：

基于匹配度，本文设计了在演变事件定义中所用到的match函数，如下所示。其中匹配度阈值要根据实际动态网络的情况和用户的偏好进行设置。

3)社团演化分析算法

在所刻画的5种演变事件中，社团出生和分裂都表示有新的社团产生，社团消失表示有现存的社团瓦解，而社团生长和合并则表示现存社团的延续。因此为了描述动态网络的演变轨迹，本文定义了社团生存周期，如定义6。

定义 6社团生存周期。假设社团在t时刻出现，其社团生存周期被定义为生长或合并的次数其中：

根据上述的定义和分析，本文所提出的社团演化分析算法如下所示。

3 实验与分析

3.1 实验数据集

本文使用真实网络数据集进行实验，以验证算法的可行性与有效性。

数据集1：Zachary空手道俱乐部网络[5]

Zachary空手道俱乐部网络是根据1970年～1972年美国一所大学空手道俱乐部34名成员之间的社会关系所构造的。节点表示成员，节点间的连接代表两个成员经常一起出现在俱乐部活动之外的其他场合。文中通过每隔一个月构建一个静态网络(即一个网络快照)的方式，建立起了Zachary空手道俱乐部在1970年～1972年的动态社会关系网络。在动态网络的建立期间，俱乐部主管John A.(节点34)与教练Mr. Hi(节点1)之间的争执而分裂成了2个各自为核心的小俱乐部，最后一次所构建的静态网络中共包含34个节点，78条边。

数据集2：Power网络

Power网络是根据1998年美国西部的高压电线路构建的。网络中的节点代表变压器、变电站和发电机，边表示的高压电传送线路。与数据集1采用相同的思路，文中通过每隔一个月构建一个静态网络(即一个网络快照)的方式，建立起了美国西部高压电线路在1998年的动态网络，最后一次所构建的静态网络中共包含4 941个节点和6 594条边。

3.2 实验分析

本文所提出的动态网络社团检测与演化分析方法由基于Memetic的静态社团检测算法和社团演化分析算法两部分组成，本节就这两个算法的性能分别进行分析。

3.2.1 基于Memetic的静态网络社团检测算法分析

1)可行性分析

采用本文所提出的基于Memetic的静态网络社团检测算法，设置种群中个体数目M=30，交叉概率Pc=0.6，变异概率Pm=0.025/Sim(u,v)，lmax=3，itermax=10 000。对数据集1和数据集2进行社团划分，在达到终止条件前其模块度值的变化曲线分别如图2a和图2b所示。

根据图2中最大模块度值所对应的社团个数，将Zachary空手道俱乐部成员关系网络划分成了4个社团，Power网络划分成了130个社团，其结果分别如图3a和图3b所示。

图2 模块度值变化曲线

图3 社团划分结果

在图3a中，数据集1被划分成的4个社团分别用不同形状进行了表示，节点越大表示节点的度值越大，基本符合该俱乐部分裂后以节点34和节点1各自为核心构成小俱乐部的实际情况。

在图3b中，数据集2被划分成的130个社团分别用不同深浅度进行了表示，但其节点的度值差距较大，表明各个节点在整个高压电网络中所承担的输送电量有所差别。这与实际中变电站、变压器和发电机所输送电量有较大差距的情况相符合。

综合图3a和图3b的分析结果可以表明：基于Memetic的静态网络社团检测算法具有可行性，社团的划分结果能够满足实际情况的需求。

2)有效性分析

关于静态网络的社团检测，第一种评价指标是度量社团划分紧密程度的模块度，如定义4。第二种评价指标是统一化互信息(normalized mutual information, NMI)，用来评估真实社团结构与算法发现到社团结构的相似度[24]，其定义如下：

式中，N矩阵的行对应真实社团，矩阵的列对应算法所发现的社团；Nij为真实社团i与算法所发现的社团j的重合节点个数；Ni·为第i行元素之和；N·j代表第j列元素之和；CA表示真实社团个数；CB表示算法所发现的社团个数；A表示真实的社团结构；B表示算法所发现的社团结构。

为验证本文算法的有效性，针对数据集1和数据集2，将本文算法与经典的GN[25]、FN[26]和BGLL[27]算法分别就模块度和NMI值进行了比较，其结果分别如表2和表3所示。

通过表2和表3可以看出，本文算法在数据集1和数据集2上的模块度和NMI值都高于其他算法，因此该算法发现社团结构的准确度高，且所发现社团的结构比较紧密。

表2 本文算法与其他算法的模块度值比较

表3 本文算法与其他算法的NMI值比较

3.2.2 社团演化分析算法

设置社团演化分析算法中社团匹配度τ的取值为0.6 (也可以根据用户偏好取其他的值)，以下实验将对社团演化分析算法的可行性和有效性进行论证。

1)可行性分析

根据表3中的算法，对数据集1因俱乐部主管John A.(节点34)与教练Mr. Hi(节点1)之间争执而分裂时社团的演变情况进行分析，其社团演变状态结果如图4所示。

图4中每一种线条代表了一个社团的动态演变轨迹。在t=18时，社团1消失，因此该社团的生存周期为17，同理可以得到其他社团的生存周期。在t=19时，社团1刚刚因分裂而消失，两个新的社团产生，而在实际情况中，正是此时该俱乐部因争执分裂成了两个各自为核心的小俱乐部，与客观情况相符。此外，从图4中还可以发现：在t=34时，社团3所代表的小俱乐部又进行了一次分裂。

图4 Zachary空手道俱乐部成员关系网络演化分析

2)有效性分析

本文通过NMI比较了Power网络已知动态社团的数量以及对应的生存周期与挖掘结果之间的差距，并将其与文献[28]中基于张量分解的社团演化分析方法进行了比较，其结果如图5所示。

图5 算法比较

实验结果表明，相比基于张量分解的社团演化分析方法，本文所提出的社团演化分析算法能够较好地刻画社团演化，验证了该算法的有效性。

4 结 束 语

本文提出了一种面向动态网络的社团检测与演化分析方法，其主要特点有：

1)该方法在时刻上运行基于Memetic的静态社团检测算法，然后在时序上运行社团演化分析算法，最终可以得到社团的动态演变轨迹；

2)设计了一种具有指向性的变异策略，将变邻域搜索算法作为局部搜索算子，提出了一种基于Memetic的静态社团检测算法，并在Zachary空手道俱乐部网络和Power网络上验证了该算法的可行性和有效性。

3)通过定义匹配度和社团生存周期，分析不同时刻社团集合的匹配度来发现社团演变事件，提出了一种社团演化分析算法。该算法在Zachary空手道俱乐部网络上进行了演化分析，在Power网络上与基于张量分解的社团演化分析方法进行了对比分析，分别验证了其可行性和有效性。

[1]FORTUNATO S. Community detection in graphs[J].Physics Report, 2010, 486(3-5)： 75-174.

[2]SPILIOPOULOU M. Evolution in social networks： a survey[J]. Social Network Data Analytics, 2011, 978(3)：149-175.

[3]FRASER H B. Modularity and evolutionary constraint on proteins[J]. Nature Genetics, 2005, 37(4)： 351-352.

[4]高琳, 杨建业, 覃桂敏. 动态网络模式挖掘方法及其应用[J]. 软件学报, 2013, 24(9)： 2042-2061.GAO Lin, YANG Jian-ye, QIN Gui-min. Methods for pattern mining in dynamic networks and applications[J].Journal of Software, 2013, 24(9)： 2042-2061.

[5]刘瑶, 王瑞锦, 刘峤. 动态社会网络的社团结构发现与分析[J]. 电子科技大学学报, 2014, 43(5)： 725-729.LIU Yao, WANG Rui-jin, LIU Qiao, et al. Community detecting and analyzing in dynamic social networks[J].Journal of University of Electronic Science and Technology of China, 2014, 43(5)： 725-729.

[6]CHAKRABARTI D, KUMAR R, TOMKINS A.Evolutionary clustering[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Philadelphia： ACM, 2006.

[7]TANTIPATHANANANDH C, BERGER-WOLF T,KEMPE D. A framework for community identification in dynamic social networks[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Jose： ACM, 2007.

[8]LIN Y R, CHI Y, ZHU S, et al. Facetnet： a framework for analyzing communities and their evolutions in dynamic networks[C]//Proceedings of the 17th International Conference on World Wide Web. Beijing： ACM, 2008.

[9]KIM M S, HAN J. A particle-and-density based evolutionary clustering method for dynamic networks[J].Proceedings of the VLDB Endowment, 2009, 2(1)： 622-633.

[10]吴斌, 王柏, 杨胜琦. 基于事件的社会网络演化分析框架[J]. 软件学报, 2011, 22(7)： 1488-1502.WU Bin, WANG Bai, YANG Sheng-qi. Framework for tracking the event-based evolution in social networks[J].Journal of Software, 2011, 22(7)： 1488-1502.

[11]杨淑莹, 张桦. 群体智能与仿生计算-Matlab技术实现[M]. 北京： 电子工业出版社, 2012.YANG Shu-ying, ZHANG Hua. Swarm intelligence and bionic calculation-technical implementation for Matlab[M].Beijing： Publish House of Electronic Industry, 2012.

[12]TASGIN M, HERDAGDELEN A, BINGOL H.Community detection in complex networks using genetic algorithms[EB/OL]. (2012-12-15). http：//arxiv.org/abs/0711.0491.

[13]PIZZUTI C. GA-NET： a genetic algorithm for community detection in social networks[C]//Proceedings of the 10th International Conference on Parallel Problem Solving from Nature. Dortmund： Springer, 2008： 1081-1090.

[14]GONG M, FU Bao, JIAO L, et al. Memetic： Algorithm for community detection in networks[J]. Physical Review E,2011, 84 (5)： 56-101.

[15]FENG Z, XU X. A novel similarity-based modularity function for graph partitioning[J]. Data Warehousing and Knowledge Discovery, 2007(46-54)： 385-396.

[16]JARBOUI B, DERBEL H. Variable neighborhood search for location routing[J]. Computers and Operations Research, 2013, 40： 47-57.

[17]范成礼, 邢清华, 范海雄. 带审敛因子的变邻域粒子群算法[J]. 控制与决策, 2014, 29(4)： 696-700.FAN Cheng-li, XING Qing-hua, FAN Hai-xiong. The particle swarm optimization and variable neighborhood search algorithm with convergence criterions[J]. Control and Decision, 2014, 29(4)： 696-700.

[18]CHEN Y Y, CHENG C Y. A hybrid approach based on the variable neighborhood search and particle swarm optimization for parallel machine scheduling problems—A case study for solar cell industry[J]. Int J Production Economics, 2013, 141： 66-78.

[19]PALLA G, BARABASI A L, VICSEK T. Quantifying social group evolution[J]. Nature, 2007, 446(7136)：664-667.

[20]PALLA G, DENENYI I. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043)： 814-818.

[21]GREENE D, DOYLE D, CUNNINGHAM P. Tracking the evolution of communities in dynamic social networks[C]//Proceedings of the Int’l Conf on Advances in Social Networks Analysis and Mining. Denmark： ASONAM,2010： 176-183.

[22]BERGER W T Y, SAIA J. A framework for analysis of dynamic social networks[C]//Proceedings of the 12th ACM SIGKDD International Conference on Konwledge Discovery and Data Mining. USA： ACM, 2006： 523-528.

[23]邓琨, 张健沛, 杨静. 利用改进遗传算法进行复杂网络社团发现[J]. 哈尔滨工程大学学报, 2013, 34(11)：1439-1444.DENG Kun, ZHANG Jian-pei, YANG Jing. Community detection in complex networks using an improved genetic algorithm[J]. Journal of Harbin Engineering University,2013, 34(11)： 1439-1444.

[24]GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. National Academy of Science, 2002, 9(12)： 7821-7826.

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

[26]BLONBEL V D, GUILLAUME J, LAMBIOTTE R, et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics Theory & Experiment,2008(10)： 155-168.

[27]王柏. 社会网络中社团发现及网络演化分析[D]. 北京：北京邮电大学, 2014.WANG Bai. Research on community detecting and evolution analysis in social network[D]. Beijing： Beijing University of Posts and Telecommunications, 2014.