Metraipolis › archive › dc_7805c044fa07

Parameter-Free Triangle Counting — arXiv:2609.24829

Source

arXiv (en)

Original

https://arxiv.org/abs/2609.24829

License (as archived)

CC0-1.0

Archived

2026-10-09T22:40:55.137Z

SHA-256 of the archived text

48e86ef64c955117350f48c7dcaa7ea68375cefed22d138292ae5bd434523e04

Stable URL of this page

https://metraipolis.com/documento/dc_7805c044fa07

How to cite

Parameter-Free Triangle Counting — arXiv:2609.24829 — arXiv (en), https://arxiv.org/abs/2609.24829 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7805c044fa07 (Metraipolis archive dc_7805c044fa07, sha256 48e86ef64c955117350f48c7dcaa7ea68375cefed22d138292ae5bd434523e04)

@misc{dc7805c044fa07,
  title = {Parameter-Free Triangle Counting — arXiv:2609.24829},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.24829},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7805c044fa07; sha256 48e86ef64c955117350f48c7dcaa7ea68375cefed22d138292ae5bd434523e04},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.24829. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\tau$ that either provides an approximation of $T$ when $\tau \le T$, or declares that $T < \tau$. Furthermore, we prove a lower bound: any parameter-free algorithm that provides a multiplicative approximation for all values of $T$ must use $\Theta(m)$ space, even on streams where the triangle count is moderately large.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.24829 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T22:24:05.657Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).