Spectral bounds in random graphs applied to spreading phenomena and percolation. (26th July 2018)

• Record Type: Journal Article
• Authors: Lemonnier, Rémi; Scaman, Kevin; Vayatis, Nicolas
• Is Part Of: Advances in applied probability. Volume 50:Number 2(2018)
• Page Start: 480
• Page End: 503
• Publication Date: 2018-07-26
• Subjects: Random graph, -- local positive correlation, -- hazard matrix, -- percolation, -- epidemiology, -- information cascade; Primary 05C80, -- Secondary 60K35, -- 92D30, -- 60J60; Probabilities -- Periodicals; Stochastic models -- Periodicals; Electronic journals; Periodicals; 519.2
• DOI: 10.1017/apr.2018.22
• Languages: English
• ISSNs: 0001-8678

Abstract

Abstract: In this paper we derive nonasymptotic upper bounds for the size of reachable sets in random graphs. These bounds are subject to a phase transition phenomenon triggered by the spectral radius of the hazard matrix, a reweighted version of the adjacency matrix. Such bounds are valid for a large class of random graphs, called local positive correlation (LPC) random graphs, displaying local positive correlation. In particular, in our main result we state that the size of reachable sets in the subcritical regime for LPC random graphs is at most of order O (√ n ), where n is the size of the network, and of order O ( n 2/3 ) in the critical regime, where the epidemic thresholds are driven by the size of the spectral radius of the hazard matrix with respect to 1. As a corollary, we also show that such bounds hold for the size of the giant component in inhomogeneous percolation, the SIR model in epidemiology, as well as for the long-term influence of a node in the independent cascade model.