A simpler sublinear algorithm for approximating the triangle count

Abstract

A recent result of Eden, Levi, and Ron (ECCC 2015) provides a sublinear time algorithm to estimate the number of triangles in a graph. Given an undirected graph $G$, one can query the degree of a vertex, the existence of an edge between vertices, and the $i$th neighbor of a vertex. Suppose the graph has $n$ vertices, $m$ edges, and $t$ triangles. In this model, Eden et al provided a $O(\poly(\eps^{-1}\log n)(n/t^{1/3} + m^{3/2}/t))$ time algorithm to get a $(1+\eps)$-multiplicative approximation for $t$, the triangle count. This paper provides a simpler algorithm with the same running time (up to differences in the $\poly(\eps^{-1}\log n)$ factor) that has a substantially simpler analysis.

References in corpus (3)

• Curvature of Co-Links Uncovers Hidden Thematic Layers in the World Wide Web
• Community structure and scale-free collections of Erdös-Rényi graphs
• Tolerating the Community Detection Resolution Limit with Edge Weighting

Cited by in corpus (5)

• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
• Slim Graph: Practical Lossy Graph Compression for Approximate Graph Processing, Storage, and Analytics
• Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation
• Testing Graph Clusterability: Algorithms and Lower Bounds
• Quantum Chebyshev's Inequality and Applications