吉林大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (6): 2042-2051.doi: 10.13229/j.cnki.jdxbgxb201606038

Previous Articles     Next Articles

Community detection method based on vertex distance and clustering of density peaks

HUANG Lan1, 2, LI Yu1, 2, WANG Gui-shen1, 2, WANG Yan1, 2   

  1. 1.College of Computer Science and Technology, Jilin University, Changchun 130012, China;
    2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China
  • Received:2015-10-26 Online:2016-11-20 Published:2016-11-20

Abstract: Based on vertex similarity in complex network and density peaks clustering, a community detection method is proposed. First, a vertex distance calculation based on vertex similarity and the shortest distance between vertexes is proffered. Then, the density peaks clustering method is applied to detect the community structure in network. The density peaks clustering method not only allows the detection of the community centers to establish the epicenter for community expansion, but also avoids the process of selecting parameters. The proposed method is compared with the classic algorithms on both real-world networks and synthetic networks. Experimental results demonstrate that the proposed community detection method is practicable and effective.

Key words: computer application, community detection, vertex distance, density peaks clustering(DPC), complex network

CLC Number: 

  • TP301.6
[1] 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.
[2] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E,2004,69(2):026113.
[3] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E,2004,69(6):066133.
[4] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Physical Review E,2004,70(6):066111.
[5] Zhu X, Ghahramani Z, Lafferty J. Semi-supervised learning using gaussian fields and harmonic functions[C]∥ICML, Washington DC,USA,2003:912-919.
[6] 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.
[7] Barber M J, Clark J W. Detecting network communities by propagating labels under constraints[J]. Physical Review E,2009,80(2):026129.
[8] Liu X, Murata T. Advanced modularity-specialized label propagation algorithm for detecting communities in networks[J]. Physica A: Statistical Mechanics and its Applications,2010,389(7):1493-1500.
[9] Rosvall M, Bergstrom C T. An information-theoretic framework for resolving community structure in complex networks[J]. Proceedings of the National Academy of Sciences,2007,104(18):7327-7331.
[10] Rosvall M, Bergstrom C T. Maps of random walks on complex networks reveal community structure[J]. Proceedings of the National Academy of Sciences,2008,105(4):1118-1123.
[11] Pons P, Latapy M. Computing Communities in Large Networks using Random Walks[M]. Berlin Heidelberg:Springer,2005:284-293.
[12] Lancichinetti A, Radicchi F, Ramasco J J, et al. Finding statistically significant communities in networks[J]. PLoS One,2011,6(4):e18961.
[13] Lancichinetti A, Fortunato S. Consensus clustering in complex networks[J]. Scientific Reports,2012,2:00336.
[14] 周春光,曲鹏程,王曦,等. DSNE: 一个新的动态社会网络分析算法[J]. 吉林大学学报:工学版, 2008,38(2):408-413.
Zhou Chun-guang,Qu Peng-cheng,Wang Xi, et al. DSNE: a new dynamic social network analysis algorithm[J]. Journal of Jilin University (Engineering and Technology Edition),2008,38(2):408-413.
[15] 才华,周春光,卢廷玉,等. 重叠社区结构的挖掘算法[J]. 吉林大学学报:工学版,2009,39(4):1035-1040.
Cai Hua,Zhou Chun-guang,Lu Ting-yu,et al. OCSMA:an algorithm to mine overlapping community structure in networks[J]. Journal of Jilin University (Engineering and Technology Edition),2009,39(4):1035-1040.
[16] Huang L,Wang G S,Wang Y,et al. Link clustering with extended link similarity and EQ evaluation division[J]. PLoS One,2013,8(6):e66005.
[17] Rodriguez A,Laio A. Clustering by fast search and find of density peaks[J]. Science,2014,344(6191):1492-1496.
[18] Hennig C, Hausdorf B. Design of dissimilarity measures: a new dissimilarity between species distribution areas[DB/OL].[2015-09-24].https://www.ucl.ac.uk/statistics/research/pdfs/rr273.pdf.
[19] Shao J,Han Z,Yang Q,et al. Community detection based on distance dynamics[C]∥Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney,Australia,2015:1075-1084.
[20] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977,33(4):452-473.
[21] Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology,2003,54(4):396-405.
[22] Gleiser P M, Danon L. Community structure in jazz[J]. Advances in Complex Systems,2003,6(4):565-573.
[23] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks[J]. Nature,1998,393(6684):440-442.
[24] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E,2008,78(4):046110.
[25] 孙延维,彭智明,李健波.基于粒子群优化与模糊聚类的社区发现算法[J].重庆邮电大学学报:自然科学版,2015,27(5):660-666.
Sun Yan-zhi,Peng Zhi-ming,Li Jian-bo. Community detection algorithm based on particle swarm optimization and fuzzy clustering [J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2015,27(5):660-666.
[26] 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.
[27] MultiplexNMI package[DB/OL].[2015-09-28]. https://sites.google.com/site/andrealancichinetti/files.
[28] Igraph R package[DB/OL].[2015-09-24].https://igraph.org/r/.
[1] LIU Fu,ZONG Yu-xuan,KANG Bing,ZHANG Yi-meng,LIN Cai-xia,ZHAO Hong-wei. Dorsal hand vein recognition system based on optimized texture features [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1844-1850.
[2] WANG Li-min,LIU Yang,SUN Ming-hui,LI Mei-hui. Ensemble of unrestricted K-dependence Bayesian classifiers based on Markov blanket [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1851-1858.
[3] JIN Shun-fu,WANG Bao-shuai,HAO Shan-shan,JIA Xiao-guang,HUO Zhan-qiang. Synchronous sleeping based energy saving strategy of reservation virtual machines in cloud data centers and its performance research [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1859-1866.
[4] ZHAO Dong,SUN Ming-yu,ZHU Jin-long,YU Fan-hua,LIU Guang-jie,CHEN Hui-ling. Improved moth-flame optimization method based on combination of particle swarm optimization and simplex method [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1867-1872.
[5] LIU En-ze,WU Wen-fu. Agricultural surface multiple feature decision fusion disease judgment algorithm based on machine vision [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1873-1878.
[6] OUYANG Dan-tong, FAN Qi. Clause-level context-aware open information extraction [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1563-1570.
[7] LIU Fu, LAN Xu-teng, HOU Tao, KANG Bing, LIU Yun, LIN Cai-xia. Metagenomic clustering method based on k-mer frequency optimization [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1593-1599.
[8] GUI Chun, HUANG Wang-xing. Network clustering method based on improved label propagation algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1600-1605.
[9] LIU Yuan-ning, LIU Shuai, ZHU Xiao-dong, CHEN Yi-hao, ZHENG Shao-ge, SHEN Chun-zhuang. LOG operator and adaptive optimization Gabor filtering for iris recognition [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1606-1613.
[10] CHE Xiang-jiu, WANG Li, GUO Xiao-xin. Improved boundary detection based on multi-scale cues fusion [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1621-1628.
[11] ZHAO Hong-wei, LIU Yu-qi, DONG Li-yan, WANG Yu, LIU Pei. Dynamic route optimization algorithm based on hybrid in ITS [J]. 吉林大学学报(工学版), 2018, 48(4): 1214-1223.
[12] HUANG Hui, FENG Xi-an, WEI Yan, XU Chi, CHEN Hui-ling. An intelligent system based on enhanced kernel extreme learning machine for choosing the second major [J]. 吉林大学学报(工学版), 2018, 48(4): 1224-1230.
[13] FU Wen-bo, ZHANG Jie, CHEN Yong-le. Network topology discovery algorithm against routing spoofing attack in Internet of things [J]. 吉林大学学报(工学版), 2018, 48(4): 1231-1236.
[14] CAO Jie, SU Zhe, LI Xiao-xu. Image annotation method based on Corr-LDA model [J]. 吉林大学学报(工学版), 2018, 48(4): 1237-1243.
[15] HOU Yong-hong, WANG Li-wei, XING Jia-ming. HTTP-based dynamic adaptive streaming video transmission algorithm [J]. 吉林大学学报(工学版), 2018, 48(4): 1244-1253.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LI Shu-sheng, ZHONG Mai-ying. Design of control system based on PID of three-axis inertially stabilized platform for airborne remote sensing[J]. 吉林大学学报(工学版), 2011, 41(增刊1): 275 -279 .
[2] LIU Song-shan, WANG Qing-nian, WANG Wei-hua, LIN Xin. Influence of inertial mass on damping and amplitude-frequency characteristic of regenerative suspension[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[3] WANG Tong-jian, CHEN Jin-shi, ZHAO Feng, ZHAO Qing-bo, LIU Xin-hui, YUAN Hua-shan. Mechanical-hydraulic co-simulation and experiment of full hydraulic steering systems[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[4] ZHANG Chun-qin, JIANG Gui-yan, WU Zheng-yan. Factors influencing motor vehicle travel departure time choice behavior[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[5] XIAO Rui, DENG Zong-cai, LAN Ming-zhang, SHEN Chen-liang. Experiment research on proportions of reactive powder concrete without silica fume[J]. 吉林大学学报(工学版), 2013, 43(03): 671 -676 .
[6] CHEN Si-guo, JIANG Xu, WANG Jian, LIU Yan-heng, DENG Wei-wen, DENG Jun-yi. Mashup of vehicular ad-hoc network and universal mobile telecommunications system[J]. 吉林大学学报(工学版), 2013, 43(03): 706 -710 .
[7] MENG Chao, SUN Zhi-xin, LIU San-min. Multiple execution paths for virus based on cloud computing[J]. 吉林大学学报(工学版), 2013, 43(03): 718 -726 .
[8] XIAN Shu, ZHENG Jin, LU Xing, ZHANG Shi-peng. Identification approach of P2P flow based on the content redistribution model[J]. 吉林大学学报(工学版), 2013, 43(03): 727 -733 .
[9] LYU Yuan-zhi, WANG Shi-gang, YU Jue-qiong, WANG Xiao-yu, LI Xue-song. Display characteristics of one-dimensional integral imaging in virtual mode based on lenticular lens array[J]. 吉林大学学报(工学版), 2013, 43(03): 753 -757 .
[10] WANG Dan, LI Yang, NIAN Gui-jun, WANG Ke. An inhomogeneity mask for spatial watermarking[J]. 吉林大学学报(工学版), 2013, 43(03): 771 -775 .