融合动态距离和随机竞争学习的社区发现算法

doi:10.11896/jsjkx.210300206

摘要/Abstract

摘要： 社区结构作为复杂网络的一个重要属性,对于了解复杂网络的组织架构和功能具有深远意义。为了解决复杂网络的社区发现问题,提出了一种融合动态距离和随机竞争学习的社区发现算法(Dynamic Distance Stochastic Competitive Learning,DDSCL)。该算法首先结合节点度值和节点间的欧氏距离来确定随机竞争学习中粒子的初始位置,使得不同粒子在游走初期不会在同一社区内进行竞争,加快了粒子的收敛速度;然后结合动态距离算法,将节点间的动态距离融入粒子优先游走过程中,使得粒子的优先游走过程更具方向性,减小了随机性,并且粒子游走的过程也会优化动态距离的变化;当粒子达到收敛状态时,节点将被对其具有最大控制力的粒子占据。最后网络中每一个粒子对应一个社区,根据各粒子占据的节点来揭示网络的社区结构。在8个真实的网络数据集上,以NMI和模块度Q值为评价指标,将DDSCL算法与现有的代表性算法进行实验比较,发现DDSCL算法整体上优于其他算法,其不仅降低了随机竞争学习中粒子优先游走的随机性,而且解决了动态距离算法中出现的碎片化社区问题,提高了社区发现结果的准确性。实验结果表明,所提算法具有有效性和可行性。

关键词: 动态距离, 复杂网络, 粒子竞争, 社区发现, 随机竞争学习

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: Community detection, Complex network, Dynamic distance, Particle competition, Stochastic competitive learning

中图分类号:

TP391

王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法[J]. 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206

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. https://doi.org/10.11896/jsjkx.210300206

参考文献

[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.

相关文章 15

[1]	郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2]	何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[3]	杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 Complex Network Analysis on Curriculum System of Data Science and Big Data Technology 计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123
[4]	何亦琛, 毛宜军, 谢贤芬, 古万荣. 基于点割集图分割的矩阵变换与分解的推荐算法 Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation 计算机科学, 2022, 49(6A): 272-279. https://doi.org/10.11896/jsjkx.210600159
[5]	唐春阳, 肖玉芝, 赵海兴, 冶忠林, 张娜. 面向双层网络的EWCC社区发现算法 EWCC Community Discovery Algorithm for Two-Layer Network 计算机科学, 2022, 49(4): 49-55. https://doi.org/10.11896/jsjkx.210800275
[6]	陈世聪, 袁得嵛, 黄淑华, 杨明. 基于结构深度网络嵌入模型的节点标签分类算法 Node Label Classification Algorithm Based on Structural Depth Network Embedding Model 计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[7]	杨旭华, 王磊, 叶蕾, 张端, 周艳波, 龙海霞. 基于节点相似性和网络嵌入的复杂网络社区发现算法 Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding 计算机科学, 2022, 49(3): 121-128. https://doi.org/10.11896/jsjkx.210200009
[8]	赵学磊, 季新生, 刘树新, 李英乐, 李海涛. 基于路径连接强度的有向网络链路预测方法 Link Prediction Method for Directed Networks Based on Path Connection Strength 计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[9]	李家文, 郭炳晖, 杨小博, 郑志明. 基于信息传播的致病基因识别研究 Disease Genes Recognition Based on Information Propagation 计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[10]	陈湘涛, 赵美杰, 杨梅. 基于子图结构的局部社区发现算法 Overlapping Community Detection Algorithm Based on Subgraph Structure 计算机科学, 2021, 48(9): 244-250. https://doi.org/10.11896/jsjkx.201100010
[11]	穆俊芳, 郑文萍, 王杰, 梁吉业. 基于重连机制的复杂网络鲁棒性分析 Robustness Analysis of Complex Network Based on Rewiring Mechanism 计算机科学, 2021, 48(7): 130-136. https://doi.org/10.11896/jsjkx.201000108
[12]	胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉. 基于复杂网络的全球航空网络结构分析与应用 Analysis and Application of Global Aviation Network Structure Based on Complex Network 计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112
[13]	王学光, 张爱新, 窦炳琳. 复杂网络上的非线性负载容量模型 Non-linear Load Capacity Model of Complex Networks 计算机科学, 2021, 48(6): 282-287. https://doi.org/10.11896/jsjkx.200700040
[14]	马媛媛, 韩华, 瞿倩倩. 基于节点亲密度的重要性评估算法 Importance Evaluation Algorithm Based on Node Intimate Degree 计算机科学, 2021, 48(5): 140-146. https://doi.org/10.11896/jsjkx.200300184
[15]	殷子樵, 郭炳晖, 马双鸽, 米志龙, 孙怡帆, 郑志明. 群智体系网络结构的自治调节:从生物调控网络结构谈起 Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network 计算机科学, 2021, 48(5): 184-189. https://doi.org/10.11896/jsjkx.210200161

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed