Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-16T17:44:05.950Z Has data issue: false hasContentIssue false

Spectral bounds in random graphs applied to spreading phenomena and percolation

Published online by Cambridge University Press:  26 July 2018

Rémi Lemonnier*
Affiliation:
École Normale Supérieure Paris-Saclay
Kevin Scaman*
Affiliation:
École Normale Supérieure Paris-Saclay
Nicolas Vayatis*
Affiliation:
École Normale Supérieure Paris-Saclay
*
* Postal address: 55 rue de Rome, 75008 Paris, France. Email address: remi@scibids.com
** Postal address: 18 Quai du Point du Jour, 92100 Boulogne-Billancourt, France. Email address: kevin.scaman@huawei.com
*** Postal address: Centre de Mathématiques et de Leurs Applications (CMLA), École Normale Supérieure Paris-Saclay, 61 Avenue President Wilson, F-94230 Cachan, France. Email address: vayatis@cmla.ens-cachan.fr
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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(n2/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.

Information

Type
Original Article
Copyright
Copyright © Applied Probability Trust 2018