计算机科学 ›› 2026, Vol. 53 ›› Issue (4): 215-223.doi: 10.11896/jsjkx.250500057
李希龙, 刘琰, 贾萌萌, 张子林
LI Xilong, LIU Yan, JIA Mengmeng, ZHANG Zilin
摘要： 针对现有基于非负矩阵分解(NMF)的社团检测方法存在需预设社团数量、易陷入局部最优及模型泛化能力有限等问题,提出了一种基于非负矩阵三因子分解(NMTF)的自适应社团检测算法(Adp-NMTF)。该算法引入动态评估和反馈机制,能够自动搜索并确定合理的社团划分数,无需人工预设;引入图正则化、稀疏性及社团独立性约束,平衡模型泛化能力与可解释性;同时利用半监督初始化与热启动策略,加速NMTF收敛过程,提高计算效率。实验结果表明,Adp-NMTF能够自适应确定网络社团数,在合成和真实网络数据集测试中,模块度(Q)、标准化互信息(NMI)和调整兰德指数(ARI)等评价指标均优于主流基线方法,同时显著提升了矩阵分解的收敛速度和计算效率。
中图分类号:
| [1]FORTUNATO S,NEWMAN M E J.20 years of network community detection[J].Nature Physics,2022,18(8):848-850. [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]CHOUDHARY C,SINGH A.Community detection algorithms for recommendation systems:techniques and metrics[J].Computing,2022,105(2):1-37. [4]JIN D,YU X,LI H,et al.A survey of community detection approaches:From statistical modeling to deep learning[J].IEEE Transactions on Knowledge and Data Engineering,2023,35(2):1149-1170. [5]FORTUNATO S,BARTHÉLEMY M.Resolution limit in community detection[J].Proceedings of the National Academy of Sciences,2007,104(1):36-41. [6]VON LUXBURG U.A tutorial on spectral clustering[J].Statistics and Computing,2007,17(4):395-416. [7]ROSVALL M,BERGSTROM C T.Maps of random walks on complex networks reveal community structure[J].Proceedings of the National Academy of Sciences,2008,105(4):1118-1123. [8]ZHANG Z,CUI P,ZHU W.Deep learning on graphs:A survey[J].IEEE Transactions on Knowledge and Data Engineering,2022,34(1):249-270. [9]DING C,LI T,PENG W,et al.Orthogonal nonnegative matrix tri-factorizations for clustering[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.2006:126-135. [10]YANG Y,YU S,PAN B,et al.Community Detection in MultiplexNetworks Using Orthogonal Non-Negative Matrix Tri-Factorization Basedon Graph Regularization and Diversity[J].Mathematics,2024,12(8):1124. [11]YANG L,ZHANG L.Community Detection Based on Co-regularizedNonnegative Matrix Tri-Factorization in Multi-view Social Networks[C]//2018 IEEE International Conference on Big Data and Smart Computing.2018:98-105. [12]LI Y,JIA C,YU J.Survey on community detection algorithms usingnonnegative matrix factorization model[J].Journal of Frontiers ofComputer Science and Technology,2016,10(1):1-13. [13]LI Y,LIU X,ZHANG H,et al.Contrastive deep nonnegativematrix factorization for community detection[C]//2024 IEEE International Conference on Acoustics,Speech and Signal Processing.2024:6725-6729. [14]LI X,YU W,XU G,et al.MSDA-NMF:A multilayer complex system model integrating deep autoencoder and NMF[J].Mathe-matics,2022,10(15):2750. [15]DING C,HE X,SIMON H D.On the equivalence of nonnegative matrix factorization and spectral clustering[C]//Proceedings of the 2005 SIAM International Conference on Data Mining.2005:126-135. [16]MA X,ZHANG Y,LIU J,et al.Semi-supervised clustering algorithm for community structure detection in complex networks[J].Physica A:Statistical Mechanics and its Applications,2009,389(1):187-197. [17]LEE D D,SEUNG H S.Algorithms for non-negative matrix factorization[J].Advances in Neural Information Processing Systems,2001,13:556-562. [18]KUANG D,DING C,PARK H.Symmetric nonnegative matrix factorization for graph clustering[C]//Proceedings of the SIAM International Conference on Data Mining.2012:126-135. [19]SHELDON B,ROBERTS S.Overlapping community detectionusing Bayesian non-negative matrix factorization[J].Physical Review E,2011,83(6):066114. [20]LIU Z,YUAN G,LUO X.Symmetry and nonnegativity-con-strained matrix factorization for community detection[J].IEEE/CAA Journal of Automatica Sinica,2022,9(9):1691-1693. [21]GUAN J,CHEN B,HUANG X.Community detection via multihop nonnegative matrix factorization[J].IEEE Transactions on Neural Networks and Learning Systems,2024,35(7):10033-10044. [22]YE F,CHEN C,WEN Z,et al.Homophily preserving community detection[J].IEEE Transactions on Neural Networks and Learning Systems.2019,31:2903-2915. [23]SONG Y,LI M,LUO X,et al.Improved symmetric and non-negative matrix factorization models for undirected,sparse and large-scaled networks:A triple factorization-based approach[J].IEEE Transactions on Industrial Informatics,2020,16(5):3006-3017. [24]LI Z,YANG J,WANG L,et al.A semi-orthogonal nonnegative matrix tri-factorization algorithm for overlapping community detection[J].Statistical Papers,2024,65(6):1-19. [25]ZHANG J,WANG F,ZHOU J.Community detection based on nonnegative matrix tri-factorization for multiplex social networks[J].Journal of Complex Networks,2024,12(2):1-16. [26]NEWMAN M E J.Community detection in networks:Modularity optimization and maximum likelihood are equivalent[J].Physical Review E,2016,94(5):052315. [27]BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008,2008(10):P10008. [28]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. |
| [1] | 秦海棋, 米据生. 复杂网络下的概念认知学习与增量学习 Concept-cognitive Learning and Incremental Learning in Complex Networks 计算机科学, 2026, 53(4): 208-214. https://doi.org/10.11896/jsjkx.250600216 |
| [2] | 俞山青, 宋亦聃, 周金涛, 周梦, 李家祥, 汪泽钰, 宣琦. 基于梯度引导的社团隐匿扰动子结构优化方法 Gradient-guided Pertuerbed Substructure Optimization for Community Hiding 计算机科学, 2025, 52(9): 376-387. https://doi.org/10.11896/jsjkx.240800107 |
| [3] | 池艺妍, 祁明泽, 黄彭奇子, 段晓君. 基于可控偏好抽样的复杂网络度分布推断方法 Degree Distribution Inference Method for Complex Networks Based on Controllable PreferentialSampling 计算机科学, 2025, 52(7): 82-91. https://doi.org/10.11896/jsjkx.241200098 |
| [4] | 缪广宇, 神策, 方博杨. 基于网络分解的故障树自动生成方法研究 Research on Automatic Generation Method of Fault Tree Based on Network Decomposition 计算机科学, 2025, 52(6A): 240900108-6. https://doi.org/10.11896/jsjkx.240900108 |
| [5] | 席颖, 邬学猛, 崔晓晖. 基于Transformer的节点影响力排序模型 Node Influence Ranking Model Based on Transformer 计算机科学, 2024, 51(4): 106-116. https://doi.org/10.11896/jsjkx.230300110 |
| [6] | 黄路路, 唐舒宇, 张伟, 代祥光. 基于Lp范数的非负矩阵分解并行优化算法 Non-negative Matrix Factorization Parallel Optimization Algorithm Based on Lp-norm 计算机科学, 2024, 51(2): 100-106. https://doi.org/10.11896/jsjkx.230300040 |
| [7] | 刘弘毅, 王瑞, 吴贯锋, 张阳. 基于核鲁棒流形非负矩阵分解和融合特征的柴油机故障诊断 Diesel Engine Fault Diagnosis Based on Kernel Robust Manifold Nonnegative Matrix Factorizationand Fusion Features 计算机科学, 2023, 50(6A): 220400128-8. https://doi.org/10.11896/jsjkx.220400128 |
| [8] | 曾祥宇, 龙海霞, 杨旭华. 基于马尔可夫相似性增强和网络嵌入的社区发现 Community Detection Based on Markov Similarity Enhancement and Network Embedding 计算机科学, 2023, 50(4): 56-62. https://doi.org/10.11896/jsjkx.220100155 |
| [9] | 段顺然, 尹美娟, 刘粉林, 焦隆隆, 于岚岚. 一种基于影响力预测的节点排序模型 Nodes’ Ranking Model Based on Influence Prediction 计算机科学, 2023, 50(3): 155-163. https://doi.org/10.11896/jsjkx.211200261 |
| [10] | 曹金鑫, 许伟忠, 金弟, 丁卫平. 复杂网络社团发现综述 Survey of Community Discovery in Complex Networks 计算机科学, 2023, 50(11A): 230100130-11. https://doi.org/10.11896/jsjkx.230100130 |
| [11] | 陈端兵, 杨志杰, 曾卓, 傅彦, 周俊临, 赵俊严. 基于子图特征的节点排序算法 Node Ranking Algorithm Based on Subgraph Features 计算机科学, 2023, 50(11A): 230100122-7. https://doi.org/10.11896/jsjkx.230100122 |
| [12] | 郑文萍, 刘美麟, 杨贵. 一种基于节点稳定性和邻域相似性的社区发现算法 Community Detection Algorithm Based on Node Stability and Neighbor Similarity 计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146 |
| [13] | 何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超. 比特币实体交易模式分析 Analysis of Bitcoin Entity Transaction Patterns 计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178 |
| [14] | 杨波, 李远彪. 数据科学与大数据技术课程体系的复杂网络分析 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 |
| [15] | 王本钰, 顾益军, 彭舒凡, 郑棣文. 融合动态距离和随机竞争学习的社区发现算法 Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning 计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206 |
|
||
首页