On Estimating the Average Degree
Venue
23rd International World Wide Web Conference, WWW '14, ACM (2014) (to appear)
Publication Year
2014
Authors
Anirban Dasgupta, Ravi Kumar, Tamas Sarlos
BibTeX
Abstract
Networks are characterized by nodes and edges. While there has been a spate of
recent work on estimating the number of nodes in a network, the edge-estimation
question appears to be largely unaddressed. In this work we consider the problem of
estimating the average degree of a large network using efficient random sampling,
where the number of nodes is not known to the algorithm. We propose a new estimator
for this problem that relies on access to edge samples under a prescribed
distribution. Next, we show how to efficiently realize this ideal estimator in a
random walk setting. Our estimator has a natural and simple implementation using
random walks; we bound its performance in terms of the mixing time of the
underlying graph. We then show that our estimators are both provably and
practically better than many natural estimators for the problem. Our work contrasts
with existing theoretical work on estimating average degree, which assume a uniform
random sample of nodes is available and the number of nodes is known.
