Friday, February 16, 2017, 3pm
Location: Planetary Hall Room 212


Eduardo López
Department of Computational and Data Sciences
George Mason University

Limited Path Percolation

Abstract

We propose a new percolation model in which reachability (a generalization of connectivity) between any pair of nodes is defined on the basis of the relative increase in distance between nodes before and after percolation removal or some other path-lengthening process. Reachability is well-justified for real-world networks where, contrary to microscopic systems, the ability to explore all possible paths of any length between nodes is not achievable. If path lengthening exceeds an externally imposed fraction tau, which reflects the specifics of the problem, node pairs are no longer reachable. This concept induces a new form of phase transition called Limited Path Percolation (LPP). We find that LPP induces in many cases first-order phase transitions in contrast to percolation, which is second order. Also, LPP predicts that networks are more fragile than what is suggested by conventional percolation models, where effectively tau is considered infinite (any path length increase is acceptable). However, very heavy-tailed power law distributions of connectivity are generally robust to the introduction of the reachability concept and behave as in conventional percolation.