# Optimal paths in disordered complex networks.

@article{Braunstein2003OptimalPI, title={Optimal paths in disordered complex networks.}, author={Lidia A. Braunstein and Sergey V. Buldyrev and Reuven Cohen and Shlomo Havlin and Harry Eugene Stanley}, journal={Physical review letters}, year={2003}, volume={91 16}, pages={ 168701 } }

We study the optimal distance in networks, l(opt), defined as the length of the path minimizing the total weight, in the presence of disorder. Disorder is introduced by assigning random weights to the links or nodes. For strong disorder, where the maximal weight along the path dominates the sum, we find that l(opt) approximately N(1/3) in both Erdos-Rényi (ER) and Watts-Strogatz (WS) networks. For scale-free (SF) networks, with degree distribution P(k) approximately k(-lambda), we find that l… Expand

#### 152 Citations

Optimal Path and Minimal Spanning Trees in Random Weighted Networks

- Mathematics, Physics
- Int. J. Bifurc. Chaos
- 2007

It is shown that the minimum spanning tree (MST) in the strong disorder limit is composed of percolation clusters, which the authors regard as "super-nodes", interconnected by a scale-free tree. Expand

Effect of disorder strength on optimal paths in complex networks.

- Mathematics, Computer Science
- Physical review. E, Statistical, nonlinear, and soft matter physics
- 2004

In order to study the transition between the strong and weak disorder regimes in the scaling properties of the average optimal path l(opt), a measure which indicates how close or far the disordered network is from the limit of strong disorder is proposed. Expand

Optimal path in random networks with disorder: A mini review

- Mathematics
- 2005

We review the analysis of the length of the optimal path lopt in random networks with disorder (i.e., random weights on the links). In the case of strong disorder, in which the maximal weight along… Expand

Scaling of optimal-path-lengths distribution in complex networks.

- Mathematics, Medicine
- Physical review. E, Statistical, nonlinear, and soft matter physics
- 2005

It is suggested, in an analogy with the average length of the optimal path, that the distribution of optimal path lengths has a universal form that is controlled by the expression (1/p(c))) (l(infinity)/a), where l(Infinity) is the optimal course length in strong disorder (a --> infinity) and p(c), the percolation threshold. Expand

Load distribution in weighted complex networks.

- Mathematics, Medicine
- Physical review. E, Statistical, nonlinear, and soft matter physics
- 2005

The effect of disorder is measured by the correlation coefficient between vertex degree and load, finding that it is larger for ER networks than for SF networks. Expand

Limited path percolation in complex networks.

- Computer Science, Medicine
- Physical review letters
- 2007

For a large class of networks, this work finds analytically and numerically a new percolation transition at p(c), where kappa(0) [triple bond] / and k is the node degree, above p( c), order N nodes can communicate within the limited path length al(ij), while below p(C), N(delta) (delta<1) nodes can communication. Expand

The Optimal Pathin an Erdős-Rényi Random Graph

- Mathematics, Physics
- 2004

We study the optimal distanceopt in random networks in the presence of disorder implemented by assigning random weights to the links. The optimal distance between two nodes is the length of the path… Expand

Transport and percolation theory in weighted networks.

- Mathematics, Physics
- Physical review. E, Statistical, nonlinear, and soft matter physics
- 2007

The distribution P(sigma) of the equivalent conductance sigma for Erdös-Rényi (ER) and scale-free (SF) weighted resistor networks with N nodes is studied and an iterative fast algorithm is provided to obtain P( sigma) and compared with the traditional algorithm of solving Kirchhoff equations. Expand

Optimal paths in complex networks with correlated weights: the worldwide airport network.

- Mathematics, Medicine
- Physical review. E, Statistical, nonlinear, and soft matter physics
- 2006

An analytical method is proposed to study percolation phenomena on networks with this kind of correlation, and the numerical results suggest that for scale-free networks with alpha< 0 , the percolations threshold p(c) is finite for lambda >3, which belongs to the same universality class as alpha=0 . Expand

Statistical Properties of Optimal Paths

- 2006

We study the statistical properties of optimal paths in weighted complex networks with general distribution of weights. We find a general criterion for the strength of disorder and show the relation… Expand

#### References

SHOWING 1-10 OF 56 REFERENCES

Scale-free networks are ultrasmall.

- Physics, Medicine
- Physical review letters
- 2003

It is shown, using analytical arguments, that scale-free networks with 2<lambda<3 have a much smaller diameter, behaving as d approximately ln(ln(N), which is the lowest possible diameter. Expand

Universality classes for self-avoiding walks in a strongly disordered system.

- Mathematics, Medicine
- Physical review. E, Statistical, nonlinear, and soft matter physics
- 2002

The behavior of self-avoiding walks (SAWs) on square and cubic lattices in the presence of strong disorder is studied to find the optimal SAW of fixed length N and fixed origin that minimizes the sum of the energies of the visited sites (or bonds). Expand

FIRST-PASSAGE PERCOLATION ON THE RANDOM GRAPH

- Mathematics
- Probability in the Engineering and Informational Sciences
- 2001

We study first-passage percolation on the random graph Gp(N) with exponentially distributed weights on the links. For the special case of the complete graph, this problem can be described in terms of… Expand

Small-World Networks: Evidence for a Crossover Picture

- Physics
- 1999

Watts and Strogatz [Nature (London) 393, 440 (1998)] have recently introduced a model for disordered networks and reported that, even for very small values of the disorder $p$ in the links, the… Expand

Resilience of the internet to random breakdowns

- Physics, Medicine
- Physical review letters
- 2000

This work shows analytically and numerically that for alpha</=3 the transition never takes place, unless the network is finite, and finds that the physical structure of the Internet is impressively robust, with p(c)>0.99. Expand

Minimum spanning trees on random networks.

- Mathematics, Physics
- Physical review letters
- 2001

The relationship to invasion percolation, to the directed polymer in a random media, to uniform spanning trees, and also the implications for the broader issue of universality in disordered systems are discussed. Expand

Statistical mechanics of complex networks

- Computer Science, Physics
- ArXiv
- 2001

A simple model based on these two principles was able to reproduce the power-law degree distribution of real networks, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network. Expand

Invasion percolation and Eden growth: Geometry and universality.

- Physics, Medicine
- Physical review letters
- 1996

The mapping of optimal paths in the strong disorder limit to the strands of invasion percolation clusters is shown to lead to a new universal property of these clusters. We suggest that the… Expand

Renormalization Group Analysis of the Small-World Network Model

- Physics, Mathematics
- 1999

We study the small-world network model, which mimics the transition between regular-lattice and random-lattice behavior in social networks of increasing size. We contend that the model displays a… Expand

The Size of the Giant Component of a Random Graph with a Given Degree Sequence

- Mathematics, Computer Science
- Comb. Probab. Comput.
- 1998

The size of the giant component in the former case, and the structure of the graph formed by deleting that component is analyzed, which is basically that of a random graph with n′=n−∣C∣ vertices, and with λ′in′ of them of degree i. Expand