动态社区的点增量发现算法

顾 炎，熊 超

(南京邮电大学 计算机学院，江苏 南京 210023)

动态社区的点增量发现算法

顾 炎，熊 超

(南京邮电大学 计算机学院，江苏 南京 210023)

当前复杂网络中动态社区发现方式大多为孤立地考察当前时间节点，没有利用之前时间节点上社区结构的信息，因而产生了大量的冗余计算。为解决此问题，基于动态社会网络在短时间内未发生过多改变的短时平滑性假设，提出了一种增量聚类动态社区发现算法。该算法将物理学领域万有引力的思想引入到动态社区发现中，针对动态社会网络中的节点，定义了节点间的相互作用力，在t-1与t时刻社区变化差量的基础上，通过比较节点间作用力对节点的社区归属进行了分析和调整，以期在t时刻快速准确地发现动态社区。在安然邮件数据集上的实验表明，当网络中的节点数量达到104以上，提出的算法能够在两分钟左右的时间内挖掘出模块度为0.53左右的社区结构，优于其他几种算法，说明该方法能够快速准确地挖掘出较好的社区结构。

节点；增量；动态网络；社区发现

0 引 言

人类是社会性动物，往往基于类似的喜好、共享的利益和共同的地缘等聚集成群体，这样的群体被称之为社区。总体上，一个社区内部个体之间的交往频繁，不同社区个体之间的交往较少。社区是基于中观尺度视角有效描述社会网络结构的重要指标，而社区发现则是社会网络分析中的基础性研究问题之一。随着Internet的不断发展和普及，开放网络环境下各种信息应用平台不断涌现，为人和人之间的沟通提供了丰富的电子技术手段和虚拟交互环境。

在此应用背景下，社区发现逐步成为工业界和学术界普遍关心的热点问题，人们希望通过对社区进行定量、有效的数据分析和挖掘，发现被虚拟数据所隐藏的人群活动规律。

复杂网络中社区发现主要研究的问题是如何挖掘出内部节点密集互联的子集，即网络中所有节点被分成多个子部分，相比于不同子部分，位于同一个子部分内的节点之间有着较为紧密的链接关系。对社区的发现和分析，有助于确定复杂网络的结构特性，找到有影响力的个人[1]，促进例如目标营销和广告[2]等的应用。社区发现问题一经社会学专家提出，便得到了诸如通信、商务、医疗等领域研究人员的广泛关注。很多研究人员也提出了各自的社区发现方法，但是这些方法大都针对的是静态社区，忽视了由于内部节点频繁的相互作用，复杂网络在不断动态演变这一事实，效果不尽如人意。因此，越来越多的研究者将目光投向动态社区发现。

社区结构的动态分析不仅有助于更好地理解复杂网络的结构，还能有效地预测网络的未来趋势[3]，对于信息传播、网络营销和群体事件的监管等应用都大有裨益。当前大多数动态社区发现方法是将不同时间节点上的复杂网络看成一个独立的网络，这类方法忽略了复杂网络随时间变化的仅是少量信息，如几个节点、几条边的加入以及消失，没有充分利用到前面时间节点上的社区结构信息，产生了大量的冗余计算。

因此通过局部调整复杂网络中少量发生改变的部分，快速得到社区结构的增量式方法成为研究人员关注的新焦点。

基于默认网络中社区数目不发生改变且不考虑节点增加与删减的假设，引入物理学领域万有引力的思想，定义节点间的作用力Fin和Fout，基于动态网络在时刻t-1和t的变化差量，通过比较Fin和Fout的大小判断节点在t时刻是否改变了社区归属，将改变了社区归属的节点划分到Fout最大的社区，其余节点保持原有社区归属，以期达到快速准确发现动态社区的目的。

1 相关工作

动态社区作为一个新兴研究领域，很多问题的提出及其研究方法都与静态社区类似。Berger-Wolf等[3]提出了分析动态社会网络的基本框架，以充分利用社区结构改变的信息来描述动态网络的社区结构。Tantipathananandh等[4]基于文献[3]的研究成果，通过构建社会成本模型，从任意图表序列中挖掘出动态网络社区结构。窦炳琳等[5]基于事件框架分析了DBLP和Facebook的数据，通过研究社区结构演化的进程发现社区间的合并和分裂很大程度上与社区本身的聚类系数相关。

从数学模型的角度，动态网络可抽象为有序的图序列。图序列是网络在不同时间节点上的快照，为社会网络研究人员提供了研究社区演化的素材。Palla等[6]利用一种基于完全子图渗透的算法聚类网络快照，对社会网络中的大小社区分别进行了分析。Asur等[7]利用马尔可夫算法聚类网络快照，基于事件框架机制分别研究了社会网络中的社区及个人。Falkowski等[8]两次使用分裂式层次聚类算法，先从每个网络快照中挖掘出静态社区，构成一组社区图，对社区图再次使用聚类算法得到动态社区。

然而，这些算法虽然准确性较高，但在效率方面往往不尽如人意。为弥补算法在效率上的缺失，在后续的研究中，研究人员又提出了许多增量聚类动态社区发现算法。

Dinh等[9]提出了MIEN(Modules Identification in Evolving Networks)算法，这是一种动态自适应算法，核心在于用紧凑的模块代替整个网络，在缩小网络规模的同时能够及时有效地更新社区结构。王玙等[10]在边的桥系数[11]这一概念的基础上，提出了一种基于桥系数的增量聚类动态社区发现算法，依据桥系数对前一个时间节点上的社区结构进行局部调整，得到当前网络的社区结构。郭进时等[12]仿照文献[13]定义了拓扑势这一概念，通过聚类属性加权序列图得到动态社区。单波等[14]定义了增量相关节点集合，通过分析和调整增量相关节点的社区归属快速挖掘出动态社区结构。

2 增量聚类形式化定义

用带有N个节点v和M条边e的无向图G=(V,E)表示复杂网络，其中V是顶点集合，E是边集合。用C=(C1,C2,…,Ck)表示网络中的社区，CSi(i=1,2,…,k)表示i社区的社区结构。

为刻画动态网络，需要在不同时刻对其采样，得到不同时刻静态网络所对应的一个无向图，这个无向图就是动态网络在这个时刻的网络快照。动态社会网络用G1,G2,…,Gn来表示，其中Gt=(Vt,Et)就是动态网络在t时刻的快照。

用模块度[15]来度量社区划分的好坏，其计算公式如下：

(1)

模块度越高，说明社区结构越好。表1列出了所用概念的符号及其描述。

表1 符号和描述

由短时平滑性假设[16]可知，Gt-1与Gt变化很小。在此背景下，重新聚类Gt会产生大量的重复计算。因此增量聚类动态社区发现主要研究的内容是：针对Gt与Gt-1的变化，基于t-1时刻的聚类结果CSt-1，通过局部调整得到CSt。

问题的形式化描述为：已知t-1时刻的社区结构CSt-1，t-1时刻的网络快照Gt-1，t时刻的网络快照Gt。求t时刻的社区结构CSt。

3 基于节点的增量聚类算法

3.1 算法基本思想

基于节点的增量聚类算法(Vertex-based Incremental Algorithm for Community Detecting，VICA)基于文献[14]的思想：在动态网络中，t时刻大部分节点的社区归属都与t-1时刻相同，只有少量节点会改变其社区归属。在t-1时刻社区结构已知的基础上，将少量改变了社区归属的节点划分给新社区，从而快速得到t时刻的社区结构。

3.1.1 增量节点

在t时刻网络中,若新加入的边的两端节点位于同一社区或者消失的边的两端节点位于不同社区，社区的凝聚力增强，社区结构不会发生改变。相反，若新加入的边的两端节点位于不同社区或者消失的边的两端节点位于同一社区，社区的凝聚力减弱，社区结构可能发生改变，这些节点就是在t时刻可能改变社区归属的节点，称之为增量相关节点[14]，所有增量相关节点构成增量相关节点集合。因为在t时刻网络中大部分节点不会改变其社区归属，所以重点研究增量相关节点。增量相关节点集合和节点改变社区归属的定义如下。

定义1:t时刻的增量相关节点集合IVt={v|e+=(u,v)且C(u)和C(v)不是同一社区或e=(u,v)且C(u)和C(v)是同一社区}。

其中，e+=(u，v)∈(EtEt-1)表示t-1时刻不存在，而在t时刻新增的边；e-=(u，v)∈(Et-1Et)表示t-1时刻存在，而t时刻删减的边。

定义2：若在t-1时刻v∈Ci，在t时刻v∈Cj，i≠j，称节点v在t时刻改变了社区归属。

3.1.2 节点间作用力

对于增量相关节点，关键工作在于判断其在t时刻是否改变了社区归属，若是，将其划分给哪个社区。

文献[14]提出的利用依存度判断增量相关节点在t时刻是否改变了社区归属，并将改变了社区归属的节点划分给其依存度最大的社区的方法未被采用，所需要的是，将改变了社区归属的节点划分给新社区后，整个网络能够获得最佳的模块度。

(2)

(3)

其中，S∈NC(v)，doutS与dS相等，意思相反。

3.1.3 聚类分析

对于在t时刻改变了社区归属的节点，下一步工作就是将其划分给新社区。

借鉴文献[18]中的Theorem 1，但Theorem 1仅适用于t时刻网络中新增节点改变社区归属的情形，并不适用于已存在的节点改变社区归属的情形。为此，提出了命题1，规定在t时刻将改变了社区归属的节点划分至NC(v)中Fout(v)最大的社区，如图1所示。

命题1:将在t时刻改变了社区归属的顶点v划分给NC(v)中Fout(v)最大的社区，整个网络的模块度最佳。

证明:假设顶点v的度为p，社区C是NC(v)中Fout(v)最大的社区，D∈NC(v)，C≠D。当v转移至C时，整个网络模块度为：

(4)

其中,A是其他社区对模块度的影响。

图1 将顶点划分给新社区

当v转移至D时,模块度为：

(5)

(6)

(7)

所以有:

(8)

于是Q-Q'>0，得证。

3.2 VICA算法

VICA算法步骤：在增量相关节点集合IVt中找到那些满足改变社区归属条件的节点v，将其划分到NC(v)中Fout(v)最大的社区中，其余顶点维持原来的社区归属。

VICA算法:

输入：t-1时刻的社区结构CSt-1,i(i=1,2,…,k)，t时刻的网络拓扑Gt;

输出：t时刻的社区结构CSt,i(i=1,2,…,k)。

1.fori=1 tokdo

2.forv∈Ct-1,ido

3.if(v∈IVt)

6.把v划分到社区Cj

7.else

8.v的社区归属不变

9.end if

10.end if

11.end for

12.end for

4 实验及结果分析

4.1 实验设计

实验数据使用安然邮件数据集，这是当前社会网络研究中使用较多的公开数据集之一，它包括安然公司150位高级管理人员从1999年1月至2002年7月期间往来的邮件，这些邮件在安然公司接受美国联邦能源监管委员会调查时被公布到网上，可在CMU计算机学院网站上下载。用这一真实的数据集对VICA算法进行验证，每个邮件联系者在数据集中都通过唯一的一个标识号来表示，每个链接则对应于邮件联系者之间发送的邮件。仿照文献[14]的做法，采集了从2000年4月到2002年4月期间的数据，得到8个类似的网络快照，在这些网络快照的基础上进行实验。

实验环境为Intel(R) Core(TM)2 2.66 GHz Quad CPU，4 GB DRAM，WinXP。为了验证VICA算法在动态社区发现问题上的有效性，用以下三种动态社区发现算法作为对照。

(1)IC算法：由单波等提出，基于短时平滑性假设，通过分析社区结构差量来发现动态社区，根据文献[14]将阈值ε设定为0.1；

(2)Framework算法：由Tantipathananandh等提出，基于染色法的算法框架来分析社团演化，为简便起见，称其为Framework算法；

(3)FaceNet算法：由Lin等[19]提出，基于快照序列，聚类以发现快照时间代价最小的网络社区，为简便起见，称其为FaceNet算法。

4.2 实验对比

首先比较四种算法的运行时间，与文献[14]类似，在上述网络快照中抽样出不同规模的网络，顶点数量分别是16，112，927，10 223，91 469，分别对应101，102，103，104，105这五个数量级。

不同规模网络算法的运行时间如图2所示。

图2 不同规模网络算法的运行时间

由图2可以看出，当网络中顶点的量级不超过103时，四种算法的运行时间相差无几，其中VICA、IC、Framework都在10 s以内，而FaceNet要稍长一些。但是当网络中顶点的量级大于103时，Framework和FaceNet的运行时间大幅增加，其中Framework增加得尤为明显，在105这个量级上运行时间已经达到了8 134 s。而此时VICA和IC的运行时间分别是126 s和118 s，增幅相对平缓。因此得出结论：在相同情况下，VICA和IC的运行时间要低于FaceNet和Framework，并且VICA的运行时间要稍高于IC，但两者的差距并不是很大。

其次比较四种算法得到的社区质量，与文献[14]一样，用模块度Modularity Q进行衡量。

算法结果的模块度如图3所示。

图3 算法结果的模块度

由图3可以看出，VICA、IC、FaceNet的Q值高于Framework，而在VICA、IC、FaceNet三者中VICA的Q值是最高的。此外，VICA、IC、FaceNet的Q值相对稳定，维持在0.53上下，而Framework的Q值则波动较大，最低为0.34，最高能达到0.50。因此得出结论：在相同情况下，相比于IC、FaceNet、Framework，VICA能够得到更好的社区。

综上所述，与IC、FaceNet、Framework算法相比，VICA算法能够在较短的运行时间内得到更好的社区结构。

5 结束语

依据短时平滑性假设，基于复杂网络在短时间内变化小这一事实，引入顶点间的相互作用力，通过分析社区变化差量，识别出改变了社区归属的节点，划分到新的社区中，快速地发现动态社区。实验在真实数据集上验证了VICA算法的准确性和高效性。VICA算法的前提在于复杂网络中社区数目保持不变，并且没有考虑顶点增加和删减的情形，显然不完备，完善这些不足是今后工作的重点。

[1] Berger-Wolf T Y,Saia J.Critical groups in dynamic social networks[R].[s.l.]:[s.n.],2005.

[2] 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.[s.l.]:ACM,2003:137-146.

[3] Berger-Wolf T Y,Saria J.A framework for analysis of dynamic social networks[C]//Proceedings of the 12th ACM SIGKDD international conference on knowledge discovery and data mining.[s.l.]:ACM,2006:523-528.

[4] Tantipathananandh C,Berger-Wolf T Y,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.[s.l.]:ACM,2007:717-726.

[5] 窦炳琳,李澍淞,张世永.基于结构的社会网络分析[J].计算机学报,2012,35(4):741-753.

[6] Palla G,Barabasi A L,Vicsek T.Quantifying social group evolution[J].Nature,2007,446(7136):664-667.

[7] Asur S,Parthasarathy S,Ucar D.An event-based framework for characterizing the evolutionary behavior of interaction graphs[J].ACM Transactions on Knowledge Discovery From Data,2009,3(4):913-921.

[8] Falkowski T.Community analysis in dynamic social networks[M].[s.l.]:[s.n.],2009.

[9] Dinh T,Xuan Y,Thai M T.Towards social-aware routing in dynamic communication networks[C]//28th international conference on performance computing and communications conference.[s.l.]:IEEE,2009:161-168.

[10] 王 玙,高 琳.动态网络桥系数增量聚类算法[J].西安电子科技大学学报,2013,40(1):30-35.

[11] Cheng X Q,Ren F X,Shen H W,et al.Bridgeness:a local index on edge significance in maintaining global connectivity[J].Journal of Statistical Mechanics:Theory and Experiment,2010(10):595-685.

[12] 郭进时,汤红波,王晓雷.基于社会网络增量的动态社区组织探测[J].电子与信息学报,2013,35(9):2240-2246.

[13] 淦文燕,赫 南,李德毅,等.一种基于拓扑势的网络社区发现方法[J].软件学报,2009,20(8):2241-2254.

[14] 单 波,姜守旭,张 硕,等.IC:动态社会关系网络社区结构的增量识别算法[J].软件学报,2009,20:184-192.

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

[16] 王 莉,程学旗.在线社会网络的动态社区发现及演化[J].计算机学报,2015,38(2):219-237.

[17] Ye Z,Hu S,Yu J.Adaptive clustering algorithm for community detection in complex networks[J].Physical Review E,2008,78(2):046115.

[18] Nguyen N P,Dinh T N,Xuan Y,et al.Adaptive algorithms for detecting community structure in dynamic social networks[C]//International conference on computer communications.[s.l.]:IEEE,2011:2282-2290.

[19] 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.[s.l.]:ACM,2008:685-694.

Vertex-based Incremental Algorithm for Dynamic Communities Detecting

GU Yan，XIONG Chao

(School of Computer Science & Technology，Nanjing University of Posts and Telecommunications，Nanjing 210023,China)

Currently,most ways of community detection in dynamic complex networks belongs to separate observations on nonce time nodes without utilization of community structural information on former time nodes,thus more redundant computation has been generated.To solve this problem,on the short-term smoothness assumption that the dynamic community networks could not generate too many changes in short-time interval,an incremental clustering algorithm for detecting dynamic communities has been proposed.The universal gravitation in physic field has been introduced into community detection and mutual forces has been defined between nodes in dynamic community.The community adscription of the node has been analyzed and adjusted through comparison of the mutual forces based on the difference betweent-1 andtinterval so as to detect dynamic community quickly and accurately attinterval.Results of experiments on Enron email dataset show that when the network has more than 104 vertices,the proposed algorithm can detect community structures with modularity at around 0.53 within about two minutes and is more efficient than other algorithms,and thus it can detect dynamic community structures quickly and accurately.

vertex;incremental;dynamic network;community detecting

2016-07-12

2016-11-17 网络出版时间：2017-05-03

国家自然科学基金资助项目(61272422)

顾 炎(1992-)，男，硕士，研究方向为社会计算。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170503.1347.002.html

TP391

A

1673-629X(2017)06-0081-05

10.3969/j.issn.1673-629X.2017.06.017