基于拓扑势的增量式动态社区发现方法  

Incremental dynamic community detection algorithm based on topology potential

作　　者：何婧 王志晓[1] 候梦男 芮晓彬 高菊远 HE Jing;WANG Zhi-xiao;HOU Meng-nan;RUI Xiao-bin;GAO Ju-yuan(School of Computer Science and Technology,China University of Mining and Technology,Xuzhou 221116,China)

机构地区：[1]中国矿业大学计算机科学与技术学院,江苏徐州221116

出　　处：《计算机工程与设计》2019年第1期45-52,共8页Computer Engineering and Design

基　　金：国家自然科学基金项目(61402482);中国博士后基金项目(2015T80555);江苏省博士后基金项目(1501012A)

摘　　要：为保证动态社区发现效率,提高动态社区划分结果的准确性,提出一种基于拓扑势的增量式动态社区发现方法。增量式方法以前一个时间片网络的社区划分结果为基础,动态调整网络变化部分的社区归属,其余部分的社区结构仍保持不变。传统增量式方法只考虑增量节点,实际上,增量节点的邻居节点也会受到影响而出现社区归属的变化。该方法考虑增量节点,依据拓扑势场理论,进一步计算增量节点影响范围内的邻居节点,重新判定这些节点的社区归属。在真实和人工网络上的实验结果表明,该算法扩大了传统增量更新的范围,在保证计算效率的基础上,有效提高了社区划分结果的准确性。To raise the accuracy of dynamic community detection while ensuring the efficiency of dynamic community detection,an incremental dynamic community detection algorithm based on topology potential was proposed.Incremental clustering revises the previous community structure to generate current community structure,and only re-defines community ownership of those changed vertices with community structure of rest partition maintaining unchanged.Actually,neighbor vertices of incremental vertices also change their community ownership under the influence of network evolution.The proposed method not only took incremental vertices into consideration,but also re-computed those vertices within the influence sphere of incremental partition.Experimental results on both synthetic and real-world networks demonstrate that the proposed method expands the re-computing scope of traditional incremental methods,which can ensure the efficiency and effectively improve the accuracy of dynamic community detection.

关 键 词：拓扑势 数据场 社交网络 动态社区发现 增量分析 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]