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

杜航原; 王文剑; 白亮

doi:10.7544/issn1000-1239.2018.20180187

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

¹(山西大学计算机与信息技术学院太原 030006)
²(计算智能与中文信息处理教育部重点实验室(山西大学) 太原 030006) (duhangyuan@sxu.edu.cn)

基金项目: 国家自然科学基金项目(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).

详细信息

中图分类号: TP391
计量
- 文章访问数: 1539
- HTML全文浏览量: 1
- PDF下载量: 1355
出版历程
- 发布日期: 2018-07-31

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

¹(College of Computer and Information Technology, Shanxi University, Taiyuan 030006)
²(Key Laboratory of Computational Intelligence & Chinese Information Processing(Shanxi University), Ministry of Education, Taiyuan 030006)

摘要

摘要: 基于搜索密度峰值的聚类思想，设计了一种网络节点的中心性度量模型，并提出了一种重叠社区发现算法.首先，定义了网络节点的内聚度和分离度，分别用于描述网络社区内部连接稠密和外部连接稀疏的结构特征，在此基础上计算节点的中心性度量表达节点对社区结构的影响力.接着，利用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.
- node centrality /
- community detection /
- overlapping network community /
- membership /
- density peaks clustering

HTML全文

参考文献(0)

施引文献(28)

期刊类型引用(8)

1.	郝志刚，秦丽. 基于多属性综合评价的食品安全标准引用网络重要节点发现方法. 计算机应用. 2022(04): 1178-1185 . 百度学术
2.	贾慧娟，刘园，史爱静，张霄宏. 一种基于标签传播的重叠社区发现算法. 小型微型计算机系统. 2022(04): 773-778 . 百度学术
3.	刘海姣，马慧芳，赵琪琪，李志欣. 融合用户兴趣偏好与影响力的目标社区发现. 计算机研究与发展. 2021(01): 70-82 . 本站查看
4.	张中军，于来行，李润川. 基于链路结构和转发行为的微博社交网络重叠社区划分方法. 郑州大学学报(理学版). 2021(04): 69-76 . 百度学术
5.	丁建立，邵酉辰. 基于成对约束的多标签传播重叠社区发现方法. 计算机工程与设计. 2020(03): 689-694 . 百度学术
6.	赵霞，张泽华，张晨威，李娴. RGNE:粗糙粒化的网络嵌入式重叠社区发现方法. 计算机研究与发展. 2020(06): 1302-1311 . 本站查看
7.	曾绍华，唐文密，詹林庆，黄秀芬. 基于自适应密度峰值聚类的野外紫色土彩色图像分割. 农业工程学报. 2019(19): 200-208 . 百度学术
8.	林胜青. 基于内容流行度的网络内部缓存智能分布方法. 咸阳师范学院学报. 2019(06): 37-41 . 百度学术