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

发布时间：2019-04-02 03:04

【摘要】：社区发现能够揭示真实社会网络的拓扑结构和动态特性.目前的社区发现算法多针对静态社会网络所设计,而绝大多数真实社会网络的社区结构是动态变化的.针对动态社区发现,现有算法通常基于社区结构平稳变化的假设,无法处理演化过程中可能出现的大量社区消亡或涌现等突发事件.为解决有效并高效地发现大规模动态社会网络的社区结构的问题,提出了一种基于邻域跟随关系的社区表示模型Follow-Community,模型刻画的社区由不同角色的节点以及节点间的跟随关系组成,通过发现节点间存在的直接或间接的跟随关系,可将跟随同一个节点的节点所构成的集合归为一个社区.基于该模型提出了一种具有接近线性时间复杂度的邻域跟随算法NFA(Neighborhood Following Algorithm),遍历网络节点一次即可得到静态社会网络的社区结构.进一步扩展得到增量邻域跟随算法iNFA(incremental Neighborhood Following Algorithm).通过更新网络演化过程中相关节点的邻域跟随关系,iNFA可发现动态社会网络的社区结构及社区演化.实验结果验证了算法在大规模动态社会网络社区发现方面具有精度、效率以及稳定性的优势.
[Abstract]:Community discovery can reveal the topology and dynamic characteristics of real social networks. Most of the current community discovery algorithms are designed for static social networks, while the community structures of most real social networks are dynamic. For dynamic community discovery, the existing algorithms are usually based on the assumption that the community structure changes steadily, and can not deal with a large number of sudden events, such as community demise or emergence, which may occur in the evolution process. In order to effectively and efficiently discover the community structure of large-scale dynamic social networks, a community representation model based on neighborhood following relationship (Follow-Community,) was proposed. The community described by the model is composed of the nodes of different roles and the following relationships between nodes. By discovering the direct or indirect following relationships between nodes, the set of nodes that follow the same node can be classified into a community. Based on this model, a neighborhood following algorithm (NFA (Neighborhood Following Algorithm),) with near linear time complexity is proposed. The community structure of the static social network can be obtained by traversing the network nodes once. Further extension of incremental neighborhood following algorithm iNFA (incremental Neighborhood Following Algorithm). INFA can discover the community structure and evolution of the dynamic social network by updating the neighborhood following relationship of the relevant nodes in the evolution process of the network. Experimental results show that the algorithm has the advantages of accuracy, efficiency and stability in community discovery of large-scale dynamic social networks.
【作者单位】：福州大学数学与计算机科学学院;福建省网络计算与智能信息处理重点实验室(福州大学);
【基金】：国家自然科学基金(61300104,61300103) 福建省教育厅科技重点项目(JK2012003) 福建省科技厅产学重大项目(2014H6014) 福建省自然科学基金(2013J01230) 福建省科技创新平台项目(2014H2005) 福建省科技平台建设项目(2009J1007)资助~~
【分类号】：TP393.09

【相似文献】