Large population limits of Markov processes on random networks

Marvin Lücke, Jobst HeitzigStochastic 2022 · arXiv

TL;DR

This paper provides a rigorous mathematical bridge between complex agent-based simulations on networks and simple, deterministic differential equations. The authors prove that as a population grows, the macroscopic behavior of interacting agents on various random networks (like Erdős–Rényi or Stochastic Block Models) converges to a "mean-field" ordinary differential equation (ODE), allowing researchers to trade heavy computation for analytical clarity.

What Problem Does This Paper Address?

In fields ranging from epidemiology to sociology, we often model systems as networks of "agents" (nodes) that change states based on their neighbors (edges). While these agent-based models (ABMs) capture rich detail, they are computationally expensive to simulate as the population size ($N$) increases.

The "holy grail" for these models is a mean-field limit: a simplified ODE that describes the system's overall state (e.g., the percentage of the population that is infected) without tracking every individual. While classical results exist for "all-to-all" interactions (where every agent talks to everyone else), real-world interactions happen on sparse or structured networks. This paper addresses the gap of proving exactly when and how these network-based stochastic processes converge to a smooth, predictable ODE.

Methods

The authors utilize a framework of collective variables—low-dimensional projections that measure the share of agents in a specific state within a specific subset of the network.

Key technical components include:

  • Theorem 3.1 (The Convergence Theorem): A high-level proof showing that if the network's "propensity functions" (the rates at which states change) can be approximated by the collective variables, the stochastic process will converge in probability to the solution of a mean-field ODE over any finite time interval.
  • Concentration Inequalities: To prove convergence for specific network types, the authors use tools like the Chernoff bound and McDiarmid’s inequality to show that local neighborhood properties (like node degree) stay close to their expected values in a large population.
  • Continuous-Time Noisy Voter Model (CNVM): They use this specific dynamical model as a primary test case to verify their theoretical results across different topologies.

Datasets

The paper does not use real-world empirical datasets. Instead, it relies on synthetic benchmarks and numerical simulations to validate the theory:

  • Erdős–Rényi (ER) Graphs: Standard random graphs where edges exist with a fixed probability.
  • Stochastic Block Models (SBM): Graphs with community structures (clusters).
  • Random Regular Graphs: Graphs where every node has exactly the same degree $d$.
  • Heterogeneous Populations: Simulations where different classes of agents (e.g., "zealots" vs. "followers") have different transition rates.

Key Insights and Ideas

  • Regularity vs. Sparsity: One of the most interesting findings is that Random Regular graphs are much "easier" to approximate than Erdős–Rényi graphs. For a regular graph, the mean-field limit holds as long as the degree $d$ goes to infinity, even if it grows extremely slowly. In contrast, ER graphs require the average degree to grow faster than $\log(N)$ to ensure the network is sufficiently connected and "well-behaved."
  • Lumping by Class: The authors show that you don't just have to track the whole population. You can "lump" agents into classes based on their traits or their position in a community (like in the Stochastic Block Model) and derive a multi-dimensional ODE that tracks the evolution of each group separately.
  • Beyond Graphons: While recent literature often uses "graphons" (limit objects for dense graphs) to study these limits, this paper’s approach is more flexible. It successfully handles Random Regular graphs, which are difficult to represent using standard graphon theory because their edges are stochastically dependent.

Key Results

  • ER Graphs (Theorem 4.4): Convergence to the mean-field limit is guaranteed if the edge probability $p$ satisfies $p = \omega(\log N / N)$. This matches the sharp threshold for network connectedness.
  • Random Regular Graphs (Corollary 4.14): Convergence is guaranteed as long as the degree $d \to \infty$ as $N \to \infty$.
  • Numerical Validation: The authors provide simulations (e.g., Figure 2 and 6) showing that as $N$ and the network density increase, the variance of the stochastic simulations vanishes, and the trajectories align perfectly with the predicted ODE.
  • Heterogeneity: The framework successfully predicts the behavior of populations with different agent types, showing that the "mean-field" isn't just for identical agents.

Limitations and Future Work

  • Optimal Variable Selection: The paper assumes we know which collective variables to track (e.g., "percentage of state A"). However, for complex systems, finding the optimal set of variables that capture the dynamics remains an open challenge.
  • Finite-Size Fluctuations: The ODE is a limit for $N \to \infty$. For medium-sized populations, the "noise" or fluctuations around the mean-field can be significant. The authors suggest that future work could use Stochastic Differential Equations (SDEs) to model these corrections.
  • Adaptive Networks: The current work assumes a static (though random) network. In many real-world scenarios, the network structure changes as the agents change states (e.g., people unfriending those with different opinions). Extending this theory to "co-evolving" or adaptive networks is a suggested next step.

Summary updated

Abstract

This record contains metadata for the MATH+ project EF4-8 "Concentration effects and collective variables for agent-based models".
BibTeX
@inproceedings{lucke2022large,
  author = {Marvin Lücke and Jobst Heitzig},
  title = {{Large population limits of Markov processes on random networks}},
  booktitle = {Stochastic},
  year = {2022},
}
Figure