arXiv preprint ·
Parameter-Free Triangle Counting
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Given an undirected, unweighted graph $G = (V,E)$ with $n$ vertices and $m$ edges, the triangle counting problem seeks the number of three-cycles in it. Triangle and subgraph counting are classical problems in graph algorithms, central to applications such as community detection, computing the clustering coefficient, motif discovery in protein networks, and social network analysis. In many of these applications, the graph datasets are so voluminous that we model them as streams of updates to an underlying graph. There are a number of foundational results for streaming triangle counting, both theoretical and practical. There is, however, one major drawback to all previous sublinear-space algorithms: to achieve both a constant factor approximation and the sublinear space guarantees, one needs to know a priori a constant factor approximation of the triangle count $T$, an inherently circular requirement. We initiate the study of parameter-free streaming triangle counting, without any a priori knowledge of $T$ or any quantities depending on $T$, provided $m$, the length of the stream. We describe a family of $O(p)$ pass parameter-free triangle counting algorithms that guarantee a mixed multiplicative and additive approximation of $T$ and use $\widetilde{O}(\frac{m+T}{\sqrt{T}})$ expected space. Moreover, this family leads to an $O(\log\log(n))$ pass algorithm that gives a $(1+\eps)$ multiplicative approximation of $T$ with the same space complexity. These algorithms rely on the notion of a \emph{verified} parametrized algorithm: an algorithm parametrized by $τ$ that either provides an approximation of $T$ when $τ\le T$, or declares that $T < τ$. Furthermore, we prove a lower bound: any parameter-free algorithm that provides a multiplicative approximation for all values of $T$ must use $Θ(m)$ space, even on streams where the triangle count is moderately large.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
High-Dimensional Ultra-Log-Concave Distributions
Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint
Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata
Improved Algorithms for the Remote Point Problem
On Deterministically Computing Total Variation Distance via Zonotope Compression
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.