Scaling Up k-Clique Percolation Community Detection

Overlapping communities are pervasive in real-world networks, where vertices often participate in multiple communities simultaneously. The k -clique percolation community (KCPC) model represents a fundamental paradigm for mining overlapping communities. However, existing KCPC mining methods are often hampered by inefficiency and scalability challenges, hindering their applicability to large-scale networks. To address these challenges, we propose several novel and efficient approaches for KCPC mining from perspectives of maximal cliques and k -cliques. Specifically, we first present a novel concept, termed Quasi-KCPC, which represents an incomplete KCPC and can be efficiently obtained as a byproduct during the maximal clique enumeration procedure. Based on Quasi-KCPC, we first propose a maximal clique enumeration-based solution that builds upon existing maximal clique adjacency graph traversal methods, but achieves improved efficiency by using Quasi-KCPC to dramatically reduce the scale of the maximal clique adjacency graph. Additionally, we propose a novel k -clique listing-based solution, which adopts a different strategy: it first enumerates (k-1)-cliques and then connects the k -cliques sharing these (k-1)-cliques into KCPC. Our method further improves efficiency by shifting the connection target from k -cliques to maximal cliques and employing Quasi-KCPC to significantly prune the k -clique enumeration tree. We also propose update algorithms for KCPC to handle dynamic addition and deletion of vertices and edges, enabling real-time analysis of KCPC. Extensive experiments on 12 large real-world graphs demonstrate the superiority of our algorithms, which can be up to two orders of magnitude faster than existing state-of-the-art solutions in KCPC mining, and almost two orders of magnitude faster than recomputation strategy in dynamic KCPC updates.