Stability of shortest paths in complex networks with random edge weights

Jae Dong Noh, Heiko Rieger

Research output: Contribution to journalArticlepeer-review

47 Scopus citations


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 [formula presented] In the infinite network-size limit [formula presented] we obtain a continuous transition with the density of activated edges [formula presented] growing like [formula presented] and with the diameter-expansion coefficient [formula presented] growing like [formula presented] in the regular network, and first-order transitions with discontinuous jumps in [formula presented] and [formula presented] at [formula presented] for the small-world (SW) network and the Barabási-Albert scale-free (SF) network. The asymptotic scaling behavior sets in when [formula presented] where the crossover size scales as [formula presented] for the regular network, [formula presented] for the SW network, and [formula presented] for the SF network. In a transient regime with [formula presented] there is an infinite-order transition with [formula presented] for the SW network and [formula presented] for the SF network. It shows that the transport pattern is practically most stable in the SF network.

Original languageEnglish
Pages (from-to)8
Number of pages1
JournalPhysical Review E
Issue number6
StatePublished - 19 Dec 2002


Dive into the research topics of 'Stability of shortest paths in complex networks with random edge weights'. Together they form a unique fingerprint.

Cite this