Clique counting in MapReduce: algorithms and experiments

DOI10.1145/2794080MaRDI QIDQ2828209zbMATH OpenOpenAlexFDO

Authors Irene Finocchi, Marco Finocchi, Emanuele G. Fusco

Publication date 24 October 2016

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.0734

zbMATH Keywords

graph algorithmsparallel algorithmsMapReduceexperimental algorithmicsclique listing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30) Parallel algorithms in computer science (68W10)

Abstract: We tackle the problem of counting the number of $k$-cliques in large-scale graphs, for any constant $kge3$. Clique counting is essential in a variety of applications, among which social network analysis. Due to its computationally intensive nature, we settle for parallel solutions in the MapReduce framework, which has become in the last few years a {em de facto} standard for batch processing of massive data sets. We give both theoretical and experimental contributions. On the theory side, we design the first exact scalable algorithm for counting (and listing) $k$-cliques. Our algorithm uses $O(m^{3/2})$ total space and $O(m^{k/2})$ work, where $m$ is the number of graph edges. This matches the best-known bounds for triangle listing when $k=3$ and is work-optimal in the worst case for any $k$, while keeping the communication cost independent of $k$. We also design a sampling-based estimator that can dramatically reduce the running time and space requirements of the exact approach, while providing very accurate solutions with high probability. We then assess the effectiveness of different clique counting approaches through an extensive experimental analysis over the Amazon EC2 platform, considering both our algorithms and their state-of-the-art competitors. The experimental results clearly highlight the algorithm of choice in different scenarios and prove our exact approach to be the most effective when the number of $k$-cliques is large, gracefully scaling to non-trivial values of $k$ even on clusters of small/medium size. Our approximation algorithm achieves extremely accurate estimates and large speedups, especially on the toughest instances for the exact algorithms. As a side effect, our study also sheds light on the number of $k$-cliques of several real-world graphs, mainly social networks, and on its growth rate as a function of $k$.

Recommendations

• Counting triangles in massive graphs with MapReduce
• Efficient triangle counting in large graphs via degree-based vertex partitioning
• Colorful triangle counting and a \textsc{MapReduce} implementation
• Estimating Clustering Indexes in Data Streams
• Parallel maximum clique algorithms with applications to network analysis

Cites work

• scientific article; zbMATH DE number 2119719 (Why is no real title available?)
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A note on an inequality involving the normal distribution
• Algorithms and data structures for external memory
• Approximate counting of cycles in streams
• Approximating Clustering Coefficient and Transitivity
• Arboricity and Subgraph Listing Algorithms
• Colorful triangle counting and a \textsc{MapReduce} implementation
• Combinatorial algorithms for feedback problems in directed graphs
• Computing and Combinatorics
• Counting arbitrary subgraphs in data streams
• Data streams: algorithms and applications.
• Efficient triangle counting in large graphs via degree-based vertex partitioning
• Emergence of Scaling in Random Networks
• Estimating Clustering Indexes in Data Streams
• Finding a Minimum Circuit in a Graph
• Finding and counting given length cycles
• Listing triangles
• Sorting, searching, and simulation in the MapReduce framework
• Triangle listing algorithms: back from the diversion

Cited in

(7)

• MapReduce-based graph structural clustering algorithm
• Estimating Clustering Indexes in Data Streams
• Lessons from the Congested Clique Applied to MapReduce
• The distributed algorithm for constructing extremal graphs without hexagon
• On linear algebraic algorithms for the subgraph matching problem and its variants
• On approximating the number of k-cliques in sublinear time
• Counting triangles in massive graphs with MapReduce

This page was built for publication: Clique counting in MapReduce: algorithms and experiments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828209)