Community Detection and Link Prediction via Cluster-driven Low-rank Matrix Completion

Junming Shao, Zhong Zhang, Zhongjing Yu, Jun Wang, Yi Zhao, Qinli Yang

Introduction

In network science, community detection and link prediction are traditionally treated as separate tasks. However, they are intrinsically linked: accurate community detection requires a complete set of links, while effective link prediction often relies on an understanding of the underlying community structure. Real-world networks further complicate this by being "noisy"—containing sparse inter-cluster edges—and incomplete.

The CLMC Framework

The Cluster-driven Low-rank Matrix Completion (CLMC) framework addresses these challenges by treating community detection and link prediction as a single, mutually reinforcing problem. The core innovation lies in decomposing the observed adjacency matrix $A$ into three distinct additive components:

  1. Clustering Matrix ($\hat{C}$): An "ideal" block-diagonal representation of the network where intra-community links are emphasized and inter-community noise is filtered.
  2. Noise Matrix ($\hat{R}$): Captures sparse inter-cluster edges that obscure the true community structure.
  3. Supplement Matrix ($E$): Identifies missing or potential connections (intra-cluster links) not present in the original observation.
Decomposition of the adjacency matrix into clustering, noise, and supplement components.

Mathematical Constraints

To ensure the decomposition is physically meaningful, CLMC applies specific constraints:

  • Low-Rankness: A nuclear norm constraint is applied specifically to the clustering matrix $\hat{C}$, reflecting the low-rank nature of community structures.
  • Block-Diagonal Structure: A Laplacian-based constraint forces $\hat{C}$ into $k$ distinct clusters.
  • Sparsity: An $\ell_1$-norm constraint on $\hat{R}$ assumes that noise is relatively sparse compared to the overall structure.

Experimental Evaluation

The model was tested on various synthetic (LFR benchmark) and real-world datasets, including the Karate club, Twitter, and transportation networks.

Key Results

  • Clustering Performance: CLMC achieved state-of-the-art results, including perfect clustering (NMI = 1.0) on the Karate dataset, outperforming methods like Ncut and Modularity.
  • Link Prediction Accuracy: CLMC consistently yielded the highest AUC across ten real-world datasets when compared to 16 other link prediction methods.
  • Robustness: The framework maintained high performance even with 10% missing data or high levels of inter-community "mixing," demonstrating its ability to "clean" network data effectively.

Conclusion

CLMC demonstrates that clustering and link prediction are symbiotic. By leveraging the low-rank properties of community structures and explicitly modeling noise and missing links, the framework provides a robust solution for understanding complex network topologies. Future work may extend this approach to directed or weighted graphs.

Summary updated

Abstract

Community detection and link prediction are highly dependent since knowing cluster structure as a priori will help identify missing links, and in return, clustering on networks with supplemented missing links will improve community detection performance. In this paper, we propose a Cluster-driven Low-rank Matrix Completion (CLMC), for performing community detection and link prediction simultaneously in a unified framework. To this end, CLMC decomposes the adjacent matrix of a target network as three additive matrices: clustering matrix, noise matrix and supplement matrix. The community-structure and low-rank constraints are imposed on the clustering matrix, such that the noisy edges between communities are removed and the resulting matrix is an ideal block-diagonal matrix. Missing edges are further learned via low-rank matrix completion. Extensive experiments show that CLMC achieves state-of-the-art performance.
BibTeX
@inproceedings{shao2019community,
  author = {Junming Shao and Zhong Zhang and Zhongjing Yu and Jun Wang and Yi Zhao and Qinli Yang},
  title = {{Community Detection and Link Prediction via Cluster-driven Low-rank Matrix Completion}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/469},
}
Figure