Stability of shortest paths in complex networks with random edge weights.

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.