一种基于邻域跟随关系的增量社区发现算法

作     者：陈羽中 施松 朱伟平 於志勇 郭昆 CHEN Yu-Zhong;SHI Song;ZHU Wei-Ping;YU Zhi-Yong;GUO Kun

作者机构：福州大学数学与计算机科学学院福州350108 福建省网络计算与智能信息处理重点实验室(福州大学)福州350108 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2017年第40卷第3期

页      面：570-583页

核心收录：

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金(61300104 61300103) 福建省教育厅科技重点项目(JK2012003) 福建省科技厅产学重大项目(2014H6014) 福建省自然科学基金(2013J01230) 福建省科技创新平台项目(2014H2005) 福建省科技平台建设项目(2009J1007)资助~~ 

主　　题：动态社会网络 社区发现 增量分析 邻域跟随 社区演化 

摘      要：社区发现能够揭示真实社会网络的拓扑结构和动态特性.目前的社区发现算法多针对静态社会网络所设计,而绝大多数真实社会网络的社区结构是动态变化的.针对动态社区发现,现有算法通常基于社区结构平稳变化的假设,无法处理演化过程中可能出现的大量社区消亡或涌现等突发事件.为解决有效并高效地发现大规模动态社会网络的社区结构的问题,提出了一种基于邻域跟随关系的社区表示模型Follow-Community,模型刻画的社区由不同角色的节点以及节点间的跟随关系组成,通过发现节点间存在的直接或间接的跟随关系,可将跟随同一个节点的节点所构成的集合归为一个社区.基于该模型提出了一种具有接近线性时间复杂度的邻域跟随算法NFA(Neighborhood Following Algorithm),遍历网络节点一次即可得到静态社会网络的社区结构.进一步扩展得到增量邻域跟随算法iNFA(incremental Neighborhood Following Algorithm).通过更新网络演化过程中相关节点的邻域跟随关系,iNFA可发现动态社会网络的社区结构及社区演化.实验结果验证了算法在大规模动态社会网络社区发现方面具有精度、效率以及稳定性的优势.