General and exact approach to percolation on random graphs
Physical Review E, (Dec 7, 2015)DOI: 10.1103/PhysRevE.92.062807
Abstract
We present a comprehensive and versatile theoretical framework to study site
and bond percolation on clustered and correlated random graphs. Our
contribution can be summarized in three main points. (i) We introduce a set of
iterative equations that solve the exact distribution of the size and
composition of components in finite size quenched or random multitype graphs.
(ii) We define a very general random graph ensemble that encompasses most of
the models published to this day, and also that permits to model structural
properties not yet included in a theoretical framework. Site and bond
percolation on this ensemble is solved exactly in the infinite size limit using
probability generating functions i.e., the percolation threshold, the size and
the composition of the giant (extensive) and small components. Several
examples and applications are also provided. (iii) Our approach can be adapted
to model interdependent graphs---whose most striking feature is the emergence
of an extensive component via a discontinuous phase transition---in an equally
general fashion. We show how a graph can successively undergo a continuous then
a discontinuous phase transition, and preliminary results suggest that
clustering increases the amplitude of the discontinuity at the transition.