2018 · 63 citations · 24 references
ComputingComputer ScienceHigh-performance ComputingAlgorithmsData MiningDistributed SystemsCommunity DetectionCommunity StructureGraph AlgorithmsGraph AnalyticsGraph MiningGraph TheoryClique AlgorithmsCliquesDegeneracyHigh PerformanceNetwork GraphsScalable Community DetectionScalable Graph Algorithms
This paper studies k-plexes, a well known pseudo-clique model for network communities. In a k-plex, each node can miss at most k-1 links. Our goal is to detect large communities in today's real-world graphs which can have hundreds of millions of edges. While many have tried, this task has been elusive so far due to its computationally challenging nature: k-plexes and other pseudo-cliques are harder to find and more numerous than cliques, a well known hard problem. We present D2K, which is the first algorithm able to find large k-plexes of very large graphs in just a few minutes. The good performance of our algorithm follows from a combination of graph-theoretical concepts, careful algorithm engineering and a high-performance implementation. In particular, we exploit the low degeneracy of real-world graphs, and the fact that large enough k-plexes have diameter 2. We validate a sequential and a parallel/distributed implementation of D2K on real graphs with up to half a billion edges.
24
Santo Fortunato · Physics Reports · 2009 · 11.3K citations · Full text
Algorithm 457: finding all cliques of an undirected graph
Coen Bron, Joep Kerbosch · Communications of the ACM · 1973 · 2.5K citations · Full text
Reverse search for enumeration
David Avis, Komei Fukuda · Discrete Applied Mathematics · 1996 · 760 citations
Arboricity and Subgraph Listing Algorithms
Norishige Chiba, Takao Nishizeki · SIAM Journal on Computing · 1985 · 665 citations