Papers › Listing Maximal k-Plexes in Large Real-World Graphs
Listing Maximal k-Plexes in Large Real-World Graphs
Zhengren Wang, Yi Zhou, Mingyu Xiao, Bakhadyr Khoussainov
Listing dense subgraphs in large graphs plays a key task in varieties of network analysis applications like community detection. Clique, as the densest model, has been widely investigated. However, in practice, communities rarely form as cliques for various reasons, e.g., data noise. Therefore, k-plex, -- graph with each vertex adjacent to all but at most k vertices, is introduced as a relaxed version of clique. Often, to better simulate cohesive communities, an emphasis is placed on connected k-plexes with small k. In this paper, we continue the research line of listing all maximal k-plexes and maximal k-plexes of prescribed size. Our first contribution is algorithm ListPlex that lists all maximal k-plexes in O^*(γᴰ) time for each constant k, where γ is a value related to k but strictly smaller than 2, and D is the degeneracy of the graph that is far less than the vertex number n in real-word graphs. Compared to the trivial bound of 2ⁿ, the improvement is significant, and our bound is better than all previously known results. In practice, we further use several techniques to accelerate listing k-plexes of a given size, such as structural-based prune rules, cache-efficient data structures, and parallel techniques. All these together result in a very practical algorithm. Empirical results show that our approach outperforms the state-of-the-art solutions by up to orders of magnitude.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections