基于个体稳定度博弈的动态社区发现算法研究

许宇光 蒋 飞 朱恩强 潘惊治 谢惠扬



基于个体稳定度博弈的动态社区发现算法研究

许宇光①蒋 飞①朱恩强①潘惊治①谢惠扬*②

①(北京大学信息科学技术学院 北京 100871)②(北京林业大学理学院 北京 100083)

在动态网络中发现社区结构是一个复杂而又有重要意义的课题。该文针对动态网络中的社区发现问题，提出一种基于个体稳定度的博弈论方法(PDG)。在该博弈方法中，网络中的每个节点都是一个独立个体。个体会根据网络中的其他个体的状态，使用最佳应对策略进行社区的选择。针对网络演化过程中的社区更新问题，该文提出了格局检测(Configuration checking)等优化策略，从而大大提高了演化网络的社区发现的效率。最后，在真实演化网络的实验中，与最新的静态和动态社区发现方法进行对比，验证了PDG方法的效率和效果。

动态社区发现；稳定度；模块度；博弈论；格局检测

1 引言

近年来，随着计算机技术的不断发展和移动互联时代的到来，网络科学，特别是社交网络的研究引起了学术界和工业界的广泛关注。其中，社区发现问题是网络科学研究中的一个关键问题。社区是网络中相互连接紧密的节点集合。在不同类型的网络中，社区有着不同的含义。例如，社交网络中，社区通常代表着具有共同兴趣的群 体[8]。社区结构是在中观层面上理解网络结构的有效途径。社区发现问题无论在理论上还是在应用上都有着十分重要的意义[9]。

社区发现问题是一个非常复杂而繁琐的问题。它的复杂性体现在以下几方面：不同类型网络的结构特性与统计特性都有着很大差异[10]，因此，对于这些网络中的社区结构进行统一的量化定义是十分困难的；不同类型的社区发现的需求，例如：非重叠社区发现(disjoint)、重叠社区发现(overlapping)、层次社区发现(hierarchical)、动态社区发现(dynamic)[11]、基于流图的社区发现(based on graph stream)；各种类型的社区发现问题都是NP难问题[6]，因此，当网络规模较大时，社区发现方法的效率是必须要考虑的问题。针对动态社区发现问题，本文设计了一种基于个体稳定度博弈的动态社区发现算法(Permanence Dynamic Game, PDG)。稳定度是一种新的衡量社区划分结果的指标[12]。稳定度指标考虑了个体在社区内部的度和在其他社区的最大度，并结合了个体在社区内的聚集系数，是一种较理想的社区评价指标。博弈中效益函数基于个体稳定度与模块度[13,14]思想设计，能有效避免模块度指标所具有的分辨率限制(resolution limit)，因此能够发现适当规模的社区。

社区发现问题以各种形式出现在不同学科的研究中，相关研究人员从不同角度给出了解决传统的静态社区发现问题的方法。其中，Palla等人[15]提出团渗透的方法解决社区发现问题，并定义在团特征图中有个节点相同的团具有连接关系。Rosvall等人[16,17]提出了一种基于信息编码的社区发现算法Infomap。大量文献的结果证明，该方法能够得到良好的社区发现结果。Raghavan等人[18]提出使用标签传播的方法进行社区发现。Chen等人[19]提出基于博弈论的社区发现算法，并证明了算法的可终止性，在此基础上Alvari等人设计了更加优化的效益函数，并能够发现重叠社区。此外，还有基于概率模型、同步理论、局部优化等其他方法，更加详细的综述请参照文献[6,20,21]。

近年来，动态社区发现受到了广泛关注。Sun等人[22]提出了一种基于信息压缩理论的非参数的动态社区划分方法GraphScope。文中提出了图片段(graph segment)的概念。图片段由多个连续时间片构成。同一个图片段中的网络应该具有容易压缩的性质，否则应放到不同图片段中。这种压缩的方法不仅能将不同的时间片进行分段，而且在压缩过程中自然形成了社区结构。Xie等人[23]提出一种基于标签传播理论的动态社区划分方法——LabelRankT。该方法是一种增量式方法，不仅保证了社区发现算法的速度，而且在一定程度上避免了标签传播方法的不稳定性。此外，其他研究人员也提出了一些解决动态社区发现问题的方法[24,25]。本文的创新性主要有3点：提出了一种基于博弈论[26]的动态社区发现算法，该方法能更好地模拟个体在演化网络中的行为，从而能达到更好的社区发现效果。该算法更加适用于在线社交网络等不断演化的网络；提出了一种结合个体稳定度和模块度的效益函数。该效益函数能高效地发现重叠社区并且消除了模块度所具有的分辨率限制；提出格局检测策略和其他优化策略。

2 基本概念与记号

为了方便表述，我们将在这一节中介绍本文所使用的符号，并阐述评价社区结果的两个重要指标：模块度(modularity)、稳定度(permanence)。弄清这两个指标的不同特性将有助于我们理解PDG博弈算法。

为了引入本文博弈模型中的效益函数，本小节将介绍两个评价社区结构的指标。其中，最为广泛使用的指标是模块度[27]。模块度计算的是每一社区内任意两点连边与否和随机连边概率的差值。模块度的计算公式为

模块度只能衡量社区内的连接情况较随机连接的偏离程度，并不能反映其他社区对该社区内节点的吸引程度。对于某一固定社区结构，计算模块度时，社区与社区之间的连边将不会被考虑。针对此问题，Chakraborty等人[12]提出另一社区结构评价指标稳定度。稳定度指标不仅考虑节点在社区内的作用，同时考虑节点被其他社区的吸引程度。节点的稳定度计算公式为

3 稳定度博弈算法PDG

社交网络中的个体的行为都是自发的，他们出于自身考虑加入社区，并从社区中获得信息、训练、乐趣等。这正好和博弈论中的参与者的行为吻合，即每个参与者都想要在博弈中最大化自己的收益。本文提出一种基于博弈论框架的动态社区发现算法PDG。其中，在每一个静态的时间片下，每个节点都被认为是一个理性的、自私的博弈参与者。然后在一定的规则下，让参与者在网络中进行自由的博弈，最终达到个体收益的最大值。社区划分的最终状态将是一个局部的纳什均衡。

3.1稳定度博弈框架

在稳定度博弈中，参与者为网络中的节点。为方便陈述，在不混淆语义的情况下，我们将不对节点、参与者、个体加以严格区分。我们规定，稳定度博弈中个体的策略为其所归属社区的集合。全局策略空间定义如下：

对应于真实的社区形成过程，每个个体在博弈时可以选择的策略由5种动作生成，分别是加入社区、离开社区、更换社区、建立社区、无动作。博弈中的另一个要素是效益函数，稳定度博弈的效益函数由两部分组成，即增益函数和损失函数。增益函数和损失函数对社区发现结果的好坏起着决定性作用。

从式(3)中可以看出，个体的增益函数由两部分组成。前半部分为个体的内度与最大外度之比的归一化结果。式(3)的后半部分可以理解为节点的实际连边情况与随机连边概率的差值。与模块度不同的是，这里的随机连边只对节点的邻居进行。它可以视为是一种改进的模块度。这种改进既便于快速计算，又能得到良好的结果。

为了便于理解，我们给出一个简单的例子。如图1所示，网络中有3个社区。节点归属于社区时，,。由于节点在社区中的度为2，所以。如式(3)中的后半部分为计算节点在社区内的改进模块度，其中求和符号展开后应为4项，每一项对应节点的一条边所带来的模块度的增加。

从式(4)中可以看出，损失函数也由两部分组成。其中一部分在于节点加入的社区并不能增加社区的聚集性，它通过节点在社区内的聚集系数体现。另一部分是由于其他社区对节点的吸引力使得节点处于当前社区的稳定性下降，它通过节点的最大外社区的吸引力体现。

定义4中的效益函数针对于节点加入单一社区的情况，但真实网络往往存在重叠社区。当加入多个社区可以使参与者的收益值增加时，参与者将加入多个社区，以此形成重叠社区划分。加入多个社区会消耗一定的代价，例如：费用、时间、精力等。针对重叠社区的情况，我们定义效益函数如下：

3.2优化策略及格局检测策略

我们只考虑节点加入两个社区的情况，多于两个社区的情况可以依次类推。

定理1可以用于快速判断是否加入重叠社区，并有效地进行剪枝。当节点加入重叠社区时，绝大多数情况将满足定理2中的条件，即加入的两个社区是包含其边数最多的社区。这时，定理2可以帮助我们快速计算效益值，以用于后续博弈。作为动态社区发现方法的一部分，我们引入格局检测策略。在最近的文献中，格局检测策略在解决NP完全问题上的有效性被证实[30]。一方面用于将上一时间片的社区发现结果传递到下一时间片，以用于下一时间片的稳定度博弈的初始化。另一方面，格局检测策略可以用来判断节点是否处于均衡状态，以用于选择博弈的候选参与者。我们定义一个节点的邻居和邻居的社区归属为节点的格局。具体定义如下：

在某一静态时间片下，格局检测是检测某一节点当前时刻的格局与上一时刻的格局是否相同。如不同，则节点可能处于非均衡状态，该节点将被当作博弈的候选参与者。另外，在完成上一时间片的社区发现进行下一时间片的初始化时，存在于上一时间片并具有与上一时间片相同格局的节点将保持上一时间片的策略。

基于个体稳定度博弈的动态社区发现算法示于表1。

在稳定度博弈中，每次博弈我们从候选参与者中随机选择一个非均衡节点。对于一个静态时间片下，稳定度博弈算法最终会达到一个局部的纳什均衡，即任何个体都无法通过单方面改变自己的策略而获得效益的提升。这里的局部性体现在我们只允许节点加入邻居所处的社区，而不能加入邻居没有加入的社区。

表1 PDG算法

具体地，对于一个新的时间片，首先使用格局检测策略对全局策略进行初始化(2~8行)，即和上个时间片格局相同的节点保持原有策略。对于新出现的节点，执行建立孤立社区的动作。

如果存在非均衡节点，随机选择一个节点。以该节点为参与者，进行稳定度博弈，即在其他节点的策略不变的情况下，选择最佳应对动作，以最大化自身效益(10~13行)。需要注意的是，如果该节点满足定理1的条件，则其不用执行加入社区动作，以达到降低复杂度的目的。但它可以进行更换社区、建立社区动作；如果该节点已经归属于多个社区，则它还可以执行离开社区动作(12行)。当执行一个最佳动作会带来效益的提升时，节点就会执行该最佳动作，然后根据格局检测策略更新非均衡节点队列(14~17行)；否则，节点会保持原有策略不变。不断地选择非均衡节点进行稳定度博弈，直到整个网络处于局部的纳什均衡状态。

4 实验结果与分析

为了定量验证我们稳定度博弈算法的效果，我们在真实动态网络中与先进的静态社区发现、动态社区发现算法进行了对比实验。实验环境是一台处理器主频为2.5 GHz，内存大小为4 GB的PC。本文提出的PDG算法以及实验相关代码见如下网址：https://github.com/Jafree/Permanence-Dynamic-Game。

4.1动态网络数据集

本文使用的动态网络数据集来源于斯坦福的开源数据平台SNAP。本文使用的数据集为AS- Internet。该数据集由于具有大量的时间片，因此能够很好地反映社区发现的效果。我们将在该数据集上进行与静态社区发现算法和动态社区发现算法的对比实验。AS-Internet数据集的具体描述如下：

AS-Internet：该数据集是由跟踪因特网中的边界路由的信息交换而生成的通信网络。它采集于1997年11月到2000年1月，由733个时间片构成。相邻的时间片可能会出现节点加入和离开、边添加和删除。AS-Internet数据集中有些时间片的变化十分剧烈，因此，好的社区发现算法应该能反映出这种变化。每个时间片的节点数、边数，相邻时间片下节点的变化数(加入和离开)和边的变化数(添加和删除)如图1所示。

图1(a1)，图1(a2)分别反映了不同时间片下的节点数和边数，图1(b1)，图1(b2)分别反映了相邻时间片下节点集合的变化数和边集合的变化数。可以看出，大约在400个时间片之前，网络中的节点数和边数逐渐增加，节点集合和边集合的变化也比较缓慢。之后，节点数和边数骤减，网络结构产生了大幅度的变化。最后时刻的时间片也出现连续的显著变化。一个好的动态社区发现算法应该不仅能够在网络平稳变化时准确地发现社区结构、保持社区结构的稳定性，而且还应在网络剧烈变化时通过社区结构的变化体现出网络结构的剧变。

4.2与静态、动态社区发现算法对比

我们将PDG算法与先进的静态社区发现算法和动态社区发现算法进行对比。静态社区发现算法把动态网络中每一时间片当作一个静态网络进行社区划分。两种静态社区发现算法如下：

Infomap[16]：使用信息编码的方法进行社区划分。经过大量文献的报道，该方法可以在较快的速度下获得很好的社区划分结果。

LabelPro[18]：基于标签传播理论的代表方法。此方法基于局部信息，收敛速度快，并可以在一些网络上，获得良好的社区发现结果。

对于动态社区发现算法，我们将与LabelRankT算法进行对比。通过对比实验，我们将看到PDG算法不仅能保持社区结构演化的稳定性，更能够获得很好社区结果。

LabelRankT[24]：基于标签传播理论的改进，是一种动态社区发现算法。该方法较静态标签传播方法具有更高的稳定性。LabelRankT算法有多个较难设置的参数，我们将在实验中使用文献[15]所推荐的可以得到最好结果的参数。

对于没有真实(groud-truth)社区划分结果的网络，就不能使用归一化互信息(NMI)进行结果的评价。尤其是对于动态网络来说，真实社区划分是很难获得的。因此，对于动态重叠社区划分，我们选择改进的模块度作为评价指标。另外，将PDG算法中的重叠损失系数设为足够高，例如令，就可以用于非重叠社区发现。

如图2所示，PDG算法的社区结果要优于其他3个算法。PDG算法所得到的模块度随着网络的不断变化稳步增高，且优于其他3个算法。然而，在中期，模块度出现一个较大的下降，并快速恢复。在最后阶段，PDG的模块度出现一定程度的下降，并低于Infomap的结果。通过仔细观察图1和图2我们可以发现PDG算法的结果的变化趋势正是反映了网络结构的变化，与我们的预期一致。Infomap算法获得了较好的结果，也是最稳定的结果，但是它几乎与网络结构无关。LabelPro算法的结果显示出了标签传播方法惯有的缺点，即不稳定性。LabelRankT作为动态的标签传播方法，在一定程度上克服了不稳定的缺点，但其结果稍劣于PDG算法。经过计算，以模块度为评价指标，PDG算法的效果较LabelRankT提高了23%，较Infomap提高了5%，较LabelPro提高了42%。

为了更加清晰地看到各种算法与网络结构变化的关系，我们绘制出了不同时间片下社区数目的变化，如图3所示。其中，Infomap算法的社区数目稳定，但图1网络的后期有剧烈变化，因此，该算法基本不能反映网络结构的变化。LabelPro算法的社区数目比较少，且处于无规则震荡。LabelRankT算法结果中的社区数目适中，虽能部分反映网络结构的变化，但也有较强的无规则性。PDG算法所发现的社区数目在前期稳定，并逐渐减少，这说明了社区演化时存在社区合并的现象。而中后期社区数目出现较大的波动，恰好反映了网络结构的剧变。

上文中提到，基于模块度优化的社区发现算法具有分辨率限制，即小规模社区不能够被发现，即使它们是团[29]。本文中博弈的效益函数，结合了稳定度和模块度的优点，从而避免了分辨率的限制。图4描述了网络中最大社区规模的变化，即最大社区中的节点数。PDG算法具有较小的最大社区规模，并且网络演化过程中最大社区较稳定。结合图3和图4, PDG算法结果中具有较多的社区数目和较小的最大社区规模，充分说明了PDG算法能够发现小规模的社区。Infomap算法在这一点上也表现出较好的结果。

图2 PDG算法与其他算法的结果对比

图3 社区数目随网络结构变化的对比图

我们绘制出各算法在不同时间片下稳定度指标(permanence)的变化，如图5所示。稳定度指标下，各算法所表现出的特性与在模块度指标下基本相同。但是各算法在该指标下区分度并不大。LankRankT算法表现出较好的结果，但仍然会出现较强的震荡现象。LabelPro算法由于稳定度值为负，因此没有在图5中画出。PDG算法和Infomap算法表现出较稳定的结果。

由于基于节点博弈的方法不易给出确切的时间复杂度，因此，我们给出PDG算法在AS-Internet网络中，对每一个时间片进行社区划分的平均时间，并给出Infomap算法的时间以作为基准。我们给出PDG算法的两个版本，即不带优化策略的版本PDG-Restart和结合优化策略后的版本PDG-Optimized。PDG算法具有很高的效率，特别是优 化策略的使用大大降低了PDG算法的时间复杂度。

5 结束语

博弈论是研究个体在博弈过程中如何在竞争与合作间选择合理策略的理论和方法。网络中的个体直接或者间接地寻求自身利益最大化的行为与博弈论的核心思想是一致的。本文提出了一种基于个体稳定度博弈的动态社区发现算法。与其他静态、动态社区发现算法相比，PDG算法的社区划分结果不仅能够反映真实的网络结构，还可以保持良好的稳定性。在模块度指标下，PDG算法较LabelRankT动态社区发现算法的效果提高了23%。此外，效益函数和优化策略的设计大大提高了PDG算法的效率。如何进一步加快PDG算法的速度和提高算法的精度是下一步的主要研究工作；另外，目前缺少具有真实社区划分的动态网络，这影响了动态社区划分结果的评价。我们将尝试建立可以生成具有真实社区划分的动态网络生成模型。

图4 最大社区规模的对比图

图5 稳定度指标随网络结构变化的对比图

[1] BARABÁSI A and ALBERT R. Emergence of scaling in random networks[J]., 1999, 286(5439): 509-512. doi: 10.1126/ science.286.5439.509.

[2] WATTS D J, DODDS P S, and NEWMAN M E. Identity and search in social networks[J]., 2002, 296(5571): 1302. doi: 10.1126/science.1070120.

[3] WU X, ZHU X, WU G Q,. Data mining with big data[J].&, 2014, 26(1): 97-107. doi: 10.1109/TKDE.2013.109.

[4] BURKE M, MARLOW C, LENTO T. Social network activity and social well-being[C]. International Conference on Human Factors in Computing Systems, Atlanta, Georgia, USA, 2010: 1909-1912. doi: 10.1145/1753326. 1753613.

[5] GIRVAN M and NEWMAN M E. Community structure in social and biological networks[J]., 2002, 99(12): 7821-7826. doi: 10.1073/pnas.12653799.

[6] FORTUNATO S. Community detection in graphs[J]., 2009, 486(3/5): 75-174. doi: 10.1016/j.physrep.2009. 11.002.

[7] XIN Y, XIE Z Q, YANG J,. An adaptive random walk sampling method on dynamic community detection[J]., 2016, 58: 10-19. doi: 10.1016/ j.eswa.2016.03.033.

[8] PALLA G and VICSEK T. Quantifying social group evolution[J]., 2007, 446(7136): 664-667. doi: 10.1038/ nature05670.

[9] ZAKRZEWSKA A. A dynamic algorithm for local community detection in graphs[C]. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2015: 559-564. doi: 10.1145/2808797. 2809375.

[10] NEWMAN M E J. The structure and function of complex networks[J]., 2003, 45(1/2): 40-45. doi: 10.1137 /S003614450342480.

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

WANG Li and CHENG Xueqi. Dynamic community in online social networksp[J]., 2015, 38(2): 219-237. doi: 10.3724/SP.J.1016.2015.00219.

[12] CHAKRABORTY T, SRINIVASAN S, GANGULY N,. On the permanence of vertices in network communities[C]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, USA, 2014: 1396-1405. doi: 10. 1145/2623330.2623707.

[13] NEWMAN M E. Modularity and community structure in networks[J]., 2006, 103(23): 8577-8582. doi: 10.1073/pnas.0601602103.

[14] CHEN M, KUZMIN K, SZYMANSKI B K,. Community detection via maximization of modularity and its variants[J]., 2015, 1(1): 46-65. doi: 10.1109/TCSS.2014.2307458.

[15] PALLA G, DERÉNYI I, FARKAS I,. Uncovering the overlapping community structure of complex networks in nature and society[J]., 2005, 435(7043): 814-818. doi: 10.1038/nature03607.

[16] ROSVALL M and BERGSTROM C T. Maps of random walks on complex networks reveal community structure[J]., 2008, 105(4): 1118-1123. doi: 10.1073/ pnas.0706851105.

[17] HELD P, KRAUSE B, KRUSE R,. Dynamic clustering in social networks using Louvain and Infomap method[J]., 2016, arXiv: 1603.02413.

[18] RAGHAVAN U N, ALBERT R, KUMARA S,. Near linear time algorithm to detect community structures in large-scale networks[J].&, 2007, 76(3 Pt 2): 036106. doi: 10.1103/PhysRevE.76.036106.

[19] ALVARI H, HASHEMI S, and HAMZEH A. Detecting Overlapping Communities in Social Networks by Game Theory and Structural Equivalence Concept[M]. Iran, Springer Berlin Heidelberg, 2011: 620-630. doi: 10.1007/978- 3-642-23887-1_79.

[20] 冷作福. 基于贪婪优化技术的网络社区发现算法研究[J]. 电子学报, 2014, 42(4): 723-729. doi: 10.3969/j.issn.0372-2112. 2014.04.016.

LENG Zuofu. Community detection in complex networks based on greedy optimization[J]., 2014, 42(4): 723-729. doi: 10.3969/j.issn.0372-2112.2014.04. 016.

[21] XIE J, KELLEY S, SZYMANSKI B K,Overlapping community detection in networks: The state-of-the-art and comparative study[J]., 2011, 45(4): 115-123. doi: 10.1145/2501654.2501669.

[22] SUN J, FALOUTSOS C, PAPADIMITRIOU S,. GraphScope: Parameter-free mining of large time-evolving graphs[C]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, California, USA, 2007: 687-696. doi: 10.1145/1281192.1281266.

[23] XIE J, CHEN M, and SZYMANSKI B K. LabelRankT: Incremental community detection in dynamic networks via label propagation[C]. The Workshop on Dynamic Networks Management and Mining, 2013: 25-32. doi: 10.1145/2489247. 2489249.

[24] CAZABET R, AMBLARD F, HANACHI C,. Detection of overlapping communities in dynamical social networks[C]. IEEE Second International Conference on Social Computing, Socialcom/IEEE International Conference on Privacy, Security, Risk and Trust, Passat 2010, Minneapolis, Minnesota, USA, 2010: 309-314. doi: 10.1109/SocialCom. 2010.51.

[25] LIN Y R, CHI Y, ZHU S,. FacetNet: A framework for analyzing communities and their evolutions in dynamic networks[C]. Proceedings of the 17th International Conference on World Wide Web, Beijing, China, 2008: 685-694. doi: 10.1145/1367497.1367590.

[26] LÃ Q D, YONG H C, SOONG B H,. An Introduction to Game Theory[M]. Switzerland, Potential Game Theory. Springer International Publishing, 2016, Chapter 1. doi: 1007/978-3-319-30869-2_1.

[27] NEWMAN M E and GIRVAN M. Finding and evaluating community structure in networks[J].&, 2004, 69(2 Pt 2): 026113-026113. doi: 10.1103/PhysRevE.69.026113.

[28] BARTHELEMY M and FORTUNATO S. Resolution limit in community detection[J]., 2007, 104(1): 36-41. doi: 10.1073/pnas.0605965104.

[29] AGARWAL G and KEMPE D. Modularity-maximizing graph communities via mathematical programming[J].er, 2008, 66(3): 409-418. doi: 10. 1140/epjb/e2008-00425-1.

[30] CAI S and SU K. Local search for Boolean satisfiability with configuration checking and subscore[J]., 2013, 204(9): 75-98. doi: 10.1016/j.artint.2013.09.001.

Research on Dynamic Community Discovery Algorithm Based on Individual Stability Game

XU Yuguang①JIANG Fei①ZHU Enqiang①PAN Jingzhi①XIE Huiyang②

①(,,100871,)②(,,100083,)

In dynamic networks, detecting community structure is a complicated and vital issue. With respect to the community detection problem in dynamic networks, a novel game-theoretic algorithm based on the permanence of agents called Permanence Dynamic Game (PDG) is proposed. In PDG algorithm, each node in the dynamic network is regarded as a self-fish agent. Every agent chooses the best response strategy to select communities he will belong to according to the statuses of other agents. For the evolution of community structure in dynamic networks, the optimization strategy of configuration checking is applied. The configuration checking strategy have many improves the efficiency of the original algorithm. Finally, to verify the effectiveness and efficiency of the proposed method, the method is compared with the state-of-art community detection algorithms on real dynamic networks.

Dynamic community detection; Permanence; Modularity; Game theory; Configuration checking

TP393

A

1009-5896(2017)04-0763-07

10.11999/JEIT161077

2016-10-13；

改回日期：2017-02-22；

2017-03-07

谢惠扬 xhyang@bjfu.edu.cn

国家重点研发计划项目(2016YFB0800700)

National Key Research and Development Project of China (2016YFB0800700)

许宇光： 男，1984年生，博士，研究方向为计算机软件与理论.

蒋 飞： 男，1989年生，博士，研究方向为计算机软件与理论.

朱恩强： 男，1983年生，博士，研究方向为计算机软件与理论.

潘惊治： 女，1992年生，硕士，研究方向为社交网络.

谢惠扬： 女，1963年生，教授，研究方向为应用数学.