Summary
This work studies how to find out important information about a network, like how many connections it has and how connected its points are, by checking a few random links and their ends. The authors show that the key factor controlling how many checks are needed is a property called the "matching number," which measures the largest set of completely separate links. They provide new methods that work well without knowing the size of the network beforehand and prove that these methods are basically the best possible in terms of the number of checks required. This improves on earlier methods that depended on the total number of points instead.
What this means in practice
- •For network engineers: Efficiently estimate total links and connection patterns in large networks using fewer random probes based on the matching number property.
- •For data analysts: Analyze large graph-based datasets by estimating structural statistics without full knowledge of the graph size or exhaustive queries.
A theory result. No direct application yet.
Abstract
Consider an unknown graph $G = (V,E)$ with vertex degrees $d_v$, accessed only by sampling uniformly random edges and querying the degrees of their endpoints. We study the query complexity of estimating the number of edges $m$ and the degree moments $M_s = \sum_{v \in V} (d_v)^s$ for fixed integers $s \ge 2$. In this model, [Beretta and Tětek, TALG 2024] estimate $m$ within relative error $\varepsilon$ using $O(\log n/\varepsilon^2+\sqrt n/\varepsilon)$ expected queries without knowing the number of vertices $n$, and [Bhattacharya and Pradhan, CIAC 2025] estimate $M_s$ using $O(n^{1-1/s}/\varepsilon^2)$ queries when $n$ is given. We show that the query complexity of both problems is governed by the matching number $ν$ of $G$ (the maximum number of pairwise disjoint edges) rather than the number of vertices $n$, and that the dependence on $\varepsilon$ for degree moments can be polynomially improved. Our algorithms rest on a simple observation: the endpoints of a maximum matching cover every edge, so a random endpoint of a random edge falls on this set of $2ν$ vertices with probability at least $1/2$. For every $\varepsilon\in(0,1]$, we give advice-free algorithms that estimate $m$ and $M_s$ within relative error $\varepsilon$ with probability at least $2/3$, without knowledge of $n$, $ν$, or other graph parameters. Specifically, our algorithms use $O(\min\{ν/\varepsilon, 1/\varepsilon^2+\sqrtν/\varepsilon\})$ expected queries for $m$ and $O(\min\{ν^{1-1/s}/\varepsilon^{2/s}, ν^{1-1/(2s-1)}/\varepsilon^{2/(2s-1)}\})$ for $M_s$. Finally, our lower bounds show that for every $k \ge 2$ and sufficiently small $\varepsilon$, these query complexities are optimal up to constant factors over graphs with matching number at most $k$.