Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (4): 56-62.doi: 10.11896/jsjkx.220100155

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

Community Detection Based on Markov Similarity Enhancement and Network Embedding

ZENG Xiangyu, LONG Haixia, YANG Xuhua   

  1. College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China
  • Received:2022-01-16 Revised:2022-06-08 Online:2023-04-15 Published:2023-04-06
  • About author:ZENG Xiangyu,born in 1998,postgra-duate.His main research interests include community detection and graph neural network.
    YANG Xuhua,born in 1971,Ph.D,professor,is a member of China Computer Federation senior.His main research interests include machine learning and network science.
  • Supported by:
    National Natural Science Foundation of China(62176236,62106225).

PDF (PC)

312

Abstract: Community structure is ubiquitous in various complex networks in nature and is one of the important characteristics of network structure.Community detection can identify useful information in the network,and help to analyze the structure and function of the network.It is widely used in social networks,biology,medicine and other fields.Aiming at the low accuracy of the current community detection algorithm based on local similarity in complex networks,a community detection algorithm based on Markov similarity enhancement and network embedding is proposed.Firstly,inspired by the idea of Markov chain,a Markov similarity enhancement method is proposed,which obtains the steady-state Markov similarity enhancement matrix through the Mar-kov iterative state transition of the initial network.According to the Markov similarity index,the network is divided into initial community structure.Then,a new community similarity index is proposed by combining the network topology and network embedding.The small community in the initial community structure is merged with its closely connected community to obtain the network community structure.On 7 real networks and artificial networks with variable parameters,compared with other 5 well-known community detection algorithms,it is proved that the proposed algorithm has a good community detection effect.

Key words: Community detection, Complex network, Markov similarity, Network embedding, Community similarity

CLC Number: 

  • TP391
[1]LI M,LU S,ZHANG L,et al.A Community Detection Method for Social Network Based on Community Embedding[J].IEEE Transactions on Computational Social Systems,2021,8(2):308-318.
[2]ZHANG W,SHANG R,JIAO L.Complex Network Graph Embedding Method Based on Shortest Path and MOEA/D for Community Detection[J].Applied Soft Computing,2020,97:106764.
[3]ACMAN M,DORP L V,SANTINI J M,et al.Large-scale Network Analysis Captures Biological Features of Bacterial Plasmids[J].Nature Communications,2020,11(1):1-11.
[4]HAN N,QIAO S J,YUAN C A,et al.Fast Community Parallel Detection Algorithm in Mobile Social Networks[J].Journal of Chongqing University of Technology:Natural Science,2020,34(1):94-102.
[5]IMANE M,NADJET K.Community Detection UsingFireworks Optimization Algorithm[J].International Journal of Artificial Intelligence Tools,2019,28(3):1950010.
[6]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(3):036106.
[7]CLAUSET A,NEWMAN M E J,MOORE C.Finding Commu-nity Structure in Very Large Networks[J].Physical Review E,2004,70(6):066111.
[8]HU F,ZHU Y,SHI Y,et al.An Algorithm Walktrap-SPM forDetecting Overlapping Community Structure[J].International Journal of Modern Physics B,2017,31(15):1750121.
[9]NEWMAN M E J,GIRVAN M.Finding and Evaluating Community Structure in Networks[J].Physical Review E,2004,69(2):026113.
[10]GIRVAN M,NEWMAN M E J.Community Structure in Social and Biological Networks[J].Proceedings of the National Aca-demy of Sciences of the United States of America,2002,99(12):7821-7826.
[11]ROSVALL M,BERGSTROM C T.Maps of RandomWalks on Complex Networks Reveal Community Structure[J].Procee-dings of the National Academy of Sciences,2008,105(4):1118-1123.
[12]EUSTACE J,WANG X,CUI Y.Community Detection UsingLocal Neighborhood in Complex Networks[J].Physica A:Statistical Mechanics and its Applications,2015,436:665-667.
[13]LIU J L,WANG D L,ZHANG Y F,et al.Local Community DetectionApproach Based on Fuzzy Similarity Relation[J].Journal of Software,2020,31(11):3481-3491.
[14]KUMAR S,PANDA B S,AGGARWAL D.Community Detection in Complex Networks Using Network Embedding and Gravitational Search Algorithm[J].Journal of Intelligent Information Systems,2020,57(1):51-72.
[15]ZHAO X,LI X,ZHANG Z H,et al.Community Detection Algorithm Combining Community Embedding and Node Embedding[J].Computer Science,2020,47(10):121-125.
[16]HE D,WANG Y,CAO J,et al.A Network Embedding-en-hanced Bayesian Model for Generalized Community Detection in Complex Networks[J].Information Sciences,2021,575:306-322.
[17]WANG D,CUI P,ZHU W.Structural Deep Network Embed-ding[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2016:1225-1234.
[18]WANG T,YIN L Y,WANG X X.A community DetectionMethod Based on Local Similarity and Degree Clustering Information[J].Physica A,2018,490:1344-1354.
[19]ZHANG J,DING X,YANG J.Revealing the Role of Node Similarity and Community Merging in Community Detection[J].Knowledge-Based Systems,2018,165:407-419.
[20]VERMA P,GOYAL R.Influence Propagation Based Community Detection in Complex Networks[J].Machine Learning with Applications,2020,12:100019.
[21]YOU X,MA Y,LIU Z.A Three-stage Algorithm on Communi-ty Detection in Social Networks[J].Knowledge-Based Systems,2020,187:104822.
[22]PEROZZI B,AL-RFOU R,SKIENA S.Deepwalk:OnlineLearning of Social Representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.2014:701-710.
[23]MIKOLOV T,CHEN K,CORRADO G,et al.Efficient Estimation of Word Representations in Vector Space[J].arXiv:1301.3781,2013.
[24]GROVER A,LESKOVEC J.Node2vec:Scalable Feature Lear-ning for Networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2016:855-864.
[25]TANG J,QU M,WANG M,et al.Line:Large-scale Information Network Embedding[C]//Proceedings of the 24th International Conference on World Wide Web.2015:1067-1077.
[26]NEWMAN M E J.Fast Algorithm for Detecting CommunityStructure in Networks[J].Physical Review E,2004,69(6):066133.
[27]NEWMAN M E J.Finding Community Structure in Networks Using the Eigenvectors of Matrices[J].Physical Review E,2006,74(3):036104.
[28]CLAUSET A,NEWMAN M E J,MOORE C.Finding Community Structure in Very Large Networks[J].Physical Review E,2004,70(6):066111.
[29]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.
[30]SU Y S,LIU C L,NIU Y Y,et al.A Community Structure Enhancement-based Community Detection Algorithm for Complex Networks[J].IEEE Transactions on Systems Man Cybernetics-Systems,2021,51(5):2833-2846.
[31]SUN Z J,SUN Y N,CHANG X F,et al.Community Detection Based on the Matthew Effect[J].Knowledge-Based Systems,2020,205:106256.
[32]ZHANG L,PAN H B,SU Y S,et al.A Mixed RepresentationBased Multiobjective Evolutionary Algorithm for Overlapping Community Detection[J].IEEE Transactions on Cybernetics,2017,47(9):2703-2716.
[33]JIANG H,LIU Z,LIU C,et al.Community Detection in Complex Networks with an Ambiguous Structure Using Central Node Based Link Prediction[J].Knowledge-Based Systems,2020,195:105626.
[34]LIU H J,MA H F,ZHAO Q Q,et al.Target Community Detection with User Interest Preferences and Influence[J].Journal of Computer Research and Development,2021,58(1):70-82.
[35]LU H,SHEN Z,SANG X S,et al.Community Detection Me-thod Using Improved Density Peak Clustering and Nonnegative Matrix Factorization[J].Neorocomputing,2020,415:247-257.
[36]CHEN Y Z,SHI S,ZHU W P,et al.An Incremental Community Detection Algorithm Based on Neighborhood Following Relationship[J].Chinese Journal of Computers,2017,40(3):570-583.
[37]NATH K,SHANMUGAM R,VARADARANJAN V.Ma-CODE:A Multi-phase Approach on Community Detection in Evolving Networks[J].Information Sciences,2021,569:326-343.
[38]SAID A,ABBASI R A,MAQBOOL O,et al.CC-GA:A Clustering Coefficient Based Genetic Algorithm for Detecting Communities in Social Networks[J].Applied Soft Computing,2018,63:59-70.
[1] DUAN Shunran, YIN Meijuan, LIU Fenlin, JIAO Longlong, YU Lanlan. Nodes’ Ranking Model Based on Influence Prediction [J]. Computer Science, 2023, 50(3): 155-163.
[2] ZHENG Wen-ping, LIU Mei-lin, YANG Gui. Community Detection Algorithm Based on Node Stability and Neighbor Similarity [J]. Computer Science, 2022, 49(9): 83-91.
[3] 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.
[4] YANG Bo, LI Yuan-biao. Complex Network Analysis on Curriculum System of Data Science and Big Data Technology [J]. Computer Science, 2022, 49(6A): 680-685.
[5] 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.
[6] 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.
[7] GUO Lei, MA Ting-huai. Friend Closeness Based User Matching [J]. Computer Science, 2022, 49(3): 113-120.
[8] 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.
[9] ZHAO Xue-lei, JI Xin-sheng, LIU Shu-xin, LI Ying-le, LI Hai-tao. Link Prediction Method for Directed Networks Based on Path Connection Strength [J]. Computer Science, 2022, 49(2): 216-222.
[10] TANG Qi-you, ZHANG Feng-li, WANG Rui-jin, WANG Xue-ting, ZHOU Zhi-yuan, HAN Ying-jun. Method of Attributed Heterogeneous Network Embedding with Multiple Features [J]. Computer Science, 2022, 49(12): 146-154.
[11] ZHENG Wen-ping, WANG Ning, YANG Gui. Overlapping Community Detection Algorithm Based on Local Path Information [J]. Computer Science, 2022, 49(12): 155-162.
[12] DUAN Xiao-hu, CAO Fu-yuan. Node Local Similarity Based Two-stage Density Peaks Algorithm for Overlapping Community Detection [J]. Computer Science, 2022, 49(12): 170-177.
[13] PAN Yu, WANG Shuai-hui, ZHANG Lei, HU Gu-yu, ZOU Jun-hua, WANG Tian-feng, PAN Zhi-song. Survey of Community Detection in Complex Network [J]. Computer Science, 2022, 49(11A): 210800144-11.
[14] YUAN Hui-lin, FENG Chong. Ranking and Recognition of Influential Nodes Based on k-shell Entropy [J]. Computer Science, 2022, 49(11A): 210800177-5.
[15] YUAN Hui-lin, HAN Zhen, FENG Chong, HUANG Bi, LIU Jun-tao. Community Discovery Method Based on Influence of Core Nodes [J]. Computer Science, 2022, 49(11A): 211100002-7.
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.