A High-Order Proximity-Incorporated Nonnegative Matrix Factorization-Based Community Detector

Community describes the functional mechanism of an undirected network, making community detection a fundamental tool for graph representation learning-related applications like social circle discovery. To date, a Symmetric and Nonnegative Matrix Factorization (SNMF) model has been frequently adopted to address this issue owing to its high interpretability and scalability. However, most existing SNMF-based community detectors neglect the high-order proximity in an undirected network, thus suffering from accuracy loss caused by incomplete information. Motivated by this discovery, this paper proposes a
H
igh-
O
rder
P
roximity-incorporated
N
onnegative
M
atrix
F
actorization (HOP-NMF)-based community detector with the following three-fold ideas: a) adopting a weighted pointwise mutual information-based approach to measure the high-order proximity among nodes in a network; b) leveraging an iterative network enhancement scheme to encode the captured high-order proximity into the network to effectively enhance the its information; and c) implementing a capacity-enlarged and graph-regularized factorization algorithm for highly-accurate representation to the enhanced network. With the above design, an HOP-NMF model is able to achieve highly-accurate community detection results. Theoretical proof is rigorously conducted to validate its convergence ability. Extensively empirical studies on eight real networks from industrial applications demonstrate that an HOP-NMF-based community detector significantly outperforms sophisticated and state-of-the-art community detectors in detection accuracy.