2018 · 128 citations · 47 references
ComputingComputer ScienceAlgorithmsData MiningParallel AlgorithmsGraph AlgorithmsGraph AnalyticsGraph MiningGraph TheoryClique AlgorithmsCliquesComputational Complexity Of Graph AlgorithmsGraph DecompositionsK-core DecompositionParallel Algorithm AnalysisParallel Graph AlgorithmsScalable Graph Algorithms
Motivated by recent studies in the data mining community which require to efficiently list all k-cliques, we revisit the iconic algorithm of Chiba and Nishizeki and develop the most efficient parallel algorithm for such a problem. Our theoretical analysis provides the best asymptotic upper bound on the running time of our algorithm for the case when the input graph is sparse. Our experimental evaluation on large real-world graphs shows that our parallel algorithm is faster than state-of-the-art algorithms, while boasting an excellent degree of parallelism. In particular, we are able to list all k-cliques (for any k) in graphs containing up to tens of millions of edges as well as all $10$-cliques in graphs containing billions of edges, within a few minutes and a few hours respectively. Finally, we show how our algorithm can be employed as an effective subroutine for finding the k-clique core decomposition and an approximate k-clique densest subgraphs in very large real-world graphs.
47
What is Twitter, a social network or a news media?
Haewoon Kwak, Changhyun Lee, Hosung Park et al. · 2010 · 6.7K citations · Full text
Uncovering the overlapping community structure of complex networks in nature and society
Gergely Palla, Imre Derényi, Illés J. Farkas et al. · Nature · 2005 · 5.4K citations · Full text
Identification of influential spreaders in complex networks
Maksim Kitsak, Lazaros K. Gallos, Shlomo Havlin et al. · Nature Physics · 2010 · 3.2K citations · Full text
{SNAP Datasets}: {Stanford} Large Network Dataset Collection
Jure Leskovec, Andrej Krevl · 2014 · 2.8K citations
Algorithm 457: finding all cliques of an undirected graph
Coen Bron, Joep Kerbosch · Communications of the ACM · 1973 · 2.5K citations · Full text