We study percolation on networks, which is 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 demonstrate how the resulting
equations can be used to calculate, among other things, the size of the
percolating cluster and the average cluster size. The calculations are exact
for sparse networks when the number of short loops in the network is small, but
even on networks with many short loops we find them to be highly accurate when
compared with direct numerical simulations. By considering the fixed points of
the message passing process, we also show that the percolation threshold on a
network with few loops is given by the inverse of the leading eigenvalue of the
so-called non-backtracking matrix.
%0 Journal Article
%1 Karrer2014Percolation
%A Karrer, Brian
%A Newman, M. . E. . J.
%A Zdeborová, Lenka
%D 2014
%J Physical Review Letters
%K message-passing, percolation
%N 20
%R 10.1103/PhysRevLett.113.208702
%T Percolation on Sparse Networks
%U http://dx.doi.org/10.1103/PhysRevLett.113.208702
%V 113
%X We study percolation on networks, which is 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 demonstrate how the resulting
equations can be used to calculate, among other things, the size of the
percolating cluster and the average cluster size. The calculations are exact
for sparse networks when the number of short loops in the network is small, but
even on networks with many short loops we find them to be highly accurate when
compared with direct numerical simulations. By considering the fixed points of
the message passing process, we also show that the percolation threshold on a
network with few loops is given by the inverse of the leading eigenvalue of the
so-called non-backtracking matrix.
@article{Karrer2014Percolation,
abstract = {{We study percolation on networks, which is 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 demonstrate how the resulting
equations can be used to calculate, among other things, the size of the
percolating cluster and the average cluster size. The calculations are exact
for sparse networks when the number of short loops in the network is small, but
even on networks with many short loops we find them to be highly accurate when
compared with direct numerical simulations. By considering the fixed points of
the message passing process, we also show that the percolation threshold on a
network with few loops is given by the inverse of the leading eigenvalue of the
so-called non-backtracking matrix.}},
added-at = {2019-06-10T14:53:09.000+0200},
archiveprefix = {arXiv},
author = {Karrer, Brian and Newman, M. . E. . J. and Zdeborov\'{a}, Lenka},
biburl = {https://www.bibsonomy.org/bibtex/2379ca3e023c19bb2c4f2cd28baa78c23/nonancourt},
citeulike-article-id = {13159338},
citeulike-linkout-0 = {http://dx.doi.org/10.1103/PhysRevLett.113.208702},
citeulike-linkout-1 = {http://arxiv.org/abs/1405.0483},
citeulike-linkout-2 = {http://arxiv.org/pdf/1405.0483},
day = 12,
doi = {10.1103/PhysRevLett.113.208702},
eprint = {1405.0483},
interhash = {5ba97e48ad3e73ff9c1d0715b6792ba0},
intrahash = {379ca3e023c19bb2c4f2cd28baa78c23},
issn = {1079-7114},
journal = {Physical Review Letters},
keywords = {message-passing, percolation},
month = nov,
number = 20,
posted-at = {2014-09-12 18:13:33},
priority = {2},
timestamp = {2019-06-10T14:53:09.000+0200},
title = {{Percolation on Sparse Networks}},
url = {http://dx.doi.org/10.1103/PhysRevLett.113.208702},
volume = 113,
year = 2014
}