A hybrid sampling scheme for triangle counting

DOI10.1137/1.9781611974782.116zbMATH Open1411.68204arXiv1610.02066OpenAlexW2951485559MaRDI 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)

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.

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

Recommendations

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

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)

Cited In (7)

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