License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.149
URN: urn:nbn:de:0030-drops-91538
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9153/
Chierichetti, Flavio ;
Haddadan, Shahrzad
On the Complexity of Sampling Vertices 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 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 uniform-at-random 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 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 (t_{mix} d_{avg} epsilon^{-2} ln delta^{-1}) vertices to obtain, with probability at least 1-delta, 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 close-to-uniform-at-random 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:1--149:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-076-7},
ISSN = {1868-8969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9153},
URN = {urn:nbn:de:0030-drops-91538},
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 |
