Identifying cohesive subgroups is a fundamental task in social network analysis. While the clique model—where every member is connected to every other member—is the standard for cohesion, it is often too restrictive for real-world data containing noise or missing links. This paper, presented at AAAI-17, addresses this by focusing on the Maximum $k$-Plex problem, a popular relaxation of the clique model.
A $k$-plex is a subset of $n$ vertices where each vertex is connected to at least $n - k$ others. Finding the largest such group is an NP-hard problem. Historically, while efficient algorithms existed for $k=1$ and $k=2$, the complexity for $k \ge 3$ remained stuck at a "brute force" theoretical bound of $2^n$. The authors introduce a new exact algorithm, BS (Branch-and-Search), that breaks this barrier and provides massive practical speedups.
Methodology: The Branch-and-Search Framework
The core of the proposed approach is a Branch-and-Search framework that transforms the task into a Constrained $k$-Plex problem. In this setup, the algorithm seeks the maximum $k$-plex that must include a specific subset of mandatory vertices. To navigate the search space efficiently, the authors introduce several technical innovations:
- Structural Reduction Rules: The algorithm identifies "reducible" vertices that can be safely deleted or moved into the mandatory set based on properties like vertex degree and distance.
- Diameter Pruning: Utilizing the property that a large $k$-plex must have a small diameter (typically $\le 2$), the algorithm aggressively prunes vertices that are too far apart to coexist in an optimal solution.
- Advanced Branching: Instead of simple binary branching, the algorithm systematically branches on "$k$-unsatisfied" vertices—those that do not yet meet the $k$-plex degree requirement.
Theoretical Breakthrough
The most significant theoretical contribution of this work is proving that for any fixed $k$, the Maximum $k$-Plex problem can be solved in $O(\sigma_k^n)$ time where $\sigma_k < 2$. This effectively breaks the $2^n$ complexity barrier for all $k \ge 3$.
As shown in the table above, for $k=3$, the complexity is approximately $1.9476^n$. While $\sigma_k$ approaches 2 as $k$ increases, the algorithm maintains a theoretical advantage over brute force for all tested values.
Empirical Evaluation
The BS algorithm was evaluated against state-of-the-art methods like OsterPlex, IPBC, and GuidedBranching across various datasets, including Erdős collaboration networks, GEOM networks, and DAYS text-mining networks.
On real-world social networks, the BS algorithm demonstrated near-instantaneous performance. As seen in the Erdős graph benchmarks, BS consistently found the maximum $k$-plex in under 0.05 seconds, whereas competing algorithms often required thousands of seconds or failed to terminate within an hour. This efficiency is largely attributed to the reduction rules, which are particularly effective on the sparse structures typical of social networks.
Conclusion
The BS algorithm represents a significant step forward in social network analysis, offering both a better theoretical complexity bound and a practical tool for large-scale graph mining. While the algorithm remains exponential, its ability to handle graphs with tens of thousands of vertices in milliseconds makes it highly suitable for real-world applications. Future research may focus on extending these techniques to find all maximal $k$-plexes for more comprehensive community detection.
Summary updated