自编码模块化增强非负矩阵分解社区检测算法

doi:10.3778/j.issn.1002-8331.2305-0108

摘要/Abstract

摘要： 社区检测一直是网络分析中的重点研究方向之一。目前大多数网络社区检测算法主要利用网络的结构信息采用贪心算法使某一指标最大化，无法充分考虑节点特征信息、边权重以及网络社区间关系不对称性等问题。针对这一情况，提出一种自编码模块化增强非负矩阵分解（autoencoder-like modularity nonnegative matrix factorization，AMNMF）社区检测算法。该算法通过采用类编码器结构拓展非负矩阵分解的深度，将模块度和图正则化器引入到非负矩阵分解的目标函数优化过程中以充分挖掘网络中的节点和社区结构信息，通过在编码器中间层添加正交约束解决了社区间关系不平衡的问题。在多个真实网络上的实验表明：AMNMF是一种有效地利用节点特征信息和网络结构信息的NMF拓展算法，与基线算法的最佳结果相比实现了约15%至122%的提升，能够准确有效完成社区检测任务。

关键词: 非负矩阵分解, 社区检测, 自编码, 模块化

Abstract: Community detection has been one of the key research directions in network analysis. Most of the current network community detection algorithms mainly use the structural information of the network to adopt a greedy algorithm to maximize a certain indicator, which cannot fully consider the node feature information, edge weight, and network community relationship asymmetry. To address this situation, this paper proposes an autoencoder-like modularity nonnegative matrix factorization (AMNMF) community detection algorithm. The algorithm expands the depth of non-negative matrix factorization by using an encoder-like structure, and introduces modularity and graph regularizer into the objective function optimization process of non-negative matrix factorization to fully mine the node and community structure information in the network. The problem of community relationship imbalance is solved by adding orthogonal constraints to the middle layer of the encoder. Experiments on multiple real networks show that：AMNMF is an effective NMF extension algorithm that uses node feature information and network structure information. Compared with the best results of baseline algorithms, it achieves an improvement of about 15% to 122%, and can accurately and effectively complete the community detection task.

Key words: nonnegative matrix decomposition, community testing, autoencoding, modular

朱玉龙, 刘建忠, 张寅宝, 张欣佳, 宋勇成, 刘思聪, 王雅博. 自编码模块化增强非负矩阵分解社区检测算法[J]. 计算机工程与应用, 2024, 60(11): 258-267.

ZHU Yulong, LIU Jianzhong, ZHANG Yinbao, ZHANG Xinjia, SONG Yongcheng, LIU Sicong, WANG YaboZHU Yulong, LIU Jianzhong, ZHANG Yinbao, ZHANG Xinjia, SONG Yongcheng, LIU Sicong, WANG Yabo. Community Detection Algorithm with Autoencoding-Like Modular Enhanced Non-Negative Matrix Factorization[J]. Computer Engineering and Applications, 2024, 60(11): 258-267.

参考文献

[1] 蒋璐, 陈云伟. 多节点多关系的混合网络社团划分研究综述[J]. 图书情报工作, 2021, 65(19): 142-150.
JIANG L, CHEN Y W. A review of community detection in hybrid networks with multiple nodes and multiple relationships[J]. Library and Information Service, 2021, 65(19): 142-150.
[2] 李金海, 何有世, 张鹏. 融合情境语义推理及社会网络的团购推荐研究[J]. 计算机工程与应用, 2021, 57(18): 163-171.
LI J H, HE Y S, ZHANG P. Research of group recommendation based on contextual semantics reasoning and social network[J]. Computer Engineering and Applications, 2021, 57(18): 163-171.
[3] LIAO L, HE X, ZHANG H, et al. Attributed social network embedding[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(12): 2257-2270.
[4] 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, 2021, 57: 51-72.
[5] CHEN D, NIE M, ZHANG H, et al. Network embedding algorithm taking in variational graph autoencoder[J]. Mathematics, 2022, 10(3): 485.
[6] LEE D, SEUNG H S. Algorithms for non-negative matrix factorization[C]//Proceedings of the 13th International Conference on Neural Information Processing Systems, 2000: 535-541.
[7] OUARET R, IONESCU A, RAMALHO O. Non-negative matrix factorization for the analysis of particle number concentrations: characterization of the temporal variability of sources in indoor workplace[J]. Building and Environment, 2021, 203: 108055.
[8] ZHAO Y, WANG C, PEI J, et al. Nonlinear loose coupled non-negative matrix factorization for low-resolution image recognition[J]. Neurocomputing, 2021, 443: 183-198.
[9] BLEE A L, DAY J C C, FLEWITT P E J, et al. Non‐negative assisted principal component analysis: a novel method of data analysis for raman spectroscopy[J]. Journal of Raman Spectroscopy, 2021, 52(6): 1135-1147.
[10] YUAN A, YOU M, HE D, et al. Convex non-negative matrix factorization with adaptive graph for unsupervised feature selection[J]. IEEE Transactions on Cybernetics, 2020, 52(6): 5522-5534.
[11] VANGARA R, BHATTARAI M, SKAU E, et al. Finding the number of latent topics with semantic non-negative matrix factorization[J]. IEEE Access, 2021, 9: 117217-117231.
[12] MEANEY C, ESCOBAR M, MOINEDDIN R, et al. Non-negative matrix factorization temporal topic models and clinical text data identify COVID-19 pandemic effects on primary healthcare and community health in Toronto, Canada[J]. Journal of Biomedical Informatics, 2022, 128: 104034.
[13] GOBIN M, NAZAROV P V, WARTA R, et al. A DNA repair and cell-cycle gene expression signature in primary and recurrent glioblastoma: prognostic value and clinical implications DNA repair and cell-cycle gene signature in GBM[J]. Cancer Research, 2019, 79(6): 1226-1238.
[14] AK?AY S, GüVEN E, AFZAL M, et al. Non-negative matrix factorization and differential expression analyses identify hub genes linked to progression and prognosis of glioblastoma multiforme[J]. Gene, 2022, 824: 146395.
[15] RAHMAN D A, LESTARI D P. COVID-19 classification using cough sounds[C]//Proceedings of the 2021 8th International Conference on Advanced Informatics: Concepts, Theory and Applications, 2021: 1-6.
[16] AN R, TONG Z, LIU X, et al. Post COVID-19 pandemic recovery of intracity human mobility in Wuhan: spatiotemporal characteristic and driving mechanism[J]. Travel Behaviour and Society, 2023, 31: 37-48.
[17] HARTIGAN J A, WONG M A. Algorithm AS136: a K-means clustering algorithm[J]. Journal of the Royal Statistical Society, 1979, 28(1): 100-108.
[18] WOLD S, ESBENSEN K, GELADI P. Principal component analysis[J]. Chemometrics and Intelligent Laboratory Systems, 1987, 2(1/2/3): 37-52.
[19] LINDE Y, BUZO A, GRAY R. An algorithm for vectorquantizer design[J]. IEEE Transactions on Communications, 1980, 28(1): 84-95.
[20] 李乐, 章毓晋. 基于线性投影结构的非负矩阵分解[J]. 自动化学报, 2010, 36(1): 23-39.
LI L, ZHANG Y J. Linear projection-based non-negative matrix factorization[J]. Acta Automatica Sinica, 2010, 36(1): 23-39.
[21] 陆佳炜, 赵伟, 张元鸣, 等. 基于TWE-NMF主题模型的Mashup服务聚类方法[J]. 软件学报, 2023, 34(6): 2727-2748.
LU J W, ZHAO W, ZHANG Y M, et al. TWE-NMF topic model-based approach for Mashup service clustering[J]. Journal of Software, 2023, 34(6): 2727-2748.
[22] 周旭, 杨佳鹏, 俎毓伟, 等. 基于NMF-HGS-RF的瓦斯涌出量预测研究[J]. 矿业安全与环保, 2023, 50(3): 117-123.
ZHOU X, YANG J P, ZU Y W, et al. Gas emission prediction based on NMF-HGS-RF[J]. Mining Safety & Environmental Protection, 2023, 50(3): 117-123.
[23] 汤辉, 孟莎莎, 彭天亮, 等. 基于Hessian图正则稀疏NMF的高光谱解混[J]. 计算技术与自动化, 2023, 42(1): 153-159.
TANG H, MENG S S, PENG T L, et al. Hyperspectral unmixing based on Hessian graph regular sparse NMF[J]. Computing Technology and Automation, 2023, 42(1): 153-159.
[24] XU Y, CUI X, ZHANG L, et al. Metastasis-related gene identification by compound constrained NMF and a semisupervised cluster approach using pancancer multiomics features[J]. Computers in Biology and Medicine, 2022, 151: 106263.
[25] SCERRI M M, WEINBRUCH S, DELMAIRE G, et al. Exhaust and non-exhaust contributions from road transport to PM10 at a Southern European traffic site[J]. Environmental Pollution, 2023, 316: 120569.
[26] ZHANG Z Y, WANG Y, AHN Y Y. Overlapping community detection in complex networks using symmetric binary matrix factorization[J]. Physical Review E, 2013, 87(6): 062803.
[27] ZHANG H, KING I, LYU M. Incorporating implicit link preference into overlapping community detection[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2015.
[28] ZHANG H, ZHAO T, KING I, et al. Modeling the homophily effect between links and communities for overlapping community detection[C]//Proceedings of the 25th International Joint Conference on Artificial Intelligence, 2016: 3938-3944.
[29] LYU T, ZHANG Y, ZHANG Y. Enhancing the network embedding quality with structural similarity[C]//Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, 2017: 147-156.
[30] RIBEIRO L F R, SAVERESE P H P, FIGUEIREDO D R. Struc2vec: learning node representations from structural identity[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2017: 385-394.
[31] WU W, KWONG S, ZHOU Y, et al. Nonnegative matrix factorization with mixed hypergraph regularization for community detection[J]. Information Sciences, 2018, 435: 263-281.
[32] CHAKRABORTY T, DALMIA A, MUKHERJEE A, et al. Metrics for community analysis: a survey[J]. ACM Computing Surveys, 2017, 50(4): 1-37.
[33] WU H, GAO L, DONG J, et al. Detecting overlapping protein complexes by rough-fuzzy clustering in protein-protein interaction networks[J]. PloS One, 2014, 9(3): 91856.
[34] 潘磊, 金杰, 王崇骏, 等. 社会网络中基于局部信息的边社区挖掘[J]. 电子学报, 2012, 40(11): 2255-2263.
PAN L, JIN J, WANG C J, et al. Detecting link communities based on local information in social networks[J]. Acta Electronica Sinica, 2012, 40(11): 2255-2263.
[35] 黄发良, 张师超, 朱晓峰. 基于多目标优化的网络社区发现方法[J]. 软件学报, 2013, 24(9): 2062-2077.
HUANG F L, ZHANG S C, ZHU X F. Discovering network community based on multi-objective optimization[J]. Journal of Software, 2013, 24(9): 2062-2077.
[36] 辛宇, 杨静, 汤楚蘅, 等. 基于局部语义聚类的语义重叠社区发现算法[J]. 计算机研究与发展, 2015, 52(7): 1510-1521.
XIN Y, YANG J, TANG C H, et al. An overlapping semantic community detection algorithm based on local semantic cluster[J]. Journal of Computer Research and Development, 2015, 52(7): 1510-1521.
[37] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.
[38] GUIMERA R, NUNES AMARAL L A. Functional cartography of complex metabolic networks[J]. Nature, 2005, 433: 895-900.
[39] FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010, 486(3/4/5): 75-174.
[40] PEI Y, CHAKRABORTY N, SYCARA K. Nonnegative matrix tri-factorization with graph regularization for community detection in social networks[C]//Proceedings of the 24th International Joint Conference on Artificial Intelligence, 2015.
[41] WANG X, CUI P, WANG J, et al. Community preserving network embedding[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2017: 203-209.
[42] MA X, ZHANG R, GUO J, et al. A contrastive pre-training approach to discriminative autoencoder for dense retrieval[C]//Proceedings of the 31st ACM International Conference on Information & Knowledge Management, 2022: 4314-4318.
[43] BOYD S, BOYD S P, VANDENBERGHE L. Convex optimization[M]. Cambridge: Cambridge University Press, 2004.
[44] DEMPSTER A P, LAIRD N M, RUBIN D B. Maximum likelihood from incomplete data via the EM algorithm[J]. Journal of the Royal Statistical Society: Series B (Methodological), 1977, 39(1): 1-22.
[45] WANG F, LI T, WANG X, et al. Community discovery using nonnegative matrix factorization[J]. Data Mining and Knowledge Discovery, 2011, 22: 493-521.
[46] ROZEMBERCZKI B, KISS O, SARKAR R. Karate Club: an API oriented open-source python framework for unsupervised learning on graphs[C]//Proceedings of the 29th ACM International Conference on Information & Knowledge Management, 2020: 3125-3132.
[47] PEDREGOSA F, VAROQUAUX G, GRAMFORT A, et al. Scikit-learn: machine learning in Python[J]. Journal of Machine Learning Research, 2011, 12: 2825-2830.
[48] ZHANG S, WANG R S, ZHANG X S. Uncovering fuzzy community structure in complex networks[J]. Physical Review E, 2007, 76(4): 046103.
[49] YE F, CHEN C, ZHENG Z. Deep autoencoder-like nonnegative matrix factorization for community detection[C]//Proceedings of the 27th ACM International Conference on Information and Knowledge Management, 2018: 1393-1402.
[50] LI P Z, HUANG L, WANG C D, et al. EdMot: an edge enhancement approach for motif-aware community detection[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019: 479-487.
[51] PEROZZI B, AL-RFOU R, SKIENA S. DeepWalk: online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014: 701-710.
[52] GROVER A, LESKOVEC J. Node2vec: scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016: 855-864.
[53] ROZEMBERCZKI B, DAVIES R, SARKAR R, et al. GEMSEC: graph embedding with self clustering[C]//Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2019: 65-72.
[54] TORRES L, CHAN K S, ELIASSI-RAD T. GLEE: geometric laplacian eigenmap embedding[J]. Journal of Complex Networks, 2020, 8(2): 29154877.