Approximating Average Parameters of Graphs
Webpage for a paper by Oded Goldreich and Dana Ron
Abstract
Inspired by Feige (36th STOC, 2004),
we initiate a study of sublinear randomized algorithms
for approximating average parameters of a graph.
Specifically, we consider the average degree of a graph
and the average distance between pairs of vertices in a graph.
Since our focus is on sublinear algorithms, these algorithms
access the input graph via queries to an adequate oracle.
We consider two types of queries.
The first type is standard neighborhood queries
(i.e., "what is the $i$th neighbor of vertex $v$?"),
whereas the second type are queries regarding the quantities
that we need to find the average of
(i.e., "what is the degree of vertex $v$?"
and "what is the distance between $u$ and $v$?", respectively).
Loosely speaking, our results indicate a difference between the
two problems: For approximating the average degree,
the standard neighbor queries suffice and in fact are preferable
to degree queries. In contrast, for approximating average distances,
the standard neighbor queries are of little help whereas distance
queries are crucial.
Note: Part of this work appeared in our work
On Estimating the Average Degree of a Graph.
Note: This work may be viewed as initiating a wider study,
concerned with the fast approximation of various averages.
See, for example, a follow-up work
on approximating the average
distance between points in metric spaces.
Material available on-line
Back to
either Oded Goldreich's homepage.
or general list of papers.