Community Detection in Multi-Layer Networks Using Joint Nonnegative Matrix Factorization

Xiaoke Ma, Di Dong, Quan Wang

IEEE Transactions on Knowledge and Data Engineering · 2018 · 170 citations · 62 references

Concepts

Abstract

Many complex systems are composed of coupled networks through different layers, where each layer represents one of many possible types of interactions. A fundamental question is how to extract communities in multi-layer networks. The current algorithms either collapses multi-layer networks into a single-layer network or extends the algorithms for single-layer networks by using consensus clustering. However, these approaches have been criticized for ignoring the connection among various layers, thereby resulting in low accuracy. To attack this problem, a quantitative function (multi-layer modularity density) is proposed for community detection in multi-layer networks. Afterward, we prove that the trace optimization of multi-layer modularity density is equivalent to the objective functions of algorithms, such as kernel <inline-formula><tex-math notation="LaTeX">$K$</tex-math></inline-formula> -means, nonnegative matrix factorization (NMF), spectral clustering and multi-view clustering, for multi-layer networks, which serves as the theoretical foundation for designing algorithms for community detection. Furthermore, a <u>S</u> emi- <u>S</u> upervised <u>j</u> oint <u>N</u> onnegative <u>M</u> atrix <u>F</u> actorization algorithm ( <i>S2-jNMF</i> ) is developed by simultaneously factorizing matrices that are associated with multi-layer networks. Unlike the traditional semi-supervised algorithms, the partial supervision is integrated into the objective of the S2-jNMF algorithm. Finally, through extensive experiments on both artificial and real world networks, we demonstrate that the proposed method outperforms the state-of-the-art approaches for community detection in multi-layer networks.

References

62