Approximately Counting Triangles in Sublinear Time

DOI10.1137/15M1054389zbMath1380.68445arXiv1504.00954MaRDI QIDQ4593251

Talya Eden, Amit Levi, Dana Ron, C. Seshadhri

Publication date: 22 November 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmssublinear algorithmstriangles counting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (21)

On triangle estimation using tripartite independent set queries ⋮ Motif estimation via subgraph sampling: the fourth-moment phenomenon ⋮ Bootstrapping exchangeable random graphs ⋮ On Sampling Edges Almost Uniformly ⋮ A second look at counting triangles in graph streams (corrected) ⋮ Estimating the number of connected components in a graph via subgraph sampling ⋮ On randomized trace estimates for indefinite matrices with an application to determinants ⋮ Efficient and Near-optimal Algorithms for Sampling Small Connected Subgraphs ⋮ Unnamed Item ⋮ Subsampling spectral clustering for stochastic block models in large-scale networks ⋮ Finding small complete subgraphs efficiently ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Unnamed Item ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Bootstrap estimators for the tail-index and for the count statistics of graphex processes ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems ⋮ Unnamed Item ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ Querying a Matrix Through Matrix-Vector Products. ⋮ Counting Triangles under Updates in Worst-Case Optimal Time ⋮ Quantum Chebyshev's Inequality and Applications

Uses Software

• DOULION

Cites Work

• Unnamed Item
• Unnamed Item
• Colorful triangle counting and a \textsc{MapReduce} implementation
• Finding and counting given length cycles
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Triangle Sparsifiers
• Counting Triangles in Massive Graphs with MapReduce
• Counting Arbitrary Subgraphs in Data Streams
• Counting Stars and Other Small Subgraphs in Sublinear-Time
• Approximating Clustering Coefficient and Transitivity
• Approximating average parameters of graphs
• Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
• Arboricity and Subgraph Listing Algorithms
• Finding a Minimum Circuit in a Graph
• Approximating the distance to properties in bounded-degree and general sparse graphs
• Listing Triangles
• Local Graph Partitions for Approximation and Testing
• An improved constant-time approximation algorithm for maximum~matchings
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Probability and Computing
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
• Experimental and Efficient Algorithms
• Computing and Combinatorics
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Efficient Triangle Counting in Large Graphs via Degree-Based Vertex Partitioning
• Property testing in bounded degree graphs

This page was built for publication: Approximately Counting Triangles in Sublinear Time