一种社交网络的增量社区检测算法及实现优化  

An Incremental Community Detection Algorithm for Social Networks and Its Optimization

作　　者：王冰玉 吴振宇[1] 沈苏彬[2] WANG Bing-yu;WU Zhen-yu;SHEN Su-bin(School of Internet of Things,Nanjing University of Posts and Telecommunications,Nanjing 210000,China;School of Computer Science ＆Technology,Nanjing University of Posts and Telecommunications,Nanjing 210000,China)

机构地区：[1]南京邮电大学物联网学院,江苏南京210000 [2]南京邮电大学计算机学院,江苏南京210000

出　　处：《计算机技术与发展》2018年第10期64-69,共6页Computer Technology and Development

基　　金：国家自然科学基金青年项目(61502246);南京邮电大学科研启动基金项目(NY215019)

摘　　要：社区检测是社交网络中常用的分析手段,目的是发现网络中联系较为紧密的节点集群,提取集群,从而进一步探索集群隐含的信息。现实中的社交网络随时间不断增大,传统的社区检测算法在不断增大的网络中运行会十分耗时,这是传统社区检测算法的一个极大弊端。针对该问题,基于传统的K-Clique社区检测算法,提出一种增量K-Clique社区检测算法。与传统K-Clique相比,增量K-Clique使用网络中新增的边和节点去更新已有的社区检测结果,而非在时间片更新时对整个网络重新进行社区检测,算法忽略极少部分的细节换取整体的高效性。实验结果表明,增量社区检测算法较传统算法在执行效率上提高显著,且检测结果与传统K-Clique几乎吻合。Community detection is a common tool to analyze social networks,aiming to discover the clusters of elements that are moreclosely connected in the network and then extract the clusters so as to further explore the hidden information of the cluster. As social network in real life is growing over time,using traditional community detection methods would be very time-consuming. This is a great disadvantage of the traditional community detection algorithm. In view of this,we propose an incremental K-Clique community detectionalgorithm based on the traditional K-Clique,which uses the edges and nodes in the new time slice to update the existing community instead of re-conducting community detection on the entire network at time slice updates. The algorithm ignores a small part of details inexchange for the overall efficiency. The experiment shows that the incremental community detection algorithm improves the execution efficiency significantly compared with the traditional one,and the detection results are almost consistent with the traditional K-clique.

关 键 词：K团 社交网络 社区检测 增量更新 

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