吉林大学学报(工学版) ›› 2017, Vol. 47 ›› Issue (1): 242-248.doi: 10.13229/j.cnki.jdxbgxb201701035

• Orginal Article • Previous Articles     Next Articles

Overlapping community detection method based on density peaks

SHI Xiao-hu1, 2, 3, 4, FENG Guo-xiang1, 2, LI Mu1, 2, LI Ying1, 2, WU Chun-guo1, 2, 3, 4   

  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;
    3.Department of Computer Science and Technology, Zhuhai College of Jilin University, Zhuhai 519041, China;
    4.Zhuhai Laboratory of Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Zhuhai College of Jilin University, Zhuhai 519041, China
  • Received:2015-05-27 Online:2017-01-20 Published:2017-01-20

RICH HTML

0   

PDF (PC)

403

Abstract: Based on the idea of clustering method by fast search and find of density peaks, we put forward an overlapping community detection method based on density peaks. In the proposed algorithm, first a new distance matrix is defined to overcome the defects of adjacency matrix being filled with integers. Then, the probability form is used to depict the possibility of each node that belongs to different clusters. The experimental results on real network show that the proposed method performs very well.

Key words: computer application, complex network, community detection, overlapping community, small world feature, modularity

CLC Number: 

  • TP391
[1] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393: 440-442.
[2] Barabasi A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509-512.
[3] 汪小帆, 李翔, 陈关荣. 复杂网络理论及其应用[M]. 北京: 清华大学出版社, 2006.
[4] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal, 1970, 49(2): 291-307.
[5] Simon H D. Partitioning of unstructured problems for parallel processing[J]. Computing Systems in Engineering, 1991, 2(2-3):135-148.
[6] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Science of the United States of America, 2002, 99(12): 7821-7826.
[7] Newman M E J, Grivan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113.
[8] Fortunato S, Barthelemy M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-41.
[9] Blondel V D, Guillaume J L, Lambiotte R, et al. Fast unfolding of communities in large networks[DB/OL].[2015-10-26].https:∥arxiv.org/abs/0803.0476.
[10] Gregory S. An algorithm to find overlapping community structure in networks[J]. Lecture Notes in Computer Science, 2007,4702: 91-102.
[11] Lee C, Reid F, Mc Daid A, et al. Detecting highly overlapping community structure by greedy clique expansion[DB/OL].[2015-10-26]. https:∥arxiv.org/abs/1002.1827.
[12] Lancichinetti A, Fortunato S, Kertesz J. Detecting the overlapping and hierarchical community structure in complex networks[DB/OL].[2015-10-26].https:∥arxiv.org/abs/0802.1218.
[13] Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.
[14] Floyd Robert W. Algorithm 97:shortest path[J]. Communications of the ACM,1962,5(6):345.
[15] 杨荟蓉. 基于概率模型的重叠社区发现算法研究[D]. 北京: 北京交通大学计算机与信心技术学院, 2011.
Yang Hui-rong. Research on overlapping community detection algorithms based on probabilistic model[D]. Beijing: School of Computer and Information Technology, Beijing Jiaotong University, 2011.
[16] Shen H, Cheng X, Cai K, et al. Detect overlapping and hierarchical community structure in networks[J]. Physical A: Statistical Mechanics and its Applications, 2009, 388(8): 1706-1712.
[17] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[18] Lusseau D, Schneider K, Boisseay 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.
[19] Newman M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3): 036104.
[20] Newman M E J. The structure and function of complex networks[J]. SIAM Review, 2003, 45(2): 167-256.
[21] Palla G, Derenyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005, 435: 814-818.
[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   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd