Respondent driven sampling and sparse graph convergence

2017/05/08 by Athreya, Siva, Röllin, Adrian
#60J20 #9482 #FOS: Mathematics #Primary 05C80 #Probability (math.PR) #Secondary 37A30

paper · doi:10.48550/arxiv.1705.02731

Abstract

We consider a particular respondent-driven sampling procedure governed by a graphon. By a specific clumping procedure of the sampled vertices we construct a sequence of sparse graphs. If the sequence of the vertex-sets is stationary then the sequence of sparse graphs converge to the governing graphon in the cut-metric. The tools used are concentration inequality for Markov chains and the Stein-Chen method.

Related

• A sampling construction of graphon 1-norm convergence
• Generalized Graphon Process: Convergence of Graph Frequencies in Stretched Cut Distance
• A Poincaré Inequality and Consistency Results for Signal Sampling on Large Graphs
• An MCMC sampling of densest k-sub-graphs of regular graphs with connected complement graph
• Limits of Sparse Configuration Models and Beyond: Graphexes and Multi-Graphexes