{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T09:11:59Z","timestamp":1772356319304,"version":"3.50.1"},"reference-count":70,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Bifurcation Chaos"],"published-print":{"date-parts":[[2007,7]]},"abstract":"<jats:p> We review results on the scaling of the optimal path length \u2113<jats:sub>opt<\/jats:sub> in random networks with weighted links or nodes. We refer to such networks as \"weighted\" or \"disordered\" networks. The optimal path is the path with minimum sum of the weights. In strong disorder, where the maximal weight along the path dominates the sum, we find that \u2113<jats:sub>opt<\/jats:sub> increases dramatically compared to the known small-world result for the minimum distance \u2113<jats:sub> min <\/jats:sub> ~ log N, where N is the number of nodes. For Erd\u0151s\u2013R\u00e9nyi (ER) networks \u2113<jats:sub> opt <\/jats:sub> ~ N<jats:sup>1\/3<\/jats:sup>, while for scale free (SF) networks, with degree distribution P(k) ~ k<jats:sup>-\u03bb<\/jats:sup>, we find that \u2113<jats:sub>opt<\/jats:sub> scales as N<jats:sup>(\u03bb - 3)\/(\u03bb - 1)<\/jats:sup> for 3 &lt; \u03bb &lt; 4 and as N<jats:sup>1\/3<\/jats:sup> for \u03bb \u2265 4. Thus, for these networks, the small-world nature is destroyed. For 2 &lt; \u03bb &lt; 3 in contrary, our numerical results suggest that \u2113<jats:sub>opt<\/jats:sub> scales as ln <jats:sup>\u03bb-1<\/jats:sup> N, representing still a small world. We also find numerically that for weak disorder \u2113<jats:sub> opt <\/jats:sub> ~ ln N for ER models as well as for SF networks. We also review the transition between the strong and weak disorder regimes in the scaling properties of \u2113<jats:sub>opt<\/jats:sub> for ER and SF networks and for a general distribution of weights \u03c4, P(\u03c4). For a weight distribution of the form P(\u03c4) = 1\/(a\u03c4) with (\u03c4<jats:sub> min <\/jats:sub> &lt; \u03c4 &lt; \u03c4<jats:sub> max <\/jats:sub>) and a = ln \u03c4<jats:sub> max <\/jats:sub>\/\u03c4<jats:sub> min <\/jats:sub>, we find that there is a crossover network size N<jats:sup>*<\/jats:sup> = N<jats:sup>*<\/jats:sup>(a) at which the transition occurs. For N \u226a N<jats:sup>*<\/jats:sup> the scaling behavior of \u2113<jats:sub>opt<\/jats:sub> is in the strong disorder regime, while for N \u226b N<jats:sup>*<\/jats:sup> the scaling behavior is in the weak disorder regime. The value of N<jats:sup>*<\/jats:sup> can be determined from the expression \u2113<jats:sub>\u221e<\/jats:sub>(N<jats:sup>*<\/jats:sup>) = ap<jats:sub>c<\/jats:sub>, where \u2113<jats:sub>\u221e<\/jats:sub> is the optimal path length in the limit of strong disorder, A \u2261 ap<jats:sub>c<\/jats:sub> \u2192 \u221e and p<jats:sub>c<\/jats:sub> is the percolation threshold of the network. We suggest that for any P(\u03c4) the distribution of optimal path lengths has a universal form which is controlled by the scaling parameter Z = \u2113<jats:sub>\u221e<\/jats:sub>\/A where [Formula: see text] plays the role of the disorder strength and \u03c4<jats:sub>c<\/jats:sub> is defined by [Formula: see text]. In case P(\u03c4) ~ 1\/(a\u03c4), the equation for A is reduced to A = ap<jats:sub>c<\/jats:sub>. The relation for A is derived analytically and supported by numerical simulations for Erd\u0151s\u2013R\u00e9nyi and scale-free graphs. We also determine which form of P(\u03c4) can lead to strong disorder A \u2192 \u221e. We then study the minimum spanning tree (MST), which is the subset of links of the network connecting all nodes of the network such that it minimizes the sum of their weights. We show that the minimum spanning tree (MST) in the strong disorder limit is composed of percolation clusters, which we regard as \"super-nodes\", interconnected by a scale-free tree. The MST is also considered to be the skeleton of the network where the main transport occurs. We furthermore show that the MST can be partitioned into two distinct components, having significantly different transport properties, characterized by centrality \u2014 number of times a node (or link) is used by transport paths. One component the superhighways, for which the nodes (or links) with high centrality dominate, corresponds to the largest cluster at the percolation threshold (incipient infinite percolation cluster) which is a subset of the MST. The other component, roads, includes the remaining nodes, low centrality nodes dominate. We find also that the distribution of the centrality for the incipient infinite percolation cluster satisfies a power law, with an exponent smaller than that for the entire MST. We demonstrate the significance identifying the superhighways by showing that one can improve significantly the global transport by improving a very small fraction of the network, the superhighways. <\/jats:p>","DOI":"10.1142\/s0218127407018361","type":"journal-article","created":{"date-parts":[[2007,9,5]],"date-time":"2007-09-05T06:23:49Z","timestamp":1188973429000},"page":"2215-2255","source":"Crossref","is-referenced-by-count":61,"title":["OPTIMAL PATH AND MINIMAL SPANNING TREES IN RANDOM WEIGHTED NETWORKS"],"prefix":"10.1142","volume":"17","author":[{"given":"LIDIA A.","family":"BRAUNSTEIN","sequence":"first","affiliation":[{"name":"Departamento de F\u00edsica, Facultad de Ciencias Exactas y Naturales, Universidad Nacional de Mar del Plata, Funes 3350, 7600 Mar del Plata, Argentina"},{"name":"Center for Polymer Studies, Boston University, Boston, MA 02215, USA"}]},{"given":"ZHENHUA","family":"WU","sequence":"additional","affiliation":[{"name":"Center for Polymer Studies, Boston University, Boston, MA 02215, USA"}]},{"given":"YIPING","family":"CHEN","sequence":"additional","affiliation":[{"name":"Center for Polymer Studies, Boston University, Boston, MA 02215, USA"}]},{"given":"SERGEY V.","family":"BULDYREV","sequence":"additional","affiliation":[{"name":"Center for Polymer Studies, Boston University, Boston, MA 02215, USA"},{"name":"Department of Physics, Yeshiva University, 500 West 185th Street Room 1112, NY 10033, USA"}]},{"given":"TOMER","family":"KALISKY","sequence":"additional","affiliation":[{"name":"Minerva Center and Department of Physics, Bar-Ilan University, 52900 Ramat-Gan, Israel"}]},{"given":"SAMEET","family":"SREENIVASAN","sequence":"additional","affiliation":[{"name":"Center for Polymer Studies, Boston University, Boston, MA 02215, USA"}]},{"given":"REUVEN","family":"COHEN","sequence":"additional","affiliation":[{"name":"Minerva Center and Department of Physics, Bar-Ilan University, 52900 Ramat-Gan, Israel"},{"name":"Department of Electrical and Computer Engineering, Boston University, Boston, MA 02215, USA"}]},{"given":"EDUARDO","family":"L\u00d3PEZ","sequence":"additional","affiliation":[{"name":"Center for Polymer Studies, Boston University, Boston, MA 02215, USA"},{"name":"Theoretical Division, Los Alamos National Laboratory, Mail Stop B258, Los Alamos, NM 87545, USA"}]},{"given":"SHLOMO","family":"HAVLIN","sequence":"additional","affiliation":[{"name":"Center for Polymer Studies, Boston University, Boston, MA 02215, USA"},{"name":"Minerva Center and Department of Physics, Bar-Ilan University, 52900 Ramat-Gan, Israel"}]},{"given":"H. EUGENE","family":"STANLEY","sequence":"additional","affiliation":[{"name":"Center for Polymer Studies, Boston University, Boston, MA 02215, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.74.47"},{"key":"rf2","volume-title":"Network Flows: Theory, Algorithms and Applications","author":"Ahuja R. K.","year":"1993"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.76.3750"},{"key":"rf4","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"Barab\u00e1si A.-L.","journal-title":"Science"},{"key":"rf5","volume-title":"Linked: The New Science of Networks","author":"Barab\u00e1si A.-L.","year":"2002"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0400087101"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.82.3180"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2005.10.009"},{"key":"rf9","volume-title":"Random Graphs","author":"Bollobas B.","year":"1985"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.68.046130"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.65.056128"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.91.168701"},{"key":"rf14","volume-title":"Nexus: Small Worlds and the Groundbreaking Theory of Networks","author":"Buchanan M.","year":"2002"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2003.08.030"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.73.036128"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-84868-1"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.85.5468"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.96.068702"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.72.2320"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.76.3754"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.85.4626"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.66.036113"},{"key":"rf24","volume-title":"Handbook of Graphs and Networks","author":"Cohen R.","year":"2002"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.90.058701"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/15\/12\/032"},{"key":"rf27","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"1990"},{"key":"rf28","volume-title":"Scaling Concepts in Polymer Physics","author":"de Gennes P.-G.","year":"1979"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.86.5076"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198515906.001.0001"},{"key":"rf31","first-page":"290","volume":"6","author":"Erd\u0151s P.","journal-title":"Publ. Math."},{"key":"rf32","first-page":"17","volume":"5","author":"Erd\u0151s P.","journal-title":"Publ. Math. Inst. Hungarian Acad. Sci."},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1016\/0378-4371(95)00321-5"},{"key":"rf35","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.87.278701"},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.017102"},{"key":"rf37","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.93.040601"},{"key":"rf38","volume-title":"The Theory of Branching Processes","author":"Harris T. E.","year":"1989"},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2004.08.053"},{"key":"rf40","doi-asserted-by":"publisher","DOI":"10.1134\/1.1753422"},{"key":"rf41","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.025102"},{"key":"rf42","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.73.035101"},{"key":"rf43","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.73.025103"},{"key":"rf45","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.046126"},{"key":"rf46","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"rf47","doi-asserted-by":"publisher","DOI":"10.1209\/epl\/i2005-10232-x"},{"key":"rf48","volume-title":"Evolution of Networks: From Biological Nets to the Internet and the WWW","author":"Mendes J. F. F.","year":"2003"},{"key":"rf49","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060204"},{"key":"rf50","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548398003526"},{"key":"rf51","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.016131"},{"key":"rf52","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.016132"},{"key":"rf53","first-page":"056110-1","volume":"68","author":"Onnela J.-P.","journal-title":"Phys. Rev. E"},{"key":"rf54","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511610905"},{"key":"rf55","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2005-00085-7"},{"key":"rf56","doi-asserted-by":"publisher","DOI":"10.1209\/epl\/i2005-10382-9"},{"key":"rf57","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.79.4060"},{"key":"rf58","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.60.R2448"},{"key":"rf59","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmb.2004.06.063"},{"key":"rf60","volume-title":"Implementing Discrete Mathematics: Combinatorics and Graph Theory With Mathematica","author":"Skiena S.","year":"1990"},{"key":"rf61","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.47.262"},{"key":"rf62","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.046133"},{"key":"rf63","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2004.08.064"},{"key":"rf64","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/10\/11\/008"},{"key":"rf65","volume-title":"Introduction to Percolation Theory","author":"Stauffer D.","year":"1994"},{"key":"rf66","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.065105"},{"key":"rf67","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.72.016121"},{"key":"rf68","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2003.08.031"},{"key":"rf69","doi-asserted-by":"publisher","DOI":"10.1017\/S026996480115206X"},{"key":"rf70","volume-title":"Six Degrees: The Science of a Connected Age","author":"Watts D. J.","year":"2003"},{"key":"rf71","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.045101"},{"key":"rf72","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.96.148702"}],"container-title":["International Journal of Bifurcation and Chaos"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218127407018361","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:00:39Z","timestamp":1565121639000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218127407018361"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7]]},"references-count":70,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2007,7]]}},"alternative-id":["10.1142\/S0218127407018361"],"URL":"https:\/\/doi.org\/10.1142\/s0218127407018361","relation":{},"ISSN":["0218-1274","1793-6551"],"issn-type":[{"value":"0218-1274","type":"print"},{"value":"1793-6551","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,7]]}}}