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, Overlapping community, Density peak, Topological structure, Data mining

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] ZHANG Yu, LU Yi-hong, HUANG De-cai. Weighted Hesitant Fuzzy Clustering Based on Density Peaks [J]. Computer Science, 2021, 48(1): 145-151.
[2] YOU Lan, HAN Xue-wei, HE Zheng-wei, XIAO Si-yu, HE Du, PAN Xiao-meng. Improved Sequence-to-Sequence Model for Short-term Vessel Trajectory Prediction Using AIS Data Streams [J]. Computer Science, 2020, 47(9): 169-174.
[3] XUE Lei, TANG Xu-qing. Algorithm for Detecting Overlapping Communities Based on Centered Cliques [J]. Computer Science, 2020, 47(8): 157-163.
[4] ZHANG Su-mei and ZHANG Bo-tao. Evaluation Model Construction Method Based on Quantum Dissipative Particle Swarm Optimization [J]. Computer Science, 2020, 47(6A): 84-88.
[5] YUAN De-yu, ZHANG Yi-fan, GAO Jian and SUN Hai-chun. Abnormal User Detection Method in Sina Weibo Based on User Feature Extraction [J]. Computer Science, 2020, 47(6A): 364-368.
[6] DENG Tian-tian, XIONG Yin-qiao and HE Xian-hao. Novel Clustering Algorithm Based on Timing-featured Alarms [J]. Computer Science, 2020, 47(6A): 440-443.
[7] LI Li. Classification Algorithm of Distributed Data Mining Based on Judgment Aggregation [J]. Computer Science, 2020, 47(6A): 450-456.
[8] ZHANG Qin, CHEN Hong-mei, FENG Yun-fei. Overlapping Community Detection Method Based on Rough Sets and Density Peaks [J]. Computer Science, 2020, 47(5): 72-78.
[9] YUAN Rong, SONG Yu-rong, MENG Fan-rong. Link Prediction Method Based on Weighted Network Topology Weight [J]. Computer Science, 2020, 47(5): 265-270.
[10] YU Hang, WEI Wei, TAN Zheng, LIU Jing-lei. Contextual Preference Collaborative Measure Framework Based on Belief System [J]. Computer Science, 2020, 47(4): 74-84.
[11] CHEN Jun-fen,ZHANG Ming,ZHAO Jia-cheng. Clustering Algorithm by Fast Search and Find of Density Peaks for Complex High-dimensional Data [J]. Computer Science, 2020, 47(3): 79-86.
[12] ZHAO Wei-ji,ZHANG Feng-bin,LIU Jing-lian. Review on Community Detection in Complex Networks [J]. Computer Science, 2020, 47(2): 10-20.
[13] YANG Xu-hua,SHEN Min. Community Detection Algorithm Based on Local Similarity of Feature Vectors [J]. Computer Science, 2020, 47(2): 58-64.
[14] WANG Shuai-hui, HU Gu-yu, PAN Yu, ZHANG Zhi-yue, ZHANG Hai-feng, PAN Zhi-song. Community Detection in Signed Networks with Game Theory [J]. Computer Science, 2020, 47(11A): 449-453.
[15] DING Wu, MA Yuan, DU Shi-lei, LI Hai-chen, DING Gong-bo, WANG Chao. Mining Trend Similarity of Multivariate Hydrological Time Series Based on XGBoost Algorithm [J]. Computer Science, 2020, 47(11A): 459-463.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .