Graph Sampling

Li-Chun Zhang

• Publisher: Chapman and Hall/CRC
• Year: 2021
• Print ISBN: 9781032067087
• eBook ISBN: 9781000540970
• Topic: Mathematics
• Subtopic: Probability & Statistics
• Index: Mathematics

Many technological, socio-economic, environmental, biomedical phenomena exhibit an underlying graph structure. Valued graph allows one to incorporate the connections or links among the population units in addition. The links may provide effectively access to the part of population that is the primary target, which is the case for many unconventional sampling methods, such as indirect, network, line-intercept or adaptive cluster sampling. Or, one may be interested in the structure of the connections, in terms of the corresponding graph properties or parameters, such as when various breadth- or depth-first non-exhaustive search algorithms are applied to obtain compressed views of large often dynamic graphs.

Graph sampling provides a statistical approach to study real graphs from either of these perspectives. It is based on exploring the variation over all possible sample graphs (or subgraphs) which can be taken from the given population graph, by means of the relevant known sampling probabilities. The resulting design-based inference is valid whatever the unknown properties of the given real graphs.

• One-of-a-kind treatise of multidisciplinary topics relevant to statistics, mathematics and data science.
• Probabilistic treatment of breadth-first and depth-first non-exhaustive search algorithms in graphs.
• Presenting cutting-edge theory and methods based on latest research.
• Pathfinding for future research on sampling from real graphs.

Graph Sampling can primarily be used as a resource for researchers working with sampling or graph problems, and as the basis of an advanced course for post-graduate students in statistics, mathematics and data science.

Chapter 1 General introduction

DOI: 10.1201/9781003203490-1

1.1 Sampling from finite populations

Denote by $U=\{1,\mathrm{...},N\}$ a population of size N. Denote by s a sample from U, $s\subset U$, according to some specified method of sampling. For any $i\in U$, let ${\pi }_i=\mathrm{Pr}(i\in s)$ be the sample inclusion probability, where ${\pi }_i>0$, which is either known before the sample is drawn or can be calculated afterwards.

Let y_i be an unknown constant associated with each population unit i, $i\in U$. Let $Y={\displaystyle \sum _{i\in U}{y}_i}$ be its population total. The Horvitz-Thompson (HT) estimator of Y is given by

$$\begin{array}{l}{\widehat{Y}}_{HT}={\displaystyle \sum _{i\in s}\frac{y_i}{{\pi }_i}}={\displaystyle \sum _{i\in U}{\delta }_i}\frac{y_i}{{\pi }_i}\hfill \end{array}$$

where ${\delta }_i=\mathbb{I}(i\in s)$. It is unbiased over hypothetically repeated sampling, denoted by $E({\widehat{Y}}_{HT})=Y$. The sampling variance of ${\widehat{Y}}_{HT}$ is given by

$$\begin{array}{l}V({\widehat{Y}}_{HT})={\displaystyle \sum _{i\in U}{\displaystyle \sum _{j\in U}(}}\frac{{\pi }_{ij}}{{\pi }_i{\pi }_j}-1)y_i{y}_j:={\displaystyle \sum _{i\in U}{\displaystyle \sum _{j\in U}{v}_{ij}}}\hfill \end{array}$$

where ${\pi }_{ij}=E({\delta }_i{\delta }_j)=\mathrm{Pr}(i\in s,j\in s)$ is the joint sample inclusion probability of $(i,j)$. Consider $V({\widehat{Y}}_{HT})$ as the total of $v_{ij}$ over $U\times U$, whose element $(ij)$ has inclusion probability ${\pi }_{ij}$ in $s\times s$. If ${\pi }_{ij}>0$ for any $(ij)\in U\times U$, then an unbiased estimator of $V({\widehat{Y}}_{HT})$ can be given by

$$\begin{array}{l}\widehat{V}({\widehat{Y}}_{HT})={\displaystyle \sum _{(ij)\in s\times s}\frac{v_{ij}}{{\pi }_{ij}}}={\displaystyle \sum _{i\in s}{\displaystyle \sum _{j\in s}(}}\frac{1}{{\pi }_i{\pi }_j}-\frac{1}{{\pi }_{ij}})y_i{y}_j\hfill \end{array}$$

1.2 Graph, motif, graph parameter

Representing a population U by a graph allows one to incorporate the connections or links among the population units in addition.

1.2.1 Graph

A graph $G=(U,A)$ consists of a set of nodes U and a set of edges A, where $\left|U\right|=N$ and $\left|A\right|=R$ are the order and size of G, respectively.

Attaching values to U or A yields a valued graph, and G is then the structure of the valued graph.

Let $A_{ij}$ be the set of edges from i to j, such that $A={\displaystyle \underset{i,j\in U}{\cup }{A}_{ij}}$. Let $a_{ij}=\left|A_{ij}\right|$. The graph is a multigraph if $a_{ij}>1$ for some $i,j\in U$; it is a simple graph otherwise.

By default, a graph is directed, or a digraph, in this book. The out-edges of node i are $A_{i+}={\displaystyle \underset{j\in U}{\cup }{A}_{ij}}$ and the in-edges of it are $A_{+i}={\displaystyle \underset{j\in U}{\cup }{A}_{ji}}$. The ou...

Table of contents

• Cover Page
• Half-Title Page
• Title Page
• Copyright Page
• Dedication Page
• Contents
• Preface
• Author Bio
• Abbreviations
• Symbols
• CHAPTER 1  ◾ General introduction
• CHAPTER 2  ◾ Bipartite incidence graph sampling and weighting
• CHAPTER 3 Strategy BIGS-IWE
• CHAPTER 4  ◾ Adaptive cluster sampling
• CHAPTER 5  ◾ Snowball sampling
• CHAPTER 6  ◾ Targeted random walk sampling
• Bibliography
• Index