On the Complexity of Sampling Vertices Uniformly from a Graph

DOI10.4230/LIPIcs.ICALP.2018.149zbMath1499.68262arXiv1710.08815OpenAlexW2963857389MaRDI QIDQ5002838

Shahrzad Haddadan, Flavio Chierichetti

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

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

Related Items (1)

Interactive proofs for social graphs

Cites Work

• Unnamed Item
• Lower bounds for sampling algorithms for estimating the average
• 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
• Approximating Clustering Coefficient and Transitivity
• Approximating average parameters of graphs
• Introduction to Testing Graph Properties
• Wedge sampling for computing clustering coefficients and triangle counts on large graphs^†
• Estimating Sizes of Social Networks via Biased Sampling
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph

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