一种基于局部模块度的增量式动态社区发现算法

荆笑鹏

摘要：为更好地适应大规模社会网络数据的应用要求，提出一种基于局部模块度的增量式动态社区发现算法。把对起始时间的社会网络执行静态社区发现获得的社区结构和局部模块度作为增量分析的基础，把局部模块度作为优化的条件，使用四种原子操作，逐步演化社区结构。使用社区结构的局部信息，提高了算法的运行效率。避免了设定参数的条件，提高了算法的适应性。实验结果表明，该算法具有一定的实际应用价值。

关键词：局部模块度；增量分析；动态社区发现；社区演化

中图分类号：TP183 文献标识码：A 文章编号：1009-3044（2016）06-0191-04

1 概述

随着社会网络应用和模型的出现和快速发展，例如：病毒式营销[1]、推荐系统[2]、影响力扩散[3]等方面，社会网络分析在这些领域中变得越来越重要，吸引了大量的专家学者进行研究。通常，社会网络数据是代表着系统内成员之间关系的一种图结构，其中节点代表个人，边代表人与人之间的相互作用。例如：公司内部职员之间的交流，学术论文之间的引用和微博用户之间的关注等。社会网络分析的目的在于从低层次的关系数据中挖掘高层次的用于描述系统结构的关系模式[4]。

在过去，大部分分析社会网络的方法是用于计算社会网络的静态信息，没有考虑社会网络成员之间相互作用的时间因素。但是，社会网络的结构是随时间变化的，成员之间的互动关系同样随时间在变化。例如，在新浪微博中，不断地有新用户注册，也有老用户离开，用户之间互动的频率也在变化。因而，对动态社会网络分析的研究也越来越多地被提出[5]。动态社区发现是在空间发现隐含社区结构的基础上，增加时间因素，以发现不同时间点或时间窗口的社区信息和社区变化情况[6]。

为了更好地适应大规模数据集，提高发现动态网络中社区的时间效率，同时克服参数预设的条件，本文提出一种动态社区发现算法。首先使用基于相似度的静态社区发现算法得到开始时间的初始社区结构，作为增量分析的基础。再以初始社区结构为基础，根据不同时间片网络拓扑的变化，将局部模块度作为优化条件，对动态社会网络进行增量分析。本文是基于以下事实：大部分社区通常随着时间的推移逐渐演变，而不会突然出现或消失[7]。

本文第2节介绍一些典型的动态社区发现算法，第3节解释本文算法的细节，第4节对本文算法的有效性进行实验验证，第5节对全文进行总结和展望。

2 相关工作

动态社会网络通常被认为是一系列网络快照，不同的快照之间具有一定时间间隔，每一个快照是网络的一个静态图。因而，对动态变化的社会网络的每一个快照使用静态的分析方法，然后在对得到的社区的演变进行表征就是很自然的思路。

Greene等[8]提出一种在动态社会网络中跟踪社区演化的模型，将社区表征为一系列重要的演化事件，使用社区匹配策略识别和跟踪动态社区。

Palla等[9]使用CPM算法获取每段时间的社区结构，可以得到具有较高连通性的节点的子集，对比和计算每个时间段得到的社区结构，实现对社区演进的分析。

增量动态社区发现算法通过对当前已知的社区结构更新，代替对每一个网络快照进行计算，从而保持良好的社区结构[10]。这种策略能够有效降低时间复杂度，能够适用于大规模的社会网络数据。

Yang等[11]根据物理系统提出一种基于网络中社区结构原理的模型。在模型中，整个网络作为一个四维空间，将网络中边和点的属性作为四维空间中的物理属性，依照万有引力定律的思想逐轮进行增量分析，得到最终的社区划分结果。

单波等[12]使用社会网络的历史信息和当前的拓扑结构来确定当前的社区结构，使用设定的参数控制增量相关的定点是否改变其归属的社区。这种方法提高了时间效率，但没有考虑社区数目和节点数目的变化。

3 基于局部模块度的增量式动态社区发现

3.1 相关概念

3.1.1 动态社会网络

图G表示为一个二元组 G（V， E），其中V表示节点的集合，E表示边的集合。动态社会网络是指图G中的节点V或者边E随时间的变化而改变的，可以用序列[G1，G2，...，Gn]表示。

令[Ci1，Ci2，...，Cim]表示[Gi]的社区划分结果，即[Ci1?Ci2?...?Cim=Gi]，其中m是社区的数量。

3.1.2 模块度[13]

模块度是一种定量手段，定义了发现的社区结构是随机产生的可能性。设一个网络被划分为k个社区，定义[k×k]的对称矩阵e，其元素[eij]表示顶点分别在社区i和社区j中的边。设[ai=jeij]，表示与社区i中所有顶点相连的边，则模块度的定义如下：

5 结束语

本文提出的基于局部模块度的增量式动态社区发现算法，在现实网络中具有一定有效性，能够应用于节点数量较多的社会网络。该算法首先对起始时间的社会网络执行静态的社区发现，并计算当前时间社区结构的局部模块度，将起始时间的社区结构和局部模块度作为下一步算法的基础，根据4种不同的原子操作，以局部相似度作为优化的目标，克服了需要预设参数的条件，选择相应的算法计算社区结构的演化，最后可以得到结束时间的社区结构和社区结构的演化过程。在每一次的操作中，只计算关于社区的局部信息，提高了算法的运行效率和准确率。通过对比实验的结果也能够证明本文的基于局部模块度的动态社区发现算法在实际社会网络中的有效性。本文算法目前只局限于单机运行，如何将此算法在多台主机上并行运行是接下来的研究工作。

参考文献：

[1] Domingos P. Mining social networks for viral marketing[J]. Journal of Retailing & Consumer Services， 2005.

[2] Bao J， Zheng Y， Mokbel M F. Location-based and preference-aware recommendation using sparse geo-social networking data[J]. Gis， 2012：199-208.

[3] Kempe D， Kleinberg J， Tardos， &#. Maximizing the spread of influence through a social network[C]// Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2003：137--146.

[4] Seary A J， Richards W D. Spectral methods for analyzing and visualizing networks： an introduction[J]. Workshop Summary & Papers， 2000：209--228.

[5] Kumar R， Novak J， Raghavan P， et al. On the Bursty Evolution of Blogspace[J]. World Wide Web-internet & Web Information Systems， 2005， volume 8（2）：159-178（20）.

[6] 王莉， 程学旗. 在线社会网络的动态社区发现及演化[J]. 计算机学报， 2015， 38（2）：219-237.

[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. ACM， 2007：717-726.

[8] Greene D， Doyle D， Cunningham P. Tracking the Evolution of Communities in Dynamic Social Networks[C]// Advances in Social Networks Analysis and Mining （ASONAM）， 2010 International Conference on. IEEE， 2010：176-183.

[9] Palla G， Barabási A L， Vicsek T. Quantifying social group evolution.[J]. Nature， 2007， 446（446）：664-7.

[10] Aynaud T， Fleury E， Guillaume J L， et al. Communities in Evolving Networks： Definitions， Detection， and Analysis Techniques[J]. Modeling and Simulation in Science， Engineering and Technology， 2013：159-200.

[11] Yang B， Liu D Y. Force-Based Incremental Algorithm for Mining Community Structure in Dynamic Network[J]. Journal of Computer Science & Technology， 2006， 21（3）：393-400.

[12] 单波， 姜守旭， 张硕，等. IC：动态社会关系网络社区结构的增量识别算法[C]// NDBC2009第26届中国数据库学术会议. 2009.

[13] Newman M E J， Girvan M. Finding and evaluating community structure in networks.[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics， 2004， 69（2 Pt 2）：026113-026113.

[14] Clauset A. Finding local community structure in networks.[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics， 2005， 72（2Pt2）：254-271.

[15] Vinh N X， Epps J， Bailey J. Information Theoretic Measures for Clusterings Comparison： Variants， Properties， Normalization and Correction for Chance[J]. Journal of Machine Learning Research， 2010， 11（1）：2837-2854.

[16] 王慧芳， 黄林鹏， 俞晟. 一种增量式的社区发现算法研究[J]. 计算机仿真， 2008， 25（1）：149-152.