Community Detection via Multihop Nonnegative Matrix Factorization

Community detection aims at finding all densely connected communities in a network, which serves as a fundamental graph tool for many applications, such as identification of protein functional modules, image segmentation, social circle discovery, to name a few. Recently, nonnegative matrix factorization (NMF)-based community detection methods have attracted significant attention. However, most existing methods neglect the multihop connectivity patterns in a network, which turn out to be practically useful for community detection. In this article, we first propose a novel community detection method, namely multihop NMF (MHNMF for brevity), which takes into account the multihop connectivity patterns in a network. Subsequently, we derive an efficient algorithm to optimize MHNMF and theoretically analyze its computational complexity and convergence. Experimental results on 12 real-world benchmark networks demonstrate that MHNMF outperforms 12 state-of-the-art community detection methods.