Weak disorder in the stochastic mean-field model of distance. II. (English) Zbl 1279.60018

The complete graph is considered where each edge carries an exponentially distributed weight with parameter equal to 1. Assume that the complete graph has \(n\) vertices that are labelled with the numbers from 1 to \(n\) and consider two arbitrary vertices; without loss of generality suppose that these are 1 and \(n\). Let \(\mathcal{P}\) be a path between vertices 1 and \(n\) and consider the weight of \(\mathcal{P}\) that is defined as \(w (\mathcal{P}) = \sum_{e \in \mathcal{P}} E_e^{-s}\), where \(E_e\) is the weight of the edge \(e\) and \(s>0\). Note that when \(s \rightarrow \infty\), the weight is in fact the minimum edge weight. The parameters that are considered are the weight of an optimal path as well as its number of edges. The main result states that for all positive values of \(s\) except for a countably infinite set, which is explicitely described, the number of edges is concentrated to a unique value, whereas the weight of an optimal path, when rescaled appropriatelly, follows, asymptotically as \(n\) grows, the Gumbel distribution. When \(s\) belongs to the exceptional set, the authors also determine the asymptotic distributions of these random variables. In particular, it is shown that the number of edges is concentrated on a set of two values, which occur with positive probability each.


60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
60K35 Interacting random processes; statistical mechanics type models; percolation theory
60F05 Central limit and other weak theorems
Full Text: DOI arXiv Euclid


[1] Aldous, D. and Steele, J.M. (2004). The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures. Encyclopaedia Math. Sci. 110 1-72. Berlin: Springer. · Zbl 1037.60008
[2] Aldous, D.J. (2001). The \(\zeta(2)\) limit in the random assignment problem. Random Structures Algorithms 18 381-418. · Zbl 0993.60018
[3] Aldous, D.J. (2010). More uses of exchangeability: Representations of complex random structures. In Probability and Mathematical Genetics. London Mathematical Society Lecture Note Series 378 35-63. Cambridge: Cambridge Univ. Press. · Zbl 1213.60068
[4] Aldous, D.J., McDiarmid, C. and Scott, A. (2009). Uniform multicommodity flow through the complete graph with random edge-capacities. Oper. Res. Lett. 37 299-302. · Zbl 1227.05158
[5] Barbour, A.D., Holst, L. and Janson, S. (1992). Poisson Approximation. Oxford Studies in Probability 2 . New York: The Clarendon Press Oxford Univ. Press. Oxford Science Publications. · Zbl 0746.60002
[6] Bhamidi, S. and van der Hofstad, R. (2012). Weak disorder asymptotics in the stochastic mean-field model of distance. Ann. Appl. Probab. 22 29-69. · Zbl 1248.60012
[7] Bhamidi, S., van der Hofstad, R. and Hooghiemstra, G. (2010). First passage percolation on random graphs with finite mean degrees. Ann. Appl. Probab. 20 1907-1965. · Zbl 1213.60157
[8] Braunstein, L.A., Buldyrev, S.V., Cohen, R., Havlin, S. and Stanley, H.E. (2003). Optimal paths in disordered complex networks. Phys. Rev. Lett. 91 168701. · Zbl 1027.05084
[9] Braunstein, L.A., Wu, Z., Chen, Y., Buldyrev, S.V., Kalisky, T., Sreenivasan, S., Cohen, R., López, E., Havlin, S. and Stanley, H.E. (2007). Optimal path and minimal spanning trees in random weighted networks. Internat. J. Bifur. Chaos Appl. Sci. Engrg. 17 2215-2255. · Zbl 1141.05336
[10] Frieze, A.M. (1985). On the value of a random minimum spanning tree problem. Discrete Appl. Math. 10 47-56. · Zbl 0578.05015
[11] Grimmett, G. and Kesten, H. (1984). Random electrical networks on complete graphs. J. London Math. Soc. (2) 30 171-192. · Zbl 0514.60097
[12] Havlin, S., Braunstein, L.A., Buldyrev, S.V., Cohen, R., Kalisky, T., Sreenivasan, S. and Stanley, H.E. (2005). Optimal path in random networks with disorder: A mini review. Phys. A 346 82-92.
[13] Howard, C.D. (2004). Models of first-passage percolation. In Probability on Discrete Structures. Encyclopaedia Math. Sci. 110 125-173. Berlin: Springer. · Zbl 1206.82048
[14] Janson, S. (1999). One, two and three times \(\log n/n\) for paths in a complete graph with random weights. Combin. Probab. Comput. 8 347-361. · Zbl 0934.05115
[15] Kesten, H. (1986). Aspects of first passage percolation. In École D’été de Probabilités de Saint-Flour , XIV- 1984. Lecture Notes in Math. 1180 125-264. Berlin: Springer. · Zbl 0602.60098
[16] Smythe, R.T. and Wierman, J.C. (1978). First-passage Percolation on the Square Lattice. Lecture Notes in Math. 671 . Berlin: Springer. · Zbl 0379.60001
[17] Sreenivasan, S., Kalisky, T., Braunstein, L.A., Buldyrev, S.V., Havlin, S. and Stanley, H.E. (2004). Effect of disorder strength on optimal paths in complex networks. Phys. Rev. E 70 46133.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.