Computer Science ›› 2022, Vol. 49 ›› Issue (3): 121-128.doi: 10.11896/jsjkx.210200009

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

Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding

YANG Xu-hua, WANG Lei, YE Lei, ZHANG Duan, ZHOU Yan-bo, LONG Hai-xia   

  1. College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China
  • Received:2021-02-01 Revised:2021-05-11 Online:2022-03-15 Published:2022-03-15
  • About author:YANG Xu-hua,born in 1971,Ph.D,professor,is a senior member of China Computer Federation.His main research interests include machine lear-ning and network science.
    LONG Hai-xia,born in 1987,Ph.D,lecturer.Her main research interests include machine learning,medical image processing and complex network analysis.
  • Supported by:
    National Natural Science Foundation of China(61773348).

Abstract: The community detection algorithm is very important for analyzing the topology and hierarchical structure of complex networks and predicting the evolution trend of complex networks.Traditional community detection algorithm does not have high accuracy and ignores the importance of network embedding.Aiming at such problems,a parameter-free community detection algorithm based on node similarity and network embedding Node2Vec method is proposed.First,we use the network embedding Node2Vec method to map network nodes into data points represented by low-dimensional vectors in Euclidean space,calculate the cosine similarity between the data points represented by the low-dimensional vector,construct a preference network according to the maximum similarity between the corresponding nodes,obtain the initial community detection,and use the maximum degree node of each initial community as a candidate node.Then we find the central node among the candidate nodes according to the average degree of the network and the average shortest path.Finally,the data points and their numbers corresponding to the central node are used as the initial centroid and cluster number,and the data represented by the low-dimensional vector are calculated by K-Means algorithm.The points are clustered,and the corresponding network nodes are divided into communities.This algorithm is a method of community division without parameters,which can independently extract parameters from the network without setting different hyper-parameters according to different networks,so that it can automatically and quickly identify the community structure of complex networks.In 8 real networks and artificial networks above,by comparing with other 5 well-known community discovery algorithms,numerical simulation experiments show that the proposed algorithm has good community discovery effect.

Key words: K-Means clustering, Network embedding, Node similarity, Parameter-free community detection, Preference network

CLC Number: 

  • TP391
[1]SAGANOWSKI S.Predicting Community Evolution in SocialNetworks[C]//the 2015 IEEE/ACM International Confe-rence.ACM,2015:3053-3096.
[2]ACMAN M,DORP L V,SANTINI J M,et al.Large-scale net-work analysis captures biological features of bacterial plasmids[J].Nature Communications,2020,11(1):46.
[3]CHOUCHANI N,ABED M.Online social network analysis:de-tection of communities of interest[J].Journal of Intelligent Information Systems,2020,54(2):1-17.
[4]NEWMAN M,GIRVAN M.Finding and evaluating community structure in networks[J].Physica A,2004,69(2):26113.
[5]KRAMER J,BOONE L,CLIFFORD T,et al.Analysis of Medical Data Using Community Detection on Inferred Networks[J].IEEE Journal of Biomedical and Health Informatics,2020,24(11):3136-3143.
[6]KOUNI I B E,KAROUI W,ROMDHANEL B.Node Impor-tance based Label Propagation Algorithm for overlapping community detection in networks[J].Expert Systems with Applications,2019,162:113020.
[7]ZIVICH P N,SMITH N R,FRERICHSL M,et al.A Guide for Choosing Community Detection Algorithms in Social Network Studies:The Question Alignment Approach[J].American Journal of Preventive Medicine,2020,59(4):597-605.
[8]ROSVALL M, BERGSTROM C T.Maps of random walks on complex networks reveal community structure[J].Proceedings of the National Academy of Sciences of the United States of America,2008,105(4):1118-1127.
[9]ZHOU T,LV L Y,ZHANG Y C.Predicting missing links via local information[J].European Physical Journal B,2009,71(4):623-630.
[10]TASGIN M,BINGOL H O.Community detection using prefe-rence networks[J].Physica A:Statistical Mechanics and its Applications,2018,495:126-136.
[11]LIU Z,MA Y.A Divide and Agglomerate Algorithm for Community Detection in Social Networks[J].Information Sciences,2019,482:321-333.
[12]ZHAO X,ZHANG Z H,ZHANG C W,et al.RGNE:A coarse-grained network embedded overlapping community discovery method[J].Computer Research and Development,2020,57(6):1302-1311.
[13]YE Z L,ZHAO H X,ZHANG K,et al.Network representation learning based on neighbor node and relationship model optimization[J].Computer Research and Development,2019,56(12):2562-2577.
[14]ZHAO X,LI X,ZHANG Z H,et al.Community discovery algorithm combining community embedding and node embedding[J].Computer Science,2020,47(10):121-125.
[15]XIE Y,GONG M,WANG S,et al.Community Discovery in Networks with Deep Sparse Filtering[J].Pattern Recognition,2018,81:50-59.
[16]HU F,LIU J,LI L,et al.Community detection in complex networks using Node2vec with spectral clustering[J].Physica A:Statistical Mechanics and its Applications,2020,45(2):13247.
[17]DING Y,WEI H,PAN Z S,et al.Overview of network representation learning algorithms[J].Computer Science,2020,47(9):52-59.
[18]PEROZZI B,AL-RFOU R,SKIENA S.Deepwalk:Online lear-ning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.2014:701-710.
[19]WANG D,CUI P,ZHU W.Structural deep network embedding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2016:1225-1234.
[20]KIPF T N,WELLING M.Semi-supervised classification withgraph convolutional networks[C]//5th International Conference on Learning Representations.ICLR,2017.
[21]YE J.Improved cosine similarity measures of simplified neutrosophic sets for medical diagnoses[J].Artificial Intelligence in Medicine,2015,63(3):171-179.
[22]ADAMIC L A,ADAR E.Friends and neighbors on the Web[J].Social Networks,2003,25(3):211-230.
[23]RAVASZ E,SOMERA A L,MONGRU D A,et al.Hierarchical Organization of Modularity in Metabolic Networks[J].Science,2002,297(5586):1551-1555.
[24]LEICHT E A,HOLME P,NEWMAN M E J.Vertex similarity in networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2006,73(2):026120.
[25]GODICHON-BAGGIONI A,MAUGIS-RABUSSEAU C,RAU A.Clustering transformed compositional data using K-means,with applications in gene expression and bicycle sharing system data[J].Journal of Applied Statistics,2017,46(1):47-65.
[26]NEWMAN M E J.Finding community structure in networksusing the eigenvectors of matrices[J].Physical Review E,2006,74(3):036104.
[27]CHATTOPADHYAY S,BASU T,DAS A K,et al.A similarity based generalized modularity measure towards effective community discovery in complex networks[J].Physica A:Statistical Mechanics and its Applications,2019,527:121338.
[28]HESAMIPOUR S,BALAFAR M A.A new method for detecting communities and their centers using the Adamic/Adar Index and game theory[J].Physica A:Statistical Mechanics and its Applications,2019,535:122354.
[29]AHAJJAM S,EL HADDAD M,BADIR H.A new scalableleader-community detection approach for community detection in social networks[J].Social Networks,2018,54:41-49.
[30]MA T,LIU Q,CAO J,et al.LGIEM:Global and local node influence based community detection[J].Future Generation Computer Systems,2020,105:533-546.
[31]LIU S S,XIA Z Y.A two-stage BFS local community detection algorithm based on node transfer similarity and Local Clustering Coefficient-Science Direct[J].Physica A:Statistical Mechanics and its Applications,2019(537):122717.
[32]LUO W J,LU N.Local community detection by the nearestnodes with greater centrality[J].Information Sciences,2020,517:377-392.
[33]YOU X,MA Y,LIU Z.A three-stage algorithm on community detection in social networks[J].Knowledge-Based Systems,2020,187(Jan.):104822.1-104822.12.
[34]CHEN D,SU H.Framework based on communicability to mea-sure the similarity of nodes in complex networks[J].Information Sciences,2020,524:241-253.
[35]GUIMERÀ R,DANON L,DÍAZ-GUILERA A,et al.Self-similar community structure in a network of human interactions[J].Physical Review E,2004,68(6 Pt 2):065103.
[36]XU R B,CHE Y,WANG X M,et al.Stacked autoencoder-based community detection method via an ensemble clustering framework[J].Information Sciences,2020,526:151-165.
[1] 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.
[2] GUO Lei, MA Ting-huai. Friend Closeness Based User Matching [J]. Computer Science, 2022, 49(3): 113-120.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[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] JIN Yu-fang, WU Xiang, DONG Hui, YU Li, ZHANG Wen-an. Improved YOLO v4 Algorithm for Safety Helmet Wearing Detection [J]. Computer Science, 2021, 48(11): 268-275.
[9] DING Yu, WEI Hao, PAN Zhi-song, LIU Xin. Survey of Network Representation Learning [J]. Computer Science, 2020, 47(9): 52-59.
[10] 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.
[11] SHI Chao-wei, MENG Xiang-ru, MA Zhi-qiang, HAN Xiao-yang. Virtual Network Embedding Algorithm Based on Topology Comprehensive Evaluation and Weight Adaptation [J]. Computer Science, 2020, 47(7): 236-242.
[12] WU Yong, WANG Bin-jun, ZHAI Yi-ming, TONG Xin. Study on Co-citation Enhancing Directed Network Embedding [J]. Computer Science, 2020, 47(12): 279-284.
[13] 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.
[14] YE Zhong-lin, ZHAO Hai-xing, ZHANG Ke, ZHU Yu. Network Representation Learning Based on Multi-view Ensemble Algorithm [J]. Computer Science, 2019, 46(1): 117-125.
[15] LIU Jing-lei, LIAO Shi-zhong. Complexity of CP-nets Learning [J]. Computer Science, 2018, 45(6): 211-215.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!