Limited Path Percolation in Complex Networks
Abstract: Does it make sense to go to work if a storm increases my commute to half a day to go and the other half to come back? Classical percolation theory, only concerned with whether a path exists from origin to destination after a portion of the network fails, would answer in the affirmative because it neglects the ``efficiency'' aspect of this communication. We propose a new and general model, Limited Path Percolation (LPP), which considers such efficiency effects by restricting the allowed paths after some network failures to those with a limited relative length increase (a limited percentage) with respect to the original paths. The percentage limit is dictated by the specifics of the problem. This model leads to a new and important set of analytical results for the largest ``communicating'' cluster which are different from those of regular percolation, as well as a new (larger) percolation threshold. These results are critical for problems such as disease propagation, data transfer on communication networks, and transportation, where short paths are most relevant.