Title: Percolation on sparse networks

Abstract: We study percolation on networks, which is widely used as a model of the resilience of networked systems such as the Internet to attack or failure and as a simple model of the spread of disease over human contact networks. We reformulate percolation as a message passing process and use the resulting equations to show, among other things, that for sparse networks, which includes most networks observed in the real world, the percolation threshold is given by the inverse of the leading eigenvalue of the so-called non-backtracking matrix. Like most message passing calculations, our results are exact on networks that have few small loops but, as we show, they also provide bounds on the percolation behavior of networks that do contain loops.