On the Complexity of Sampling Vertices Uniformly from a Graph

DOI10.4230/LIPICS.ICALP.2018.149MaRDI QIDQ5002838zbMATH OpenOpenAlexFDO

Authors Flavio Chierichetti, Shahrzad Haddadan

Publication date 28 July 2021

Full work available at URL https://arxiv.org/abs/1710.08815

zbMATH Keywords

samplingsocial networkslower boundsgraph exploration

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

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 $Omegaleft(t_{mmix}{d}_{mavg}epsilo{n}^{-2}lndelt{a}^{-1}ight)$ 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.

Recommendations

• Uniform random sampling of planar graphs in linear time
• On random sampling in uniform hypergraphs
• Uniform sampling of directed and undirected graphs conditional on vertex connectivity
• Uniform sampling of digraphs with a fixed degree sequence
• A linear-time algorithm for sampling graphs with given degrees
• Uniform sampling of bipartite graphs with degrees in prescribed intervals
• Tight bounds on vertex connectivity under vertex sampling
• Towards random uniform sampling of bipartite graphs with given degree sequence
• Tight Bounds on Vertex Connectivity Under Sampling
• Sampling geometric inhomogeneous random graphs in linear time

Cites work

• Approximating Clustering Coefficient and Transitivity
• Approximating average parameters of graphs
• Chernoff-Hoeffding bounds for Markov chains: generalized and simplified
• Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters
• Estimating graph parameters via random walks with restarts
• Estimating sizes of social networks via biased sampling
• Introduction to testing graph properties
• Lower bounds for sampling algorithms for estimating the average
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Wedge sampling for computing clustering coefficients and triangle counts on large graphs^†

Cited in

(11)

• On random sampling in uniform hypergraphs
• Interactive proofs for social graphs
• Estimating graph parameters via random walks with restarts
• On sampling edges almost uniformly
• Sampling to provide or to bound: With applications to fully dynamic graph algorithms
• How large is your graph?
• Uniform random sampling of planar graphs in linear time
• Brief announcement: How large is your graph?
• Scalable Uniform Graph Sampling by Local Computation
• Tight Bounds on Vertex Connectivity Under Sampling
• A fair-cost analysis of the random neighbor sampling method

This page was built for publication: On the Complexity of Sampling Vertices Uniformly from a Graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5002838)