Inferring Global Network Structure from Local Samples

This direction is split into other directions: network sampling bias. Its last version stays readable and citable here.

Version 1 of 188 papers97 conceptsfrozen 2026-10-04

In an ideal world, a network scientist would have a complete map of the system they are studying—every router on the Internet, every user on Twitter, or every protein in a cell. In reality, modern networks are effectively unbounded. As Kshitijaa Jaglan and Ulrik Brandes note in Tight Sampling in Unbounded Networks, the sheer scale of social platforms combined with restrictive API rate limits makes a full census impossible.

This constraint has birthed a research direction focused on network inference: the art of reconstructing global topological properties from tiny, often biased, local snapshots.

The Network as a Species Problem

When we sample a network using probes (like traceroute) or crawlers, we are essentially performing a "census of the unseen." Alain Barrat, Eric D. Kolaczyk, and Luca Dall'Asta reframed this in Network Inference from TraceRoute Measurements: Internet Topology 'Species' as a classic statistical "species problem."

If a biologist finds 10 unique species of beetles in a forest, how many total species exist? In a network, if we observe 1,000 nodes via random paths, how many nodes are we missing? By treating nodes as "species" and discovery events as "sightings," researchers can use non-parametric estimators to predict the true size and connectivity of the Internet or biological graphs without ever seeing the whole picture.

Correcting the Bias of Discovery

The primary challenge in this field is that sampling is rarely uniform. Most common traversal methods, such as Breadth-First Search (BFS), are notoriously biased. Maciej Kurant and Athina Markopoulou proved in On the bias of BFS that these traversals over-sample high-degree "hub" nodes.

This bias is further complicated by "private nodes." Kazuki Nakajima and Kazuyuki Shudo found that when a significant portion of a social network is hidden by privacy settings, the perceived network shape is fundamentally distorted. To fix this, researchers develop weighting schemes that account for the "collisions" (nodes visited multiple times) during random walks to back-calculate the true average degree and total population size.

The Latent Geometry of Missing Data

Perhaps the most surprising insight in this field is that we can find shortest paths even when the vast majority of the network is missing. In Finding shortest and nearly shortest path nodes in large substantially incomplete networks, Maksim Kitsak and colleagues demonstrate that real-world networks often possess a latent geometry.

By embedding a partially observed graph into hyperbolic space, the underlying "map" of the network becomes clear. Because shortest paths in these networks follow specific geometric trajectories, researchers can identify the nodes likely to lie on a path even if 90% of the links are unobserved. The intuition is that the global structure is "encoded" into the local curvature of the connections we can see.

Structural Signatures of "Found Data"

Often, we don't design our samples; we simply "find" data. Austin R. Benson and Jon Kleinberg explored this in Found Graph Data and Planted Vertex Covers. They realized that if a dataset is collected by monitoring a specific "core" group (e.g., all emails sent or received by a specific department), the resulting graph has a unique mathematical signature: the monitored group forms a vertex cover.

Every single edge in the observed graph must touch at least one member of that core group. This structural constraint allows researchers to work backward: by identifying the vertex cover of a "found" dataset, they can unmask the original observational bias and reconstruct the missing interactions between the unmonitored "peripheral" nodes.

Predicting Global Dynamics from Egonets

Can we predict if a virus will become an epidemic without knowing the full social graph? Victor M. Preciado and Moez Draief suggest we can. In Structural Analysis of Viral Spreading Processes... Using Egonets, they show that by analyzing "egonets"—the immediate neighborhoods of sampled individuals—one can calculate tight bounds on the network's epidemic threshold.

The intuition is that global spreading is a sum of local interactions. If you understand the "spectral moments" (the local density and branching) of enough small neighborhoods, you can statistically bound the behavior of the entire system. This allows for real-time epidemiological modeling on networks that are too large to ever fully map.

Papers in this version

Showing 60 of 88 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_inferring_global_network_structure_from__a3468a66,
  title = {Inferring Global Network Structure from Local Samples},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/inferring-global-network-structure-from-local-samples/rdr_a3468a66775a409cb61f0c119dae2611},
  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_inferring_global_network_structure_from__a3468a66_v1,
  title = {Inferring Global Network Structure from Local Samples},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/inferring-global-network-structure-from-local-samples/rdr_a3468a66775a409cb61f0c119dae2611/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}