Abstract
We study a number of graph exploration problems in the following natural scenario: an algorithm starts exploring an undirected graph from some seed vertex; the algorithm, for an arbitrary vertex v that it is aware of, can ask an oracle to return the set of the neighbors of v. (In the case of social networks, a call to this oracle corresponds to downloading the profile page of user v.) 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 uniformatrandom vertex), while accessing/downloading as few vertices 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 t_{mix} and average degree d_{avg}  two measures that are believed to be quite small in realworld 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 (t_{mix} d_{avg} epsilon^{2} ln delta^{1}) vertices to obtain, with probability at least 1delta, an epsilon additive approximation of the average of a bounded function on the vertices 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 closetouniformatrandom vertex from the graph. Finally, we give lower bounds for the problems of estimating the average degree of the graph, and the number of vertices of the graph.
BibTeX  Entry
@InProceedings{chierichetti_et_al:LIPIcs:2018:9153,
author = {Flavio Chierichetti and Shahrzad Haddadan},
title = {{On the Complexity of Sampling Vertices Uniformly from a Graph}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {149:1149:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9153},
URN = {urn:nbn:de:0030drops91538},
doi = {10.4230/LIPIcs.ICALP.2018.149},
annote = {Keywords: Social Networks, Sampling, Graph Exploration, Lower Bounds}
}
Keywords: 

Social Networks, Sampling, Graph Exploration, Lower Bounds 
Collection: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) 
Issue Date: 

2018 
Date of publication: 

04.07.2018 