Description

Transport in Weighted Networks: Partition into Superhighways and Roads

Categories

Published

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Transcript

a r X i v : c o n d - m a t / 0 5 1 1 5 2 5 v 2 [ c o n d - m a t . d i s - n n ] 3 M a y 2 0 0 6
Transport in weighted networks:Partition into superhighways and roads
Zhenhua Wu,
1
Lidia A. Braunstein,
2,1
Shlomo Havlin,
3
and H. Eugene Stanley
1
1
Center for Polymer Studies, Boston University,Boston, Massachusetts 02215, USA
2
Departamento de F´ısica, Facultad de Ciencias Exactas y Naturales,Universidad Nacional de Mar del Plata,Funes 3350, 7600 Mar del Plata, Argentina
3
Minerva Center of Department of Physics,Bar-Ilan University, Ramat Gan, Israel
Abstract
Transport in weighted networks is dominated by the minimum spanning tree (MST), the treeconnecting all nodes with the minimum total weight. We ﬁnd that the MST can be partitionedinto two distinct components, having signiﬁcantly diﬀerent transport properties, characterized bycentrality — number of times a node (or link) is used by transport paths. One component, the
superhighways
, is the inﬁnite incipient percolation cluster; for which we ﬁnd that nodes (or links)with high centrality dominate. For the other component,
roads
, which includes the remainingnodes, low centrality nodes dominate. We ﬁnd also that the distribution of the centrality for theinﬁnite incipient percolation cluster satisﬁes a power law, with an exponent smaller than that forthe entire MST. The signiﬁcance of this ﬁnding by showing that one can improve signiﬁcantly theglobal transport by improving a very small fraction of the network, the superhighways.
PACS numbers: 89.75.HcKeywords: Betweenness Centrality, Minimum spanning tree, Optimal path, Transport, Maximum ﬂow,Random Resistor Network
1
Recently much attention has been focused on the topic of complex networks, which char-acterize many natural and man-made systems, such as the internet, airline transport system,power grid infrastructures, and the world wide web [1, 2, 3]. Besides the static propertiesof complex networks, dynamical phenomena such as transport in networks are of vital im-portance from both theoretical and practical perspectives. Recently much eﬀort has beenfocused on weighted networks [4, 5], where each link or node is associated with a weight.Weighted networks yield a more realistic description of real networks. For example, thecable links between computers in the internet network have diﬀerent weights, representingtheir capacities or bandwidths.In weighted networks the minimum spanning tree (MST) is a tree including all of thenodes but only a subset of the links, which has the minimum total weight out of all possibletrees that span the entire network. Also, the MST is the union of all “strong disorder”optimal paths between any two nodes [6, 7, 8, 9, 10, 11, 12]. The MST which plays amajor role for transport is widely used in diﬀerent ﬁelds, such as the design and operation of communication networks, the traveling salesman problem, the protein interaction problem,optimal traﬃc ﬂow, and economic networks [5, 13, 14, 15, 16, 17, 18].An important quantity that characterizes transport in networks is the betweenness cen-trality,
C
, which is the number of times a node (or link) used by the set of all shortestpaths between all pairs of nodes [19, 20, 21]. For simplicity we call the “betweenness cen-trality” here “centrality” and we use the notation “nodes” but similar results have beenobtained for links. The centrality,
C
, quantiﬁes the “importance” of a node for transportin the network. Moreover, identifying the nodes with high
C
enables, as shown below, toimprove their transport capacity and thus improve the global transport in the network. Theprobability density function (pdf) of
C
was studied on the MST for both scale-free (SF) [22]and Erd˝os-R´enyi (ER) [23] networks and found to satisfy a power law,
P
MST
(
C
)
∼
C
−
δ
MST
(1)with
δ
MST
close to 2 [21, 24].Here we show that a sub-network of the MST [25], the inﬁnite incipient percolation cluster(IIC) has a signiﬁcantly higher average
C
than the entire MST — i.e., the set of nodes insidethe IIC are typically used by transport paths more often than other nodes in the MST. —In this sense the IIC can be viewed as a set of
superhighways
(SHW) in the MST. The nodes2
on the MST which are not in the IIC are called
roads
, due to their analogy with roads whichare not superhighways (usually used by local residents). We demonstrate the impact of thisﬁnding by showing that improving the capacity of the superhighways (IIC) is surprisinglya better strategy to enhance global transport compared to improving the same number of links of the highest
C
in the MST, although they have higher
C
[26]. This counterintuitiveresult shows the advantage of identifying the IIC subsystem, which is very small comparedto the full network [27]. Our results are based on extensive numerical studies for centralityof the IIC, and comparison with the centrality of the entire MST. We study ER, SF andsquare lattice networks.To generate a ER network of size
N
with average degree
k
, we pick at random a pair of nodes from all possible
N
(
N
−
1)
/
2 pairs, link this pair, and continue this process until wehave exactly
k
N/
2 edges. We disallow multiple connections between two nodes and self-loops in a single node. To construct SF networks with a prescribed power law distribution
P
(
k
)
∼
k
−
λ
with
k
≥
k
min
[22], we use the Molloy-Reed algorithm [28, 29]. We assign toeach node
i
a random number
k
i
of links drawn from this power law distribution. Then wechoose a node
i
and connect each of its
k
i
links with randomly selected
k
i
diﬀerent nodes.To construct a
weighted
network, we next assign a weight
w
i
to each link from a uniformdistribution between 0 and 1. The MST is obtained from the weighted network using Prim’salgorithm [30]. We start from any node in the largest connected component of the networkand grow a tree-like cluster to the nearest neighbor with the minimum weight until theMST includes all the nodes of the largest connected component. Once the MST is built, wecompute the value of
C
of each node by counting the number of paths between all possiblepairs passing through that node . We normalize
C
by the total number of pairs in the MST,
N
(
N
−
1)
/
2, which ensures that
C
is between 0 and 1 [31].To ﬁnd the IIC of ER and SF networks, we start with the fully connected network andremove links in descending order of their weights. After each removal of a link, we calculate
κ
≡
k
2
/
k
, which decreases with link removals. When
κ <
2, we stop the process becauseat this point, the largest remaining component is the IIC [32]. For the two dimensional(2D) square lattice we cut the links in descending order of their weights until we reach thepercolation threshold,
p
c
(= 0
.
5). At that point the largest remaining component is theIIC [33].To quantitatively study the centrality of the nodes in the IIC, we calculate the pdf,3
P
IIC
(
C
) of
C
. In Fig. 1 we show for nodes that for all three cases studied, ER, SF andsquare lattice networks,
P
IIC
(
C
) satisﬁes a power law
P
IIC
(
C
)
∼
C
−
δ
IIC
,
(2)where
δ
IIC
≈
1
.
2 [ER
,
SF]1
.
25 [square lattice]
.
(3)Moreover, from Fig. 1, we ﬁnd that
δ
IIC
< δ
MST
, implying a larger probability to ﬁnd alarger value of
C
in the IIC compared to the entire MST. Our values for
δ
MST
are consistentwith those found in Ref. [24]. We obtain similar results for the centrality of the links. Ourresults thus show that the IIC is like a network of
superhighways
inside the MST. When weanalyze centrality for the entire MST, the eﬀect of the high
C
of the IIC is not seen sincethe IIC is only a small fraction of the MST. Our results are summarized in Table I.To further demonstrate the signiﬁcance of the IIC, we compute for each realization of the network the average
C
over all nodes,
C
. In Fig. 2, we show the histograms of
C
forboth the IIC and for the other nodes on the MST. We see that the nodes on the IIC have amuch larger
C
than the other nodes of the MST.Figure 3 shows a schematic plot of the SHW inside the MST and demonstrates its use bythe path between pairs of nodes. The MST is the “skeleton” inside the network, which playsa key role in transport between the nodes. However, the IIC in the MST is like the “spine inthe skeleton”, which plays the role of the superhighways inside a road transportation system.A car can drive from the entry node A on roads until it reaches a superhighway, and ﬁndsthe exit which is closest to the exit node B. Thus those nodes which are far from each otherin the MST should use the IIC superhighways more than those nodes which are close toeach other. In order to demonstrate this, we compute
f
, the average fraction of pairs of nodes using the IIC, as a function of
ℓ
MST
, the distance between a pair of nodes on the MST(Fig. 4). We see that
f
increases and approaches one as
ℓ
MST
grows. We also show that
f
scales as
ℓ
MST
/N
ν
opt
for diﬀerent system sizes, where
ν
opt
is the percolation connectednessexponent [9, 10].The next question is how much the IIC is used in transport on the MST? We deﬁne theIIC
superhighway usage
,
u
≡
ℓ
IIC
ℓ
MST
,
(4)4
where
ℓ
IIC
is the number of the links in a given path of length
ℓ
MST
belonging to the IICsuperhighways. The average usage
u
quantiﬁes how much the IIC is used by the transportbetween all pairs of nodes. In Fig. 5(a), we show
u
as a function of the system size
N
.Our results suggest that
u
approaches a constant value and becomes independent of
N
for large
N
. This is surprising since the average value of the ratio between the number of nodes on the IIC and on the MST,
N
IIC
/N
MST
, approaches zero as
N
→∞
[27], showingthat although the IIC contains only a tiny fraction of the nodes in the entire network, itsusage for the transport in the entire network is constant. We ﬁnd that
u
≈
0
.
3 for ERnetworks,
u
≈
0
.
2 for SF networks with
λ
= 4
.
5, and
u
≈
0
.
64 for the square lattice.The reason why
u
is not close to 1
.
0 is that in addition to the IIC, the optimal pathpasses through other percolation clusters, such as the second largest and the third largestpercolation clusters. In Fig. 5, we also show for ER networks, the average usage of the twolargest and the three largest percolation clusters for a path on the MST and we see that theaverage usage increases signiﬁcantly and is also independent of
N
. However, the number of clusters used by a path on MST is relatively small and proportional to ln
N
[34], suggestingthat the path on the MST uses only a few percolation clusters and a few jumps betweenthem (
∼
ln
N
) in order to get from an entry node to an exit node on the network. When
N
→∞
the average usage of all percolation clusters should approach 1.Can we use the above results to improve the transport in networks? It is clear that byimproving the capacity or conductivity of the highest
C
links one can improve the transport(see Fig. 5(b) inset). We hypothesize that improving the IIC links (strategy I), whichrepresent the superhighways is more eﬀective than improving the same number of links withthe highest
C
in the MST (strategy II), although they have higher centrality [26]. To test thehypothesis, we study two transport problems: (i) current ﬂow in random resistor networks,where each link of the network represents a resistor and (ii) the maximum ﬂow problem wellknown in computer science [36]. We assign to each link of the network a resistance/capacity,
e
ax
, where
x
is an uniform random number between 0 and 1, with
a
= 40. The valueof
a
is chosen such as to have a broad distribution of disorder so that the MST carriesmost of the ﬂow [10, 34]. We randomly choose
n
pairs of nodes as sources and other
n
nodes as sinks and compute ﬂow between them. We compare the transport by improvingthe conductance/capacity of the links on the IIC (strategy I) with that by improving thesame number of links but those with the highest
C
in the MST (strategy II). Since the two5

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x