Computer Science ›› 2022, Vol. 49 ›› Issue (5): 170-178.doi: 10.11896/jsjkx.210300206

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

Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning

WANG Ben-yu, GU Yi-jun, PENG Shu-fan, ZHENG Di-wen   

  1. School of Information and Network Security,People’s Public Security University of China,Beijing 100032,China
  • Received:2021-03-21 Revised:2021-05-18 Online:2022-05-15 Published:2022-05-06
  • About author:WANG Ben-yu,born in 1998,postgra-duate.His main research interests include complex network and deep lear-ning.
    GU Yi-jun,born in 1968,Ph.D,professor,Ph.D supervisor.His main research interests include complex network and deep learning.
  • Supported by:
    National Natural Science Foundation of China(61871204) and National Natural Science Youth Fund(61702026).

Abstract: Community structure is an important property of complex networks.It is profoundly significant for understanding the organizational structure and functions of complex networks.A community detection algorithm (Dynamic Distance Stochastic Competitive Learning,DDSCL) is proposed to solve the community detection problem of complex networks.DDSCL is based on dynamic distance and stochastic competitive learning.The algorithm first combines node degree values and Euclidean distances between nodes to determine the initial positions of particles in stochastic competitive learning,which will allow different particles to not compete within the same community at the beginning of the wander,speeding up the convergence of the particles.The dyna-mic distance between nodes is then combined with a dynamic distance algorithm to incorporate the dynamic distance between nodes into the particle prioritization walking process.The particle prioritization process is more directional and less random in this way.The particle travel process will also optimize the change in dynamic distance.When the particles reach a convergence state,the node is occupied by the particle that has the most control over it.Each particle in the network eventually corresponds to a community,and the community structure of the network is revealed according to the nodes occupied by each particle.DDSCL is compared in experimental tests on eight real network datasets,and it uses NMI and modularity Q -value as evaluation metrics.It’s found that DDSCL outperforms other algorithms overall.The algorithm first reduces the randomness of preferential walking of particles in stochastic competitive learning.Then DDSCL solves the problem of fragmented communities arising from dynamic distance algorithms,and improves the accuracy of community detection results.The experimental results show the proposed algorithm’s effectiveness.

Key words: Complex network, Community detection, Dynamic distance, Stochastic competitive learning, Particle competition

CLC Number: 

  • TP391
[1]FORTUNATO S.Community detection in graphs[J].Physics reports,2010,486(3/4/5):75-174.
[2]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.
[3]RADICCHI F,CASTELLANO C,CECCONI F,et al.Defining and identifying communities in networks[J].Proceedings of the national academy of sciences,2004,101(9):2658-2663.
[4]WANG Z,WANG C,LI X,et al.Evolutionary Markov Dyna-mics for Network Community Detection[J/OL].IEEE Transactions on Knowledge and Data Engineering,2020.https://ieeexplore.ieee.org/abstract/document/9099469.
[5]BIAN Y,LUO D,YAN Y,et al.Memory-based random walk for multi-query local community detection[J].Knowledge and Information Systems,2020,62(5):2067-2101.
[6]El KOUNI I B,KAROUI W,ROMDLHANE L B.Node Importance based Label Propagation Algorithm for overlapping community detection in networks[J].Expert Systems with Applications,2020,162:113020.
[7]SILVA T C,ZHAO L.Stochastic competitive learning in complex networks[J].IEEE Transactions on Neural Networks and Learning Systems,2012,23(3):385-398.
[8]SHAO J,HAN Z,YANG Q,et al.Community detection based on distance dynamics[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2015:1075-1084.
[9]KOHONEN T.The self-organizing map[J].Proceedings of the IEEE,1990,78(9):1464-1480.
[10]KOSKO B.Stochastic competitive learning[C]//1990 IJCNN International Joint Conference on Neural Networks.IEEE,1990:215-226.
[11]CARPENTER G A,GROSSBERG S.ART 2:Self-organization of stable category recognition codes for analog input patterns[J].Applied Optics,1987,26(23):4919-4930.
[12]QUILES M G,ZHAO L,ALONSO R L,et al.Particle competition for complex network community detection[J].Chaos:An Interdisciplinary Journal of Nonlinear Science,2008,18(3):033107.
[13]SILVA T C,ZHAO L.Detecting and preventing error propagation via competitive learning[J].Neural Networks,2013,41:70-84.
[14]VERRI F A N,URIO P R,ZHAO L.Network unfolding map by vertex-edge dynamics modeling[J].IEEE Transactions on Neural Networks and Learning Systems,2016,29(2):405-418.
[15]RODRIGUES R D,ZHAO L,ZHENG Q,et al.Structural out-lier detection:A tourist walk approach[C]//2017 13th International Conference on Natural Computation,Fuzzy Systems and Knowledge Discovery (ICNC-FSKD).IEEE,2017:382-387.
[16]GAO X,ZHENG Q,VERRI F A N,et al.Particle competition for multilayer network community detection[C]//Proceedings of the 2019 11th International Conference on Machine Learning and Computing.2019:75-80.
[17]LI W,GU Y,YIN D,et al.Research on the community number evolution model of public opinion based on stochastic competitive learning[J].IEEE Access,2020,8:46267-46277.
[18]PASSERINI J A R,BREVE F.Complex Network Construction for Interactive Image Segmentation Using Particle Competition and Cooperation:A New Approach[C]//International Confe-rence on Computational Science and Its Applications.Cham:Springer,2020:935-950.
[19]LI J H,WANG C D,LI P Z,et al.Discriminative metric learning for multi-view graph partitioning[J].Pattern Recognition,2018,75:199-213.
[20]SUN H,CH’NG E,YONG X,et al.A fast community detection method in bipartite networks by distance dynamics[J].Physica A:Statistical Mechanics and its Applications,2018,496:108-120.
[21]SUN H,JIA X,HUANG R,et al.Distance dynamics basedoverlapping semantic community detection for node-attributed networks[J/OL].Computational Intelligence,2020.https://onlinelibrary.wiley.com/doi/abs/10.1111/coin.12324.
[22]WAN J,HAN D,YANG Z,et al.An improved algorithm for detecting community defined by node-to-node dynamic distance[J].International Journal of Modern Physics C (IJMPC),2020,31(11):1-18.
[23]HENNIG C,HAUSDORF B.Design of dissimilarity measures:A new dissimilarity between species distribution areas[M]//Data Science and Classification.Berlin,Heidelberg:Springer,2006:29-37.
[24]DANIELSSON P E.Euclidean distance mapping[J].Computer Graphics and Image Processing,1980,14(3):227-248.
[25]REAL R,VARGAS J M.The probabilistic basis of Jaccard’s index of similarity[J].Systematic Biology,1996,45(3):380-385.
[26]CLAUSET A,NEWMAN M E J,Moore C.Finding community structure in very large networks[J].Physical Review E,2004,70(6):066111.
[27]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.
[28]PONS P,LATAPY M.Computing communities in large net-works using random walks[C]//International Symposium on Computer and Information Sciences.Berlin,Heidelberg:Sprin-ger,2005:284-293.
[29]ZACHARY W W.An information flow model for conflict and fission in small groups[J].Journal of Anthropological Research,1977,33(4):452-473.
[30]GIRBAN 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.
[31]LUSSEAU D,SCHNEIDER K,BOISSEAU O J,et al.The bo-ttlenose dolphin community of Doubtful Sound features a largeproportion of long-lasting associations[J].Behavioral Ecology
and Sociobiology,2003,54(4):396-405.
[32]ADAMIC L A,GLANCE N.The political blogosphere and the 2004 US election:divided they blog[C]//Proceedings of the 3rd International Workshop on Link Discovery.2005:36-43.
[33]GUIMERA R,DANON L,DIAZ-GUILERA A,et al.Self-similar community structure in a network of human interactions[J].Physical Review E,2003,68(6):065103.
[34]LESKOVEC J,KLEINBERG J,FALOUTSOS C.Graph evolution:Densification and shrinking diameters[J].ACM transactions on Knowledge Discovery from Data (TKDD),2007,1(1):2.
[35]MCAULEY J J,LESKOVEC J.Learning to discover social circles in ego networks[C]//NIPS.2012:539-547.
[36]YANG J,LESKOVEC J.Defining and evaluating network communities based on ground-truth[J].Knowledge and Information Systems,2015,42(1):181-213.
[37]WHITLEY D,STARKWEATHER T,BOGART C.Genetic algorithms and neural networks:Optimizing connections and connectivity[J].Parallel Computing,1990,14(3):347-361.
[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] 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.
[3] 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.
[4] PU Shi, ZHAO Wei-dong. Community Detection Algorithm for Dynamic Academic Network [J]. Computer Science, 2022, 49(1): 89-94.
[5] LI Jia-wen, GUO Bing-hui, YANG Xiao-bo, ZHENG Zhi-ming. Disease Genes Recognition Based on Information Propagation [J]. Computer Science, 2022, 49(1): 264-270.
[6] CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure [J]. Computer Science, 2021, 48(9): 244-250.
[7] MU Jun-fang, ZHENG Wen-ping, WANG Jie, LIANG Ji-ye. Robustness Analysis of Complex Network Based on Rewiring Mechanism [J]. Computer Science, 2021, 48(7): 130-136.
[8] HU Jun, WANG Yu-tong, HE Xin-wei, WU Hui-dong, LI Hui-jia. Analysis and Application of Global Aviation Network Structure Based on Complex Network [J]. Computer Science, 2021, 48(6A): 321-325.
[9] WANG Xue-guang, ZHANG Ai-xin, DOU Bing-lin. Non-linear Load Capacity Model of Complex Networks [J]. Computer Science, 2021, 48(6): 282-287.
[10] MA Yuan-yuan, HAN Hua, QU Qian-qian. Importance Evaluation Algorithm Based on Node Intimate Degree [J]. Computer Science, 2021, 48(5): 140-146.
[11] YIN Zi-qiao, GUO Bing-hui, MA Shuang-ge, MI Zhi-long, SUN Yi-fan, ZHENG Zhi-ming. Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network [J]. Computer Science, 2021, 48(5): 184-189.
[12] 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.
[13] LIU Sheng-jiu, LI Tian-rui, XIE Peng, LIU Jia. Measure for Multi-fractals of Weighted Graphs [J]. Computer Science, 2021, 48(3): 136-143.
[14] GONG Zhui-fei, WEI Chuan-jia. Link Prediction of Complex Network Based on Improved AdaBoost Algorithm [J]. Computer Science, 2021, 48(3): 158-162.
[15] 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.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] ZHU Wen-qiang. Personalized Trustworthy Group Identifying Model Based on O2O Service-oriented Mobile Social Network[J]. Computer Science, 2018, 45(6): 76 -83 .
[2] JI Hai-juan, ZHOU Cong-hua, LIU Zhi-feng. Symbolic Aggregate Approximation Method of Time Series Based on Beginning and End Distance[J]. Computer Science, 2018, 45(6): 216 -221 .
[3] ZHANG Yong-gang, CHENG Zhu-yuan. Research Progress on Max Restricted Path Consistency Constraint Propagation Algorithms[J]. Computer Science, 2018, 45(6A): 41 -45 .
[4] HAO Jun-sheng,LI Bing-feng,CHEN Xi,GAO Wen-juan. Design and Implementation of Network Subscription System Based on Android Platform[J]. Computer Science, 2018, 45(6A): 591 -594 .
[5] LIAO Jun, JIANG Chao-hui, GUO Chun and PING Yuan. Classification Anonymity Algorithm Based on Weight Attributes Entropy[J]. Computer Science, 2017, 44(7): 42 -46 .
[6] GAO Fang and HUANG Zhang-qin. Embedded Neural Network Face Recognition Method Based on Heterogeneous Multicore Parallel Acceleration[J]. Computer Science, 2018, 45(3): 288 -293 .
[7] LU Jia-wei, MA Jun, ZHANG Yuan-ming and XIAO Gang. Service Clustering Approach for Global Social Service Network[J]. Computer Science, 2018, 45(3): 204 -212 .
[8] WANG Rong-bing, AN Wei-kai, FENG Yong and XU Hong-yan. Important Micro-blog User Recommendation Algorithm Based on Label and PageRank[J]. Computer Science, 2018, 45(2): 276 -279 .
[9] LUO Yong-qi,YAN Xue-feng,FENG Xiang-wen and ZHOU Yong. Research and Implementation of Dynamic Data-driven Traffic Simulation Framework[J]. Computer Science, 2014, 41(Z6): 459 -462 .
[10] ZHANG Yan-feng,HUANG Xiang-sheng,LI Hang and WANG Meng-wei. Fast Stereo Matching Based on Progressive Reliable Point Growing Matching for Speckle Pattern Images[J]. Computer Science, 2014, 41(Z6): 143 -146 .