Spectral Bounds in Random Graphs Applied to Spreading Phenomena and\n Percolation

2016/03/25 by Rémi Lemonnier, Lemonnier, Rémi, Kevin Scaman +3
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1603.07970

openalex publication_date 2016/03/25 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28

Abstract

In this paper, we derive nonasymptotic theoretical bounds for the influence\nin random graphs that depend on the spectral radius of a particular matrix,\ncalled the Hazard matrix. We also show that these results are generic and valid\nfor a large class of random graphs displaying correlation at a local scale,\ncalled the LPC random graphs. In particular, they lead to tight and novel\nbounds in percolation, epidemiology and information cascades. The main result\nof the paper states that the influence in the sub-critical regime for LPC\nrandom graphs is at most of the order of O(\√(n)) where n is the size of\nthe network, and of O(n^2/3) in the critical regime, where the epidemic\nthresholds are driven by the size of the spectral radius of the Hazard matrix\nwith respect to 1. As a corollary, it is also shown that such bounds hold for\nthe size of the giant component in inhomogeneous percolation, the SIR model in\nepidemiology, as well as for the long-term influence of a node in the\nIndependent Cascade Model.\n

Related

• Tight Bounds for Influence in Diffusion Networks and Application to Bond Percolation and Epidemiology
• Asymptotics of the spectral radius for directed Chung-Lu random graphs\n with community structure
• Percolation on random graphs
• Epidemics on critical random graphs with heavy-tailed degree distribution
• Bounding basic characteristics of spatial epidemics with a new percolation model