Computer Science ›› 2020, Vol. 47 ›› Issue (2): 58-64.doi: 10.11896/jsjkx.181202433

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

Community Detection Algorithm Based on Local Similarity of Feature Vectors

YANG Xu-hua,SHEN Min   

  1. (College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)
  • Received:2018-12-27 Online:2020-02-15 Published:2020-03-18
  • About author:YANG Xu-hua,born in 1971,Ph.D,professor,Ph.D supervisor,is member of China Computer Federation.His main research interests include machine learning,complex networks and intelligent transportation systems.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61773348) and Zhejiang Natural Science Foundation (LY17F030016).

Abstract: Community discovery and analysis is a hot topic in the study of complex network structures and functions.At present,the widely used algorithm for community partitioning has some problems,such as high time complexity,inaccurate quantification of the number of community cores,and low partitioning accuracy.Therefore,this paper proposed a community detection algorithm ELSC based on local similarity of feature vectors.The algorithm first calculates the eigenvector centrality of each node in the network.On this basis,the eigenvector local similarity (ELS) and eigenvector attractiveness (EA) indicators were proposed.The ELS index indicates the similarity between nodes.To form the initial community,the similarity between the nodes within the same community is higher,and the similarity between different community nodes is lower.The EA index considers the local similarity and the eigenvector centrality ratio,indicating the node.The attraction is used to optimize the initial community and complete the community division of the network.The algorithm determines the node by the most value,avoiding the problem that the threshold number of nodes is uncertain.The modularity and standardized mutual information between the proposed algorithm and six well-known algorithms were compared on seven real networks.Numerical simulation results show that the algorithm has high accuracy and low time complexity.

Key words: Community detection, Eigenvector attractiveness, Eigenvector centrality, Eigenvector local similarity

CLC Number: 

  • TP391
[1]NEWMAN M E J,CLAUSET A.Structure and inference in annotated networks [J].Nature Communications,2016,7:11863.
[2]HU F,WANG M Z,WANG Y R,et al.An algorithm J-SC of detecting communities in complex networks [J].Physics Letters A,2017,381(42):3604-3612.
[3]HU F,LIU Y H.A new algorithm CNM-Centrality of detecting communities based on node centrality [J].Physics A,2016,446:138-151.
[4]WANG T,YIUN L Y,WANG X X.A community detection method based on local similarity and degree clustering information [J].Physics A,2018,490:1344-1354.
[5]CHEN L G,WANG Y R,HUANG X M,et al.SA-SOM algorithm for detecting communities in complex networks [J].Phy-sics Letters B,2017,31(29):1750262.
[6]CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks [J].Physical Review E,2004,70:066111.
[7]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:2691-2698.
[8]LI Y F,JIA C Y,YU J.A parameter-free community detection method based on centrality and dispersion of nodes in complex networks [J].Physics A,2015,438:321-334.
[9]YUTAKA I.SUEMATSU L,YUTA K.A Framework for Fast Community Extraction of Large-Scale Networks [J].ACM,2008,978:1215-1216.
[10]BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al. Fast unfolding of communities in large networks [J].Journal of Statistical Mechanics,2008,2008:p10008.
[11]BARBE R M J,CLARK J W.Detecting network communities by propagating labels under constraints [J].Physical Review E,2009,80:026129.
[12]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:036106.
[13]ŠUBELJ L,BAJEC M.Ubiquitousness of link-density and link-pattern communities in real-world networks [J].The European Physical Journal B,2012,85:1-11.
[14]JIN H,WANG S,LI C.Community detection in complex net-works by density-based clustering [J].Physics A,2013,392(19):4606-4618.
[15]GONG M,LIU J.Novel heuristic density-based method for community detection in networks [J].Physics A,2014,403:71-84.
[16]ZHOU H.Distance,dissimilarity index,and network community structure [J].Physical Review E,2003,67(6):061901.
[17]ROSVALL M,BERGSTROM C T.Maps of random walks on complex networks reveal community structure [J].PNAS,2008,105(4):1118-1123.
[18]MACQUEEN J B.Some methods for classification and analysis of multivariate observations in:Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability [J].American Mathematical Society,1967(66):281-297.
[19]JIANG Y W,JIA C V,YU J.An efficient community detection method based on rank centrality [J].Physics A,2013,392:2182-2194.
[20]XU H T,WU H,FANG X J,et al.Finding Key Stations of Hangzhou Public Bicycle System by an Improved K-Means Algorithm [J].Journal of Mechanics of Materials and Structures,2012,209:925-929.
[21]FENDER A,EMAD N,PETITION S.Parallel Jaccard and Related Graph Clustering Techniques [J].ACM ISBN,2017,978:4503-5125.
[22]EUSTACE J.Community detection using local neighborhood in complex networks [J].Physics A,2015,436:665-677.
[23]BAGROW J P,BOLLT E M.Local method for detecting communities [J].Physical Review E,2005,72 (4):046108.
[24]CLAUSET A.Finding local community structure in networks [J].Physical Review E,2005,72(2):026132.
[25]HUANG J,SUN H,LIU Y,et al.Towards online multiresolution community detection in large-scale networks [J].PLOS ONE,2011,6(8):e23829.
[26]GLEISER P M,DANON L.Community structure in Jazz[J].Advances in Complex Systems,2003,6:565-573.
[27]LANCICHINETTI A,FORTUNATO S,RADIHHI F.Benchmark graphs for testing community detection algorithms [J].Physical Review E,2008,78:046110.
[28]HU Q C,ZHANG Y,XING C X.Research on Maximization Method of Social Network Influence Based on Overlapping Community Division [J].Computer Science,2018,45(6):32-35.
[29]REN X L,LV L Y.Review of ranking nodes in complex networks [J].Chinese Science Bulletin,2014,9(13):1175-1197.
[30]ZHANG D,LI X H,LIU H,et al.Service-Oriented Network Node Importance Ranking Method in SDN Network[J].Chinese Journal of Computers,2018,41(11):2624-2636.
[31]QIAO S J,HAN N,ZHANG K F,et al.Overlapping community detection algorithm in complex network big data[J].Journal of Software,2017,28(3):631-647.
[32]DAI D B,TANG C L,XIONG W.Sequence clustering algorithm based on global and local similarity [J].Journal of Software,2010,21(4):702-717.
[1] HE Xi, HE Ke-tai, WANG Jin-shan, LIN Shen-wen, YANG Jing-lin, FENG Yu-chao. Analysis of Bitcoin Entity Transaction Patterns [J]. Computer Science, 2022, 49(6A): 502-507.
[2] WANG Ben-yu, GU Yi-jun, PENG Shu-fan, ZHENG Di-wen. Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning [J]. Computer Science, 2022, 49(5): 170-178.
[3] 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.
[4] PU Shi, ZHAO Wei-dong. Community Detection Algorithm for Dynamic Academic Network [J]. Computer Science, 2022, 49(1): 89-94.
[5] CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure [J]. Computer Science, 2021, 48(9): 244-250.
[6] YANG Xu-hua, WANG Chen. Community Detection Algorithm in Complex Network Based on Network Embedding and Local Resultant Force [J]. Computer Science, 2021, 48(4): 229-236.
[7] XU Xin-li, XIAO Yun-yue, LONG Hai-xia, YANG Xu-hua, MAO Jian-fei. Attributed Network Embedding Based on Matrix Factorization and Community Detection [J]. Computer Science, 2021, 48(12): 204-211.
[8] PAN Yu, ZOU Jun-hua, WANG Shuai-hui, HU Gu-yu, PAN Zhi-song. Deep Community Detection Algorithm Based on Network Representation Learning [J]. Computer Science, 2021, 48(11A): 198-203.
[9] NING Yi-xin, XIE Hui, JIANG Huo-wen. Survey of Graph Neural Network in Community Detection [J]. Computer Science, 2021, 48(11A): 11-16.
[10] XUE Lei, TANG Xu-qing. Algorithm for Detecting Overlapping Communities Based on Centered Cliques [J]. Computer Science, 2020, 47(8): 157-163.
[11] 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.
[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] 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.
[14] 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.
[15] ZHAO Xia, LI Xian, ZHANG Ze-hua, ZHANG Chen-wei. Community Detection Algorithm Combing Community Embedding and Node Embedding [J]. Computer Science, 2020, 47(10): 121-125.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!