ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2018, Vol. 55 ›› Issue (8): 1619-1630.doi: 10.7544/issn1000-1239.2018.20180187

所属专题: 2018数据挖掘前沿进展专题

• 人工智能 • 上一篇    下一篇

基于网络节点中心性度量的重叠社区发现算法

杜航原1,王文剑2,白亮2   

  1. 1(山西大学计算机与信息技术学院 太原 030006);2(计算智能与中文信息处理教育部重点实验室(山西大学) 太原 030006) (duhangyuan@sxu.edu.cn)
  • 出版日期: 2018-08-01
  • 基金资助: 
    国家自然科学基金项目(61673295,61773247);山西省自然科学(青年科技研究)基金项目(201701D221097);山西省回国留学人员科研资助项目(2016-004);山西省研究生联合培养基地人才培养项目(2017JD05) This work was supported by the National Natural Science Foundation of China (61673295, 61773247), the Natural Science Foundation of Shanxi for Youths (201701D221097), the Research Project Supported by Shanxi Scholarship Council of China (2016-004), and the Program for Fostering Talents of Shanxi Province Joint Postgraduate Training Base (2017JD05).

An Overlapping Community Detection Algorithm Based on Centrality Measurement of Network Node

Du Hangyuan1, Wang Wenjian2,Bai Liang2   

  1. 1(College of Computer and Information Technology, Shanxi University, Taiyuan 030006);2(Key Laboratory of Computational Intelligence & Chinese Information Processing(Shanxi University), Ministry of Education, Taiyuan 030006)
  • Online: 2018-08-01

摘要: 基于搜索密度峰值的聚类思想,设计了一种网络节点的中心性度量模型,并提出了一种重叠社区发现算法.首先,定义了网络节点的内聚度和分离度,分别用于描述网络社区内部连接稠密和外部连接稀疏的结构特征,在此基础上计算节点的中心性度量表达节点对社区结构的影响力.接着,利用3δ法则选择中心度异常大的节点作为社区中心.以隶属度表达社区间的重叠特性,并给出了非中心节点的隶属度迭代计算方法,将各节点分配到其可能隶属的网络社区,以实现重叠社区划分.最后,利用人工网络和真实网络对提出的重叠社区发现算法进行验证,实验结果表明:该算法在社区发现质量和计算效率方面都优于许多已有重叠社区发现算法.

关键词: 节点中心度, 社区发现, 重叠网络社区, 隶属度, 密度峰值聚类

Abstract: Based on the idea of density peak clustering method, a centrality measurement model for network nodes is designed, and a new community detection algorithm for overlapping network is also proposed. In the algorithm, the cohesion and separation of network nodes are defined at first, to describe the structural feature of community that the intra links inside one community are dense while the inter links between communities are sparse. Depend on that, centrality measurement is calculated for each node to express its influence on network community structure. Then the nodes with tremendous centralities are selected by the 3δ principle as community centers. The overlapping features between communities are represented by memberships, and the iterative calculation methods for the memberships of non-central nodes are put forward. After that, according to their memberships, all the nodes in network can be allocated to their possible communities to accomplish the overlapping community detection. At last, the proposed algorithm is verified by the simulation on both synthetic networks and social networks. The simulation results reflect that our algorithm outperforms other competitive overlapping community detection algorithms in respect of both detection quality and computational efficiency.

Key words: node centrality, community detection, overlapping network community, membership, density peaks clustering

中图分类号: