JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2021, Vol. 56 ›› Issue (1): 91-102.doi: 10.6040/j.issn.1671-9352.4.2020.145

Previous Articles    

Overlapping community detection based on density peaks and network embedding

ZHANG Yi-ming, WANG Guo-yin*, HU Jun, FU Shun   

  1. Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
  • Published:2021-01-05

PDF (PC)

28

Abstract: Density peaks is a density-based clustering algorithm. It assumes that the center points of the cluster have higher density and are surrounded by nodes with lower density. Due to the character of graph structure, density peaks cannot be directly applied to network structure, and most of density peaks based community detection algorithms based on density peaks are based on graph topology or adjacency matrix to measure node approximation, which often leads to great computational complexity. This paper proposes an overlapping community detection algorithm based on density and network embedding(OCDDNE). The proposed algorithm firstly embeds the network structure characteristics of nodes in network structure through network embedding, and then clusters the embedded node vectors based on the improved method of density peaks, so that the structural relationship between the encoded vectors can be better revealed and the overlapping communities which each node is located is determined. Experiments on synthetic networks and real networks data show that the proposed algorithm can efficiently find the overlapping community structure in networks, and it is superior to other algorithms especially in complex networks with high structural complexity.

Key words: overlapping community detection, network embedding, density peak, complex network, belonging coefficient

CLC Number: 

  • TP391
[1] RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191):1492-1496.
[2] CUI P, WANG X, PEI J, et al. A survey on network embedding[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 31(5):833-852.
[3] 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.
[4] 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.
[5] GREGORY S. Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2010, 12(10):103018.
[6] LU M, ZHANG Z, QU Z, et al. LPANNI: overlapping community detection using label propagation in large-scale complex networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 31(9):1736-1749.
[7] AHN Y Y, BAGROW J P, LEHMANN S. Link communities reveal multiscale complexity in networks[J]. Nature, 2010, 466(7307):761-764.
[8] LANCICHINETTI A, FORTUNATO S, KERTÉSZ J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics, 2009, 11(3):033015.
[9] LANCICHINETTI A, RADICCHI F, RAMASCO J J, et al. Finding statistically significant communities in networks[J]. PloS One, 2011, 6(4):e18961.
[10] WHANG J J, GLEICH D F, DHILLON I S. Overlapping community detection using seed set expansion[C] //Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. New York: ACM, 2013: 2099-2108.
[11] BAI X, YANG P, SHI X. An overlapping community detection algorithm based on density peaks[J]. Neurocomputing, 2017, 226:7-15.
[12] 黄岚, 李玉, 王贵参, 等. 基于点距离和密度峰值聚类的社区发现方法[J]. 吉林大学学报(工学版), 2016, 46(6):2042-2051. HUANG Lan, LI Yu, WANG Guishen, et al. Community detection method based on vertex distance and clustering of density peaks[J]. Journal of Jilin University(Engineering and Technology Edition), 2016, 46(6):2042-2051.
[13] PEROZZI B, AL-RFOU R, SKIENA S. Deepwalk: online learning of social representations[C] //Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data mining. New York: ACM, 2014: 701-710.
[14] GROVER A, LESKOVEC J. node2vec: scalable feature learning for networks[C] //Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data mining. New York: ACM, 2016: 855-864.
[15] WANG D, CUI P, ZHU W. Structural deep network embedding[C] //Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data mining. New York: ACM, 2016: 1225-1234.
[16] TANG J, QU M, WANG M, et al. Line: large-scale information network embedding[C] //Proceedings of the 24th International Conference on World Wide Web. Switzerland: ACM, 2015: 1067-1077.
[17] LI A Q, AHMED A, RAVI S, et al. Reducing the sampling complexity of topic models[C] //Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2014: 891-900.
[18] MIKOLOV T, SUTSKEVER I, CHEN K, et al. Distributed representations of words and phrases and their compositionality[C] //Advances in Neural Information Processing Systems. Lake Tahoe: ACM, 2013: 3111-3119.
[19] RECHT B, RE C, WRIGHT S, et al. Hogwild: a lock-free approach to parallelizing stochastic gradient descent[C] //Advances in Neural Information Processing Systems. Granada: ACM, 2011: 693-701.
[20] MCDAID A F, GREENE D, HURLEY N. Normalized mutual information to evaluate overlapping community finding algorithms[J]. arXiv Preprint arXiv:1110.2515, 2011.
[21] COLLINS L M, DENT C W. Omega: a general formulation of the rand index of cluster recovery suitable for non-disjoint solutions[J]. Multivariate Behavioral Research, 1988, 23(2):231-242.
[22] 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.
[23] HUBERT L, ARABIE P. Comparing partitions[J]. Journal of Classification, 1985, 2(1):193-218.
[24] XIE J, SZYMANSKI B K. Towards linear time overlapping community detection in social networks[C] //Pacific-Asia Conference on Knowledge Discovery and Data Mining. Berlin: Springer, 2012: 25-36.
[25] COSCIA M, ROSSETTI G, GIANNOTTI F, et al. Demon: a local-first discovery method for overlapping communities[C] //Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2012: 615-623.
[26] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4):046110.
[27] ZACHARY W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4):452-473.
[28] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12):7821-7826.
[29] YIN H, BENSON A R, LESKOVEC J, et al. Local higher-order graph clustering[C] //Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2017: 555-564.
[30] GLEISER P M, DANON L. Community structure in jazz[J]. Advances in Complex Systems, 2003, 6(4):565-573.
[31] KNUTH D E. The stanford graphbase: a platform for combinatorial computing[M]. New York: ACM Press, 1993.
[32] LESKOVEC J, MCAULEY J J. Learning to discover social circles in ego networks[C] //Advances in Neural Information Processing Systems. Lake Tahoe: ACM, 2012: 539-547.
[1] Kan XU,Rui-xin LIU,Hong-fei LIN,Hai-feng LIU,Jiao-jiao FENG,Jia-ping LI,Yuan LIN,Bo XU. Academic paper recommendation based on heterogeneous network embedding [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(11): 35-45.
[2] YANG Ya-ru, WANG Yong-qing, ZHANG Zhi-bin, LIU Yue, CHENG Xue-qi. Social network user identity linkage model based on comprehensive information [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2019, 54(9): 105-113.
[3] WANG Xin, ZUO Wan-li, ZHU Feng-tong, WANG Ying. Important-node-based community detection algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(11): 67-77.
[4] Si-min WEI,Xian-hua ZHANG,Zhen ZHANG,Qing-chun MENG,Xia-ran ZHANG. Virtual brand community opinion leader recognition based on complex network——example of the Meizu Flyme community [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2018, 53(11): 26-34.
[5] SUN Song-tao, HE Yan-xiang, CAI Rui, LI Fei, HE Fei-yan. Comparative study of methods for Micro-blog sentiment evaluation tasks [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(11): 43-50.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd