基于个体稳定度博弈的动态社区发现算法研究-许宇光.pdf
<p>第 39 卷第 4 期 电 子 与 信 息 学 报 Vol. 39No.4 2017 年 4 月 Journal of Electronics & Information Technology Apr. 2017 基于个体稳定度博弈的动态社区发现算法研究 许宇光蒋 飞朱恩强潘惊治谢惠扬*(北京大学信息科学技术学院 北京 100871) (北京林业大学理学院 北京 100083) 摘 要：在动态网络中发现社区结构是一个复杂而又有重要意义的课题。 该文针对动态网络中的社区发现问题， 提出一种基于个体稳定度的博弈论方法(PDG)。 在该博弈方法中， 网络中的每个节点都是一个独立个体。个体会根据网络中的其他个体的状态， 使用最佳应对策略进行社区的选择。 针对网络演化过程中的社区更新问题， 该文提出了格局检测( Configuration checking)等优化策略 ，从而大大提高了演化网络的社区发现的效率。 最后，在真实演化网络的实验中，与最新的静态和动态社区发现方法进行对比，验证了 PDG 方法的效率和效果。 关键词：动态社区发现；稳定度；模块度；博弈论；格局检测 中图分类号： TP393 文献标识码： A 文章编号： 1009-5896(2017)04-0763-07 DOI: 10.11999/JEIT161077 Research on Dynamic Community Discovery Algorithm Based on Individual Stability Game XU YuguangJIANG FeiZHU EnqiangPAN JingzhiXIE Huiyang(School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China) (College of Science, Beijing Forestry University, Beijing 100083, China) Abstract: 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. Key words: Dynamic community detection; Permanence; Modularity; Game theory; Configuration checking 1 引言近年来，随着计算机技术的不断发展和移动互联时代的到来，网络 科学 ， 特别是社交网络 的研究引起了学术界和工业界的广泛关注1 4-。 其中，社区发现问题是网络 科学研究中的一个 关键问 题5 7-。 社区是网络中相互连接紧密的节点集合。在不同类型的网络中，社区有着不同的含义。 例如，社交网络中，社区 通常 代表着 具有 共同兴趣的群 体8。 社区结构是在中观层面上理解网络结构的有效收稿日期： 2016-10-13；改回日期： 2017-02-22；网络出版： 2017-03-07 *通信作者：谢惠扬 xhyangbjfu.edu.cn 基金项目：国家重点研发计划项目(2016YFB0 800700) Foundation Item: National Key Research and Development Project of China (2016YFB0800700) 途径。 社区发现问题无论在理论上还是在应用上都有着十分重要的意义9。 社区发现问题是一个非常 复杂而繁琐 的问题。它的复杂性体现在以下几方面： 不同类型网络的结构特性与统计特性都有 着 很大差异10， 因此，对于这些网络中的社区结构进行统一 的量化定义是十分困难的；不同类型的社区发现的需求，例如：非重叠社区发现(disjoint )、重叠社区发现(overlapping )、层次社区发现( hierarchical)、动态社区发现(dynamic)11、 基于流图的社区发现(based on graph stream)； 各种类型的社区发现问题都是 NP 难问 题6， 因此， 当网络规模较大时，社区发现方法的效率 是必须要考虑的问题。针对动态社区发现问题，本文设计了一种基于个体稳定度博弈的动态社区发万方数据764 电 子 与 信 息 学 报 第 39 卷 现算法(P ermanence Dynamic Game, PDG)。稳定度是一种新的衡量社区划分结果的指标12。稳定度指标考虑了 个体在社区内部的度和在其他社区的最大度，并结合了个体在社区内的聚集系数，是一种较理想的社区评价指标。 博弈中 效益函数基于个体稳定度与模块度13,14思想设计，能 有效避免模块度指标所具有的分辨率限制(resolution limit )， 因此能够发现适当规模的社区。 社区发现问题以各种形式出现在不同学科的研究 中 ， 相关研究人员从不同角度给出了解决 传统的静态社区发现问题的方法。其中， Palla 等人15提出团渗透的方法解决社区发现问题，并定义在 k 团特征图中有 1k - 个节点相同的 k 团 具有连接关系。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 博弈算法。 动态社区发现所研究的 对象是动态网络。我们将具有 T 个时间片的动态网络 表示为1,GG= 2, TGG ，其 中 (, )t ttG VE= 为时刻 t 下的无向网络结构图。 不同时刻的 网络中可能增加 删除节点、增加删除边。 ,t tt tn Vm E=分别为 t 时刻下网络的节点数和边数。 本文中一些常用的符号：tG 为第 t 个时间片的网络表示； ,nm为某一时刻网络的节点数、边数。 A为某一时刻网络的邻接矩阵； ()Dv 为节点v 的度； ()cIv为节 点 v 归属于社区 c 时的内度 。max()cEv为节点 v 归属于社区 c 时的最大外度；in()cCv为节点 v 归属于社区 c 时的内聚集系数；itS 为tG 网络中的全局策略。 为了引入本文博弈模型中的效益函数，本小节将 介绍两个 评价社区结构的指标。 其中，最为广泛使用的指标是模块度27。 模块度计算的是每一社区内任意两点连边与否和随机连边概率的差值。 模块度的计算公式为 ,() ()122ijc i cj ci jDiDjQAmm=-(1) 其中， c 表示任一社区。 模块度的取值范围是- 11，越高的模块度表示社区 结构越好。但是，有学者发现，模块度指标对于 较 大 规模社区具有倾向性，即较大规模社区会产生较高的模块度。基于模块 优化的社区发现算法，不 能识别小规模 社区，具有分辨率限制28,29。 模块度只能衡量社区内的连接情况 较随机连接的 偏离程度 ，并不能反映其他社区 对该社区内节点的吸引程度 。 对于某一固定社区结构， 计算模块度时，社区与社区之间的 连 边将不会被考虑。 针对此问题， Chakraborty 等人12提出另一社区结构评价指标稳定度。稳定度指标不仅考虑 节点在社区内的作用，同时考虑节点被其他 社区的 吸引 程度 。节点 v 的稳定度计算公式为 inmax() 1Perm() 1 ()() ()ccc cIvv CvE v Dv= × -(2) 其中， c 表示节点 v 所归属的社区， 节点 v 在社区内的作用通过节点 v 的 内度 ()cIv和 社区内聚集系数in()cCv体现。节 点 v 在其他社区的参与程度通过它的最大外度max()cEv体现。 网络在某一社区结构下的稳定度为所有 节点稳定度的平均值。 稳定度指标 的取值范围为- 11。 3 稳定度博弈算法PDG 社交网络中的个体的行为都是自发的，他们出万方数据第 4 期 许宇光等： 基于个体稳定度博弈的动态社区发现算法研究 765 于自身考虑加入社区，并从社区中获得信息、训练、乐趣等。这正好和博弈论中的参与者的行为吻合，即每个参与者都想要在博弈中最大化自己的收益。本文提出一种基于博弈论框架的 动态 社区发现算法PDG。 其中， 在每一个静态的时间片下， 每个节点都 被认为是 一个理性的、自私的 博弈 参与者。 然后在一定的规则下，让 参与者 在网络中进行自由的博弈，最终达到个体收益的最大值。 社区划分的最终状态将是一个局部的纳什均衡。 3.1 稳定度博弈框架 在稳定度博弈 中 ， 参与者为网络中的节点。为方便陈述， 在不混淆 语义 的情况下，我们将 不对 节点、参与者、个体加以严格区分 。 我们规定， 稳定度 博弈中个体的策略为其所归属 社区 的 集合 。 全 局策略空间定义如下： 定义1 博弈中的全局策略空间 S 为网络 G 中所有个体 的 可能策略的笛卡尔乘积 ，即 ( )1=S S ( )2 ()n× ××S S 。 对于网络中的每个参与者 v ，其策略 () ()Sv vS 为其加入社区的集合。 对应于真实的社区形成过程，每个个体在博弈时可以选择的策略由 5 种动作生成，分别是加入社区、离开社区、更换社区、建立社区、无动作。博弈中的另一个要素是效益函数， 稳定度 博弈 的 效益函数由两部分组成，即增益函数和 损失函数。 增益函数和损失函数对社区发现结果 的好坏 起着 决定性作用。 定义2 当个体 v 归属于单一社区 c 时，个体 v的增益函数为 max max( ) , 1() 11()() () () ()() ()2vjcc cccvjSj c AIvGvEvDv IvEvDvDjAm= ×+-(3) 从式(3 )中可以看出，个体的增益函数由两部分 组成。前半部分为个体 v 的内度 ()cIv与最大外度 max()cEv之比的归一化结果。 式(3 )的后半部分可以理解为节点 v 的实际连边情况 与 随机连边概率的差值。 与模块度不同的是，这里的随机连边只对节点 v的邻居进行。它 可以视为是一种 改进的模块度。 这种改进既便于快速计算，又能得到良好的结果。 为了便于理解，我们给出一个简单的例子。如图 1 所示，网络中有 3 个社区。节点 v 归属于社区A 时， () 4AIv= , () 7Dv = 。由于节点 v 在社区 c 中的度为 2， 所以max2AE = 。 如式(3)中 ()AGv的后半部分为计算节点 v 在社区内的改进模块度，其中求和符号展开后应为 4 项，每一项对应节点 v 的一条边所带来的模块度的增加。 定义3 当个体 v 归属于单一社区 c 时，个体 v的损失函数为 maxinmax( ) (v), 11() 1 ()() ()() ()2vjcc ccvjSj S ALv C vIv E vDvDjAm=- +-(4) 从式(4) 中可以看出，损失函数也由两部分组成。其中一部分在于节点加入的社区并不能增加社区的聚集性， 它通过节点在社区内的聚集系数体现。另一部分是由于其他社区对节点的吸引力使得节点处于当前社区的稳定性下降，它通过节点的最大外社区的吸引力体现。 定义4 当个体 v 归属于单一社区 c 时，个体 v的效益函数为 () () ()c ccUv Gv Lv=- (5) 定义 4 中的效益函数针对于节点加入单一社区的情况，但真实网络往往存在重叠社区。当加入多个社区可以使参与者的收益值增加时，参与者将加入多个社区，以此形成重叠社区划分。加入多个社 图 1 AS-Internet 网络结构变化图 万方数据766 电 子 与 信 息 学 报 第 39 卷 区会消耗一定的代价，例如： 费用、 时间、 精力等。针对重叠社区的情况，我们定义效益函数如下： 定义5 设全局策略为 S ， 当个体 v 归属于多个社区时，个体 v 的效益函数为 ( )()() () () 1Scc SvU v U v Sv = -(6) 其中， 为重叠损失系数， ()Sv 为个体 v 加入的社区数目， ()cUv为式(5) 中加入单一社区时的效益。显然，当个体 已经加入了 一个社区时，每多加入一个社区会造成 的损失。 3.2 优化策略及格局检测策略 我们只 考虑节点加入两个社区的情况，多于两个社区的情况可以依次类推。 定理1 设节点 v 加入的单一当前社区为 c ， 如果 ()cUv 且2max() ()cIv E v> ，那么节点 v 的效益值为12Perm ( ) Perm ( )ccvv+-。 其中， max()Ev表示节点 v 在除1c 和2c 外的其他社区中的最大度。 定理 1 可以用于快速判断是否加入重叠社区，并 有效地进行剪枝。 当节点加入重叠社区时，绝大多数情况将满足定理 2 中的条件，即加入的两个社区是包含其边数最多的社区。这时，定理 2 可以帮助我们快速 计算效益值，以用于 后续 博弈。 作为动态社区发现方法的一部分，我们引入格局检测策略。在最近的文献中，格局检测策略在解决 NP 完全问题上的有效性被证实30。 一方面用于将上一时间片的社区发现结果传递到下一时间片 ，以用于 下一时间片的稳定度博弈的 初始化 。 另一方面， 格局检测策略可以用来判断节点是否处于均衡状态，以用于选择博弈的 候选参与者。 我们定义一个节点的邻居和邻居的社区归属为节点的格局。具体定义如下： 定义6 设当前时间片 为 G ， 当前 稳定度博弈的全局策略为 S , ()Nv 表示节点 v 的邻居集合， 那么节点 v 的格局则表示为 Conf ( ) ( , ( ) ( )tGv jSj j Nv= (7) 在 某一静态 时间片下， 格局检测是检测某一节点 当前时刻 的格局与上一时刻的 格局是否相同。如不同，则节点可能处于非均衡状态 ， 该节点将 被 当作 博弈的候选参与者。另外，在完成上一时间片 的社区发现进行下一时间片的初始化时，存在于上一时间片并 具有与上一时间片相同格局的节点 将 保持上一时间片的策略。 基于个体稳定度 博弈的动态社区发现算法示于表 1。 在稳定度博弈中，每次博弈我们从候选参与者中随机选择一个非均衡节点。对于一个静态时间片 表1 PDG算法 下，稳定度博弈算法最终会达到一个局部的纳什均衡，即任何个体都无法通过单方面改变自己的策略而获得效益的提升。这里的局部性体现在我们只允许节点加入邻居所处的社区，而不能加入邻居没有加入的社区。 具体地，对于一个新的时间片，首先使用格局检测策略对全局策略进行初始化( 28 行)，即 和 上个时间片格局相同的节点保持原有策略。对于新出现的节点，执行建立孤立社区的动作。 如果存在非均衡节点，随机选择一个节点。以该节点为参与者，进行稳定度博弈，即在其他节点的策略不变的情况下，选择最佳应对动作，以最大化自身效益 (1013 行)。需要注意的是，如果该节点满足定理 1 的条件，则其不用执行加入社区动作，以达到降低复杂度的目的。但它可以进行更换社区、建立社区动作；如果该节点已经归属于多个社区，则它还可以执行离开社区动作(12 行 )。当执行一个最佳动作会带来效益的提升时，节点就会执行该最佳动作，然后根据格局检测策略更新非均衡节点队列 (1417 行)；否则，节点 会保持原有策略不变。不断地选择非均衡节点进行稳定度博弈，直到 整个网络处于局部的纳什均衡状态。 稳定度博弈算法( PDG) 输入：T snapshots, 12,TGG G 输出：Strategy for each snapshot,12,TSS S 1 for each tG do 2 if 1t = then 3 | ;ttS vV v V 4 agent_pool | ;tv vV 5 end if 6 else 7 11,agent_pool ConfCheck( , , );t t ttS G GS- 8 end else 9 While agent_pool is not empty do 10 ( )node rand ;om pool 11 Perform permanence game for node; 12 Use Theorem 1 to prune action; 13 Select action greedily such that max join leave switch createmax , , , ;u uu u u= 14 if max()tu Sv> then 15 Update ()tSv using responding action; 16 Update agent_pool using configuration checking strategy; 17 end if 18 end while 19 end for 20 return 12,TSS S 万方数据第 4 期 许宇光等： 基于个体稳定度博弈的动态社区发现算法研究 767 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 算法与先进的静态社区发现算法和动态社区发现算法进行对比。 静态社区发现算法把动态网络中每一时间片当作一个静态网络进行社区划分。两种静态社区发现算法如下： Infomap16：使用信息编码的方法进行社区划分 。经过大量文献的报道，该方法可以在较 快的速度下获得很好的社区划分结果。 LabelPro18：基于标签传播理论的代表方法。此 方法基于局部信息 ， 收敛速度 快 ， 并 可以 在一些网络上，获得良好的社区发现结果。 对于动态社区发现算法，我们将与 LabelRankT算法进行对比。通过对比实验 ， 我们将看到 PDG算法不仅能保持社区结构演化的稳定性，更能够获得很好社区结果。 LabelRankT24： 基于标签传播理论的改进，是一种动态社区发现算法。该方法较静态标签传播方法 具有 更高 的稳定性。LabelRankT 算法有多个较难设置的参数，我们将在实验中使用文献 15所推荐的可以得到最好结果的参数。 对于没有真实( groud-truth)社区划分结果的网络，就不能使用归一化 互信息(NMI )进行结果的评价 。 尤其是对于动态网络来说，真实社区划分是很难获得的。 因此，对于动态重叠社区划分， 我们选择改进的模块度作为评价指标。另外，将 PDG 算法中的重叠损失系数 设为足够高，例如令 10 = ，就可以用于非重叠社区发现。 如图 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算法结果中具有较多的社区数目和较 万方数据768 电 子 与 信 息 学 报 第 39 卷 图 2 PDG 算法与其他算法的结果对比 图 3 社区数目随 网络结构变化的对比图 小的最大社区规模，充分说明了 PDG 算法能够发现小规模的社区。Infomap 算法在这一点上也表现出较好的结果。 我们绘制出各算法在不同时间片下稳定度指标(permanence)的变化，如图 5 所示。 稳定度指标下，各算法所表现出的特性与在模块度指标下基本相同。但是各算法在该指标下区分度并 不大。LankRankT 算法表现出较好的结果，但仍然会出现较强的震荡现象。 LabelPro 算法由于稳定度值为负，因此没有在图 5 中画出。 PDG 算法和 Infomap 算法表现出较稳定的结果。 由于基于节点博弈的方法不易给出确切的时间复杂度，因此，我们给出 PDG 算法在 AS-Internet网络中，对每一个时间片进行社区划分的平均时间，并给出 Infomap 算法的时间以作为基准。我们给出PDG 算法的两个版本，即不带优化策略的版本PDG-Restart 和结合优化策略后的版本 PDG- Optimized。 PDG 算法具有很高的效率，特别是优 化策略的使用大大降低了 PDG 算法的时间复杂度。 5 结束语 博弈论是研究个体在博弈过程中如何在竞争与合作间选择合理策略的理论和方法。网络中的个体直接或者间接地寻求自身利益最大化的行为与博弈论的核心思想是一致的。本文提出了一种基于个体稳定度博弈的动态社区发现算法。与其他静态、动态社区发现算法相比， PDG算法的社区划分结果不仅能够反映真实的网络结构，还可以保持良好的稳定性。在模块度指标下，PDG 算法较 LabelRankT动态社区发现算法的效果提高了23% 。此外，效益函数和优化策略的设计大大提高了PD G算法的效率。如何进一步加快PDG 算法的速度和提高算法的精度是下一步的主要研究工作；另外，目前缺少具有真实社区划分的动态网络，这影响了动态社区划分结果的评价。我们将尝试建立可以生成具有真实社区划分的动态网络生成模型。 图 4 最大社区规模 的对比图 图 5 稳定度指标随网络结构变化的对比图 参 考 文 献 1 BARABÁSI A and ALBERT R. Emergence of scaling in random networksJ. Science, 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 networksJ. Science, 2002, 296(5571): 1302. doi: 10.1126/science.1070120. 3 WU X, ZHU X, WU G Q, et al. Data mining with big dataJ. IEEE Transactions on Knowledge & Data Engineering, 2014, 26(1): 97-107. doi: 10.1109/TKDE.2013.109. 4 BURKE M, MARLOW C, LENTO T. Social network activity and social well-beingC. 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 networksJ. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12): 7821-7826. doi: 10.1073/pnas.12653799. 6 FORTUNATO S. Community detection in graphsJ. Physics 万方数据第 4 期 许宇光等： 基于个体稳定度博弈的动态社区发现算法研究 769 Reports, 2009, 486(3/5): 75-174. doi: 10.1016/j.physrep.2009. 11.002. 7 XIN Y, XIE Z Q, YANG J, et al. An adaptive random walk sampling method on dynamic community detectionJ. Expert Systems with Applications, 2016, 58: 10-19. doi: 10.1016/ j.eswa.2016.03.033. 8 PALLA G and VICSEK T. Quantifying social group evolutionJ. Nature, 2007, 446(7136): 664-667. doi: 10.1038/ nature05670. 9 ZAKRZEWSKA A. A dynamic algorithm for local community detection in graphsC. 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 networksJ. SIAM Review, 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 networkspJ. Chinese Journal of Computers, 2015, 38(2): 219-237. doi: 10.3724/SP.J.1016.2015.00219. 12 CHAKRABORTY T, SRINIVASAN S, GANGULY N, et al. On the permanence of vertices in network communitiesC. 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 n</p>
黑公网安备:91230400333293403D
