Community detection using fast low-cardinality semidefinite programming
This work provides a more robust and effective method for community detection in networks, which is beneficial for researchers and practitioners analyzing complex network structures.
This paper addresses the challenge of community detection in networks by proposing a new low-cardinality algorithm that generalizes local updates to maximize a semidefinite relaxation derived from max-k-cut. The algorithm empirically achieves global semidefinite optimality for small cases and outperforms state-of-the-art methods on real-world datasets with minimal additional time cost.
Modularity maximization has been a fundamental tool for understanding the community structure of a network, but the underlying optimization problem is nonconvex and NP-hard to solve. State-of-the-art algorithms like the Louvain or Leiden methods focus on different heuristics to help escape local optima, but they still depend on a greedy step that moves node assignment locally and is prone to getting trapped. In this paper, we propose a new class of low-cardinality algorithm that generalizes the local update to maximize a semidefinite relaxation derived from max-k-cut. This proposed algorithm is scalable, empirically achieves the global semidefinite optimality for small cases, and outperforms the state-of-the-art algorithms in real-world datasets with little additional time cost. From the algorithmic perspective, it also opens a new avenue for scaling-up semidefinite programming when the solutions are sparse instead of low-rank.