Large Deviations of Non-Stochastic Interacting Particles on Sparse Random Graphs

2020/10/27 by James MacLaurin, MacLaurin, James
Biochemistry, Genetics and Molecular Biology · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Diffusion and Search Dynamics #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2010.14421

openalex publication_date 2020/10/27 · openalex created_date 2020/11/09 · openalex updated_date 2026/07/28

Abstract

This paper concerns the large deviations of a system of interacting particles on a random graph. There is no stochasticity, and the only sources of disorder are the random graph connections, and the initial condition. The average number of afferent edges on any particular vertex must diverge to infinity as N→ ∞, but can do so at an arbitrarily slow rate. These results are thus accurate for both sparse and dense random graphs. A particular application to sparse Erdos-Renyi graphs is provided. The theorem is proved by pushing forward a Large Deviation Principle for a `nested empirical measure' generated by the initial conditions to the dynamics. The nested empirical measure can be thought of as the density of the density of edge connections: the associated weak topology is more coarse than the topology generated by the graph cut norm, and thus there is a broader range of application.

Citations

• Locally interacting diffusions as space-time Markov random fields

Related

• On the large deviation rate function for marked sparse random graphs
• Large deviations for marked sparse random graphs with applications to interacting diffusions
• An alternative approach to large deviations for the almost-critical Erdős-Rényi random graph
• An introduction to large deviations for random graphs
• The large deviation principle for interacting dynamical systems on random graphs