title: Stability of shortest paths in complex networks with random edge weights.
abstract: We study shortest paths and spanning trees of complex networks with random edge weights. Edges which do not belong to the spanning tree are inactive in a transport process within the network. The introduction of quenched disorder modifies the spanning tree such that some edges are activated and the network diameter is increased. With analytic random-walk mappings and numerical analysis, we find that the spanning tree is unstable to the introduction of disorder and displays a phase-transitionlike behavior at zero disorder strength epsilon =0. In the infinite network-size limit (N--> infinity ), we obtain a continuous transition with the density of activated edges Phi growing like Phi approximately epsilon (1) and with the diameter-expansion coefficient Upsilon growing like Upsilon approximately epsilon (2) in the regular network, and first-order transitions with discontinuous jumps in Phi and Upsilon at epsilon=0 for the small-world (SW) network and the Barabási-Albert scale-free (SF) network. The asymptotic scaling behavior sets in when N>>N(c), where the crossover size scales as N(c) approximately epsilon (-2) for the regular network, N(c) approximately exp(alpha epsilon (-2)) for the SW network, and N(c) approximately exp(alpha|ln epsilon | epsilon (-2)) for the SF network. In a transient regime with N<<N(c), there is an infinite-order transition with Phi approximately Upsilon approximately exp[-alpha/(epsilon (2)ln N)] for the SW network and approximately exp[-alpha/(epsilon (2)ln N/ln ln N)] for the SF network. It shows that the transport pattern is practically most stable in the SF network.
authors.affiliation: Theoretische Physik, Universität des Saarlandes, 66041 Saarbrücken, Germany.
authors.forename: Jae Dong
authors.initials: JD
authors.lastname: Noh
authors.forename: Heiko
authors.initials: H
authors.lastname: Rieger