Title: On the Complexity of Sampling Nodes Uniformly from a Graph,
Abstract: We study a number of graph exploration problems in the following natural
scenario: an algorithm starts exploring an undirected graph from some seed
node; the algorithm, for an arbitrary node $v$ that it is aware of, can ask an
oracle to return the set of the neighbors of $v$. (In social network analysis,
a call to this oracle corresponds to downloading the profile page of user $v$
in a social network.) The goal of the algorithm is to either learn something
(e.g., average degree) about the graph, or to return some random function of
the graph (e.g., a uniform-at-random node), while accessing/downloading as few
nodes of the graph as possible. Motivated by practical applications, we study
the complexities of a variety of problems in terms of the graph's mixing time
and average degree -- two measures that are believed to be quite small in
real-world social networks, and that have often been used in the applied
literature to bound the performance of online exploration algorithms. Our main
result is that the algorithm has to access $\Omega\left(t_{\rm mix} d_{\rm avg}
\epsilon^{-2} \ln \delta^{-1}\right)$ nodes to obtain, with probability at
least $1-\delta$, an $\epsilon$-additive approximation of the average of a
bounded function on the nodes of a graph -- this lower bound matches the
performance of an algorithm that was proposed in the literature. We also give
tight bounds for the problem of returning a close-to-uniform-at-random node
from the graph. Finally, we give lower bounds for the problems of estimating
the average degree of the graph, and the number of nodes of the graph.