Computer Science ›› 2021, Vol. 48 ›› Issue (9): 244-250.doi: 10.11896/jsjkx.201100010

• Artificial Intelligence • Previous Articles     Next Articles

Overlapping Community Detection Algorithm Based on Subgraph Structure

CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei   

  1. College of Computer Science and Electronic Engineering,Hunan University,Changsha 410000,China
  • Received:2020-11-02 Revised:2021-03-22 Online:2021-09-15 Published:2021-09-10
  • About author:CHEN Xiang-tao,born in 1973,Ph.D,associate professor,is a member of China Computer Federation.His main research interests include data mining,heterogenous information network,social network and network embedding.
  • Supported by:
    National Natural Science Foundation of China(61873089),National Key R&D Program of China(2018YFC0910405) and National Natural Science Foundation of China(61572180)

Abstract: Local community detection algorithms usually select seed nodes for community detection.To improve the quality of effectiveness of seed node selection,we propose an overlapping community detection algorithm based on subgraph structure(SUSBOCD).This algorithm proposes a new measure of node importance,which not only considers the number of neighbors,but also considers the degree of density between neighbors.First,SUSBOCD selects the most important node that is not visited and the most similar neighbor node,and merges the two nodes and their common neighbor nodes to form an initial seed subgraph.The process runs iteratively until all nodes have been visited.Second,the similarity is judged according to the neighborhood information of the seed subgraph.If it is similar,it is merged to form the initial community structure.The process runs iteratively until all seed subgraphs are visited.Finally,we optimize the community.If there are nodes without assigned communities,they are added to the most similar community,and then the community structure with high overlap is merged.Experiments on real and artificial networks show that SUSBOCD can improve the quality of overlapping community partition effectively in the three evaluation indexes of ONMI,EQ and Omega.

Key words: Community expansion, Community optimization, Local expansion, Overlapping community detection, Seed selection

CLC Number: 

  • TP391
[1]NEWMAN M E J.The structure of scientific collaboration networks[J].Proceedings of the National Academy of Sciences,2001,98(2):404-409.
[2]NEWMAN M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.
[3]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.
[4]LANCICHINETTI A,FORTUNATO S,KERTÉSZ J.Detec-tingthe overlapping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11(3):033015.
[5]CHEN Q,WU T T,FANG M.Detecting local community structures in complex networks based on local degree central nodes[J].Physica A:Statistical Mechanics and its Applications,2013,392(3):529-537.
[6]LI Y,HE J,WU Y X.Overlapping Community Discovery Me-thod Based on Greedy Expansion of Seed Nodes[J].Journal of Chinese Computer Systems,2019,40(5):1115-1119.
[7]WANG X,LIU G,LI J,et al.Locating structural centers:A density-based clustering method for community detection[J].PloS one,2017,12(1):e0169355.
[8]WANG X,LIU G,LI J.Overlapping community detection based on structural centrality in complex networks[J].IEEE Access,2017,5:25258-25269.
[9]RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[10]YU Z Y,CHEN J J,GUO K.Overlapping Community Detection Based on Influence and Seeds Extension[J].Acta Electronica Sinica,2019,47(1):153-160.
[11]ZHANG X,WANG C,SU Y,et al.A fast overlapping community detection algorithm based on weak cliques for large-scale networks[J].IEEE Transactions on Computational Social Systems,2017,4(4):218-230.
[12]GREGORY S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2010,12(10):2011-2024.
[13]PALLA G,IMRE D,ILLÉS F,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818.
[14]COSCIA M,ROSSETTI G,GIANNOTTI F,et al.DEMON:a Local-First Discovery Method for Overlapping Communities [C]//Proceeding of ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.2012:615-623.
[15]CHEN X,LI J.Overlapping Community Detection by Node-Weighting[C]//Proceedings of the 2nd International Confe-rence on Compute and Data Analysis,ICCDA.2018:70-74.
[1] NING Yi-xin, XIE Hui, JIANG Huo-wen. Survey of Graph Neural Network in Community Detection [J]. Computer Science, 2021, 48(11A): 11-16.
[2] XUE Lei, TANG Xu-qing. Algorithm for Detecting Overlapping Communities Based on Centered Cliques [J]. Computer Science, 2020, 47(8): 157-163.
[3] 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.
[4] 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.
[5] LIU Chun, ZHANG Guo-liang. Software Feature Extraction Method Based on Overlapping Community Detection [J]. Computer Science, 2019, 46(12): 201-207.
[6] ZHANG Zhong-zheng and LI Jian-wu. Parallelizable Overlapping Community Detection Algorithm Based on Local Expansion [J]. Computer Science, 2016, 43(9): 61-65.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!