Colorful triangle counting and a \textsc{MapReduce} implementation

DOI10.1016/J.IPL.2011.12.007MaRDI QIDQ413300zbMATH OpenOpenAlexFDO

Authors Rasmus Pagh, Charalampos E. Tsourakakis

Publication date 4 May 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2011.12.007

zbMATH Keywords

concentration of measuregraph algorithmsparallel algorithmsrandomized algorithms

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Recommendations

• Efficient triangle counting in large graphs via degree-based vertex partitioning
• Efficient triangle counting in large graphs via degree-based vertex partitioning
• Approximately counting triangles in sublinear time
• Counting triangles in massive graphs with MapReduce
• How hard is counting triangles in the streaming model?

Cites work

• A note on an inequality involving the normal distribution
• Approximating Clustering Coefficient and Transitivity
• Computing and Combinatorics
• Concentration of multivariate polynomials and its applications
• Divide and conquer martingales and the number of triangles in a random graph
• Efficient triangle counting in large graphs via degree-based vertex partitioning
• Finding and counting given length cycles
• scientific article; zbMATH DE number 2119719 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• Main-memory triangle computations for very large (sparse (power-law)) graphs
• Matrix multiplication via arithmetic progressions
• On the concentration of multivariate polynomials with small expectation
• Random generation of combinatorial structures from a uniform distribution
• The infamous upper tail
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Triangle sparsifiers

Cited in

(15)

• FURL: fixed-memory and uncertainty reducing local triangle counting for multigraph streams
• A second look at counting triangles in graph streams (corrected)
• The distributed algorithm for constructing extremal graphs without hexagon
• Clique counting in MapReduce: algorithms and experiments
• Counting triangles in massive graphs with MapReduce
• Efficient Computation of the Weighted Clustering Coefficient
• Approximately counting triangles in sublinear time
• Density independent algorithms for sparsifying k-step random walks
• Efficient computation of the Weighted Clustering Coefficient
• Counting simplices in hypergraph streams
• Brief announcement: improved massively parallel triangle counting in O(1) rounds
• Towards optimal dynamic indexes for approximate (and exact) triangle counting
• Near uniform triangle sampling over adjacency list graph streams
• A second look at counting triangles in graph streams
• Distributed discovery of frequent subgraphs of a network using MapReduce

Describes a project that uses

Uses Software

• DOULION

This page was built for publication: Colorful triangle counting and a \textsc{MapReduce} implementation

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