摘要
传统的动态网络社区发现方法是对每个时刻的网络分别通过静态算法进行社区检测,进而分析各个社区之间的关系,可能导致较高的时间开销.根据相邻时刻之间的拓扑结构变化不大的特点,提出一种考虑社区结构稳定度和增量相关节点相结合进行社区发现的方法 IPCSCDA(Incremental Parallel Community Detection Algorithm Considering The Stability Of Community Structure).算法以前一个时刻得到的社区结构为基础,通过基于Jaccard系数的社区归属判定条件来调整增量相关节点的社区归属,同时考虑每个社区的结构稳定度,以发现动态网络社区.通过增量方法分析相邻时刻网络的变化,避免了对整个网络进行重新划分,从而大大减少了算法的时间开销.在人工数据集和真实数据集上的实验表明,提出的算法具有良好的动态社区发现能力.
One of the traditional ways for detecting dynamic communities is to find the communities at each interval through the static community detection algorithms. However,it usually leads to high computation complexity. In this paper,a novel algorithm considering the stability of community structure with the strategy of incremental related vertices with the name IPCSCDA( Incremental Parallel Community Detection Algorithm Considering The Stability Of Community Structure) is proposed. Depending on the communities found at the previous interval,the new algorithm uses Jaccard index to adjust the incremental related vertices belong to while considering the stability of community structures at the same time. The repartitioning of the whole network can be avoided by incrementally analyzing the variation of the networks,so that the time cost can be greatly reduced. Experiments on artificial and real datasets show that the proposed algorithm is capable of discovering dynamic communities effectively.
作者
郭昆
李国辉
陈羽中
吴伶
许倩
GUO Kun;LI Guo-hui;CHEN Yu-zhong;WU Ling;XU Qian(College of Mathematics and Computer Sciences, Fuzhou University, Fuzhou 350116, China;Fujian Provincial Key Laboratory of Network Computing and Intelligent Information Processing ,Fuzhou 350116 ,China;Key Laboratory of Spatial Data Mining & Information Sharing, Ministry of Education, Fuzhou 350002, China;School of Economics and Management, Fuzhou University, Fuzhou 350116, China;State Grid Electic Power Company,Fuzhou 350003 ,China)
出处
《小型微型计算机系统》
CSCD
北大核心
2018年第7期1548-1553,共6页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(61300104
61300103)资助
福建省科技创新平台建设项目(2009J1007)资助
福建省自然科学基金项目(2013J01230
2013J01232)资助
福建省高校杰出青年科学基金项目(JA12016)资助
福建省高等学校新世纪优秀人才支持计划项目(JA13021)资助
福建省教育厅科技重点项目(JK2012003)资助
福建省科技厅产学重大项目(2014H6014)资助
福建省科技创新平台计划项目(2009J1007
2014H2005)资助
海西政务大数据应用协同创新中心
关键词
动态网络
增量算法
标签传播
社区稳定度
dynamic community
incremental algorithm
label propagation
community stability