Transport in Weighted Networks: Partition into Superhighways and Roads

Zhenhua Wu, Lidia A. Braunstein, Shlomo Havlin, and H. Eugene Stanley

Phys. Rev. Lett. 96, 148702 – Published 13 April 2006

Abstract

Transport in weighted networks is dominated by the minimum spanning tree (MST), the tree connecting all nodes with the minimum total weight. We find that the MST can be partitioned into two distinct components, having significantly different transport properties, characterized by centrality—the number of times a node (or link) is used by transport paths. One component, superhighways, is the infinite incipient percolation cluster, for which we find that nodes (or links) with high centrality dominate. For the other component, roads, which includes the remaining nodes, low centrality nodes dominate. We find also that the distribution of the centrality for the infinite incipient percolation cluster satisfies a power law, with an exponent smaller than that for the entire MST. The significance of this finding is that one can improve significantly the global transport by improving a tiny fraction of the network, the superhighways.

Received 21 November 2005

DOI:https://doi.org/10.1103/PhysRevLett.96.148702

Authors & Affiliations

Zhenhua Wu¹, Lidia A. Braunstein^2,1, Shlomo Havlin³, and H. Eugene Stanley¹

¹Center for Polymer Studies, Boston University, Boston, Massachusetts 02215, USA
²Departamento de Física, Facultad de Ciencias Exactas y Naturales, Universidad Nacional de Mar del Plata, Funes 3350, 7600 Mar del Plata, Argentina
³Minerva Center of Department of Physics, Bar-Ilan University, Ramat Gan, Israel

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 96, Iss. 14 — 14 April 2006

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
The PDF of the centrality of nodes for (a) an ER graph with $⟨ k ⟩ = 4$ , (b) a SF with $λ = 4.5$ , (c) a SF with $λ = 3.5$ , and (d) a $90 \times 90$ square lattice. For ER and SF $N = 8192$ , and for the square lattice $N = 8100$ . We analyze $10^{4}$ realizations. For each graph, the solid circles show $P_{IIC} (C)$ ; the unfilled circles show $P_{MST} (C)$ .Reuse & Permissions
Figure 2
The normalized PDF for superhighway and roads of $⟨ C ⟩$ , the $C$ averaged over all nodes in one realization. (a) An ER network, (b) a SF network with $λ = 4.5$ , (c) a SF network with $λ = 3.5$ , and (d) a square lattice network. To make each histogram, we analyze 1000 network configurations.Reuse & Permissions
Figure 3
Schematic graph of the network of connected superhighways (heavy lines) inside the MST (shaded area). A, B, and C are examples of possible entry and exit nodes, which connect to the network of superhighways by “roads” (thin lines). The middle size lines indicate other percolation clusters with much a smaller size compared to the IIC.Reuse & Permissions
Figure 4
The average fraction $⟨ f ⟩$ of pairs using the SHW, as a function of $ℓ_{MST}$ , the distance on the MST. (a) An ER graph with $⟨ k ⟩ = 4$ , (b) a SF with $λ = 4.5$ , (c) a SF with $λ = 3.5$ , and (d) a square lattice. For ER and SF: (○) $N = 1024$ and (□) $N = 2048$ with $10^{4}$ realizations. For a square lattice: (○) $N = 1024$ and (□) $N = 2500$ with $10^{3}$ realizations. The $x$ axis is rescaled by $N^{ν_{opt}}$ , where $ν_{opt} = 1 / 3$ for ER and for SF with $λ > 4$ , and $ν_{opt} = (λ - 3) / (λ - 1)$ for SF networks with $3 < λ < 4$ [9]. For the $L \times L$ square lattice, $ℓ_{MST} \sim L^{d_{opt}}$ , and since $L^{2} = N$ , $ν_{opt} = d_{opt} / 2 \approx 0.61$ [7, 8].Reuse & Permissions
Figure 5
(a) The average usage $⟨ u ⟩ \equiv ⟨ ℓ_{IIC} / ℓ_{MST} ⟩$ for different networks, as a function of the number of nodes $N$ ○ (ER with $⟨ k ⟩ = 4$ ), □ (SF with $λ = 4.5$ ), ◇ (SF with $λ = 3.5$ ), △ ( $L \times L$ square lattice). The symbols (⊳) and (⊲) represent the average usage for ER with $⟨ k ⟩ = 4$ when the two largest percolation clusters and the three largest percolation clusters are taken into account, respectively. (b) The ratio between the flow using strategy I, $F_{sI}$ , and that using strategy II, $F_{sII}$ , as a function of the factor of improving conductivity or capacity. The inset is the ratio between the flow using strategy I and the flow in the original network $F_{0}$ . The data are all for ER networks with $N = 2048$ , $⟨ k ⟩ = 4$ , and $n = 50$ (○), $n = 250$ (◇), and $n = 500$ (□). The unfilled symbols are for current flow and the solid symbols are for maximum flow.Reuse & Permissions

Physical Review Letters