📊 statistics

Exact Likelihood Inference for Snowball-Sampled Erd\H{o}s-Rényi Networks

This paper derives an exact likelihood-based inference framework for estimating edge probabilities in Erdős-Rényi networks from snowball-sampled data, demonstrating that the proposed maximum likelihood estimator and confidence intervals effectively eliminate the substantial bias inherent in standard analysis methods.

Original authors: Nurzhan Sapargali, Sergio Buttazzo, G\''oran Kauermann

Published 2026-08-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Nurzhan Sapargali, Sergio Buttazzo, G\''oran Kauermann

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to figure out how many people in a massive, invisible city are friends with each other. You can't see the whole city, so you decide to use a clever trick: you pick one person, ask them who their friends are, then ask those friends who their friends are, and keep going for a few rounds. This is called "snowball sampling," because your list of known people grows like a rolling snowball. But here's the catch: this method is biased. If you start with a popular person, you'll quickly find a huge crowd of friends, making it look like everyone in the city is super social. If you start with a loner, you'll barely find anyone. The problem is that the way you found the people (by following friendship links) is exactly the same thing you are trying to measure (how many friendships exist). If you just count the friends you found and divide by the number of people you met, you'll get a wrong answer that makes the city seem much more connected than it really is. This paper tackles that specific puzzle: how to fix the math so we can get the true answer, even when our detective work is inherently biased.

The authors of this paper, Nurzhan Sapargali, Sergio Buttazzo, and Göran Kauermann, have found a way to solve this puzzle for a specific type of network where every pair of people has the same, independent chance of being friends. They call this an "Erdős–Rényi" network, which is like a giant room where everyone flips a coin to decide if they shake hands with everyone else. In this simplified world, they discovered that the "snowball" method actually follows a very precise, predictable pattern. Instead of ignoring how the sample was collected, they wrote down the exact mathematical recipe (a likelihood function) that describes exactly how likely it is to see the specific group of people and connections you found, given the true friendship rate.

Their big breakthrough is showing that this messy, biased sample can be untangled using a "curved exponential family." That's a fancy way of saying the data fits into a neat mathematical box with just two key numbers that hold all the information needed to solve the mystery: the number of actual friendships you found, and a special count that includes the "missing" people you didn't find but know were excluded because they weren't friends with your starting group. Using this, they created a new, corrected way to calculate the friendship rate. When they tested this with computer simulations, they found that the old, standard way of counting was often wildly wrong—sometimes overestimating the friendship rate by ten or even a hundred times, especially if the network was sparse and the sample was small. In contrast, their new "snowball-corrected" estimator was almost perfectly accurate, even when the sample covered less than 0.1% of the total network.

To make sure they weren't just getting lucky, they also built a way to create "confidence intervals," which are like a range of guesses that says, "We are 95% sure the true answer is somewhere between X and Y." Because the math for this specific network is so complex, they couldn't just use a standard formula. Instead, they used a computer trick called Monte Carlo simulation, which involves running thousands of fake snowball samples to see how the numbers behave. They found that their new confidence intervals hit the target almost exactly, capturing the true value 95% of the time, while being much tighter and more useful than the wide, broad guesses you'd get from the old methods.

However, the authors are careful to point out that this magic trick only works for networks where friendships are completely random and independent, like flipping coins. Real-world networks are messier; some people are naturally more popular, and friendships often cluster in groups. The paper explicitly rules out using this exact formula for those complex, real-world scenarios without further changes. They also note that their math assumes the very first person you picked (the "ego") was chosen randomly, not because they were famous or popular. If you accidentally picked a celebrity to start your snowball, the math breaks down again. While they solved the problem for this specific, simplified case, they suggest that their approach could be a template for fixing similar problems in more complex networks in the future. For now, though, they have provided a precise, exact solution for the "coin-flip" version of the network world, proving that with the right math, you can see the whole forest even when you've only walked through a tiny, biased corner of it.

Technical Summary: Exact Likelihood Inference for Snowball-Sampled Erdős–Rényi Networks

Problem Statement
Network data collected via link-tracing designs, such as snowball sampling, present a fundamental inferential challenge: the mechanism used to select the sample depends on the very network structure (specifically, the edge density) that the analysis seeks to estimate. Treating the observed subgraph as a complete, representative realization of the population network—ignoring the sampling design—leads to systematically biased inference. While general solutions for network sampling often require intractable combinatorial sums over possible network completions (Handcock and Gile, 2010), this paper addresses the specific case of $r$ -wave snowball sampling with full-neighbourhood recruitment drawn from an Erdős–Rényi (ER) population. The authors aim to derive an exact likelihood that accounts for the sampling mechanism, thereby enabling unbiased estimation of the edge probability $\pi$ and valid confidence intervals, even when the sample covers a negligible fraction of the total network.

Methodology
The paper develops a closed-form derivation of the joint probability of observing both the sampled wave sets ( $V^{(0)}, \dots, V^{(r)}$ ) and the induced adjacency matrix ( $Y^{(r)}$ ) under the ER model.

Factorization of the Likelihood: The joint probability is factorized into the marginal probability of the wave sets and the conditional probability of the adjacency matrix given those sets.
- Wave Sets: The probability of observing specific wave sizes is derived by treating the recruitment process as a sequence of Bernoulli sampling designs. For the first wave, inclusion is a simple Bernoulli trial with probability $\pi$ . For subsequent waves ( $k \ge 2$ ), a vertex is included if it has at least one edge to the preceding wave, leading to a success probability of $1 - (1-\pi)^{n_{k-1}}$ .
- Adjacency Matrix: The conditional distribution of edges is constrained by the sampling design. Edges between non-adjacent waves must be zero. Edges between adjacent waves must satisfy the condition that every vertex in wave $k$ has at least one edge to wave $k-1$ . Edges within the same wave remain unconstrained Bernoulli trials.
Curved Exponential Family: The resulting joint probability mass function is shown to belong to a curved exponential family in the parameter $\pi$ . The likelihood depends on the data only through two scalar quantities:
- $|E^{(r)}|$ : The number of observed edges in the sample.
- $T(n)$ : A sufficient statistic representing the total number of "constrained" vertex pairs, defined as the sum of pairs within waves, pairs between adjacent waves, pairs between non-adjacent waves, and the product of unsampled nodes with the cumulative size of previous waves.
Estimation and Inference:
- Maximum Likelihood Estimator (MLE): The exact MLE, $\hat{\pi} = |E^{(r)}| / T(n)$ , is derived. This estimator corrects the standard estimator (which divides edges by the total possible pairs in the observed subgraph) by incorporating the information about unsampled nodes and the exclusion mechanism.
- Confidence Intervals: Due to the complexity of the sampling distribution's asymptotic behavior (which depends heavily on the relationship between $N$ and $\pi$ ), the authors construct confidence intervals via test inversion. They utilize Monte Carlo simulation with importance sampling to approximate the sampling distribution of the MLE under various candidate values of $\pi$ , allowing for the construction of conservative confidence sets without relying on asymptotic normality.

Key Results

Exact Likelihood Derivation: The paper provides the first closed-form expression for the likelihood of an $r$ -wave snowball sample from an ER network, resolving a specific open problem posed by Crane (2018).
Bias Reduction: Simulation studies demonstrate that the standard estimator, which ignores the sampling design, exhibits severe upward bias, particularly in sparse networks or when the number of waves is small (e.g., overestimating $\pi$ by one to two orders of magnitude in 1-wave samples). In contrast, the proposed snowball-corrected MLE remains approximately unbiased across all tested scenarios, even when the sample covers as little as 0.1% of the network.
Valid Inference: The Monte Carlo confidence intervals constructed via test inversion achieve nominal coverage levels (e.g., 95%) within Monte Carlo error across a range of edge probabilities and wave counts. These intervals are substantially narrower than those based on standard relative likelihood brackets.
Sufficiency: The pair $(|E^{(r)}|, T(n))$ is identified as a minimal sufficient statistic for $\pi$ , ensuring that the proposed estimator utilizes all information contained in the sample regarding the edge probability.

Significance and Claims
The authors claim that this work provides a tractable, exact solution to the selection bias problem in network sampling for the foundational Erdős–Rényi model. By explicitly modeling the sampling mechanism rather than ignoring it or conditioning it away (as in some conditional ERGM approaches), the method recovers information about the unsampled portion of the network.

The paper posits that the derived framework demonstrates a general principle: for network models where the likelihood factorizes over dyads (independent edges), the snowball sampling mechanism can be accounted for with a targeted, low-cost correction rather than intractable marginalization. This offers a principled alternative to estimators that treat sampled networks as complete population graphs. The authors explicitly limit their current contribution to the ER model and endogenous ego selection or partial observability of the final wave are discussed as extensions requiring future work, though the latter is shown to be formally equivalent to treating those edges as unsampled.

Technical Summary: Exact Likelihood Inference for Snowball-Sampled Erdős–Rényi Networks

More like this