On the Complexity of Sampling Vertices Uniformly from a Graph
On the Complexity of Sampling Vertices Uniformly from a Graph
复制标题
关于从图中均匀采样顶点的复杂性
DOI：
10.4230/lipics.icalp.2018.149
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Shahrzad Haddadan
中科院分区：
文献类型：
--
作者：
Flavio Chierichetti;Shahrzad Haddadan
我们在以下自然场景中研究了一些图探索问题：算法从某个种子顶点开始探索无向图;对于它所知道的任意顶点v，算法可以要求oracle返回v的邻居集。（在社交网络的情况下，对该oracle的调用对应于下载用户v的个人资料页面。）该算法的目标是学习一些东西（例如，平均度），或者返回图的某个随机函数（例如，均匀随机顶点），同时访问/下载尽可能少的图的顶点。
受实际应用的启发，我们研究了图的混合时间t_{mix}和平均度d_{avg}方面的各种问题的复杂性-这两个措施，被认为是相当小的，在现实世界的社交网络，并经常被用于在应用文献中绑定的在线探索算法的性能。
我们的主要结果是，该算法必须访问Omega（t_{mix} d_{avg}<$^{-2} ln delta^{-1}）顶点，以至少1-delta的概率获得图的顶点上的有界函数的平均值的一个可加性近似-这个下界与文献中提出的算法的性能相匹配。
我们还给出了严格的边界的问题，返回一个接近均匀随机顶点的图。最后，我们给出了估计图的平均度和图的顶点数的下界。
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.