Heterogeneous micro-structure of percolation in sparse networks. (28th August 2017)

• Record Type: Journal Article
• Authors: Kühn, Reimer; Rogers, Tim
• Is Part Of: Europhysics letters. Volume 118:Number 6(2017:Jun.)
• Publication Date: 2017-08-28
• Subjects: 89.75.Hc -- 64.60.ah -- 05.70.Fh; Physics -- Periodicals; Electronic journals; 530.05
• DOI: 10.1209/0295-5075/118/68003
• Languages: English
• ISSNs: 0295-5075

Abstract

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