Mitigating Sampling Bias in Partially Observed Networks

34 concepts31 papers1 proposal

In an era of billion-node social graphs and massive web crawls, researchers rarely have the luxury of seeing the "whole picture." Whether due to platform API rate limits, privacy restrictions, or the sheer computational cost of exhaustive data collection, most network science is performed on samples. However, these samples are not neutral mirrors of the global network; they are often distorted by the very methods used to collect them.

The central challenge in this field is understanding how partial observability—the state of seeing only a fraction of nodes and edges—introduces systematic biases that can lead to incorrect conclusions about a network's size, structure, and dynamics.

The Structural Bias of Discovery

The most common way to explore a large network is to follow its links, yet the path taken dictates what is found. As Maciej Kurant and Athina Markopoulou mathematically quantified in Towards Unbiased BFS Sampling, Breadth-First Search (BFS) is inherently biased toward high-degree nodes. Because popular nodes have more "roads" leading to them, a crawler is far more likely to stumble upon a celebrity or a major hub than a peripheral user.

This bias isn't just a minor statistical noise; it fundamentally alters the perceived topology. If a researcher uses a biased sample to estimate the average number of friends a person has, they will consistently overestimate the result. To counter this, Maciej Kurant et al. proposed "star sampling" in Coarse-Grained Topology Estimation via Graph Sampling, which looks at categories of neighbors to reconstruct global patterns from tiny, localized fragments.

API Constraints and Edge Omission

In the modern digital landscape, data access is often mediated by Application Programming Interfaces (APIs) that impose strict rate limits. These constraints force researchers to make trade-offs between the depth of their crawl and the breadth of the network they cover. Edo Liberty et al. argue in Estimating Sizes of Social Networks via Biased Sampling that we can actually turn these biases to our advantage. By using biased random walks that intentionally seek out popular nodes, researchers can estimate the total size of a network with significantly fewer API queries than uniform sampling would require.

However, limited access often leads to "edge omission," where the majority of connections between nodes are simply missing from the dataset. David R. Bild notes in Aggregate Characterization of User Behavior in Twitter and Analysis of the Retweet Graph that partial sampling can cause observed structural properties to deviate wildly from the true network. This is particularly problematic in studies of influence; Jiasen Yang et al. showed in Should We Be Confident in Peer Effects Estimated From Social Network Crawls? that standard crawls lead to highly inaccurate estimates of how much users influence their peers.

The Egocentric Perspective

Sampling bias also arises from the perspective of the data source. When a dataset is built from a single individual's communication logs—such as the FOIA-released emails analyzed by Nate Veldt et al. in Fauci-Email: A JSON Digest of Anthony Fauci's Released Emails—the resulting graph is "egocentric." It captures every interaction involving that central node but remains blind to lateral conversations between other participants.

A similar "visibility gap" occurs in corporate settings. Apoorv Agarwal et al. found in A Comprehensive Gold Standard for the Enron Organizational Hierarchy that relying on a limited number of user inboxes creates a biased social graph that can misrepresent an individual's true rank and influence within an organization.

Correcting for Human Limitations

In physical social networks, the "API" is often a human respondent. Researchers face "respondent fatigue," where participants can only remember or list a small number of friends. Naghmeh Momeni et al. explore this in Inferring Structural Characteristics of Networks with Strong and Weak Ties from Fixed-Choice Surveys, noting that fixed-choice surveys (e.g., "list your top 5 friends") truncate the network's true connectivity.

To mitigate this, researchers use methods like Respondent-Driven Sampling (RDS). However, even RDS is prone to bias because people do not recruit their friends at random. Xin Lu proposed the $RDS I^{ego}$ estimator in Linked Ego Networks: Improving Estimate Reliability and Validity with Respondent-driven Sampling, which asks participants about the composition of their entire social circle to correct for the idiosyncratic choices of recruiters. Similarly, the "Network Scale-Up Method" described by Carlos Baquero et al. in The CoronaSurveys System for COVID-19 Incidence Data Collection and Processing leverages the social knowledge of individuals to estimate the prevalence of rare events (like COVID-19 infections) more accurately than direct self-reporting.

Toward Representative Inference

The goal of this research direction is to move from "sampling by convenience" to "sampling by design." Whether it is Junzhou Zhao et al. using indirect jumps to sample loosely connected graphs in Sampling online social networks by random walk with indirect jumps, or Yun Wang et al. steering random walks toward specific hypotheses in A Sampling-based Framework for Hypothesis Testing on Large Attributed Graphs, the objective remains the same: to ensure that the small slice of the network we can see is a statistically valid representation of the whole.

Key Foundational Work

Coarse-Grained Topology Estimation via Graph Sampling (2011) — contributed 2 concept elements to this direction.
Towards Unbiased BFS Sampling (2011) — contributed 1 concept elements to this direction.
Experience versus talent shapes the structure of the Web (2008) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_network_sampling_bias_951a8540,
  title = {network sampling bias},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/network-sampling-bias/rdr_951a85409e8141db9fafa3f95051237b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_network_sampling_bias_951a8540_v1,
  title = {network sampling bias},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/network-sampling-bias/rdr_951a85409e8141db9fafa3f95051237b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake