Sampling on Social Networks from a Decision Theory Perspective

Simón Lunagómez, Edoardo M. Airoldi

Abstract

Some of the most used sampling mechanisms that propagate through a social network are defined in terms of tuning parameters; for instance, Respondent-Driven Sampling (RDS) is specified by the number of seeds and the maximum number of referrals. We are interested in the problem of optimizing these tuning parameters with the purpose of improving the inference of a population quantity, where such quantity is a function of the network and measurements taken at the nodes. This is done by formulating the problem in terms of Decision Theory. The optimization procedure for different sampling mechanisms is illustrated via simulations in the fashion of the ones used for Bayesian clinical trials.

Introduction

Sampling "hidden" or hard-to-reach populations—such as individuals with rare medical conditions, niche market segments, or marginalized groups—presents a significant challenge for researchers. Because no comprehensive sampling frame or "master list" exists for these populations, researchers often rely on link-tracing designs like Respondent-Driven Sampling (RDS). In RDS, a small set of initial "seeds" is recruited, and these individuals are given coupons to refer their peers, who then refer others in a cascading chain.

While RDS is widely utilized, its implementation often relies on heuristics or "rules of thumb." Practitioners must decide on critical tuning parameters: How many seeds should be used? How many referrals should each participant be allowed? Historically, these choices have been driven by budget constraints or convention rather than statistical optimization. This paper addresses this gap by providing a rigorous mathematical framework to calibrate these parameters, ensuring that the resulting sample provides the most accurate possible inference about the population.

A Decision-Theoretic Framework

The authors approach the optimization of sampling designs through two distinct but complementary lenses: Bayesian Decision Theory and Information Theory.

1. Bayesian Decision Theory

Adopting Lindley’s formulation of experimental design, the authors treat the choice of a sampling design as a "decision." The objective is to select a design that minimizes an Expected Loss Function (such as Mean Squared Error) across the space of possible network structures allowed by prior knowledge. By treating the sampling process as a decision problem, researchers can formally weigh the trade-offs between different configurations of seeds and referrals.

2. Information Theory and Data Compression

In scenarios where a researcher may not have a specific population quantity in mind at the outset, the authors propose a novel approach based on data compression. Here, a partially sampled network is viewed as a compressed representation of the full, unobserved network. The "best" sampling design is defined as the one that preserves the maximum amount of information, thereby minimizing the information loss when attempting to reconstruct the full network from the sample. This provides a general-purpose metric for ranking designs even in the absence of a specific loss function.

Computational Strategy and Simulation

One of the primary difficulties in network sampling is "non-ignorability": the sampling process itself depends on the structure of the network being studied. To account for this, the authors utilize Bayesian Model Averaging (BMA) and Markov Chain Monte Carlo (MCMC) methods to impute unobserved portions of the network. This allows for a fully probabilistic treatment of the data.

To validate this framework, the authors conducted extensive simulations using various network models:

  • Erdős-Rényi Graphs: For purely random connectivity.
  • Stochastic Block Models (SBM): To simulate community structures.
  • Latent Space Models: To capture more complex social geometries.

To simulate real-world measurements (such as disease status or behavioral traits), they employed Markov Random Fields (MRF), which create realistic dependencies between connected individuals in the network.

Key Insights and Results

The research yields several critical insights into the behavior of network sampling:

  • The Optimality of Referrals: Simulations revealed that the relationship between the number of referrals ($m$) and estimation error is non-monotonic. For a fixed sample size, the authors found that $m=3$ referrals were often optimal. Interestingly, increasing referrals beyond this point sometimes increased the posterior loss, suggesting that there is a "sweet spot" between the depth and breadth of a network search.
  • The Impact of Seeds: The number of initial seeds ($w_0$) has a significant impact on performance. In a 200-node network simulation, increasing the seed count from 5 to 15 consistently reduced the log-expected loss, highlighting the importance of a broad starting base for RDS.
  • Validation of Data Compression: A major finding was the high level of consistency between the rankings produced by the Data Compression (DC) approach and those from traditional Decision Theory. This suggests that DC is a robust proxy for optimization when specific loss functions are difficult to define.
  • Addressing Ignorability: Traditional statistical criteria often struggle to distinguish between "ignorable" designs (where the sampling doesn't depend on the data). The authors' DC approach successfully rewards designs that capture more underlying network structure, providing a more nuanced tool for design selection.

Conclusion and Future Work

This paper moves RDS from a heuristic-based method to a calibrated scientific tool. By providing a mathematical basis for choosing sampling parameters, researchers can now design surveys that are tailored to the expected density and structure of the target network.

However, the authors note that the "fully Bayesian" approach is computationally intensive, which may limit its application to massive networks without further algorithmic optimization. Future research directions include accounting for "noisy self-reporting" (where participants misreport their number of connections) and developing adaptive sampling techniques. In an adaptive framework, the sampling design could be updated in real-time as data is collected, much like modern adaptive clinical trials, to further maximize the efficiency of the inference.

Summary updated

Abstract

Some of the most used sampling mechanisms that propagate through a social network are defined in terms of tuning parameters, for instance, Respondent-Driven Sampling (RDS) is specified by the number of seeds and maximum number of referrals. We are interested in the problem of optimising these tuning parameters with the purpose of improving the inference of a population quantity, where such quantity is a function of the network and measurements taken at the nodes. This is done by formulating the problem in terms of Decision Theory. The optimisation procedure for different sampling mechanisms is illustrated via simulations in the fashion of the ones used for Bayesian clinical trials.
BibTeX
@misc{lunagomez2018sampling,
  author = {Simón Lunagómez and Edoardo M. Airoldi},
  title = {{Sampling on Social Networks from a Decision Theory Perspective}},
  year = {2018},
  eprint = {1811.07829},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.07829},
}

Loading related content...

Figure