A mathematically principled framework for deriving edge-based mean-field approximations for a broad class of Markov processes on networks using approximate lumping is presented, which yields density-dependent population processes that reduce to a low-dimensional system of ordinary differential equations.
Abstract
Mean-field approximations for dynamical processes on networks are widely used, but existing derivations often rely either on moment closures or on idealised assumptions about network structure, leaving the nature of the underlying averaging unclear. Here we present a mathematically principled framework for deriving edge-based mean-field approximations for a broad class of Markov processes on networks using approximate lumping. We consider models in which each vertex is in one of a finite number of vertex states and transitions depend on the number of neighbours in each state. Our approach partitions the full Markov chain state space according to the number of vertices and edges in each possible state, and averages transition rates between partitions. This yields density-dependent population processes that, in the limit of large system size, reduce to a low-dimensional system of ordinary differential equations. We demonstrate the method on single graphs and graph ensembles, such as Erd\H{o}s-R\'enyi random networks, and show that well-known edge-based mean-field approximations arise as special cases of our approach. Our approximate lumping framework clarifies the nature of the averaging underlying mean-field approximations, providing a basis for future work on assessing their accuracy.
Predicting the percolation threshold of highly clustered networks from local statistics remains difficult, because short loops break the independence assumption underlying tree-like message passing. Existing remedies address loopy connectivity either through prescribed local motifs in random-graph ensembles or through a single network's realized topology, leaving an ensemble-level treatment of arbitrary connectivity patterns absent. Here, we develop a loopy message-passing framework for random clustered graph ensembles based on generalized-edge statistics, which characterize overlap patterns among the neighborhoods of different nodes. This yields a progressively refined approximation scheme based on neighborhoods of increasing size around each node. The low-order approximations recover previous equations for random network ensembles, and the new result that yields refined threshold prediction is developed by the second-order approximation. We show that the effectiveness of this framework depends not only on short-cycle density but also on the internal consistency of generalized edges. To diagnose this effectiveness, we introduce the generalized-edge closure coefficient (GECC) to quantify this consistency. Because GECC is computed entirely from local statistics and does not rely on any percolation calculation, it serves as an a priori diagnostic for the reliability of the approximation. Using synthetic and real networks, the threshold is evaluated via the second-order and lower-order approximations. Comparisons with Monte Carlo simulations show that GECC captures key structural features that strongly affect the percolation threshold. These results establish ensemble-based loopy message passing as an efficient route for predicting the percolation threshold in large clustered networks.
We derive a one-dimensional reduction for nonlinear dynamics on simplicial complexes containing both pairwise and triangular (higher-order) interactions. The effective state is defined using a mixed weight determined by the pairwise and triangular degrees of each node. The resulting reduced equation retains two structural coefficients, associated separately with the pairwise and higher-order coupling channels. A fluctuation expansion identifies the closure assumptions underlying the reduction and shows how deviations of individual node states from the effective state contribute to the approximation error. We numerically validate the proposed framework on Gene-regulatory dynamics, the double-well system, and SIS spreading. The states of the reduced model are compared with full-network simulations through coupling-parameter sweeps, steady-state branch calculations, and progressive node-removal experiments on synthetic and real-world networks. The reduced model successfully reproduces the principal transitions and steady-state branches in all three dynamical systems considered. Agreement is strongest for relatively homogeneous networks and deteriorates when structural heterogeneity produces a broader distribution of node states. The closure diagnostics account for this loss of accuracy and indicate when a single effective state is no longer sufficient. The reduction therefore provides a tractable description of resilience in systems with coexisting pairwise and higher-order interactions.
Amit Tiwari, C. Hens, Prosenjit Kundu· 0 citations
The analysis of random walks on networks often relies on global quantities that average over nodes, thereby masking local differences in diffusion speed. This study introduces a vertex-level quantity Hi, defined as the finite-window fitted scaling exponent of the mean squared resistance distance ⟨Ωi2(t)⟩∼Cit2Hi from a given node i. We found nodes with Hi values below 0.5 (echo effect) and above 0.5 (catapult effect). The exponent is computed exactly via matrix powers of the transition matrix. We systematically evaluate Hi on several synthetic network families, generalized Sierpiński graphs, Newman-Watts small-world networks, and a custom grid-path-complete graph, and on two real-world networks (international E-road network and western U.S. power grid). We found nodes with Hi values less than 0.5 (subdiffusive regime) and greater than 0.5 (apparent superdiffusion) in both model networks and real-world networks. Analysis of model networks shows that when a node has an echo effect, its Hi value is less than 0.5, whereas when it has a catapult effect, its Hi value is greater than 0.5. In the two real networks, most nodes are in the subdiffusive regime and the overall heterogeneity of the local diffusion exponents is low, as indicated by Rényi indices of 0.0835 (E-road network) and 0.0555 (power grid). Comparisons with classical centrality measures indicate that Hi provides information not captured by those measures. The local diffusion exponent offers a vertex-level, dynamics-based tool for identifying structural bottlenecks and node roles, complementing global network characterizations.
Susceptible-infected-susceptible (SIS) epidemic models on networks are governed by hierarchical moment equations where the dynamics of smaller subsystems depend on the state of larger ones. Moment closure approximations, which truncate this hierarchy by expressing higher-order state probabilities in terms of lower-order ones, are essential for obtaining tractable reduced systems. Higher-order networks, which extend the pairwise structure to include group interactions, introduce a combinatorial explosion of closure configurations, making systematic derivation harder. Consequently, existing higher-order SIS models are derived heuristically, where structural and dynamical assumptions underpinning their closures are not always apparent from the formulation alone. We develop a bottom-up derivation of higher-order SIS dynamics, building systematically from node-level equations to pairs, triplets, and three-body interactions. Central to our approach is a network-dependent closure operator that generates topologically appropriate approximations from local pairwise and triadic structure. Using this framework, we recover three existing higher-order SIS models--Burgio et al.'s maximal clique, Malizia et al.'s pair-based and inter-order models--as special cases, each arising under specific topological and dynamical assumptions. Our derivation reveals assumptions that are invisible from heuristic approaches: for instance, Malizia et al.'s inter-order overlap parameter is insufficient alone to express the model within our framework despite performing well against simulations, with the original derivation implicitly invoking additional structural assumptions. Our framework offers both a foundation for higher-order epidemic modeling and a constructive pathway for understanding the assumptions implicit in heuristically derived mean-field closures and provides a principled method of generating new models.
Kevin Teo, Péter L. Simon, I. Z. Kiss· 0 citations
Extreme epidemic risk is controlled by the right tail of the outbreak-size distribution, but this distribution is generally unknown for non-Markovian spreading on networks. Here we determine this distribution by mapping non-Markovian SIR dynamics to an effective Markovian description. We show that arbitrary infection and recovery time statistics can be incorporated through a single edge transmissibility, yielding an effective Markovian process that reproduces the full outbreak-size statistics. For weakly heterogeneous networks, the reduction yields a universal well-mixed semiclassical theory governed by the bond-percolation reproductive number. Outbreak statistics across diverse waiting-time distributions and topologies collapse onto one predictive curve. For highly heterogeneous and empirical networks, the corresponding effective Markovian dynamics on the network captures the complete distribution. Our results provide a direct route from measured waiting-time distributions to quantitative predictions of network-level extreme-outbreak risk.
In recent years, nonlinear dynamics derived from kinetic theory have gained attention in the context of sampling configurations of spin systems such as the Ising model. We focus on nonlinear dynamics for the hard-core model, a canonical spin system with hard constraints that specifies a distribution over independent sets in a graph, weighted by their sizes. We explore two distinct types of nonlinear dynamics: the mean-field dynamics, which preserves the density (or average size) of independent sets, and the single-site dynamics, which preserves the marginal vector (i.e., the occupancy probabilities of the vertices). These dynamics are natural stochastic processes for sampling from the hard-core model with a specified density or marginal vector, respectively, both of which are canonical instances of maximum entropy distributions that have been studied in various contexts. In contrast to linear Markov chains, there is a significant lack of a fundamental theoretical framework for nonlinear dynamics. We develop foundational theoretical tools for analyzing nonlinear dynamics within the context of the hard-core model. We establish almost linear convergence of both the mean-field and single-site dynamics at sufficiently low density through novel coupling arguments. We also establish exponential decay of relative entropy for the mean-field dynamics all the way up to the critical density. Additionally, we design new algorithms for sampling from the hard-core distribution with either a specified density or a specified marginal vector. These algorithms are based on a related linear Markov chain, called the particle-system dynamics and inspired by the so-called Kac's program, that approximates the associated nonlinear dynamics. As we demonstrate in the paper, they are comparable in time complexity, but simpler to implement, than traditional approaches based on learning parameter values.
Mehrad Abbaszadeh Minab, Pietro Caputo, Zongchen Chen et al.· 0 citations