Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (12): 170-177.doi: 10.11896/jsjkx.211000025

• Database & Big Data & Data Science • Previous Articles     Next Articles

Node Local Similarity Based Two-stage Density Peaks Algorithm for Overlapping Community Detection

DUAN Xiao-hu1, CAO Fu-yuan1,2   

  1. 1 School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China
    2 Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education,Shanxi University,Taiyuan 030006,China
  • Received:2021-10-08 Revised:2021-11-04 Published:2022-12-14
  • About author:DUAN Xiao -hu,born in 1996,postgra-duate,is a member of China Computer Federation.His main research interests include cluster analysis and so on.CAO Fu-yuan,born in 1974,professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include Data mining and machine learning.
  • Supported by:
    National Natural Science Foundation of China(61976128) and Applied Basic Research Program of Shanxi Province(201901D111035).

PDF (PC)

358

Abstract: In order to detect overlapping community structures in complex networks,the idea of density peaks clustering algorithm is introduced.However,applying the density peaks clustering algorithm to community detection still has problems such as how to measure the distance between nodes and how to generate overlapping partition results.Therefore,a node local similarity based two-stage density peaks algorithm for overlapping community detection is proposed (LSDPC).By combining hub promoted index and connection contribution degree,a new node local similarity index is defined,and the node distance is measured with the node local similarity.Then the local density and minimum distance of nodes are used to calculate their center values and Chebyshev inequality is used to select communities’ center nodes.The overlapping communities are obtained through initial assignment and overlapping assignment.Experimental results on real network datasets and synthetic network datasets show that the proposed algorithm can effectively detect overlapping community structure,and the results are better than that of other algorithms.

Key words: Overlapping community detection, Density peaks, Node similarity, k-nearest neighbors, Degree of membership

CLC Number: 

  • TP391
[1]HAN N,QIAO S J,YUAN C A,et al.A Fast Parallel Community Detection Algorithm for Mobile Social Networks[J].Journal of Chongqing University of Technology (Natural Science),2020,34(1):94-102.
[2]FORTUNATO S,HRIC D.Community detection in networks:a user guide[J].Physics Reports,2016,659:1-44.
[3]ZHAO W J,ZHANG F B,LIU J L.Review on Community Detection in Complex Networks [J].Computer Science,2020,47(2):10-20.
[4]RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[5]RAVASE E,SOMERA A L,MONGRU D A,et al.Hierarchical organization of modularity in metabolic networks[J].Science,2002,297(5586):1553-1555.
[6]DING J J,CHEN Z T,HE X X,et al.Clustering by finding density peaks based on Chebyshev's inequality[C]//Proceedings of the 2016 35th Chinese Control Conference.IEEE,2016:7169-7172.
[7]PALLA G,DERENYI I,FARKAS I,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[8]GREGORY S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2010,12(10):2011-2024.
[9]XIE J,SZYMANSKI B K,LIU X.SLPA:Uncovering overlap-ping communities in social networks via a speaker-listener intera-ction dynamic process[C]//Proceedings of the 2011 IEEE 11th International Conference on Data Mining Workshops.IEEE,2011:344-349.
[10]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.
[11]LANCICHINETTI A,FORTUNATO S,KERTÉSZ J.Detec-ting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11(3):1-18.
[12]YU Z Y,CHEN J J,GUO K,et al.Overlapping community detection based on influence and seeds extension[J].Chinese Journal of Electronics,2019,47(1):153-160.
[13]COSCIA M,ROSSETTI G,GIANNOTTI F,et al.DEMON:a local-first discovery method for overlapping communities[C]//Proceedings of the18th ACM SIGKDD International Confe-rence on Knowledge Discovery and Data Mining.ACM,2012:615-623.
[14]AHN Y Y,BAGROW J,LEHMANN S.Link communities reveal multiscale complexity in networks[J].Nature,2010,466(7307):761-764.
[15]PAN L,JIN J,WANG C J,et al.Detecting Link Communities Based on Local Information in Social Networks[J].Chinese Journal of Electronics,2012,40(11):2255-2263.
[16]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.
[17]HUANG L,LI Y,WANG G S,et al.Community detectionmethod based on vertex distance and clustering of density peaks[J].Journal of Jilin University (Engineering and Technology Edition),2016,46(6):2042-2051.
[18]DING J J,HE X X,YUAN J Q,et al.Community detection by propagating the label of center[J].Physica A:Statistical Mechanics and Its Applications,2018,503:675-686.
[19]BAI X Y,YANG P L,SHI X H.An overlapping communitydetection algorithm based on density peaks[J].Neurocompu-ting,2017,226:7-15.
[20]XU M L,LI Y H,LI R X,et al.EADP:An extended adaptive density peaks clustering for overlapping community detection in social networks[J].Neurocomputing,2019,337(2019):287-302.
[21]FENG Y F,CHEN H M.Topological structure based density peak algorithm for overlapping community detection[J].Computer Science,2019,46(10):39-48.
[22]WANG X F,LI X,CHEN G R.Network science:an introduction[M].Beijing:Higher Education Press,2012.
[23]SHAO J M,HAN Z C,YANG Q L,et al.Community detection based on distance dynamics[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2015:1075-1084.
[24]LÜ L Y.Link prediction on complex networks[J].Journal ofUniversity of Electronic Science and Technology of China,2010,39(5):651-661.
[25]XIE J Y,GAO H C,XIE W X,et al.Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors[J].Information Sciences,2016,354:19-40.
[26]NEWMAN M.Network data [EB/OL].http://www.personal.umich.edu/~mejn/netdata/.
[27]KUNEGIS J.KONECT:the Koblenz network collection[C]//Proceedings of the 22nd International Conference on World Wide Web.ACM,2013:1343-1350.
[28]LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms [J].Physical Review E,2008,78(4):046110.
[29]FORTUNATO S.LFR benchmark graphs [EB/OL].https://www.santofortunato.net/resources.
[30]NICOSIA V,MANGIONI G,CARCHIOLO V,et al.Extending the definition of modularity to directed graphs with overlapping communities[J].Journal of Statistical Mechanics:Theory and Experiment,2009,2009(3):3024-3046.
[1] 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.
[2] ZHENG Wen-ping, WANG Ning, YANG Gui. Overlapping Community Detection Algorithm Based on Local Path Information [J]. Computer Science, 2022, 49(12): 155-162.
[3] CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure [J]. Computer Science, 2021, 48(9): 244-250.
[4] 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.
[5] NING Yi-xin, XIE Hui, JIANG Huo-wen. Survey of Graph Neural Network in Community Detection [J]. Computer Science, 2021, 48(11A): 11-16.
[6] WANG Wei-dong, XU Jin-hui, ZHANG Zhi-feng, YANG Xi-bei. Gaussian Mixture Models Algorithm Based on Density Peaks Clustering [J]. Computer Science, 2021, 48(10): 191-196.
[7] ZHANG Yu, LU Yi-hong, HUANG De-cai. Weighted Hesitant Fuzzy Clustering Based on Density Peaks [J]. Computer Science, 2021, 48(1): 145-151.
[8] XUE Lei, TANG Xu-qing. Algorithm for Detecting Overlapping Communities Based on Centered Cliques [J]. Computer Science, 2020, 47(8): 157-163.
[9] 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.
[10] 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.
[11] ZHANG Qin, CHEN Hong-mei, FENG Yun-fei. Overlapping Community Detection Method Based on Rough Sets and Distance Dynamic Model [J]. Computer Science, 2020, 47(10): 75-82.
[12] LIU Chun, ZHANG Guo-liang. Software Feature Extraction Method Based on Overlapping Community Detection [J]. Computer Science, 2019, 46(12): 201-207.
[13] ZHANG Hu, WU Yong-ke, YANG Zhi-zhuo and LIU Quan-ming. Community Detection Method Based on Multi-layer Node Similarity [J]. Computer Science, 2018, 45(1): 216-222.
[14] ZHANG Zhong-zheng and LI Jian-wu. Parallelizable Overlapping Community Detection Algorithm Based on Local Expansion [J]. Computer Science, 2016, 43(9): 61-65.
[15] FANG Xin-wei, CHEN Shu-qiao, REN Ze-rong and JIANG Yi-ming. Collaborative Caching Algorithm Based on Node Similarity in Content Centric Networking [J]. Computer Science, 2016, 43(4): 81-85.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.