Computer Science ›› 2021, Vol. 48 ›› Issue (4): 229-236.doi: 10.11896/jsjkx.200200102

• Artificial Intelligence • Previous Articles     Next Articles

Community Detection Algorithm in Complex Network Based on Network Embedding and Local Resultant Force

YANG Xu-hua, WANG Chen   

  1. College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China
  • Received:2020-06-24 Revised:2020-06-05 Online:2021-04-15 Published:2021-04-09
  • About author:YANG Xu-hua,born in 1971,Ph.D,professor,is a member of China Computer Federation.His main research interests include machine learning,complex networks,and intelligent transportation systems.
  • Supported by:
    National Natural Science Foundation of China(61773348) and Natural Science Foundation of Zhejiang Province,China(LY17F030016).

Abstract: Community detection can reveal the inherent structure dynamic behavior in complex networks and it is the current research hotspot.In this paper,we propose a community detection algorithm based on network embedding and local resultant force.The network topological space is transformed into euclidean space,and network nodes are converted into vector data points.First,based on the gravity model and the network topology,a local resultant force and a local resultant force cosine centrality index(LFC) are proposed.The center node of each initial small community is determined by the LFC of the node and the distance between nodes.Then the rest of the non-central nodes are classified to the nearest central node to form the initial small community.Finally,communities are merged by optimizing the modularity to find the optimal network community structure.Compared with 6 well-known community detection algorithms on 6 real-world networks and artificial networks with adjustable parameters,the new proposed algorithm shows good performance in the community detection.

Key words: Community detection, Gravity model, Local resultant force, Local resultant force cosine centrality, Network embedding

CLC Number: 

  • TP391
[1]MAHMOOD A,SMALL M.Subspace Based Network Community Detection Using Sparse Linear Coding[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(3):801-812.
[2]LEBERKNIGHT C,INALTEKIN H,CHIANG M,et al.TheEvolution of Online Social Networks:A tutorial survey[J].IEEE Signal Processing Magazine,2012,29(2):41-52.
[3]PAGANI G A,AIELLO M.The Power Grid as a complex network:A survey[J].Physica A:Statistical Mechanics and its Applications,2013,392(11):2688-2700.
[4]CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical Review E,2004,70(6 Pt 2):066111.
[5]NEWMAN M E J,GIRVAN M.Finding and Evaluating Community Structure in Networks[J].Physical Review E,2004,69(2 Pt 2):26-113.
[6]GUI C,ZHANG R,ZHAO Z,et al.LPA-CBD an improved label propagation algorithm based on community belonging degree for community detection[J].International Journal of Modern Physics C,2018,29(3):1850011.
[7]MOHOTTI W A,NAYAK R.Corpus-based Augmented Media Posts with Density-based Clustering for Community Detection[C]//IEEE International Conference on Tools with Artificial Intelligence.IEEE Computer Society,2018:379-386.
[8]ZARANDI F D,RAFSANJANI M K.Community detection in complex networks using structural similarity[J].Physica A:Statistical Mechanics and Its Applications,2018,503:882-891.
[9]SAOUD B,ABEDLOUAHAB M.Node similarity and modularity for finding communities in networks[J].Physica A:Statistical Mechanics and its Applications,2018,429:1958-1966.
[10]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(12):7821-7826.
[11]NEWMAN M E J.Fast algorithm for detecting communitystructure in networks[J].Physical Review E,2003,69(6 Pt 2):66-133.
[12]WEN X,CHEN W N,LIN Y,et al.A Maximal Clique BasedMultiobjective Evolutionary Algorithm for Overlapping Community Detection[J].IEEE Transactions on Evolutionary Computation,2016,PP(99):1.
[13]AMIRI B,HOSSAIN L,CRAWFORD J W.An efficient mul-tiobjective evolutionary algorithm for community detection in social networks[C]//Proceedings of the IEEE Congress on Evolutionary Computation(CEC 2011).IEEE,2011:2193-2199.
[14]LI W,JIANG S,JIN Q.Overlap community detection usingspectral algorithm based on node convergence degree[J].Future Generation Computer Systems,2017,79(1):408-416.
[15]IMANE M,NADIET K.Community Detection Using Fireworks Optimization Algorithm[J].International Journal of Artificial Intelligence Tools,2019,28(3):1950010.
[16]NIU X Z,SI W Y,SHE K.Evolutionary Community Detection in Dynamic Networks[J].Journal of Software,2017,28(7):1773-1789.
[17]LV L Y,ZHOU T.Link prediction in complex networks:A survey[J].Physica A:Statistical Mechanics and its Applications,2011,390(6):1150-1170.
[18]LEYDESDORFF L.On the normalization and visualization ofauthor co-citation data:Salton’s Cosine versus the Jaccard index[J].Journal of the American Society for Information Science and Technology,2008,59(1):77-85.
[19]RAVASZ E,SOMERA A L,MONGRU D A,et al.Hierarchical organization of modularity in metabolic networks[J].Science,2002,297(5586):1551-1555.
[20]ZHANG H,WU Y K,YANG Z Z,et al.Community Detection Method Based on Multi-layer Node Similarity[J].Computer Science,2018,45(1):216-222.
[21]PEROZZI B,AL-RFOU R,SKIENA S.DeepWalk:OnlineLearning of Social Representations[C]//The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York City,USA,2014.
[22]TANG J,QU M,WANG M,et al.LINE:Large-scale information network embedding[C]//The 24th International Confe-rence on World Wide Web.Florence,Italy,2015:1167-1177.
[23]GROVER A,LESKOVEC J.node2vec:Scalable Feature Lear-ning for Networks[C]//The 22nd ACM SIGKDD International Conference.San Francisco,USA,2016:855-864.
[24]WANG D,CUI P,ZHU W.Structural Deep Network Embed-ding[C]//The 22nd ACM SIGKDD International Conference.ACM,2016:1225-1234.
[25]HUANG J B,SUN H L,LIU Y G,et al.Towards Online Multiresolution Community Detection in Large-Scale Networks[J].PLoS ONE,2011,6(8):e23829.
[26]LANCICHINETTI A,FORTUNATO S.Detecting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11(3):033015.
[27]REICHARDT J,BORNHOLDT S.Statistical mechanics of community detection[J].Physical Review E,2006,74(1):016110.
[28]RONHOVDE P,NUSSINOV Z.Local resolution-limit-freePotts model for community detection[J].Physical Review E,2010,81(4):46-114.
[29]MARTELOT E L,HANKIN C.Multi-scale Community Detection using Stability Optimisation within Greedy Algorithms[J].Eprint Arxiv,2012,9(3):323-348.
[30]DANON L,DUCH J,DIAZ-GUILERA A,et al.Comparingcommunity structure identification[J].Journal of Statistical Mechanics,2005,2005(9):P09008.
[31]TASGIN M,BINGOL H O.Community detection using prefe-rence networks[J].Physica A Statistical Mechanics and its Applications,2017,495:126-136.
[32]HU F,WANG M,WANG Y,et al.An algorithm J-SC of detecting communities in complex networks [J].Physics Letters A,2017,381(42):3604-3612.
[33]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].Physica A:Statistical Mechanics and its Applications,2015,438:321-334.
[34]CHENG F,CUI T,SU Y,et al.A Local Information basedMulti-objective Evolutionary Algorithm for Community Detection in Complex Networks[J].Applied Soft Computing,2018,69:357-367.
[35]CHEN L G,WANG Y R,HUANG X M,et al.SA-SOM algorithm for detecting communities in complex networks[J].Physics Letters B,2017,31(29):1750262.
[36]GLEISER P M,DANON L.Community structure in Jazz[J].Advances in Complex Systems,2003,6(4):565-573.
[37]LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms[J].Physical Review E Statistical Nonlinear and Soft Matter Phy-sics,2008,78(4 Pt 2):046-110.
[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] CHEN Shi-cong, YUAN De-yu, HUANG Shu-hua, YANG Ming. Node Label Classification Algorithm Based on Structural Depth Network Embedding Model [J]. Computer Science, 2022, 49(3): 105-112.
[4] GUO Lei, MA Ting-huai. Friend Closeness Based User Matching [J]. Computer Science, 2022, 49(3): 113-120.
[5] 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.
[6] PU Shi, ZHAO Wei-dong. Community Detection Algorithm for Dynamic Academic Network [J]. Computer Science, 2022, 49(1): 89-94.
[7] CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure [J]. Computer Science, 2021, 48(9): 244-250.
[8] ZHENG Su-su, GUAN Dong-hai, YUAN Wei-wei. Heterogeneous Information Network Embedding with Incomplete Multi-view Fusion [J]. Computer Science, 2021, 48(9): 68-76.
[9] HU Xin-tong, SHA Chao-feng, LIU Yan-jun. Post-processing Network Embedding Algorithm with Random Projection and Principal Component Analysis [J]. Computer Science, 2021, 48(5): 124-129.
[10] ZHANG Jian-xiong, SONG Kun, HE Peng, LI Bing. Identification of Key Classes in Software Systems Based on Graph Neural Networks [J]. Computer Science, 2021, 48(12): 149-158.
[11] 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.
[12] NING Yi-xin, XIE Hui, JIANG Huo-wen. Survey of Graph Neural Network in Community Detection [J]. Computer Science, 2021, 48(11A): 11-16.
[13] 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.
[14] ZHU Guo-hui, ZHANG Yin, LIU Xiu-xia, SUN Tian-ao. Energy Efficient Virtual Network Mapping Algorithms Based on Node Topology Awareness [J]. Computer Science, 2020, 47(9): 270-274.
[15] DING Yu, WEI Hao, PAN Zhi-song, LIU Xin. Survey of Network Representation Learning [J]. Computer Science, 2020, 47(9): 52-59.
Full text



No Suggested Reading articles found!