Approximately Counting Triangles in Sublinear Time

We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read the entire graph. In this work we design a sublinear-time algorithm for approximating the number of triangles in a graph, where the algorithm is given query access to the graph. The allowed queries are degree queries, vertex-pair queries and neighbor queries. We show that for any given approximation parameter 0<; epsilon<; 1, the algorithm provides an estimate hat{t} such that with high constant probability, (1-epsilon) t<; hat{t}κ(1+epsilon)t, where t is the number of triangles in the graph G. The expected query complexity of the algorithm is O(n/t̂{1/3} + min {m, m̂{3/2}/t}) poly(log n, 1/epsilon), where n is the number of vertices in the graph and m is the number of edges, and the expected running time is (n/t̂{1/3} + m̂{3/2}/t) poly(log n, 1/epsilon). We also prove that Omega(n/t̂{1/3} + min {m, m̂{3/2}/t}) queries are necessary, thus establishing that the query complexity of this algorithm is optimal up to polylogarithmic factors in n (and the dependence on 1/epsilon).

Authors

• Talya Eden
• Amit Levi
• Dana Ron
• C. Seshadhri 0001

Keywords

• Approximation algorithms
• Approximation methods
• Algorithm design and analysis
• Complexity theory
• TV
• Yttrium
• Computer science
• Sublinear Time
• High Probability
• Running Time
• Random Variables
• Differences In Distribution
• Expected Value
• Estimation Algorithm
• Perfect Match
• Average Degree
• Random Graph
• Vertex Degree
• Pair Of Vertices
• Neighboring Vertices
• Statistical Distance
• Number Of Graphs
• Types Of Queries
• Expected Time
• Chebyshev’s Inequality
• Random Edge
• Complete Bipartite Graph
• Triangles Counting
• Sublinear Approximation Algorithm