Heterogeneous micro-structure of percolation in sparse networks

Reimer Kühn, Tim Rogers

Research output: Contribution to journalLetterpeer-review

17 Citations (Scopus)
127 Downloads (Pure)

Abstract

We examine the heterogeneous responses of individual nodes in sparse networks to the random removal of a fraction of edges. Using the message-passing formulation of percolation, we discover considerable variation across the network in the probability of a particular node to remain part of the giant component, and in the expected size of small clusters containing that node. In the vicinity of the percolation threshold, weakly non-linear analysis reveals that node-to-node heterogeneity is captured by the recently introduced notion of non-backtracking centrality. We supplement these results for fixed finite networks by a population dynamics approach to analyse random graph models in the infinite system size limit, also providing closed-form approximations for the large mean degree limit of Erdos-Rényi random graphs. Interpreted in terms of the application of percolation to real-world processes, our results shed light on the heterogeneous exposure of different nodes to cascading failures, epidemic spread, and information flow.

Original languageEnglish
Article number68003
JournalEUROPHYSICS LETTERS
Volume118
Issue number6
Early online date28 Aug 2017
DOIs
Publication statusPublished - 2017

Fingerprint

Dive into the research topics of 'Heterogeneous micro-structure of percolation in sparse networks'. Together they form a unique fingerprint.

Cite this