Triangle counting method estimates quickly without preset memory or totals
Scalable Triangle Counting: The Threshold Algorithm
Data Structures and AlgorithmsDatabases
Summary
Counting triangles in large networks helps understand connections but is usually expensive and slow. The authors introduce a simple method that reads only part of the network edges until it sees enough triangles, then estimates the total count accurately without needing prior information about the network size. Their method is faster and uses less memory compared to previous ones, especially on huge networks. Tests show it returns good estimates very early in the process, saving time and computing resources.
What this means in practice
- •For network analytics teams: Estimate triangle counts in massive network streams early and with limited memory to enable faster graph analysis pipelines.
- •For social media engineers: Provide quick estimates of connected user triads without needing to store or process all user interactions upfront.
Authors
Asaf Etgar, Anna Gilbert, Quanquan C. Liu, Andrew McGregor
Abstract
We study one-pass triangle counting on random-order edge streams. We present a remarkably simple algorithm---read edges from the stream until $Q$ triangles are observed in the prefix, then output $Q\,(m/S)^3$ where $S$ is the stopping length---and prove that, when the maximum number of triangles incident to any edge satisfies $η\le T^{2/3}$, this is a $(1\pm\varepsilon)$-approximation of $T$ with probability $1-δ$ using $O(\varepsilon^{-2}\log(1/δ)\, m/T^{1/3})$ memory. Crucially, the algorithm does not need any a priori estimate of $T$, in sharp contrast with state-of-the-art sampling-rate based algorithms (McGregor and Vorotnikova, PODS 2020; Tsourakakis et al., KDD 2009). It also does not need a prescribed memory budget: the stopping rule self-selects the prefix length and can return an estimate before reading the entire stream. The proof rests on a Schudy--Sviridenko concentration argument for an independent-edge-sampling estimator, coupled to the without-replacement prefix produced by the algorithm. On six real temporal streams, the algorithm's stopping prefix follows the predicted cube-root scaling and achieves at most $6\%$ error at a $10\%$ prefix, without using $T$. At a fixed stored-edge budget, variance-reduced reservoir samplers are often more accurate, but only after reading the entire stream. On a separate, much larger, $1.8\times10^9$-edge graph, the threshold algorithm reads $0.46\%$ of the stream and returns $3.8\%$ error, while the strongest reservoir baselines do not finish a pass within the wall-clock cap.