Abstract
We establish a functional weak law of large numbers for observable macroscopic state variables of interacting particle systems (e.g., voter and contact processes) over fast time-varying sparse random networks of interactions. We show that, as the number of agents $N$ grows large, the proportion of agents $\left(\overline{Y}_{k}^{N}(t)\right)$ at a certain state $k$ converges in distribution -- or, more precisely, weakly with respect to the uniform topology on the space of \emph{c`adl`ag} sample paths -- to the solution of an ordinary differential equation over any compact interval $\left[0,T\right]$. Although the limiting process is Markov, the prelimit processes, i.e., the normalized macrostate vector processes $\left(\mathbf{\overline{Y}}^{N}(t)\right)=\left(\overline{Y}_{1}^{N}(t),\ldots,\overline{Y}_{K}^{N}(t)\right)$, are non-Markov as they are tied to the \emph{high-dimensional} microscopic state of the system, which precludes the direct application of standard arguments for establishing weak convergence. The techniques developed in the paper for establishing weak convergence might be of independent interest.
Introduction
In fields ranging from statistical mechanics to epidemiology, a primary goal is to understand the macroscopic behavior of large-scale systems of interacting agents. For instance, one might want to predict the percentage of a population infected with a virus over time. While the "microstate"—the specific status and connectivity of every individual—determines the system's future, tracking every agent in a massive system is analytically and computationally impossible.
The fundamental challenge is that these macrostates are typically non-Markovian. Knowing the current percentage of infected individuals is insufficient for prediction; one also needs to know the specific network structure, such as whether infected individuals are clustered or distributed. While "fluid limits" (where stochastic systems become deterministic) are well-understood for complete networks where every agent can interact with every other, this paper addresses the more realistic and difficult scenario of sparse networks that change rapidly over time.
Methodology
The authors utilize the Finite Markov Information-Exchange (FMIE) framework to model agent interactions. Their key innovation is the assumption of fast network mixing: every time an interaction occurs between two agents, the entire network's edges are randomly rewired (shuffled). This mechanism ensures that local dependencies do not persist long enough to bias the macroscopic trajectory.
To prove that the system converges to a deterministic ODE as the number of agents ($N$) grows, the authors developed a multi-step analytical approach:
- Gap Process Analysis: They defined a "gap process" to measure the instantaneous deviation between the actual interaction rate on the sparse network and the expected rate in a perfectly mixed system. Proving that this gap vanishes is central to the convergence proof.
- Coupling and Martingales: They introduced an auxiliary process that is easier to analyze and "coupled" it to the original system. Using Martingale theory and Bernstein concentration inequalities, they showed that random fluctuations in the system's trajectory converge to zero in probability.
- Skorokhod Representation: This tool was used to establish weak convergence on the space of sample paths, ensuring the result holds over any compact time interval $[0, T]$.
Theoretical Insights
The paper's most significant insight is the Recovery of the Determinism Principle. It demonstrates that fast random rewiring effectively "washes away" microscopic configuration details. In the limit of a large population, the macroscopic state "realizes" the microstate, making the system's evolution predictable.
Crucially, the authors show that sparsity is not a barrier to determinism. Even when the network is sparse—meaning the number of edges grows only linearly with the number of agents ($O(N)$)—a deterministic fluid limit can still be achieved if the network changes fast enough. This challenges the common intuition that dense connectivity is required for mean-field-like behavior. The introduction of the "gap process" provides a general technique for handling non-Markovian prelimit processes, which could be a valuable tool for researchers studying other types of networked systems where local structure usually complicates global analysis.
Convergence Results
The primary theoretical contribution is a formal proof (Theorem 9) that the empirical distribution of agent states converges weakly to the solution of a specific ODE: $$\dot{y}_k(t) = d \cdot \mathbf{y}(t)^\top (\Gamma \odot C(k)) \mathbf{y}(t)$$ where $d$ is the average degree of the network, and $\Gamma$ and $C(k)$ represent interaction rates and state transition rules, respectively.
The authors illustrated this with a simulation of a binary contact process (an epidemic model) on a cycle network ($d=2$). For a population of 100 nodes, the system's trajectory is noisy and fluctuates significantly around the theoretical curve. However, with 4000 nodes, the stochastic path becomes almost indistinguishable from the smooth ODE curve, confirming the emergence of the "fluid limit" behavior.
Discussion and Future Work
While the results provide a rigorous foundation for understanding sparse interacting systems, they rely on the "fast network mixing" regime where the network is rewired after every single interaction. This is a strong assumption that may not hold in all real-world scenarios.
Future research directions suggested by the authors include:
- Characterizing the broadest possible class of network dynamics (e.g., slower rewiring or specific non-random topologies) that still lead to an exact fluid limit.
- Exploring "mesoscale" dynamics where the network changes at a speed comparable to the agent interactions themselves.
- Applying these techniques to practical scenarios like malware spread in mobile ad-hoc communication networks.
Summary updated