Effect of disorder strength on optimal paths in complex networks

Phys Rev E Stat Nonlin Soft Matter Phys. 2004 Oct;70(4 Pt 2):046133. doi: 10.1103/PhysRevE.70.046133. Epub 2004 Oct 29.

Abstract

We study the transition between the strong and weak disorder regimes in the scaling properties of the average optimal path l(opt) in a disordered Erdos-Rényi (ER) random network and scale-free (SF) network. Each link i is associated with a weight tau(i) identical withexp (a r(i) ) , where r(i) is a random number taken from a uniform distribution between 0 and 1 and the parameter a controls the strength of the disorder. We find that for any finite a , there is a crossover network size N* (a) at which the transition occurs. For N<<N* (a) the scaling behavior of l(opt) is in the strong disorder regime, with l(opt) approximately N(1/3) for ER networks and for SF networks with lambda>/=4 , and l(opt) approximately N (lambda-3) (/ (lambda-1) ) for SF networks with 3<lambda<4 . For N>>N* (a) the scaling behavior is in the weak disorder regime, with l(opt) approximately ln N for ER networks and SF networks with lambda>3 . In order to study the transition we propose a measure which indicates how close or far the disordered network is from the limit of strong disorder. We propose a scaling ansatz for this measure and demonstrate its validity. We proceed to derive the scaling relation between N* (a) and a . We find that N* (a) approximately a(3) for ER networks and for SF networks with lambda>/=4 , and N* (a) approximately a (lambda-1) (/ (lambda-3) ) for SF networks with 3<lambda<4 .