Overlapping community detection algorithm for attributed networks

doi:10.11772/j.issn.1001-9081.2019051177

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (11): 3151-3157.DOI: 10.11772/j.issn.1001-9081.2019051177

• The 2019 CCF Conference on Artificial Intelligence (CCFAI2019) • Previous Articles Next Articles

Overlapping community detection algorithm for attributed networks

DU Hangyuan¹, PEI Xiya¹, WANG Wenjian²

1. College of Computer and Information Technology, Shanxi University, Taiyuan Shanxi 030006, China;
2. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education(Shanxi University), Taiyuan Shanxi 030006, China

Received:2019-05-24 Revised:2019-07-17 Online:2019-09-16 Published:2019-11-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61902227,61673295,61773247), the Project of Shanxi Province Science Foundation for Youths (201701D221097).

面向属性网络的重叠社区发现算法

杜航原¹, 裴希亚¹, 王文剑²

1. 山西大学计算机与信息技术学院, 太原 030006;
2. 计算智能与中文信息处理教育部重点实验室(山西大学), 太原 030006

通讯作者: 王文剑
作者简介:杜航原(1985-),男,山西太原人,副教授,博士,CCF会员,主要研究方向:聚类分析、复杂网络理论;裴希亚(1993-),女,山西长治人,硕士研究生,主要研究方向:机器学习;王文剑(1968-),女,山西太原人,教授,博士,CCF高级会员,主要研究方向:计算智能、机器学习、机器视觉。
基金资助:
国家自然科学基金资助项目（61902227，61673295，61773247）；山西省应用基础研究计划青年项目（201701D221097）。

Abstract

Abstract: Real-world network nodes contain a large number of attribute information and there is an overlapping characteristic between communities. Aiming at the problems, an overlapping community detection algorithm for attributed networks was proposed. The network topology structure and node attributes were fused to define the intensity degree and interval degree of network nodes, which were designed to describe the characteristics of community-the dense interior connection and the sparse exterior connection respectively. Based on the idea of density peak clustering, the local density centers were selected as community centers. On this basis, an iteration calculating method for the membership of non-central nodes about each community was proposed, and the division of overlapping communities was realized. The simulation experiments were carried out on real datasets. The experimental results show that the proposed algorithm has better performance in community detection than LINK algorithm, COPRA algorithm and DPSCD (Density Peaks-based Clustering Method).

Key words: attribute network, overlapping community detection, density peak clustering, community center, node membership

摘要： 针对现实世界的网络节点中包含大量属性信息并且社区之间呈现出重叠特性的问题，提出了一种面向属性网络的重叠社区发现算法。融合网络的拓扑结构和节点属性定义了节点的密集度和间隔度，分别用于描述社区内部连接紧密和外部连接松散的特点。基于密度峰值聚类的思想搜索局部密度中心作为社区中心，在此基础上给出了非中心节点关于各个社区的隶属度的迭代计算方法，实现了重叠社区的划分。在真实数据集上进行了仿真实验，实验结果表明所提算法相对于LINK、COPRA和DPSCD能获得更好的社区划分结果。

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

CLC Number:

TP391

DU Hangyuan, PEI Xiya, WANG Wenjian. Overlapping community detection algorithm for attributed networks[J]. Journal of Computer Applications, 2019, 39(11): 3151-3157.

杜航原, 裴希亚, 王文剑. 面向属性网络的重叠社区发现算法[J]. 计算机应用, 2019, 39(11): 3151-3157.

References

[1] MA T, WANG Y, TANG M, et al. LED:a fast overlapping communities detection algorithm based on structural clustering[J].Neurocomputing, 2016, 207:488-500.
[2] 时京晶. 三种经典复杂网络社区结构划分算法研究[J]. 电脑与信息技术, 2011,19(4):41-43.(SHI J J. Research on three classical complex network community structure partition algorithms[J]. Computer and Information Technology, 2011, 19(4):41-43.)
[3] 赵建军,汪清,由磊,等. 基于信息传递和峰值聚类的自适应社区发现算法[J]. 重庆大学学报, 2018, 41(11):76-83. (ZHAO J J, WANG Q, YOU L, et al. Adaptive community discovery algorithm based on information transfer and peak clustering[J].Journal of Chongqing University, 2018, 41(11):76-83.)
[4] 刘大有,金弟,何东晓, 等.复杂网络社区挖掘综述[J]. 计算机研究与发展, 2013, 50(10):2140-2154. (LIU D Y, JIN D, HE D X, et al. Review of mining of complex network communities[J].Journal of Computer Research and Development, 2013, 50(10):2140-2154.)
[5] 朱牧,孟凡荣,周勇. 基于链接密度聚类的重叠社区发现算法[J]. 计算机研究与发展, 2013, 50(12):2520-2530. (ZHU M, MENG F R, ZHOU Y. Overlapping community detection algorithm based on link density clustering[J]. Journal of Computer Research and Development, 2013, 50(12):2520-2530.)
[6] SARSWAT A, GUDDETI R M R. A novel overlapping community detection using parallel CFM and sequential nash equilibrium[C]//Proceedings of the 2018 10th International Conference on Communication Systems & Networks. Piscataway:IEEE, 2018:649-654.
[7] PALLA G, DERÉNYI I, FARKAS I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435(7043):814-818.
[8] FARKAS I, ÁBEL D, PALLA G, et al. Weighted network modules[J]. New Journal of Physics, 2007, 9:180.
[9] LANCICHINETTI A, FORTUNATO S, KERTESZ J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics, 2009, 11:033015.
[10] ZHANG S, WANG R S, ZHANG X S. Identification of overlapping community structure in complex networks using fuzzy c-means clustering[J]. Physica A:Statistical Mechanics and its Applications, 2007, 374(1):483-490.
[11] AHN Y Y, BAGROW J P, LEHMANN S. Link communities reveal multiscale complexity in networks[J]. Nature, 2010, 466(7307):761.
[12] GREGORY S. An algorithm to find overlapping community structure in networks[C]//Proceedings of the 11th European Conference on Principles of Data Mining and Knowledge Discovery. Berlin:Springer, 2007:91-102.
[13] RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76(3):036106.
[14] 张振宇,朱培栋,王可,等.拓扑结构与节点属性综合分析的社区发现算法[J].计算机技术与发展,2018,28(4):1-5.(ZHANG Z Y, ZHU P D, WANG K, et al. Community detection algorithm for comprehensive analysis of topology and node attributes[J]. Computer Technology and Development,2018,28(4):1-5.)
[15] TIAN Y, HANKINS R A, PATEL J M. Efficient aggregation for graph summarization[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2008:567-580.
[16] FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814):972-976.
[17] WANG M, ZUO W, WANG Y. An improved density peaks-based clustering method for social circle discovery in social networks[J]. Neurocomputing, 2016, 179:219-227.
[18] HE T, CHAN K C C. MISAGA:an algorithm for mining interesting subgraphs in attributed graphs[J]. IEEE Transactions on Cybernetics, 2017, 48(5):1369-1382.
[19] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J].Science,2014, 344(6191):1492-1496.
[20] BENSON A R, GLEICH D F, LESKOVEC J. Higher-order organization of complex networks[J].Science, 2016,353(6295):163-166.
[21] LI P Z, HUANG L, WANG C D, et al. Community detection using attribute homogenous motif[J]. IEEE Access, 2018, 6:47707-47716.
[22] CHEN X, XIA C, WANG J. A novel trust-based community detection algorithm used in social networks[J]. Chaos, Solitons & Fractals, 2018, 108:57-65.
[23] LESKOVEC J,KREVL A. Stanford large network dataset collection[DB/OL].[2019-03-02].https://snap.standford.edu/data/index.html.
[24] SHEN H, CHENG X, CAI K, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A:Statistical Mechanics and Its Applications, 2009, 388(8):1706-1712.
[25] BU Z, GAO G, WU Z, et al. Local community extraction for non-overlapping and overlapping community detection[C]//Proceedings of the 10th International Conference on Advanced Data Mining and Applications. Berlin:Springer, 2014:98-111.

Overlapping community detection algorithm for attributed networks

面向属性网络的重叠社区发现算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

[1]	LYU Jia, XIAN Yan. Co-training algorithm combining improved density peak clustering and shared subspace [J]. Journal of Computer Applications, 2021, 41(3): 686-693.
[2]	CHENG Qiwei, CHEN Qimai, HE Chaobo, LIU Hai. Overlapping community detection method based on improved symmetric binary nonnegative matrix factorization [J]. Journal of Computer Applications, 2020, 40(11): 3203-3210.