The effects of initial conditions on the accuracy of mean-field approximations of Markov processes on large random graphs

Pierfrancesco Dionigi, Dániel Keliger · 2025

Read The effects of initial conditions on the accuracy of mean-field approximations of Markov processes on large random graphs by Pierfrancesco Dionigi, Dániel Keliger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-12872.txt.

Introduction

Epidemics on networks are often forecast with mean-field shortcuts, and the starting state quietly governs how wrong those shortcuts run. Pierfrancesco Dionigi and Dániel Keliger quantify that effect in this 2025 paper. Their processes cover standard infection models on large random graphs. The approximation in focus tracks each node's state while averaging its neighbors.

Classic theory on complete graphs bounds the error by network size. On random graphs the error instead hinges on the average degree and the initial conditions. Generic starts give the worst case; special starts do better. Forecasts for sparse real networks inherit this sensitivity. Knowing the error's true drivers tells modelers when to trust the shortcut.

Catalog record

CREATORPierfrancesco Dionigi, Dániel Keliger
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-12872

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The effects of initial conditions on the accuracy of mean-field approximations of Markov processes on large random graphs Pierfrancesco Dionigi, Dániel Keliger Abstract We study the evolution of a general class of stochastic processes (containing, e.g. SIS and SIR models) on large random networks, focusing on a particular general class of random graph models. To approximate the expected dynamics of these processes, we employ a mean-field technique known as the N-Intertwined Mean-Field Approximation (NIMFA) [ 26 ] . Our primary goal is to quantify the impact of the randomness in the network topology on the accuracy of such approximations. While classical work by Kurtz [ 18 ] established strong approximation results for density-dependent Markov chains using mean-field on the complete-graph of order N N , yielding error bounds of order 1 N \frac{1}{\sqrt{N}} , we demonstrate that in the context of NIMFA on random graphs, the error admits a refined characterization depending on initial conditions. Specifically, for generic initial conditions, the worst case error is of order 1 d \frac{1}{\sqrt{d}} , where d d is the expected average degree of the graph. This result highlights how network sparsity contributes an additional source of variability not captured by classical mean-field approaches. Furthermore, when the initial conditions are taken to be fairly homogeneous, we show that the error term is of order 1 N + 1 d \frac{1}{\sqrt{N}}+\frac{1}{d} , where N N is the number of nodes, underscoring the intricate role of the choice of initial conditions in the error bounds. Our analysis connects with recent interest in quantifying the role of graph heterogeneity in epidemic thresholds and dynamics [ 8 , 21 , 12 ] . Keywords: Stochastic Processes, Markov Chains, Mean-field Approximation, NIMFA, Random Graphs. AMS2020 subject classification: 60K35, 60K37, 60J27, 82C22, 05C80, 91D30 1 Introduction The study of stochastic processes on networks is central to understand the spread of epidemics, information, and behaviors in complex systems. This in turn prompted in the recent years a prolific research aimed to understand the underlying geometrical structure governing these complex systems and how it influences dynamics. This was one of the main drives that triggered the boom of network science during the last 30 years: networks indeed represent a pivotal tool in the study of systems constructed by complex interactions. The variety of areas where networks have been adopted is huge; their application in biology, economics, sociology, industrial applications and many more different areas required the birth of a very diversified range of networks models (or ensembles in physics literature) that are able to capture specific features of the real world system they try to represent [ 20 , 4 , 10 , 22 ] . Together with the classic Erdős-Rényi random graph is worth to mention, Chung-Lu random graphs, Inhomogeneous random graphs, Stochastic Block model, Preferential Attachment models and Maximal Entropy random graphs [ 6 , 11 , 1 , 3 , 24 ] . A lot of research focused as well on how the main properties of these graph models might affect the dynamical behavior, such as spectral properties, degree fluctuations, connectivity properties and many more [ 19 , 23 , 9 , 13 ] . On the other hand, there is a complete opposite driving force in the study of stochastic processes: for most of them the exact solution of the related master equation is unfeasible. Furthermore, most of the times our ability to solve (or at least give an attempt) these problems heavily depends on the set of possible initial conditions, leading to leading to three layers of randomness. Therefore, over the years, different approaches relying either on assumptions that lead to simplifications or on approximations were attempted. Most of the times these approaches rely on averaging the noise provided by the background randomness of the graph, or try to plug in independence conditions in order for some equations to decouple, provided that the initial conditions respect certain conditions; collectively these approaches are called mean-field models. These approximations often reduce the complexity of the system by replacing stochastic interactions with deterministic equations that describe average behavior. Therefore, each of these approaches, no matter how sophisticated, introduce approximations, and, as with every approximation, we pay an an error in the accuracy of our model. Given the richness in the choice of the underlying graph model, in the possible initial conditions, and in the ways in which the processes can be approximated, is of central interest understanding the error we pay for different choices and different approximations. This translates into trying to figure out general upper and lower bounds that assure how much this error can be and how it can depend from the possible choices of graph ensembles, initial conditions, and process’ dynamics. This question relates closely to the classical work by Kurtz [ 18 ] , who developed strong approximation theorems for density-dependent Markov chains. In his framework, the network structure is implicitly averaged out, effectively modeling interactions as occurring on a weighted complete graph. Under this assumption, he derived an error bound of order \frac{1}{\sqrt{N}} , where N is the size of the system. Despite penalizing the network geometry, the seminal idea of Kurtz has been for long time the main result in this area. Attempts have been made to indeed plug in a more refined account for the network geometry. For example, in [ 15 ] , the authors show how to implement an Heterogeneous Mean-Field Approximation(HMFA) is effective to take into account the annealed version of the underlying random graph model, i.e. the average adjacency matrix. In this paper, we investigate the performance of NIMFA, the N-Intertwined Mean-Field Approximation , when applied to stochastic processes on a fairly general class of random graphs that are able to model real world communities. This technique has gained attention due to its tractability and improved accuracy over naive homogeneous and heterogeneous mean-field models, particularly when applied to heterogeneous networks, which are not necessarily dense, but have large degrees [ 26 , 2 , 25 ] . Our focus is on understanding how the randomness of the underlying network model influences the accuracy of this approximation, particularly as the graph size and average degree vary. In contrast with the work of Kurtz, the NIMFA approach retains the individual network structure and thus introduces an additional source of randomness due to the graph itself, i.e. the graphs can be considered quenced without any necessary averaging procedure ( annealing ). Our main contribution is to rigorously quantify this additional randomness source and its influence on the error term. Our work relies on the results of [ 17 ] . There the authors show a tight bound of order \frac{1}{\sqrt{N}}+\frac{1}{d} where d is the average degree of the quenched graph. In our work (Theorems 3 and 4 ), in the special case when the initial conditions of the process are fairly homogenous, we show that the approximation error for the annealed NIMFA , i.e. the HRF obtained by annealing the graph model after applying the NIMFA, is of the same order, \frac{1}{\sqrt{N}}+\frac{1}{d} , where d is the expected average degree of the network. This result demonstrates that in sparse networks, where d\ll\sqrt{N} , the randomness of the graph has a non-negligible effects

Read the complete text