Computer Science ›› 2019, Vol. 46 ›› Issue (10): 39-48.doi: 10.11896/jsjkx.180901644

• Big Data & Data Science • Previous Articles     Next Articles

Topological Structure Based Density Peak Algorithm for Overlapping Community Detection

FENG Yun-fei1, CHEN Hong-mei1,2   

  1. (School of Information Science and Technology,Southwest Jiaotong University,Chengdu 611756,China)1
    (Key Laboratory of Cloud Computing and Intelligent Technology,Southwest Jiaotong University,Chengdu 611756,China)2
  • Received:2018-09-04 Revised:2018-11-14 Online:2019-10-15 Published:2019-10-21

Abstract: With the continuous development of modern network science,people’s lives have been greatly facilitated.The study on complex networks is an important driving force for the development of modern network science,and the community is an important structure for research on complex networks.Most of the existing community discovery methods are highly complex,so this paper applied the density peak clustering algorithm proposed in recent years to community discovery,and proposed an efficient community discovery algorithm.Due to the particularity of the data structure of complex network,the complex network data are stored in the form of topological graphorad jacency matrix,and thus how to effectively calculate the distance between nodes and the local density of each node,and how to select the core nodes of the community are the key problems when density peak clustering algorithm is applied tocommunity discovery.In light of this,this paper calculated the local density of each node by the degree of each node and its neighbor nodes in the network topological graph,measured the distance between nodes by the similarity between nodes,and discretized the distance to expediently select the core nodes for this algorithm.Moreover,the core hop values were defined to accurately select community centers,thus avoiding the large communities annex small communities.Experiments were carried out on the LFR artificial network dataset and the real network dataset with the evaluation indexes of the extended modularity,the adjusted rand coefficient and the normalized mutual information.Experimental results in real networks show that the proposed algorithm has good effects and obvious advantages in some real networks compared with other algorithms.In the artificial network,the algorithm also has advantages.Therefore,the proposed algorithm is more stable than other algorithms.

Key words: Community detection, Data mining, Density peak, Overlapping community, Topological structure

CLC Number: 

  • TP391
[1]FORTUNATO S.Community detection in graphs[J].Physics Reports-Review Section of Physics Letters,2010,486(3):75-174.
[2]NEWMAN M E J.The structure and function of complex networks[J].Siam Review,2003,45(2):167-256.
[3]YU Z D,YU H Q.Micro-Blog user recommendation based on community discovery and topic analysis[J].Journal of East China University of Science and Technology(Natural Science Edition),2014,40(6):763-768.(in Chinese)
余紫丹,虞慧群.基于社区发现及主题分析的微博用户推荐[J].华东理工大学学报(自然科学版),2014,40(6):763-768.
[4]MA F M,WANG G.Method for commodity recommendation based on user community[J].Computer & Digital Engineering,2013,41(8):1354-1356.(in Chinese)
麻风梅,王刚.基于用户社区的商品推荐方法[J].计算机与数字工程,2013,41(8):1354-1356.
[5]PAN W F,LI B,SHAO B,et al.Service classification and re-commendation based on software networks[J].Chinese Journal of Computers,2011,34(12):2355-2369.(in Chinese)
潘伟丰,李兵,邵波,等.基于软件网络的服务自动分类和推荐方法研究[J].计算机学报,2011,34(12):2355-2369.
[6]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of National Academy of Science,2002,99(12):7821-7826.
[7]NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E Statistical Nonli-near and Soft Matter Physics,2004,69(6):066133.
[8]DERENYI I,PALLA G,VICSEK T.Clique percolation in random networks[J].Physical review letters,2005,94(16):160202.
[9]CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical Review E Statistical Nonlinear and Soft Matter Physics,2004,70(6):066111.
[10]DANON L,DIAZGUILERA A,ARENAS A.Effect of size heterogeneity on community identification in complex networks[J].Journal of Statistical Mechanics:Theory and Experiment,2006,2006(11):P11010.
[11]ZHU X,GHAHRAMANI Z.Learning from labeled and unlabeled data[J].Technology Report,2002,3175(2004):237-244.
[12]LIU S C,ZHU F X,GAN L.A label-propagation-probability-based algorithm for overlapping community detection[J].Chinese Journal of Computers,2016,39(4):717-729.(in Chinese)
刘世超,朱福喜,甘琳.基于标签传播概率的重叠社区发现算法[J].计算机学报,2016,39(4):717-729.
[13]ZHANG X K,REN J,SONG C,et al.Label propagation algorithm for community detection based on node importance and label influence[J].Physics Letters A,2017,381(33):2691-2698.
[14]LI L,JIAO L,ZHAO J,et al.Quantum-behaved discrete multi-objective particle swarm optimization for complex network clustering[J].Pattern Recognition,2017,63:1-14.
[15]LIU Q,ZHOU B,LI S,et al.Community detection utilizing a novel multi-swarm fruit fly optimization algorithm with hill-climbing strategy[J].Arabian Journal for Science & Engineering,2016,41(3):807-828.
[16]JIANG S Y,YANG B H,WANG L X.An adaptive dynamic community detection algorithm based on incremental spectral clustering[J].Acta Automatica Sinica,2015,41(12):2017-2025.(in Chinese)
蒋盛益,杨博泓,王连喜.一种基于增量式谱聚类的动态社区自适应发现算法[J].自动化学报,2015,41(12):2017-2025.
[17]ZHOU X,LIU Y,WANG J,et al.A density based link clustering algorithm for overlapping community detection in networks[J].Physica A Statistical Mechanics & Its Applications,2017,486(2017):65-78.
[18]RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[19]YANG J,WANG G Y,PANG Z L.Relative researches of clustering by fast search and find of density peaks[J].Journal of Nanjing University(Natural Science),2017,53(4):791-801.(in Chinese)
杨洁,王国胤,庞紫玲.密度峰值聚类相关问题的研究[J].南京大学学报(自然科学版),2017,53(4):791-801.
[20]SHI X H,FENG G X,LI M,et al.Overlapping community detection method based on density peaks[J].Journal of Jilin University(Engineering and Technology Edition),2017,47(1):242-248.(in Chinese)
时小虎,冯国香,李牧,等.基于密度峰值的重叠社区发现算法.吉林大学(工学版),2017,47(1):242-248.
[21]HUANG L,LI Y,WANG G S,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.(in Chinese)
黄岚,李玉,王贵参,等.基于点距离和密度峰值聚类的社区发现方法[J].吉林大学学报(工学版),2016,46(6):2042-2051.
[22]HENNIG C,HAUSDORF B.Design of dissimilarity measures:A new dissimilarity between species distribution areas[M]//Data Science And Classification.Berlin Heidelberg:Springer,2006:29-37.
[23]SHEN H,CHENG X,CAI K,et al.Detect overlapping and hie-rarchical community structure in networks[J].Physica A Statistical Mechanics & Its Applications,2009,388(8):1706-1712.
[24]SANTOS J M,EMBRECHTS M.On the use of the adjusted rand index as a metric for evaluating supervised classification[C]//Proceeding of the 19th International Conference on Artificial Neural Networks.Berlin Heidelberg:Springer,2009:175-184.
[25]DANON L,DIAZGUILERA A,DUCH J,et al.Comparing community structure identification[J].Journal of Statistical Mechanics:Theory and Experiment,2005,2005(9):P09008.
[26]LANCICHINETTI A,FORTUNATO S.Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2009,80(1):016118.
[27]BAI X,YANG P,SHI X.An overlapping community detection algorithm based on density peaks[J].Neurocomputing,2017,226:7-15.
[28]HUANG L,WANG G,WANG Y,et al.A link density clustering algorithm based on automatically selecting density peaks for overlapping community detection[J].International Journal of Modern Physics B,2016,30(24):1650167.
[29]GAITERI C,CHEN M M,SZYMANSKI K,et al.Identifying robust communities and multi-community nodes by combining top-down and bottom-up approaches to clustering[J].Scientific Reports,2015,5:16361.
[30]XIE J,SZYMANSKI B K,LIU X.SLPA:Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process[C]//Proceedings of the 11th IEEE International Conference of Data Mining Workshops.Washington,CD:IEEE,2011:344-349.
[1] LI Rong-fan, ZHONG Ting, WU Jin, ZHOU Fan, KUANG Ping. Spatio-Temporal Attention-based Kriging for Land Deformation Data Interpolation [J]. Computer Science, 2022, 49(8): 33-39.
[2] HE Xi, HE Ke-tai, WANG Jin-shan, LIN Shen-wen, YANG Jing-lin, FENG Yu-chao. Analysis of Bitcoin Entity Transaction Patterns [J]. Computer Science, 2022, 49(6A): 502-507.
[3] WANG Ben-yu, GU Yi-jun, PENG Shu-fan, ZHENG Di-wen. Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning [J]. Computer Science, 2022, 49(5): 170-178.
[4] YAO Xiao-ming, DING Shi-chang, ZHAO Tao, HUANG Hong, LUO Jar-der, FU Xiao-ming. Big Data-driven Based Socioeconomic Status Analysis:A Survey [J]. Computer Science, 2022, 49(4): 80-87.
[5] YANG Xu-hua, WANG Lei, YE Lei, ZHANG Duan, ZHOU Yan-bo, LONG Hai-xia. Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding [J]. Computer Science, 2022, 49(3): 121-128.
[6] KONG Yu-ting, TAN Fu-xiang, ZHAO Xin, ZHANG Zheng-hang, BAI Lu, QIAN Yu-rong. Review of K-means Algorithm Optimization Based on Differential Privacy [J]. Computer Science, 2022, 49(2): 162-173.
[7] PU Shi, ZHAO Wei-dong. Community Detection Algorithm for Dynamic Academic Network [J]. Computer Science, 2022, 49(1): 89-94.
[8] ZHANG Ya-di, SUN Yue, LIU Feng, ZHU Er-zhou. Study on Density Parameter and Center-Replacement Combined K-means and New Clustering Validity Index [J]. Computer Science, 2022, 49(1): 121-132.
[9] MA Dong, LI Xin-yuan, CHEN Hong-mei, XIAO Qing. Mining Spatial co-location Patterns with Star High Influence [J]. Computer Science, 2022, 49(1): 166-174.
[10] CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure [J]. Computer Science, 2021, 48(9): 244-250.
[11] XU Hui-hui, YAN Hua. Relative Risk Degree Based Risk Factor Analysis Algorithm for Congenital Heart Disease in Children [J]. Computer Science, 2021, 48(6): 210-214.
[12] YANG Xu-hua, WANG Chen. Community Detection Algorithm in Complex Network Based on Network Embedding and Local Resultant Force [J]. Computer Science, 2021, 48(4): 229-236.
[13] ZHANG Yan-jin, BAI Liang. Fast Symbolic Data Clustering Algorithm Based on Symbolic Relation Graph [J]. Computer Science, 2021, 48(4): 111-116.
[14] TANG Xin-yao, ZHANG Zheng-jun, CHU Jie, YAN Tao. Density Peaks Clustering Algorithm Based on Natural Nearest Neighbor [J]. Computer Science, 2021, 48(3): 151-157.
[15] ZHANG Han-shuo, YANG Dong-ju. Technology Data Analysis Algorithm Based on Relational Graph [J]. Computer Science, 2021, 48(3): 174-179.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!