A hybrid sampling scheme for triangle counting

DOI10.1137/1.9781611974782.116zbMATH Open1411.68204OpenAlexW2951485559MaRDI QIDQ4575862FDOQ4575862

Authors John Kallaugher, Eric Price

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We study the problem of estimating the number of triangles in a graph stream. No streaming algorithm can get sublinear space on all graphs, so methods in this area bound the space in terms of parameters of the input graph such as the maximum number of triangles sharing a single edge. We give a sampling algorithm that is additionally parameterized by the maximum number of triangles sharing a single vertex. Our bound matches the best known turnstile results in all graphs, and gets better performance on simple graphs like $G(n,p)$ or a set of independent triangles. We complement the upper bound with a lower bound showing that no sampling algorithm can do better on those graphs by more than a log factor. In particular, any insertion stream algorithm must use $sqrtT$ space when all the triangles share a common vertex, and any sampling algorithm must take $T^{f}rac13$ samples when all the triangles are independent. We add another lower bound, also matching our algorithm's performance, which applies to all graph classes. This lower bound covers "triangle-dependent" sampling algorithms, a subclass that includes our algorithm and all previous sampling algorithms for the problem. Finally, we show how to generalize our algorithm to count arbitrary subgraphs of constant size.

Recommendations

• How hard is counting triangles in the streaming model?
• Computing and Combinatorics
• scientific article; zbMATH DE number 6862103

Cited in

(8)

• Computing and Combinatorics
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Graph sketching and streaming: new approaches for analyzing massive graphs
• On triangle estimation using tripartite independent set queries
• How hard is counting triangles in the streaming model?
• Triangle sparsifiers
• Efficient triangle counting in large graphs via degree-based vertex partitioning
• Efficient triangle counting in large graphs via degree-based vertex partitioning

This page was built for publication: A hybrid sampling scheme for triangle counting

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