Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries

We revisit the problem of designing sublinear algorithms for estimating the average degree of an \(n\)-vertex graph. The standard access model for graphs allows for the following queries: sampling a uniform random vertex, the degree of a vertex, sampling a uniform random neighbor of a vertex, and “pair queries” which determine if a pair of vertices form an edge. In this model, original results [Goldreich-Ron, RSA 2008; Eden-Ron-Seshadhri, SIDMA 2019] on this problem prove that the complexity of getting \((1+\varepsilon)\)-multiplicative approximations to the average degree, ignoring \(\varepsilon\)-dependencies, is \(\Theta(\sqrt{n})\). When random edges can be sampled, it is known that the average degree can be estimated in \(\tilde{O}(n^{1/3})\) queries, even without pair queries Motwani-Panigrahy-Xu-ICALP-2007, Beretta-Tetek-TALG-2024.