Dual Supervised Network Embedding Based Community Detection Algorithm
ZHENG Wenping1,2,3, WANG Yingnan1, YANG Gui1
1. School of Computer and Information Technology, Shanxi University, Taiyuan 030006; 2. Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, Shanxi University, Taiyuan 030006; 3. Institute of Intelligent Information Processing, Shanxi University, Taiyuan 030006
Abstract A network embedding based community detection algorithm is easy to fall into local extremes during the independent node embedding or clustering process. Aiming at this problem, a dual supervised network embedding based community detection algorithm(DSNE) is proposed. Firstly, a graph auto-encoder is utilized to gain the embedding of nodes to maintain the first-order similarity of the network. Then, the modularity is optimized to find the communities with nodes tightly connected. The communities with similar nodes in the embedding space are discovered by self-supervised clustering optimization. A mutual supervision mechanism is introduced into DSNE to keep the consistency between the discovered communities in modularity optimization and self-supervised clustering and prevent the algorithm from falling into local extremes. Results of comparative experiments show DSNE exhibits better performance on 4 real complex networks.
Fund:National Natural Science Foundation of China(No.62072292), 1331 Engineering Project of Shanxi Province
Corresponding Authors:ZHENG Wenping, Ph.D., professor. Her research inte-rests include complex network analysis and bioinformatics.
About author:: WANG Yingnan, master student. His research interests include graph neural network and community detection. YANG Gui, Ph.D., senior experimentalist. His research interests include data mining and bioinformatics.
[1] BLONDEL V D, GUILLAUME J, LAMBIOTTE R.Fast Unfolding of Communities in Large Networks [J/OL]. [2021-03-21]. http://antipaedo.lip6.fr/T12/communities.pdf. [2] NEWMAN M E J. Fast Algorithm for Detecting Community Structure in Networks. Physical Review E, 2004, 69(6). DOI: 10.1103/PhysRevE.69.066133. [3] CLAUSET A, NEWMAN M E J, MOORE C. Finding Community Structure in Very Large Networks. Physical Review E, 2004, 70(6). DOI: 10.1103/PhysRevE.70.066111. [4] 郭昆,彭胜波,陈羽中,等.基于密度聚类的增量动态社区发现算法.模式识别与人工智能, 2018, 31(11): 965-978. (GUO K, PENG S B, CHEN Y Z, et al. Incremental Dynamic Community Detection Algorithm Based on Density Clustering. Pa-ttern recognition and Artificial Intelligence, 2018, 31(11): 965-978.) [5] RAGHAVAN U N, ALBERT R, KUMARA S.Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks. Physical Review E, 2007, 76(3). DOI: 10.1103/PhysRevE.76.036106. [6] BARBER M J, CLARK J W.Detecting Network Communities by Propagating Labels under Constraints. Physical Review E, 2009, 80(2). DOI: 10.1103/PhysRevE.80.026129. [7] LIU X, MURATA T.Advanced Modularity-Specialized Label Propagation Algorithm for Detecting Communities in Networks. Physica A: Statistical Mechanics and Its Applications, 2010, 389(7): 1493-1500. [8] LI W, HUANG C, WANG M, et al. Stepping Community Detection Algorithm Based on Label Propagation and Similarity. Physica A: Statistical Mechanics and Its Applications, 2017, 472: 145-155. [9] 王杰. 数据驱动的蛋白质互作用网络中复合体检测算法研究.博士学位论文.太原:山西大学, 2019. (WANG J.Data-Driven Research on Algorithms of Protein Complex Detection in Protein Interaction Networks. Ph.D. Dissertation, Taiyuan,China: Shanxi University, 2019.) [10] 郭昆,陈而宝,郭文忠.基于边密度聚类的重叠社区发现算法.模式识别与人工智能, 2018, 31(8): 693-703. (GUO K, CHEN E B, GUO W Z.Overlapping Community Detection Based on Edge Density Clustering. Pattern Recognition and Artificial Intelligence, 2018, 31(8): 693-703.) [11] PEROZZI B, AL-RFOU R, SKIENA S.DeepWalk: Online Lear-ning of Social Representations // Proc of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York,USA: ACM, 2014: 701-710. [12] GROVER A, LESKOVEC J. node2Vec: Scalable Feature Learning for Networks // Proc of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York,USA: ACM, 2016: 855-864. [13] WANG D X, CUI P, ZHU W W.Structural Deep Network Embe-dding // Proc of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York,USA: ACM, 2016: 1225-1234. [14] CAO S S, LU W, XU Q K.Deep Neural Networks for Learning Graph Representations // Proc of the 30th AAAI Conference on Artificial Intelligence. Palo Alto,USA: AAAI, 2016: 1145-1152. [15] WANG X, CUI P, WANG J, et al. Community Preserving Network Embedding // Proc of the 31st AAAI Conference on Artificial Intelligence. Palo Alto,USA: AAAI, 2017: 203-209. [16] YANG C, LIU Z Y, ZHAO D L.Network Representation Learning with Rich Text Information // Proc of the 24th International Joint Conference on Artificial Intelligence. New York,USA: ACM, 2015: 2111-2117. [17] HUANG X, LI J D, HU X.Accelerated Attributed Network Embedding // Proc of the SIAM International Conference on Data Mining. Philadelphia,USA: SIAM, 2017: 633-641. [18] KIPF T N, WELLING M.Variational Graph Auto-Encoders[C/OL].[2021-03-21]. http://arxiv.org/pdf/1611.07308.pdf. [19] KIPF T N, WELLING M.Semi-supervised Classification with Gra-ph Convolutional Networks[C/OL]. [2021-03-21].https://arxiv.org/pdf/1609.02907v3.pdf. [20] SALEHI A, DAVULCU H.Graph Attention Auto-Encoders // Proc of the 32nd IEEE International Conference on Tools with Artificial Intelligence. Washington,USA: IEEE, 2020: 989-996. [21] XIE J Y, GIRSHICK R, FARHADI A.Unsupervised Deep Embedding for Clustering Analysis // Proc of the 33rd International Conference on Machine Learning. New York,USA: ACM, 2016: 478-487. [22] WANG C, PAN S R, HU R Q, et al. Attributed Graph Clus-tering: A Deep Attentional Embedding Approach // Proc of the 28th International Joint Conference on Artificial Intelligence. San Francisco,USA: Morgan Kaufmann, 2019: 3670-3676. [23] BO D Y, WANG X, SHI C, et al. Structural Deep Clustering Network // Proc of the 29th International World Wide Web Confe-rence. New York,USA: ACM, 2020: 1400-1410. [24] ROSVALL M, BERGSTROM C T.Maps of Random Walks on Com-plex Networks Reveal Community Structure. Proceedings of the National Academy of Sciences of the United States of America, 2008, 105(4): 1118-1123. [25] YANG L, CAO X C, HE D X, et al. Modularity Based Community Detection with Deep Learning // Proc of the 25th International Joint Conference Artificial Intelligence. New York,USA: ACM, 2016: 2252-2258. [26] FORTUNATO S, BARTHELEMY M.Resolution Limit in Community Detection. Proceedings of the National Academy of Sciences of the United States of America, 2007, 104(1): 36-41.
2022, Vol. 35 
