糖心TV

Title: Limited Path Percolation in Complex Networks

Abstract:

We propose a new percolation model in which communication (connectivity) between  any pair of nodes is defined on the basis of the relative increase in distance  between nodes before and after percolation removal. This definition is well  justified for real-world networks where, contrary to microscopic systems, the  ability to explore all possible paths between nodes is not achievable. By defining two nodes as connected if their distance after percolation removal does not increase beyond a chosen factor A>1, we can study the size of the  largest "communicating cluster" after removal of a fraction of the network links or nodes. Factor A represents a percentage of length increase that is acceptable  in order for pairs of nodes to preserve communication. For a large class of  networks we find analytically a new "limited path percolation transition" which  is a function of the original network structure and A. The usual percolation definition is recovered when A is allowed to be infinite. Above the limited path  percolation transition, a "spanning communicating cluster" of linear size with  respect to the original network emerges. Between the usual percolation  threshold and the new limited path percolation threshold, the largest  communicating cluster has power-law size. Our analytical results are supported  by simulations on real and model networks. This new model is of great importance  in network design, routing algorithms, and immunization strategies, where short  paths are most relevant.