Heterogeneous micro-structure of percolation in sparse networks

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...

Full description

Saved in:
Bibliographic Details
Published in:Europhysics letters 2017-06, Vol.118 (6), p.68003
Main Authors: Kühn, Reimer, Rogers, Tim
Format: Article
Language:English
Subjects:
05.70.Fh
64.60.ah
89.75.Hc
Cluster analysis
Heterogeneity
Information flow
Message passing
Networks
Nodes
Nonlinear analysis
Percolation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Erd s-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.
ISSN:0295-5075
1286-4854
DOI:10.1209/0295-5075/118/68003