← 研踪 PaperTrailarXiv:2601.06262 · v3
Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model
首次提交 2026-01-10 03:16
版本更新 2026-11-06 21:47
雷达观测 2026-11-09 11:19
摘要
Community detection is a fundamental task in data analysis, and block models provide an approach for identifying diverse community structures. The degree-corrected block model (DCBM) is an established model that captures node degree heterogeneity. However, inference methods are computationally costly and sensitive to initialization, while cheaper alternatives, such as spectral or modularity-based approaches, may be less effective at recovering certain non-assortative structures. In this work, we show that DCBM inference can be reformulated as a constrained nonnegative matrix trifactorization problem. Leveraging this insight, we propose a scalable community detection method with a theoretically grounded initialization providing an initial partition for inference algorithms. Our approach is agnostic to network structure and applies to any graph representable by a DCBM. Experiments on synthetic and real-world benchmark networks show that our method achieves community recovery comparable to, and sometimes better than, that achieved by the DCBM inference methods, while being faster: it processes a graph with 100,000 nodes and 500,000 edges in about 30 seconds. Moreover, the initialization significantly improves solution quality. Overall, this work provides a scalable and robust framework for community detection and highlights the benefits of a matrix-factorization perspective for the DCBM.
作者备注：19 pages, 7 figures, code and data available from https://github.com/Alexia1305/OtrisymNMF_DCBM
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-06 21:47 · 最新观测版本
Matrix Factorization Framework for Community Detection under the Degree-Corrected Block Model
Community detection is a fundamental task in data analysis, and block models provide an approach for identifying diverse community structures. The degree-corrected block model (DCBM) is an established model that captures node degree heterogeneity. However, inference methods are computationally costly and sensitive to initialization, while cheaper alternatives, such as spectral or modularity-based approaches, may be less effective at recovering certain non-assortative structures. In this work, we show that DCBM inference can be reformulated as a constrained nonnegative matrix trifactorization problem. Leveraging this insight, we propose a scalable community detection method with a theoretically grounded initialization providing an initial partition for inference algorithms. Our approach is agnostic to network structure and applies to any graph representable by a DCBM. Experiments on synthetic and real-world benchmark networks show that our method achieves community recovery comparable to, and sometimes better than, that achieved by the DCBM inference methods, while being faster: it processes a graph with 100,000 nodes and 500,000 edges in about 30 seconds. Moreover, the initialization significantly improves solution quality. Overall, this work provides a scalable and robust framework for community detection and highlights the benefits of a matrix-factorization perspective for the DCBM.
查看此版本解读 →查看此版本原文 ↗