, 肖琰 1,2 , 张云雷 1,2 1. 北京邮电大学 智能通信软件与多媒体北京市重点实验室, 北京 100876;
2. 北京邮电大学 计算机学院, 北京 100876
收稿日期：2016-09-29
基金项目：国家"九七三"重点基础研究发展计划（2013CB329606）；北京市共建项目专项资助
作者简介：吴斌(1969-), 男, 教授。E-mail:wubin@bupt.edu.cn
摘要：动态社团发现是研究网络演化的关键步骤。在数据量迅猛增长的情况下，社团发现的单机算法效率较低。该文提出了一种基于Spark的并行增量动态社团发现算法（parallel incremental dynamic community detection algorithm based on Spark，PIDCDS），为了在GraphX并行图计算平台上通过最大化持久力发现社团，该算法对节点的持久力计算公式进行了有效修正。PIDCDS计算每个时间片中增量节点的持久力指标，更新其社团归属，在保证一定的社团划分准确性的基础上减少计算量。通过与FacetNet动态社团发现算法做比较，该算法能够获得更好的稳定性，同时能发现更真实的社团划分。对比不同规模网络在PIDCDS上的运行时间，发现该时间随着网络节点和边数的增加缓慢增长，性能较高，并且增加执行器核数将在一定程度上加速算法的执行。
关键词：并行动态社团发现持久力Spark增量计算
Parallel incremental dynamic community detection algorithm based on Spark
WU Bin1,2
, XIAO Yan1,2, ZHANG Yunlei1,21.Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications, Beijing 100876, China;
2.School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
Abstract: Dynamic community detection is a crucial step in researching network evolution. Nonparallel algorithms cannot efficiently mine community structures with large amounts of data. This paper presents a parallel incremental dynamic community detection algorithm based on Spark (PIDCDS), which maximizes the total permanence of the vertices in the network to discover the community structure. PIDCDS uses parallel computations on GraphX to calculate a specialized permanence as the community partition metric. Only the permanence of the incremental vertices is computed in each step to derive a new community structure. This algorithm is accurate with less computations. PIDCDS has better stability and more accurately detects the community structure than the FacetNet algorithm. PIDCDS performs well and the execution time increases only slowly as the network scale increases. More cores will accelerate PIDCDS to some extent.
Key words: parallel dynamic community detectionpermanenceSparkincrement computation
不论是传统学科还是新兴学科都离不开对网络的研究[1]，社团发现[2]在其中占据非常重要的一席之地。社团是指在同一网络中，对于一个特定的集合内节点之间的连接比较紧密，但是集合与集合之间的连接比较稀疏[3]，同一社团中的节点或有共同的性质或在网络中扮演着相同的角色。
计算机技术的迅猛发展使得虚拟网络中的社团发现成为了一个研究热点。按照网络拓扑结构是否随时间变化，可以将社团发现划分为静态社团发现和动态社团发现。现已提出很多静态社团发现算法，它们往往基于优化某一目标函数，例如模块度[4]，最后输出整个网络中节点的社团划分。然而静态社团发现忽略了不同时间点网络的变化情况，只考虑了一段时间内网络的叠加形成的网络快照，无法检测到网络社团结构的演化过程。因此，在复杂网络的研究过程中，动态社团发现逐渐被重视起来，而且动态社团是分析研究网络演化的研究点之一，在灾害预警、动物迁徙、人员流失等应用中具有重要的价值[5]。
目前，许多动态社团发现算法采用最大化模块度发现动态网络中的模块结构，实际中具有相同模块度的网络划分在网络连接紧密程度上不同，使得模块度不能很好衡量社团划分质量的好坏。Chakraborty等[6]提出的持久力(permanence)和模块度相似，能够衡量社团质量的好坏，持久力相较于模块度定义更加细粒度，此外，持久力的度量不仅考虑节点在社团内部的连接密度，同时也考虑其与邻居社团的最大外部连接边数，将其应用于静态社团发现时已经能产生很好的效果。持久力对于大规模网络中小社团的发现不会像模块度一样分辨率受限制，其对于网络结构的改变也非常敏感。基于这些情况，本文将持久力度量运用在动态社团发现中，相邻时间片之间采用增量聚类计算方法[7]，首先对第一个时刻的网络进行聚类，得到初始时刻网络的社团分配；然后在其他时刻的网络进行社团划分时，依据前一时刻网络社团结构，结合网络的增量变化部分，调整部分节点的社团归属，使得网络变化满足短时平滑性，并得到符合该时刻网络结构的社团分配。从而利用已知的社团划分结果，避免对全部节点进行计算，有效降低了算法的复杂度，保证算法有很好的可扩展性。
此外，随着网络规模的迅速增大，社团发现的求解变得更复杂，算法耗时且效率不高。为提高计算速度，节省大型和复杂问题的解决时间，并行计算已被提出。在当前分布式环境越来越明显的情况下，MapReduce和Spark[8]的使用更加广泛，Hadoop[9]已经被用来可靠、高效地处理大数据，通过Map(映射)和Reduce(归约)通常可以大量减少算法运行时间，但是MapReduce对数据的处理是分步的，其I/O操作在数据量不大的情况下占据了不少运行时间，这时Spark这种基于内存的计算方式就有很大的优势，它会在内存中以接近“实时”的时间完成所有数据分析，能弥补MapReduce的缺失，其迭代能力更强，更适合社团发现中的图计算，GraphX[10]更是其中专门设计用于图和图并行计算的API (application programming interface)，借助它可以方便且高效地完成图计算的一整套流水作业。目前的并行社团发现算法[11-12]大部分都是静态的，动态社团发现算法也大多是单机实现的，将并行和动态结合起来，不仅能解决静态社团发现不能处理的网络变化问题，也能在速度上得到很大提升，最终得到更广泛地应用。
将持久力公式直接用于这里的并行动态社团发现算法时会带来一些问题，主要是关于节点内部聚集系数的计算，故而本文对节点持久力计算公式进行了修正。事实上，GraphX当前的版本没有提供图的修改操作，而动态网络是随着时间片改变的，本文为解决这个问题，将任何一个时间片中出现过的节点和节点之间的连边都存储在网络图中，通过网络中节点和连边在每个时间片设置的标志位，标示在相应的时间片中网络的哪些节点和连边是存在的。
本文的主要研究内容如下：1) 在保证发现网络社团结构准确性的前提下，修正社团划分度量指标公式，降低并行社团发现算法的时间和空间消耗；2) 提出一种基于Spark GraphX的并行增量动态社团发现算法(PIDCDS)，根据上一时刻网络结构，计算当前时刻增量节点的社团归属，其他节点社团归属不变，保持了网络结构变化的短时平滑性。实验表明，该算法能比较好地探测到动态网络各个时间片的社团结构，比FacetNet算法更稳定，能发现更真实的社团划分，而且网络规模变大时，算法运行时间缓慢增长。
1 基本概念和定义动态网络由一系列网络快照〈g1, g2, …，gt, …〉组成，其中gt表示t时刻的节点和连边组成的网络。对于每个时刻(时间片)，动态社团发现算法都会计算得到当前网络的社团划分{s1, s2, s3, …}，其中每个元素都表示一个社团的节点集合，这里考虑的社团划分是非重叠的，即对于任意的i和j，si∩sj=?。本文采用键值对Map (vertex, community)的数据结构存储每个时刻的节点及所属社团，各个时刻的Map组成整个网络改变过程中每个时间片的社团结构集合。
1.1 持久力持久力(permanence)[6]衡量了网络中节点对于所属社团的依存度。节点v的持久力计算公式为
| ${\text{Perm}}\left( v \right) = \frac{{I\left( v \right)}}{{{E_{\max }}\left( v \right)}} \times \frac{1}{{D\left( v \right)}}- \left[{1-{c_{{\text{in}}}}\left( v \right)} \right].$ | (1) |
 |
| 图 1 节点v的持久力计算[6] |
| 图选项 |
1.2 邻居社团信息基于GraphX并行图计算库，为计算持久力，每个节点需要先获取其邻居社团信息，这里将其定义为(neigCommunity，(vertexNum，triangleNum))的集合形式。对于一个节点，其每个邻居社团对应着这样一组数据，neigCommunity是社团标号，vertexNum是节点在该社团的邻居节点数目，triangleNum是节点在该社团的邻居节点之间的连边数。
1.3 增量节点定义1 ?节点vt+={v|v∈Vt/Vt-1}表示t时刻网络中新增的节点；vt-={v|v∈Vt-1/Vt}表示t-1时刻网络中存在而t时刻网络中不存在的节点。
定义2 ?连边et+={e|e∈Et/Et-1}表示t时刻网络中新增的连边；et-={e|e∈Et-1/Et}表示t-1时刻网络中存在而t时刻消失的边。
定义1和定义2描述了动态网络在每个时刻网络变化的所有可能情况：增加/删除节点，增加/删除边。
定义3 ?增量节点即是出现上述情况时可能改变其社团归属的节点，具体定义如下。
1) 若节点v∈vt+，则v属于增量节点集合。
2) 若v∈vt-，则v所在社团的所有节点都属于增量节点集合。
3) 若连边e∈et+，则有2种情况：如果e有一个端节点属于vt+，那么另一个端节点加入增量节点集合，否则如果e的两端节点不在同一社团内，那么两端节点都加入增量节点集合。
4) 若e∈et-，同时e的两端节点在同一社团内，则整个社团的节点都属于增量节点集合。
1.4 社团发现结果评价指标NMI定义N为混合矩阵(confusion matrix)，其元素Nij表示真实社团i中的节点出现在算法发现时社团j中的节点数量。给定真实社团结构数目CA和算法发现社团数目CB，则2个社团划分之间的相似性度量NMI[13](normalized mutual information)的公式为
| $\begin{gathered} {\text{NMI}}\left( {A, B} \right) = \frac{{-2\sum\limits_{i = 1}^{{C_A}} {\sum\limits_{j = 1}^{{C_B}} {{N_{ij}}\lg \frac{{{N_{ij}}N}}{{{N_{i.}}{N_{.j}}}}} } }}{{\sum\limits_{i = 1}^{{C_A}} {{N_{i.}}\lg \frac{{{N_{i.}}}}{N} + \sum\limits_{j = 1}^{{C_B}} {{N_{.j}}\lg \frac{{{N_{.j}}}}{N}} } }}, \hfill \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;0 \leqslant {\text{NMI}} \leqslant {\text{1}}{\text{.}} \hfill \\ \end{gathered} $ | (2) |
2 基于Spark的并行增量动态社团发现算法描述2.1 并行图计算库Spark GraphX本文的所有并行化算法都基于Spark GraphX并行图计算库设计实现，GraphX库的图迭代计算过程可以抽象为3个部分：1) 消息发送，网络中的连边按照特定的连边方向往顶点发送消息；2) 消息合并，顶点在接收到邻居顶点发送来的消息时，将它们合并为单一的消息或单一的集合；3) 顶点处理程序，图中的每个顶点在合并消息后，顶点处理程序会根据接收到的消息计算，更新各个顶点的属性。GraphX正是以这样的抽象方式使得大规模网络能够分布式计算。
2.2 PIDCDS2.2.1 节点持久力计算公式修正本文的核心思想来源于Chakraborty等[6]提出的一个启发式的旨在获得全局最大持久力的Max_Permanence静态社团发现算法。该算法会迭代多次计算整个网络中节点的持久力，直至算法收敛或者达到最大迭代次数，而在每轮的迭代过程中，每个节点计算其当前持久力以及邻居节点的持久力之和，然后使节点的社团归属分别设置为其邻居社团标号，再计算新的节点持久力以及邻居节点持久力之和，如果新的计算结果更优，则更改该节点的社团归属；否则，重置为原始的社团标号。
但是，本文基于Spark对每个节点进行并行持久力计算时会遇到一个问题，就是关于公式中内部聚集系数的计算。在GraphX中设计实现时，各个节点首先应该收集其自身及邻居节点的邻居社团信息，然后依据这些信息进行顶点计算，更新其社团归属。在这个过程中，当节点的社团归属被设置为其邻居社团标号时，节点之前所属社团以及当前所属社团中的邻居节点的内部聚集系数都将因为该节点的移出或移入发生改变，而这一变化无法通过已经收集到的信息得出，原因是内部聚集系数的改变与邻居节点和该节点的共同邻居数有关，这一信息的存储和收集比较麻烦，如果强行收集该信息，那么每个节点上存储的信息可能就包括其各个邻居节点的具体信息，而非处理好的邻居社团信息，这样就相当于又把整个图存储了多遍，对于大数据计算尤其不可取。所以本文在保证一定正确性的前提下对持久力计算公式进行了修正，修正后的公式为
| ${\text{newPerm}}\left( v \right) = \frac{{I\left( v \right)}}{{{E_{\max }}\left( v \right)}} \times \frac{1}{{D\left( v \right)}}- \left[{1-\frac{{{T_{{\text{in}}}}\left( v \right)}}{{{T_{\max }}\left( v \right)}}} \right].$ | (3) |
2.2.2 最大持久力计算算法最大化图中各个节点的持久力之和是发现社团结构的关键步骤，对于动态网络的每个时间片都是必需的，本文参考Max_Permanence算法的实现思想，修正节点持久力计算公式，按增量节点计算最大持久力，从而得到各个时间片网络的社团划分。
现有的GraphX库中支持迭代计算的接口Pregel已经满足不了这里的需求。因为这里需要在每次迭代的过程中更新整个网络中节点的社团归属，并返回一个新的节点带有社团归属的网络。所以，本文设计了一个新的myPregel迭代函数，伪代码如下。
算法1 ?最大持久力计算myPregel。
输入：图graph、邻居社团信息获取函数information、最大迭代次数maxIterations、顶点计算函数vprog、消息发送函数sendMsg以及消息合并函数mergerMsg。
输出：更新后的节点包含社团标号的图。
1) var info=information(graph)；/*各个节点获取其邻居社团信息*/
2) var g=graph.outerJoin(info.vertices)；
3) var msg=g.aggregate(sendMsg, mergeMsg)；/*发送、合并邻居社团信息*/
4) var activeMsg = msg.count()；
5) var i=0；
6) var oldSum=Int.MinValue；
7) var sum=oldSum+1；/*节点持久力之和*/
8) while (activeMsg>0 and i < maxIterations and sum>oldSum)
9) oldSum=sum；
10) val v=g.vertices.innerJoin(msg)(vprog)；/*顶点计算，更新节点的社团归属*/
11) g=g.outerJoin(v)；
12) sum=g.vertices.map.sum()；
13) i+=1；
14) if (i < maxIterations and sum>oldSum)
15) val c=g.vertices.mapValues.values；
16) val num=c.countByValue()；/*统计每个社团的节点个数*/
17) val newGraph=g.mapVertices；/*更新图节点的所属社团节点数目属性*/
18) info=information(newGraph)；
19) g=newGraph.outerJoin(info.vertices)；
20) msg=g.aggregate(sendMsg, mergeMsg)；
21) activeMsg = msg.count()；
22) return g.mapVertices
最大持久力计算时只有节点增量标志属性为true的节点会完成顶点计算，更新其社团归属。消息发送函数sendMsg首先分别判断连边两端的节点是否属于增量节点，如果是，则将另一端节点的邻居社团信息发送给该节点。增量节点将接收到的来自同一社团节点的消息合并，根据这些信息采用修正后的持久力计算公式计算当前节点及其邻居节点的持久力之和，再将该节点的社团归属分别更改为其邻居社团标号，修改相应信息，计算得到新的持久力之和，最终使得持久力之和最大化。这一过程中各个节点并行完成计算，依据计算结果得到节点带有新社团标号和持久力值的图，如果图中节点持久力之和没有增加或达到最大迭代次数或图中无增量节点，最大持久力计算完毕，得到相应时间片的网络的社团结构划分。
此外，由于g是循环迭代的，为避免RDD (resilient distributed datasets)链太长产生的重复计算，这里对g进行cache操作，而且定义了prevG来保存每次循环中上一次的g，在对g进行操作后，循环结束前将preG释放，既减少了计算量，又减少了RDD的存储空间。
2.2.3 动态社团发现PIDCDSSpark平台的GraphX目前的版本没有提供图的修改操作，如图节点的增加/减少、连边的增加/减少，所以本文实现增量动态社团发现算法的动态网络不能每个时间片增量地改变，而是整个网络动态演化的每个时间片网络拓扑结构的累积，通过网络中节点和连边在每个时间片设置的标志位，标示在相应的时间片中网络的哪些节点和连边是存在的。若某一时间片中节点或者连边存在，则设置这些节点和连边对应时间片的位为真，反之，则为假。通过这样的方式，可以标示每个时间片的动态网络拓扑结构的快照。整个并行增量动态社团发现算法的伪代码如下。
算法2?增量动态社团发现dynamicCDetection。
输入：动态网络拓扑结构累积图graph、时间片数steps、最大迭代次数iterations。
输出：每个时间片网络快照的社团划分。
1) val res；/*存储社团划分结果*/
2) val subG=graph.sub；/*初始时刻网络*/
3) var g=max_perm(subG, iterations)；/*通过最大持久力计算探测初始时刻的社团结构*/
4) res +=g.map.vertices.zip.collect.key.Map；
5) var i=1；/*时间片序号*/
6) def candidateComputeEdgeFunc(ctx)；/*计算网络中的增量节点相关信息，发送消息*/
7) def candidateSetMergeMsg(a, b)；/*聚合消息，判断顶点的增量类型*/
8) while (i < steps)
9) val newGraph = graph.join(g.vertices)；/*利用前一时间片的社团划分结果更新动态网络拓扑结构累积图*/
10) g=newGraph.sub；
11) val c=g.vertices.mapValues.values；
12) val num=c.countByValue()；/*统计每个社团的节点个数*/
13) val vRdd=newGraph.aggregateMessages；/*计算增量节点相关信息*/
14) val ng=g. outerJoin(vRdd).map；/*更新当前时间片网络中节点的增量标志以及所属社团节点数目属性*/
15) g=myPregel(ng, information, iterations)；/*迭代更新增量节点的社团归属*/
16) res+=g.map.vertices.zip.collect.key.Map；
17) i+=1；
18) return res
当进行增量动态社团发现时，初始时刻的网络中节点增量标志全部被置为true，通过Max_permanence函数调用myPregel接口，迭代更新所有节点的社团归属。对于其他时间片的网络，则根据消息发送函数中相邻2个时间片源节点、目的节点和连边的标志位判断得出增量节点相关信息，聚合消息后，得到相应顶点的增量类型，计算出可能改变社团归属的节点集合，增量地计算集合中节点的社团归属。
这里的g也是循环迭代的，故采用与myPregel中一样的方法来减少计算量和RDD存储空间。此外，这里对newGraph等也进行了cache操作，优化计算过程。
3 实验结果与分析本文的实验环境为5台Dell R720服务器组成的小型集群，CPU均为Intel(R) Xeon(R) CPU E5-2620 v2。其中4台服务器为slave节点，1台为master节点，每台服务器的配置如表 1所示。PIDCDS采用Scala2.10.4进行开发，集群环境为Spark1.5.1，运行的模式为Spark On Yarn，其中Yarn对应的Hadoop版本为2.6.0。
表 1 实验所用的服务器配置方案
| 配置参数 | 数值 |
| 处理器 | 2 |
| 硬盘读写速度/(MB·s-1) | 199 |
| 操作系统 | Centos 6.5 |
| JDK版本 | V1.7.0 |
| 磁盘容量/T | 1 |
| 运行内存/GB | 64 |
表选项
3.1 节点持久力计算公式修正的有效性验证为了验证节点持久力计算公式修正的有效性，这里将公式修正前后的Max_Permanence算法在静态模拟网络数据集上的实验结果进行对比，证明了修正后的公式同样能有效地发现网络中的社团结构。
1) 静态模拟网络数据集。
本文选取了Lancichinetti等[14]于2008年提出的基准测试网络作为静态模拟网络数据集，它是在GN (Girvan-Newman)基准网络的基础上引入真实网络的特征，包括网络节点度和社团大小分布的不均匀性。通过设置以下参数即可控制网络的拓扑结构：网络的节点数N，节点的平均度值k，最大的节点度值kmax，节点度的幂律分布指数γ，社团大小的幂律分布指数β，控制节点在所属社团外与社团内连边数之比的混合参数μ。除了上述6个必填参数外，还有2个可选参数：最小社团节点数smin和最大社团节点数smax。
调节参数生成静态网络的同时，对应的标准节点社团划分也会随之产生，便于与算法发现的社团结构进行对比，验证算法结果的准确性。
2) 实验结果比较。
实验根据μ∈[0.1，0.9]产生9组不同混合参数的网络数据，其他参数设为相同的值：N=2 000、k=20、kmax=40、γ=2、β=1、smin=20、smax=60。
分别计算9组网络在公式修正前后的Max_Permanence算法上输出结果的正确性，输出的各个社团划分结果与生成的标准社团划分之间的NMI值如表 2所示。可以看出，2种计算公式的准确性大体上都随着混合参数的增大而减小，这是因为混合参数越大时，网络中的节点更多地与所属社团外的节点相连，网络社团结构相对来说变得不明显，不易探测。而对于同一网络，节点持久力计算公式修正后Max_Permanence算法的结果在一定范围内或变得更优或变得略劣，但同样能比较有效地发现网络中的社团结构，尤其当混合参数较小时，节点在所属社团外的连边数较少，更多地与所属社团内的节点相连，网络社团结构相对明显，公式修正的效果更好。
表 2 公式修正前后社团划分结果比较
| 混合参数 | 公式修正前NMI值 | 公式修正后NMI值 |
| 0.1 | 0.91 | 0.88 |
| 0.2 | 0.89 | 0.95 |
| 0.3 | 0.85 | 0.97 |
| 0.4 | 0.80 | 0.94 |
| 0.5 | 0.77 | 0.90 |
| 0.6 | 0.70 | 0.65 |
| 0.7 | 0.59 | 0.51 |
| 0.8 | 0.48 | 0.46 |
| 0.9 | 0.43 | 0.44 |
表选项
3.2 PIDCDS在人工合成网络数据集上的实验1) 人工合成动态网络数据集和FacetNet算法。
这里采用Li等[15]提出的包含社团结构的动态基准网络数据进行实验，其初始时刻的网络即是节3.1中描述的基准测试网络。该数据生成过程中有4种网络演化事件被定义，分别为节点产生、节点消失、社团扩张收缩以及社团合并分裂。通过向初始时刻静态网络中注入演化事件，并引入演化率控制注入事件后网络的演化速率，产生下一时刻网络数据；通过向不同时刻的网络注入演化事件，即可得到一系列按时间排序的网络快照。因此，生成人工合成动态网络数据时，仍然需要设置节3.1中的参数，同时设置演化率α控制事件的演化速率。
本文为接下来的所有实验设定的5组演化事件依次为社团合并分裂、社团扩张收缩、节点增加、节点减少以及前面4种演化事件同时注入共同作用于动态网络。每组演化事件作用于社团的持续时间片长度取决于α倒数的四舍五入值。实验采用的动态网络数据充分考虑了网络的多种可能变化情况，使实验结果更具全面性。
实验中采用FacetNet动态社团发现算法[16]进行对比，该算法基于进化聚类而非增量聚类，通过非负矩阵分解分析社团及其变化过程，不仅使得任一时刻网络的聚类结果尽可能符合当前真实的社团结构，而且与前一时刻网络社团结构尽量保持一致，但是FacetNet算法需要输入社团个数，而PIDCDS通过最大化持久力自动识别社团个数。
2) 实验结果比较。
实验根据α∈{0.2, 0.4, 0.6, 0.8}生成4组不同演化率的动态基准网络数据，混合参数μ设为0.2，其他参数和节3.1设置相同的值。将这4组数据分别输入PIDCDS和FacetNet算法中，得到的社团划分与真实社团结构的相似性比较结果NMI如图 2所示。
 |
| 图 2 PIDCDS和FacetNet算法在不同数据集上的对比实验 |
| 图选项 |
由于动态网络数据合成的演化率取值不同，在依次注入设定的5组演化事件后，得到动态网络的时间序列长度也不相同，演化率取值越小，时间序列越长，网络结构改变越平滑。而对于同一网络的各个时间片，若演化事件较多，则该时间片网络变化较大，社团结构的探测可能更难，例如注入第5组演化事件的时候。从实验结果可以看出，对于网络结构变化较平滑的情况，PIDCDS算法能够比较好地探测到各个时间片的社团结构。当网络结构变化较大(演化率取值较大)时，除了NMI值略微有所下降外，依然取得很好的结果。
与FacetNet算法相比，整体上看，α较小时，2种算法发现社团结构的能力相差不大，但是随着α的增加，FacetNet算法的性能衰减比PIDCDS算法严重。而且FacetNet算法的结果NMI值变化非常频繁，说明随着时间片的推移该算法本身就不够稳定。虽然在初始时刻FacetNet算法得到的NMI值比PIDCDS算法得到的高，但是随着时间的推移，PIDCDS算法的社团发现结果NMI值变化比较平滑，这与本文选择增量计算有较大的关系，除初始时刻外，每个时间片的社团划分都是在前一时间片结果的基础上修改得到的，过程中只考虑那些可能改变社团归属的节点，其余节点社团标号保持不变，使得算法输出结果更准确，能探测到动态网络中更加真实的社团结构，结果NMI值也更稳定。而FacetNet算法虽然也保持网络结构变化的短时平滑性，但它对任一时刻的网络社团划分都是重新计算而非增量计算，所以其结果NMI值变化较频繁，不够稳定。由于该算法在计算当前时刻结果时尽量保证社团结构与前一时刻一致，随着时间片的推移，多次重新计算累积的误差也使得网络社团划分结果更可能偏离真实社团结构，尤其在α取值较大、网络变化较剧烈时，当前时刻的社团结构往往与前一时刻相差较大、不会保持一致，重新计算累积的误差可能更大，从而导致严重的性能衰减。
3.3 PIDCDS的时间性能及在真实网络数据集上的实验1) PIDCDS的时间性能。
实验根据N∈[10 000，60 000]产生6组不同节点规模的人工合成动态网络数据，以检验随着网络规模的增大算法在运行时间方面的性能。其他参数设置为：k=30、kmax=50、γ=2、β=1、μ=0.2、α=0.5，N取10 000时社团节点数smin=30、smax=70，结合实际情况，当节点总数增加时社团大小很可能也会增大，因此之后每增加1万节点，社团节点数最小和最大值都增加10，得到的实验结果如图 3所示。
 |
| 图 3 不同规模的网络在PIDCDS上的运行时间 |
| 图选项 |
随着网络节点和边的增加，算法运行时间趋于线性增长，由于人工合成动态网络生成的随机性，可能有些网络社团结构比较明显，不需要太多的迭代计算即可得到社团划分，例如N=40 000和N=50 000时，相较于上一组网络数据，算法运行时间增加的很少。
2) 动态真实网络数据集上的实验。
本文选择了某省10个月的通话数据作为动态真实网络数据集进行实验，该数据集中平均每个月的网络包含大约54万节点和100万条连边，网络中的节点为某一用户，当用户之间通话次数大于阈值时，2个用户之间有一条连边。通过这样的处理，以月为单位得到一个10个时间片的通话动态网络数据，总节点数达到160多万，连边数接近568万。
该数据在PIDCDS上的运行时间大约是25 858 s，对比节3.3的实验可以发现，通话动态网络数据的计算时间是偏低的，其中一个重要的原因是人工合成的网络中节点平均度值k统一被取为30，导致节点数为1万时连边数就达到节点数的15倍左右，而这里的真实网络连边数并没有那么多，在邻居社团信息获取、顶点计算等情况时，每个点需要处理的数据更少，速度也就有所提高。此外，本文利用这组真实数据对每个执行器核数取值的加速情况进行实验，得到表 3所示结果。
表 3 不同执行器核数在PIDCDS上的加速情况
| 执行器核数 | 运行时间/s |
| 4 | 25 858 |
| 8 | 20 354 |
| 12 | 20 044 |
表选项
从实验结果可以看出，在一定程度上增加执行器核数可以使算法运行更快，这里的执行器数量保持10不变。但在数据量不变的情况下，核数增加到完全足够该数据实现最大并行化执行时，继续增加执行器核数对算法运行时间的加速比将减少。
4 结论本文基于持久力度量，将并行计算和增量计算相结合，提出了一种动态社团发现算法PIDCDS，在Spark GraphX图并行计算平台上修正持久力计算公式、设计每个时间片的最大持久力计算方法、通过RDD的多次迭代最终完成整个动态网络的社团检测。实验表明: PIDCDS能较好地完成动态网络中的社团挖掘，而且在网络随时间片推移的过程中，通过增量聚类计算保持了网络的短时平滑性，运行效果比FacetNet更好，也能发现更真实的社团划分。同时，PIDCDS在Spark上运行时的性能变化不会很剧烈，即随着网络规模的增大，其执行时间增长缓慢，并且通过在真实通话动态网络数据上的实验发现增大内核数会在一定程度上加速算法的执行。通过动态社团发现，分析网络中相邻时间片社团之间的联系以及社团结构的演化过程将是下一步的研究内容。
参考文献
| [1] | 李国杰. 网络科学:21世纪的元科学[J]. 中国计算机学会通讯, 2016, 12(4): 7.LI Guojie. Network science:The meta science in the 21st century[J]. Communications of the China Computer Federation, 2016, 12(4): 7. (in Chinese) |
| [2] | Fortunato S. Community detection in graphs[J]. Physics Reports, 2010, 486(3): 75–174. |
| [3] | 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. DOI:10.1073/pnas.122653799 |
| [4] | Newman M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577–8582. DOI:10.1073/pnas.0601602103 |
| [5] | 汪小帆, 李翔, 陈关荣. 网络科学导论[M]. 北京: 高等教育出版社, 2012.WANG Xiaofan, LI Xiang, CHEN Guanrong. Network Science:An Introduction[M]. Beijing: Higher Education Press, 2012. (in Chinese) |
| [6] | Chakraborty T, Srinivasan S, Ganguly N, et al. On the permanence of vertices in network communities[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, NY, USA:ACM, 2014:1396-1405. https://arxiv.org/pdf/1406.2426 |
| [7] | Ning H, Xu W, Chi Y, et al. Incremental spectral clustering by efficiently updating the eigen-system[J]. Pattern Recognition, 2010, 43(1): 113–127. DOI:10.1016/j.patcog.2009.06.001 |
| [8] | Zaharia M, Chowdhury M, Das T, et al. Resilient distributed datasets:A fault-tolerant abstraction for in-memory cluster computing[C]//Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. Berkeley, CA, USA:USENIX Association, 2012:141-146. http://www.sciencedirect.com/science/article/pii/S1876610217303041 |
| [9] | Apache. Hadoop[EB/OL].[2016-07-29]. http://hadoop.apache.org/. |
| [10] | Xin R S, Gonzalez J E, Franklin M J, et al. GraphX:A resilient distributed graph system on spark[C]//Proceedingsof the 1st Int Workshop on Graph Data Management Experiences and Systems. New York, NY, USA:ACM, 2013. |
| [11] | Lu H, Halappanavar M, Kalyanaraman A. Parallel heuristics for scalable community detection[J]. Parallel Computing, 2015, 47: 19–37. DOI:10.1016/j.parco.2015.03.003 |
| [12] | Staudt C L, Meyerhenke H. Engineering parallel algorithms for community detection in massive networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(1): 171–184. DOI:10.1109/TPDS.2015.2390633 |
| [13] | Danon L, Diaz-Guilera A, Duch J, et al. Comparing communitystructure identification[J]. Journal of Statistical Mechanics:Theory and Experiment, 2005(9): P09008. |
| [14] | Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4): 046110. DOI:10.1103/PhysRevE.78.046110 |
| [15] | LI Xiaoming, WU Bin, GUO Qian, et al. Dynamic community detection algorithm based on incremental identification[C]//2015 IEEE International Conference on Data Mining Workshop (ICDMW). Atlantic City, NJ, USA:IEEE, 2015. http://ieeexplore.ieee.org/document/7395763/ |
| [16] | 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. New York, NY, USA:ACM, 2008:685-694. |
