基于粒子竞争机制的半监督社区发现算法

doi:10.3778/j.issn.1673-9418.2106040

摘要/Abstract

摘要： 社区发现是复杂网络重要研究内容之一。传统社区发现算法在复杂网络结构不清晰时效果不佳，并且无法有效利用复杂网络中易获取的先验信息。为了解决复杂网络的社区发现问题，提出一种融合节点粒子竞争机制和边粒子竞争机制的半监督社区发现算法（SSPC）。该算法首先通过网络中的先验信息在已标记节点上产生粒子。接下来粒子通过既定的规则在网络中执行游走和重启步骤，充分体现粒子游走的倾向性，降低粒子游走的随机性，加快粒子的收敛速度并且限制粒子游走范围。最后，当粒子达到收敛状态时，网络中的节点将被某一类粒子占据。根据各类粒子占据的节点来揭示网络的社区结构。在真实网络数据集和LFR人工基准网络上与近几年具有代表性的社区发现算法进行实验对比，发现SSPC算法在NMI指标上整体优于其他算法，可以获得更好的社区发现结果。

关键词: 粒子竞争机制, 半监督学习, 社区发现, 粒子游走, 重启机制

Abstract: Community detection is one of important research elements of complex networks. Traditional community detection algorithms are ineffective when the structure of complex networks is unclear. They cannot effectively exploit the easily accessible a priori information in complex networks. A semi-supervised community detection algorithm based on particle competition (SSPC) is proposed to solve community detection problem of complex networks. SSPC combines the node particle competition and the edge particle competition. Firstly, SSPC generates particles on the tagged nodes through a priori information in the network. Next, the particles perform walking and restarting steps in the network through established rules, which fully reflects particles’ tendency to walk, reducing particles’ randomness walking, accelerating particles’ convergence speed and limiting particles’ walking range. Finally, when the particles reach convergence, the nodes in the network will be occupied by a certain class of particles. The community structure of network is revealed based on the nodes occupied by each class of particles. Experimental comparisons with representative community detection algorithms of recent years on real network datasets and the LFR artificial benchmark network reveal that SSPC outperforms other algorithms overall in NMI index and can obtain better community detection results.

Key words: particle competition, semi-supervised learning, community detection, particle walking, restart mechanism

王本钰, 顾益军, 彭舒凡. 基于粒子竞争机制的半监督社区发现算法[J]. 计算机科学与探索, 2023, 17(3): 608-619.

WANG Benyu, GU Yijun, PENG Shufan. Semi-supervised Community Detection Algorithm Based on Particle Competition[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(3): 608-619.

参考文献

[1] JIN S, ZENG X, XIA F, et al. Application of deep learning methods in biological networks[J]. Briefings in Bioinforma-tics, 2021, 22(2): 1902-1917.
[2] CHUNAEV P. Community detection in node-attributed social networks: a survey[J]. Computer Science Review, 2020, 37: 100286.
[3] WU L, ZHANG Q, CHEN C H, et al. Deep learning techni-ques for community detection in social networks[J]. IEEE Access, 2020, 8: 96016-96026.
[4] NEWMAN M E J, GIRVAN M. Finding and evaluating com-munity structure in networks[J]. Physical Review E, 2004, 69(2): 026113.
[5] 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.
[6] SILVA T C, ZHAO L. Stochastic competitive learning in com-plex networks[J]. IEEE Transactions on Neural Networks and Learning Systems, 2012, 23(3): 385-398.
[7] SHAO J, HAN Z, YANG Q, et al. Community detection ba-sed on distance dynamics[C]//Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, Aug 10-13, 2015. New York: ACM, 2015: 1075-1084.
[8] ZHANG T, XIONG Y, ZHANG J, et al. CommDGI: commu-nity detection oriented deep graph infomax[C]//Proceedings of the 29th ACM International Conference on Information & Knowledge Management, Galway, Oct 19-23, 2020. New York: ACM, 2020: 1843-1852.
[9] XIE Y, WANG X, JIANG D, et al. High-performance com-munity detection in social networks using a deep transitive autoencoder[J]. Information Sciences, 2019, 493: 75-90.
[10] JIA Y T, ZHANG Q Q, ZHANG W N, et al. Community-GAN: community detection with generative adversarial nets[C]//Proceedings of the 2019 World Wide Web Conference, San Francisco, May 13-17, 2019. New York: ACM, 2019: 784-794.
[11] LIU D, BAI H Y, LI H J, et al. Semi-supervised community detection using label propagation[J]. International Journal of Modern Physics B, 2014, 28(29): 1450208.
[12] ZHANG Z Y, SUN K D, WANG S Q. Enhanced commu-nity structure detection in complex networks with partial back-ground information[J]. Scientific Reports, 2013, 3(1): 1-7.
[13] ZHANG Z Y. Community structure detection in complex net-works with partial background information[J]. Europhysics Letters, 2013, 101(4): 48005.
[14] HUA Z, YANG Y, QIU H. Node influence-based label pro-pagation algorithm for semi-supervised learning[J]. Neural Computing and Applications, 2021, 33(7): 2753-2768.
[15] LIU D, LI Q, RU Y, et al. The network representation lear-ning algorithm based on semi-supervised random walk[J]. IEEE Access, 2020, 8: 222956-222965.
[16] FAN L, XU S, LIU D, et al. Semi-supervised community detection based on distance dynamics[J]. IEEE Access, 2018, 6: 37261-37271.
[17] LU H, SANG X, ZHAO Q, et al. Community detection al-gorithm based on nonnegative matrix factorization and pair-wise constraints[J]. Physica A: Statistical Mechanics and Its Applications, 2020, 545: 123491.
[18] 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.
[19] QUILES M G, ZHAO L, ALONSO R L, et al. Particle com-petition for complex network community detection[J]. Chaos: An Interdisciplinary Journal of Nonlinear Science, 2008, 18(3): 033107.
[20] 王本钰, 顾益军, 彭舒凡, 等. 融合动态距离和随机竞争学习的社区发现算法[J]. 计算机科学, 2022, 49(5): 170-178.
WANG B Y, GU Y J, PENG S F, et al. Community detec-tion algorithm based on dynamic distance and stochastic com-petitive learning[J]. Computer Science, 2022, 49(5): 170-178.
[21] SILVA T C, ZHAO L. Detecting and preventing error propa-gation via competitive learning[J]. Neural networks, 2013, 41: 70-84.
[22] LI W, YIN D, YUAN D, et al. Particle propagation model for dynamic node classification[J]. IEEE Access, 2020, 8: 140205-140215.
[23] VERRI F A N, URIO P R, ZHAO L. Advantages of edge-centric collective dynamics in machine learning tasks[J]. Jour-nal of Applied Nonlinear Dynamics, 2018, 7(3): 269-285.
[24] RODRIGUES R D, ZHAO L, ZHENG Q, et al. Structural outlier detection: a tourist walk approach[C]//Proceedings of the 2017 13th International Conference on Natural Compu-tation, Fuzzy Systems and Knowledge Discovery, Guilin, Jul 29-31, 2017. Piscataway: IEEE, 2017: 382-387.
[25] GAO X, ZHENG Q, VERRI F A N, et al. Particle compe-tition for multilayer network community detection[C]//Pro-ceedings of the 2019 11th International Conference on Ma-chine Learning and Computing, Zhuhai, Feb 22-24, 2019. New York: ACM, 2019: 75-80.
[26] LI W, GU Y, YIN D, et al. Research on the community num-ber evolution model of public opinion based on stochastic competitive learning[J]. IEEE Access, 2020, 8: 46267-46277.
[27] PASSERINI J A R, BREVE F. Complex network construc-tion for interactive image segmentation using particle com-petition and cooperation: a new approach[C]//LNCS 12249: Proceedings of the 20th International Conference on Com-putational Science and Its Applications, Cagliari, Jul 1-4, 2020. Cham: Springer, 2020: 935-950.
[28] LUSSEAU D, SCHNEIDER K, BOISSEAU O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology, 2003, 54(4): 396-405.
[29] GIRBAN M, NEWMAN M E J. Community structure in so-cial and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.
[30] 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, Chicago, Aug 21- 25, 2005. New York: ACM, 2005: 36-43.
[31] YANG J, LESKOVEC J. Defining and evaluating network communities based on ground-truth[J]. Knowledge and In-formation Systems, 2015, 42(1): 181-213.
[32] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Bench-mark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4): 046110.
[33] ZHOU K, MARTIN A, PAN Q, et al. SELP: semi-supervised evidential label propagation algorithm for graph data clus-tering[J]. International Journal of Approximate Reasoning, 2018, 92: 139-154.
[34] LIU D, LIU X, WANG W, et al. Semi-supervised community detection based on discrete potential theory[J]. Physica A: Statistical Mechanics and Its Applications, 2014, 416: 173-182.
[35] ROSVALL M, BERGSTROM C T. Maps of random walks on complex networks reveal community structure[J]. Procee-dings of the National Academy of Sciences, 2008, 105(4): 1118-1123.
[36] CLAUSET A, NEWMAN M E J, MOORE C. Finding com-munity structure in very large networks[J]. Physical Review E, 2004, 70(6): 066111.
[37] PONS P, LATAPY M. Computing communities in large net-works using random walks[C]//Proceedings of the 2005 In-ternational Symposium on Computer and Information Sciences, Istanbul, Oct 26-28, 2005. Berlin: Springer, 2005: 284-293.
[38] WHITLEY D, STARKWEATHER T, BOGART C. Genetic algorithms and neural networks: optimizing connections and connectivity[J]. Parallel Computing, 1990, 14(3): 347-361.