JAIST Repository
https://dspace.jaist.ac.jp/

Title

Traffic properties for stochastic routing on
scale‑free networks

Author(s)Hayashi, Yukio; Ono, Yasumasa

Citation

IEICE TRANSACTIONS on Communications, E94‑B(5):1311‑1322

Issue Date

2011‑05‑01

Type

Journal Article

Text version

publisher

URL

http://hdl.handle.net/10119/10317

RightsCopyright (C)2011 IEICE. Yukio Hayashi, andYasumasa Ono, IEICE TRANSACTIONS on
Communications, E94‑B(5), 2011, 1311‑1322.
http://www.ieice.org/jpn/trans̲online/

Description

Japan Advanced Institute of Science and Technology

IEICE TRANS. COMMUN., VOL.E94–B, NO.5 MAY 2011

1311

PAPER

Traﬃc Properties for Stochastic Routing on Scale-Free Networks
Yukio HAYASHI†a) and Yasumasa ONO† , Members

SUMMARY
For realistic scale-free networks, we investigate the traffic properties of stochastic routing inspired by a zero-range process known
in statistical physics. By parameters α and δ, this model controls degreedependent hopping of packets and forwarding of packets with higher performance at more busy nodes. Through a theoretical analysis and numericalsimulations, we derive the condition for the concentration of packets at a
few hubs. In particular, we show that the optimal α and δ are involved in
the trade-oﬀ between a detour path for α < 0 and long wait at hubs for
α > 0; In the low-performance regime at a small δ, the wandering path for
α < 0 better reduces the mean travel time of a packet with high reachability. Although, in the high-performance regime at a large δ, the diﬀerence
between α > 0 and α < 0 is small, neither the wandering long path withshort wait trapped at nodes (α = −1), nor the short hopping path withlong wait trapped at hubs (α = 1) is advisable. A uniformly random walk
(α = 0) yields slightly better performance. We also discuss the congestion
phenomena in a more complicated situation with packet generation at eachtime step.
key words: traﬃc dynamics, degree-dependent random walks, zero-range
process, phase transition, scale-free network

1.

Introduction

In daily socio-economic network systems, many commodities, passengers, or information fragments (abstractly referred to as packets in this paper) are delivered from one
place to another place. In general, it is expected to send
and receive packets as quickly as possible without encountering traﬃc congestion which would force packets to wait
at nodes. Even if packets are concentrated (or condensed interm of statistical physics) on just a few nodes in some partsof a network, this situation may cause congestion over the
network. Thus, one of the important issues is a routing strategy: how to select a forwarding node in the neighbors of theresident node of a packet. Since the eﬃciency of transportation or communication depends on not only routing strategy,
but also on network topology, we should consider a realistic
problem setting for the routing and the topology. In addition, considering the interaction of accumulated packets ina buﬀer (called queue) at each node is necessary, since it
crucially aﬀects the traﬃc flow on a network. This paper
discusses traﬃc properties that depend on routing strategies
in the interaction of packets on a realistic network topology.
During this decade, a new research field, complex network science, has been created [1], since a common topoManuscript received March 16, 2010.
Manuscript revised September 8, 2010.
†
The authors are with Japan Advanced Institute of Science andTechnology, Nomi-shi, 923-1292 Japan.
a) E-mail: yhayashi@jaist.ac.jp
DOI: 10.1587/transcom.E94.B.1311

logical structure called scale-free (SF) was found to exist in
many real networks such as the Internet, the World-WideWeb, power grids, airline networks, social collaboration
networks, human sexual contacts, and biological metabolic
pathways, etc. The SF structure is characterized by the property that the distribution of degree (the number of connections to a node) follows a power-law. In other words, thenetwork consists of many nodes with low degrees and a few
hubs with high degrees. Moreover, a SF network naturally
emerges in social acquaintance relationships or peer-to-peer
communications, and it has short paths compared with large
network size (the total number of nodes).
In a realistic SF network, a routing path is shortened bypassing through hubs for the forwarding of a packet. However, many packets may be concentrated at the hubs [2], in
whose queues the packets are cumulatively stored if they
arrive in a quantity larger than the processing limit for forwarding. In such a situation, there exists a trade-oﬀ between
delivering packets on a short path and avoiding traﬃc congestion. To improve communication eﬃciency even in a dynamic environment for a wireless or ad hoc network, various routing schemes are being developed. Because, in an
ad hoc network, many nodes (such as base stations or communication sites) and connections between them are likely
to change over time, then global information, e.g., a routing
table in the Internet, cannot be applied. In early work, somedecentralized routing developed to reduce energy consumption in sensor or mobile networks, however they lead to thefailure of guaranteed delivery [3]; in the flooding algorithm,
multiple redundant copies of a message are sent and cause
congestion, while greedy and compass routing may occasionally fall into infinite loops or into a dead end. Thus, we
focus on stochastic routing methods using only local information with respect to the resident node of a packet and tothe connected neighbors on a path, due to their simplicity
and power. If the terminal node of a packet is included in
the neighbors of the resident node, then the packet is deterministically sent to the terminal in order to guarantee reachability unless the connectivity is broken. We call this neighbor search (or n-search) only at the last step to the terminal.
Note that the development of stochastic routing methods isstill in progress depending on device and information processing technologies. Although we suppose a mixture of
wireless and wired communications in future networks, firstof all, we aim to understand the relations for traﬃc properties between fixed network topology and routing methods.
Here, it is usually assumed for simplicity that each node has

c 2011 The Institute of Electronics, Information and Communication Engineers
Copyright IEICE TRANS. COMMUN., VOL.E94–B, NO.5 MAY 20111312

the same performance in the forwarding of packets.
The enhancement of performance in forwarding is also
reasonable [4], [5]. For example, in the Internet or airline
networks, an important facility with many connections has
high performance; more packets or flights are processed as
the incoming flux of communication requests or of passengers increases. Such higher performance at more busy nodes
is eﬀectively applied in a zero-range process (ZRP) [6], [7],which tends to distribute packets throughout the whole network, instead of avoiding paths through hubs.
In this paper, from the random walk version, we extend the ZRP on a SF network to the degree-dependent hopping rule, which parametrically controls routing strategies
in the trade-oﬀ between the selection of a short path passing through hubs, and the avoidance of hubs at which many
packets are condensed and wait in queues for a long time.
The above models in statistical physics are useful for the
analysis of complex phenomena involved in transition form
a free-flow phase to a congestion phase, or the opposite transition. Most research on traﬃc congestion rely on numerical simulations. Although a few other theoretical analyses
based on the mean-field approximation [8] have been done,
we can not compare them to the ZRP, simply because of different problem settings. Thus, we consider a combination ofsettings as modified traﬃc models, and numerically investigate them.
The organization of this paper is as follows. In Sect. 2,
we briefly review the related models in recent studies. In
Sect. 3, we introduce a stochastic packet transfer model defined by the ZRP, in which all packets persist without any
generation and removals. Then, in terms of fundamental
properties, we approximately analyze the stationary probability of incoming packets at each node on SF networks,
and derive the phase transition for condensation of packets
at hubs in the degree-dependent hopping rule. In Sect. 4,
we numerically confirm the phase transition, and as a new
result, show the trade-oﬀ between a detour wandering pathand long wait at hubs. Moreover, we discuss the congestion
phenomenon in the modified traﬃc models with packet generation. In Sect. 5, we summarize these results and describe
some issues for further research.
2.

Related Work

Many traﬃc models have been proposed in various problem settings for routing, node capacity, and packet generation. They are summarized in Table 1. The basic processes
for packet transfer consist of the selection of a forwarding(coming-in) node and the jumping-out of packets in the nodecapacity. In these models (including our model discussed
later), a significant issue commonly arises from the tradeoﬀ between delivering packets on a shorter path and avoiding the congestion caused by a concentration of packets ona few nodes such as hubs.
In the typical models, a 
forwarding node k is chosen with probability either Kkα / j∈Ni K αj [9]–[11] or (m(k) +1)−β / j∈Ni (m( j) + 1)−β [12]. Here, α and β are real param-

Table 1 Recent traﬃc models for complex networks. When a packet isforwarded from a current node i to k ∈ Ni , the neighboring node k is chosenwith probability Πk or by minimizing an objective function on a routing
path. The node capacity ci is defined by the number of simultaneouslytransferable packets from each node i. Here, K(xl ) denotes the degree of
node xl , Θ(x) is the step function, and m∗ is a threshold, β ≥ 0, and 0 ≤ η̄ <1.
Ref.

selection of
forwarding node

node
capacity

packetgeneration[10]

Πk ∝ Kkα−1 ≤ α ≤ 1
min l K(xl )β
on a path {x0 , . . . , xn }ci = 10 or
ci = K i

Yesci = 1Yes[12]Πk ∝ (m(k) + 1)−βci = 1Yes[13]

Πk ∝ Kk (m(k) + 1)−βci = 5Yes[14]

min hdk + (1 − h)m(k)0≤h≤1ci = 1Yes[8]random walkwith a refusal prob.
η̄Θ(m(k) − m∗ )ci = 1YesΠk ∝ Kkα
α>0jumping rate
mδ(i)

No

[11]

[6], [7], [15][16]eters, Kk and m(k) denote the degree and the dynamicallyoccupied queue length by packets at node k in the connectedneighbors Ni to the resident node i of the packet. Thesemethods are not based on a random walk (selecting a forwarding node uniformly at random among the neighbors),
but on the extensions (including the uniformly random one
at α, β = 0) called preferential and congestion-aware walks,
respectively. Note that α > 0 leads to a short path passing
through hubs, and that α < 0 and β > 0 lead to the avoidanceof hubs and congested nodes with large m(k) . In stochastic
routing methods, instead of using the shortest path, the optimal values α = −1 and β = 1 for maximizing the generation
rate of packets in a free-flow regime have been obtained bynumerical simulations [10], [11]. A correlation between thecongestion at node level and a betweenness centrality measure was suggested [12].
Other routing schemes [8], [13], [14] have also been
considered, taking into account lengths of both the routing
path and of the queue. In a deterministic model [14], a forwarding node k is chosen among neighbors Ni by minimizing the quantity hdk + (1 − h)m(k) with a weight 0 ≤ h ≤ 1, dk
denoting the distance from k to the terminal node. Since wemust solve the optimization problems, these models [11],[14] are not suitable for wireless or ad hoc communication
networks. Thus, stochastic routing methods using only local
information are potentially promising. In a stochastic model[8], k ∈ Ni is chosen at random, and a packet at the top ofits queue is sent with probability 1 − η(m(k) ) or refused withprobability η(m(k) ) as a nondecreasing function of the queue
length m(k) . This model is simplified by the assumption ofa constant arrival rate of packets, for analyzing the criticalpoint of traﬃc congestion in a mean-field equation [8].

HAYASHI and ONO: TRAFFIC PROP. FOR STOCHASTIC ROUTING ON SF

1313

With a diﬀerent processing power at each node [10],it has also been considered that the node capacity ci is proportional to its degree Ki , therefore more packets jump out
from a node as the degree becomes larger. On the other
hand, in the ZRP [6], [7], [15], the forwarding capacity at
a node depends on the number of m(i) defined as a queue
length occupied by packets at node i. The ZRP is a solvable theoretical model for traﬃc dynamics. In particular, in
the ZRP with a random walk at α = 0, the phase transition
between condensation of packets at hubs and uncondensation on SF networks has been derived [6], [7]. For α > 0, a
similar phase transition has been analyzed in the mean-fieldapproximation [16].
In the next two sections, based on a straightforward approach introduced in Refs. [6], [7], we derive the phase transition in the ZRP on SF networks with the degree-dependent
hopping rule for both α > 0 and α < 0, inspired by preferential [9]–[11] and congestion-aware walks. Although the rule
is not identical to the congestion-aware routing scheme [12]based on occupied queue length m(k) , α < 0 corresponds to
avoiding hubs with large degrees, where many packets tend
to be concentrated. Furthermore, we study the traﬃc properties in the case with neighbor search into a terminal nodeat the last step.
3.

Packet Transfer Model

3.1 Routing Rule
Consider a system of M interacting packets
on a network ofNm(i) , where
N nodes with a density ρ = M/N, M = i=1m(i) ≥ 0 denotes the occupation number of packets in thequeue at each node 1 ≤ i ≤ N. For simplicity, we assume that the queue length is not limited, and that the order of stored packets is ignored. If there is a limitation on
the queue length, it may become necessary to discuss a cascading problem [17]–[19] whose dynamics are very complicated.
To investigate the predicted properties from the theoretical analysis in the ZRP [6], [7], [15], we use the sameproblem setting, such that all packets persist on paths in
the network without generation or removals of packets. For
more complex situations with packet generation, some models modified by adding diﬀerent routing rules will be investigated in Sect. 4.2.
In this routing rule related to the ZRP, the total number M of packets is constant at any time, and each node
performs a stochastic local search as follows: at each time
step, a packet jumps out of a node i stochastically at a given
rate qi (m(i) ) as a function of m(i) , and then comes into oneof the neighboring nodes k ∈ Ni chosen with probability
Kkα / k ∈Ni Kkα . When a packet is transferred from i to k, thequeue length m(k) is increased by one unit, and m(i) is simultaneously decreased. The above processes are conceptual,
the relaxation dynamics for the simulation of packet transfer is necessary, and described in Sect. 4. The eﬀect of thedeterministic neighbor search into a terminal node at the lastFig. 1 Combination of consecutive nodes on the route from node i to j.
The dashed rectangles correspond to the sum of Eqs. (1)–(3).

step will also be discussed later.
3.2 Stationary Probability in α-Random Walks
Before investigating the influence of dynamic queue lengths
on traﬃc properties, we consider the stationary probabilityof incoming packets at each node. As mentioned in the previous subsection, we extend a random walk routing [15],[20], in which a walker (packet) chooses a node uniformly
at random among the neighbors of the current node on apath, to a degree-dependent routing. We call it α-randomwalk.
As in Ref. [20], for the probability Pi j of finding thewalker at node j ∈ Nk from node i through the intermediate
nodes k ∈ Ni at time t, the master equation is
Pi j (t + 1) =





k

K αj

α Pik (t).
j ∈Nk K j(1)

By iterating Eq. (1), an explicit expression for the transition
probability Pi j to go from node i through j1 , . . . , jt−1 to j int steps follows as
Pi j (t) =

j1 ,..., jt−1

K αj1

α × ...× j1 ∈Ni K j

1

K αj

α,
j ∈N jt−1 K j

(2)
where the sum j1 ,..., jt−1 is taken over the connected paths
between nodes i and j, as shown in Fig. 1. In the opposite
directions of the same paths, the transition probability P ji
follows as
P ji (t) =
jt−1 ,..., j1



K αjt−1αjt−1 ∈N j K j

t−1

×...× Kiαα.
i ∈N j1 Ki

(3)

We assume the network to be uncorrelated: there is no correlation
between two degrees
connected nodes, so that
 of any

α
α
α


K
=
K
·
K
and
K
= K j · K α hold by usi
j1
jt−1
j1
jt−1
ing the mean value K α of the α-power of the degree. By

IEICE TRANS. COMMUN., VOL.E94–B, NO.5 MAY 2011

1314
Table 2 Numerically estimated exponent β ≈ 1 + α for the lines fromthe plotted marks in Fig. 2 by using the mean-square-error method for the
independent walks of M = 1000 packets. These values give the averagedβslopes for P∞
j ∝ K j in 100 BA networks with N = 1000 and K = 10.
αwithoutβwith n-search
β

1.0
0.5
0.0
−0.5
−1.0

2.245
1.611
1.039
0.524
0.022

2.143
1.576
1.027
0.519
0.019

Fig. 2 Probability of incoming at a node with degree K in the α-random
walk of M = 1000 independent packets (equivalent to the case of δ = 1)
through 1000 rounds. The lines guide the estimated slopes in the left column (without n-search) in Table 2, and the plotted marks show the probability obtained in a BA network with N = 1000 and K = 10.

comparing the expression of Pi j in Eq. (2) with that of P ji in
Eq. (3), we obtain the equivalent relation
Kj
Ki
P ji .
α Pi j =Kj
KiαThus, for any source i and step t, Pi j is proportional to K 1+αj ,while P ji is proportional to Ki1+α . Consequently, the stationary solution P∞j of the incoming probability Pi j is proportional to K 1+α
j . This form, related only to the degree ofthe forwarding node j, is suitable for the theoretical analysisof the ZRP presented in the next subsection and in the Appendix. The approximative solution is also obtained froma diﬀerent approach to the master equation [10] under thesame assumption of uncorrelated networks.
Figure 2 shows the stationary solution P∞j ∝ K βj andthe exponent β ≈ 1 + α ≥ 0 for the SF networks (generated by the BA: Barabási-Albert model [1]). Table 2 also
shows that the estimated exponents β are consistent in thecases both with and without neighbor search into a terminal
node at the last step. Here, the terminal is chosen from allnodes uniformly at random. After arriving at the terminal,
the packet is restarted (resent) from the node to a new terminal, in order to maintain the persistency of packets in the
ZRP.
3.3 Phase Transition in the ZRP
We discuss the phase transition between condensation anduncondensation in the ZRP with degree-dependent hopping
rule of packets. For the configurationm(1) , . . . , m(i) , . . . , m(N)of occupation at each node, the stationary solution of a single packet is given by the factorized form

Fig. 3 Illustration of the queue length occupied by packets at each
node. For the sum ∗ in Eq. (6), there are many combinations of{m(1) , . . . , m(i−1) , m(i+1) , . . . , m(N) } satisfying ji m( j) = M − ω.

P(m(1) , . . . , m(i) , . . . , m(N) ) =1 N
Π fi (m(i) ),Z i=1

where Z is a normalization factor and ∞ Pidef m(i)fi (m(i) ) = Πω=1,
qi (ω)(4)(5)

for an integer m(i) > 0 and fi (0) = 1. We consider a function
qi (ω) = ωδ with a parameter 0 ≤ δ ≤ 1 for forwarding performance. This means that a node works harder for transfer,as it has more packets in the queue with larger ω and δ.
Using the probability distribution in Eq. (4) and the staβtionary probability P∞i ∝ Ki , we can calculate the meandef value m(i) at each node. Here, m(i) = ∞ω=0 ωPi (m(i) =ω) is defined by using the probability distribution Pi (m(i)) =ω) of the number of packets occupying node i.
1 
Pi (m(i) = ω) =fi (ω)Π ji f j (m( j) ),
(6)
Zi ∗

where the sum ∗ is taken in combination{m(1) , . . . , m(i−1) ,m(i+1) , . . . , m(N) } on the constraint ji m( j) = M − ω asshown in Fig. 3, and Zi is a normalization factor. It is diﬃcult to directly solve the normalization factor Zi or Z. Thus,
introducing a fugacity variable z [21], the mean value isgiven by a generating function∂ ln Fi (z)ωzω fi (ω)=z,(7)m(i) = ω ω
z
f
(ω)
∂z
i
ω
where the second term in the right-hand side of Eq. (7) isdue to the definition∞def
Fi (z) =zω fi (ω).
ω=0

HAYASHI and ONO: TRAFFIC PROP. FOR STOCHASTIC ROUTING ON SF

1315
Table 3 Scaling of the crossover degree Kc , the mean occupation number mK at a node with degree K and mhub at the hub with the maximum
degree Kmax for the cases: (A) δ > δc , (B) δ = δc , (C) 0 < δ < δc , and (D)δ = 0. A blank denotes no correspondence.
Kc
(A)
(B)
(C)
(D)

mK<Kc

(ln Kmax )δc /β
1−δ/δc
Kmax
Kmax(K/Kc )β(K/Kc )βββK /(Kmax − K β )

mK>Kc

mhub

K β/δ

O(N δc /δ )O(N/ ln N)O(N)ρN(K/Kc )β/δc(K/Kc )β/δβ
From the definition (5), qi (ω) = ωδ , and P∞i ∝ Ki , we have

Fi (z) =∞(zK β )ωi(ω !)δ
ω=0

,

(8)

 β
K
(Kiβ )ω
The fubecause fi (ω) = Πωm=1 miδ = (ω!)δ in Eq. (5).
gacity z should be determined from the self-consistencyNequationN ρ = i=1 m(i) /N as a function of z. Note thatM = i=1 m(i) is the total number of packets in a networkof N nodes, and that the density ρ is constant at N, M → ∞.
In this paper, we consider a SF network whose degree
distribution follows a power-law P(K) ∼ K −γ . According to
the performances of jumping-out, we classify the following
defcases (A) δ > δc = β/(γ − 1), (B) δ = δc , (C) δ < δc , and(D) δ = 0 for a critical value δc of the phase transition fromuncondensation to condensation of packets, or the opposite
transition. Since the derivation is the same as in Refs. [6],[7] at α = 0, except with a slight modification for a generalvalue of α (and the corresponding β ≈ 1 + α), we briefly
review it in the Appendix. We summarize the generalized
results for 0 ≤ |α| ≤ 1 in Table 3 (from that for α = 0).
In the cases (B) and (C), many packets condensate at nodes
with degree K > Kc because of the larger exponent β/δ > β.
Note that the queue length occupied by packets is rewritten
as mKi taking into account the dependence on the degree Ki .
4.

Simulation

In Sect. 4.1, we numerically investigate the basic propertiesof packet transfer in the ZRP. In Sect. 4.2, we further discuss
congestion phenomena with packet generation.
4.1 Traﬃc Properties for α-Random Walks in the ZRP
We have performed simulations for M = 1000 packets on
SF networks generated by the BA model [1] with a size
N = 1000, an average degree K = 10, and an exponentγ = 3 of P(K) ∼ K −γ . From the initial state in which
one packet is set on each node, the following processes
are repeated as the relaxation of the ZRP [7] from nodebased dynamics to particle-based dynamics [21]. At eachtime step, a packet is selected at random. With probability qi (m(i) )/m(i) = mδ−1(i) , the packet jumps out of its resident
node i, and hops 
to one of the neighboring nodes j ∈ Ni withprobability K αj / j ∈Ni K αj . Otherwise, the selected packet

Fig. 4 Typical results for the mean occupation number mK of packets
at a node with degree K in the routing without n-search. Inset: the caseswith n-search. The circle and cross marks correspond to the results in 1000
and 100 rounds, respectively. The dashed lines show the slopes β and β/δ inTable 3. Note that condensation of packets at the nodes with high degrees
occurs in Case(C). These results are obtained from the averages of 100
samples of packet transfer on a BA network whose maximum degree is theclosest to the average value Kmax = 132 in the 100 realizations.

does not move with probability 1 − qi (m(i) )/m(i) . The time ismeasured as a unit of one round (Monte Carlo sweep) consisting of M trials of the random selection of a packet.
Figure 4 shows the mean occupation number mKof packets at a node with degree K in the cases bothwith/without neighbor search (n-search), while the top of
Fig. 4 shows the predicted piecewise linear behavior [16] forthe crossover degree Kc shown in Table 4; the steeper line
indicates condensation at the nodes with high degrees, andthe bottom of Fig. 4 shows that condensation is suppressedby a more gentle line. As shown in the insets, the marks
slightly deviate from a line, especially in the head and thetail, because of the eﬀect of n-search into a terminal nodeat the last step. In these cases at the top and the bottom of
Fig. 4, the critical values of δc ≈ (1 + α)/(γ − 1) are 0.75 > δ
and 0.25 < δ, respectively. Thus, condensation of pack-IEICE TRANS. COMMUN., VOL.E94–B, NO.5 MAY 2011

1316
Table 4 Classification of the cases in Table 3 for the combinations of1−δ/δc, for δc = β/2α and δ. The values in the mid-columns are Kc = Kmax
in the case (C), corresponding to the maximum, average, and minimum of
Kmax = 189, 132, 98 in each vertical triplet from the top to the bottom.
These results are obtained in 100 realizations of BA networks with N =1000 and K = 10.
0.0

0.2

0.5

0.8

δc

1.0

(D)

74.26
55.29
43.28

18.29
14.98
12.71

4.504
4.063
3.731

1.122

0.5

(D)

51.44
39.27
31.39

7.304
6.374
5.693

1.037
1.034
1.032

0.805

0.0

(D)

25.15
20.16
16.79

1.221
1.204
1.191

(A)

0.519

-0.5

(D)

3.478
3.193
2.975

(A)

(A)

0.262

-1.0

(D)

(A)

(A)

(A)

0.011

α

δ

ets at hubs can be avoided as the performance of transfer
is enhanced at a large δ, although the transition depends on
the probability of incoming packets according to the valueof α; a negative α induces a nearly homogeneous visitingof nodes, while a positive α induces a heterogeneously biased visiting of the nodes with high degrees. We note thatthe uncondensed phase is maintained in a wide range ofδ > δc ≈ (1 + α)/(γ − 1) for α < 0, as shown in the case (A)of Table 4.
Next, in order to study the traﬃc properties, such as thetravel time on the routing path, we consider packet dynamics
in a realistic situation with n-search into a terminal node at
the last step. If the terminal is included among the neighborsof the resident node for a randomly selected packet, then it
is deterministically forwarded to the terminal node, taking
into account the reachable chance, otherwise it is stochastically forwarded to a neighboring node j with probability
K αj / j ∈Ni K αj . The n-search is practically eﬀective and necessary in order to reach a terminal node. Remember thatthe estimated values of β are similar to both with/without
n-search, as shown in Table 2. Therefore, the behavior of
the mean occupation number mK is similar to that shownin Fig. 4 and the inset. In the following discussions, if weleave out n-search, then the optimal parameter values of αand δ may be changed for low-latency delivery, although thediﬀerence is probably small from the above similarity. By
selecting hubs for α > 0, a packet is terminated with higher
probability even in only the stochastic forwarding, because aterminal node is highly likely to be connected to some hubs.
At the same time, this leads to congestion at hubs. However, in the case without n-search, a packet may wander fora very long time, which is not bounded a priori for the simulation of the packet transfer. It is intractable due to huge
computations. Thus, we focus on the case with n-search.

We investigate the traﬃc properties for reachability of
packets, the number of hops, the travel time T a including thewait time of a trapped packet in queues, and the sum T w of
wait times on a path until arrival at the terminal. Note thatthe travel time is T a = T w + (time to one hop) × (the number of hops). We also define the averaged wait time T w /Nw
per node, where Nw is the number of trappings in queues
at the nodes on a routing path. These measures are cumulatively counted in the observed interval after 1000 rounds,
and averaged over 100 samples of this simulation. Here, we
discarded the initial 1000 rounds as a transient before thestationary state of m(i) is reached.
Figure 5 shows, from the top to the bottom, the convergence of reachability, the mean number of restarted packets
per round, and the mean travel time in the high-performance
regime at δ = 0.8. The inset shows a slightly slow convergence in the low-performance regime at δ = 0.0. For othermeasures, similar convergence properties are obtained. We
compare these curves in terms of the values of α; they shift
up from α = −1.0 to α = 0.5 in the case (A) δ > δc , while
down from α = 0.5 to α = 1.0 in the case (C) δ < δc .
This non-monotonic dependence on α is related to the condensation transition, since the change between δ > δc andδ < δc occurs at the critical value α = 0.6 for the equivalence δc ≈ (1 + α)/(γ − 1) ⇔ δ = 0.8. Thus, it appears
when α is greater or less than 0.5 in Fig. 5. In the following,
we briefly explain each property: reachability, the numberof restarts, and T a . The reachability of the restarted packets is around 0.99 on similar curves for all values of α at
δ = 0.8, while these curves separate in increasing order of
α at δ = 0.0 (see the inset at the top of Fig. 5). Note thatthe number of restarted packets cumulatively increases as
the observed interval is longer, although the rate per roundis constantly around 3 ∼ 5 in the ordering from α = 0,α = ±0.5, to α = ±1 for δ = 0.8, and less than 1 in theordering from α = −1.0 to α = 1.0 for δ = 0.0, as shown inthe middle of Fig. 5 and in the inset. The maximum and theminimum lines for the mean travel time T a are obtained at
α = −1 and α = 0, respectively, for δ = 0.8. However, allof the curves shift up for δ = 0.0 (see the inset at the bottom of Fig. 5), and T a is longer as the value of α increases,
because of the waiting at high-degree nodes.
We further investigate the above traﬃc properties, especially for the forwarding of packets with more detailed
values of δ for 30000 rounds in the quasi-convergent state.
As shown in Fig. 6, the mean travel time T a decreases
as the value of δ increases with higher forwarding performance, because the wait time trapped in a queue decreases
on average. In particular, packets tend to be trapped at hubs
for a long time when α > 0, and then T a is longer. In contrast, the number of hops increases on average as the valueof δ increases, because some longer paths are included inhigher reachability. The path length counted by hops tends
to be short through hubs when α > 0, however it tends to belong on a wandering path when α < 0. Therefore the number of hops increases in decreasing order of α. Note thatthe number of hops is very small compared to T a , which

HAYASHI and ONO: TRAFFIC PROP. FOR STOCHASTIC ROUTING ON SF

1317

Fig. 6 The mean travel time (top) and the mean number of hops (bottom). The , +, ∗, ×, and  marks correspond to α = 1.0, 0.5, 0.0, −0.5,
and −1.0, respectively. The simulation conditions are the same as in Fig. 5.

Fig. 5 Convergence properties in the high-performance regime at δ = 0.8
in the observed interval [rounds] after the transient state of mK . Inset:
results in the low-performance regime at δ = 0.0. These results are obtained
from the averages of 100 samples of packet transfers on a BA network
whose maximum degree is the closest to the average value Kmax = 132 in
the 100 realizations.

is dominated by the mean wait time T w ≈ T a on a path.
As shown in Fig. 7, the mean number Nw of trappings
at nodes on a path increases when α > 0 and decreases when
α < 0 as the value of δ increases with higher forwarding performance. This up-down phenomenon may be caused by atrade-oﬀ between the avoidance of trapping through suﬃciently high forwarding performance at a node and the in-clusion of longer paths with high reachability. The mean
wait time T w /Nw per node decreases as the value of δ increases, and is longer in increasing order of α because of thelong wait time at hubs.
In summary, the wandering path for α < 0 better reduces the mean travel time of a packet with high reachability in the low-performance regime at a small δ, while in
the high-performance regime at a large δ, the diﬀerence between α > 0 and α < 0 is small, neither the wandering
long path with short wait trapped at nodes (α = −1), nor the
short hopping path with long wait trapped at hubs (α = 1)
is advisable. Thus, a uniformly random walk (α = 0) yields
slightly better performance.
4.2 Congestion Phenomenon
This subsection discusses the congestion phenomenon when
packets are randomly generated at each node at a constantrate p, and removed at the terminal nodes (not restarted
within the persistency). In order to reduce the computationalload, the packet dynamics starts from the initial state: there
are no other packets than the ones that are generated. We
compare the phenomenon in our traﬃc model based on the
ZRP with that in the following modifications related to theIEICE TRANS. COMMUN., VOL.E94–B, NO.5 MAY 2011

1318
Table 5Modified traﬃc models.

Refusaln-search

const. arrivalNo η̄ = 0
Yes η̄ > 0

ZRP
Mod 1

Mod 3
Mod 2

with probability 1 − μ.
Mod 3: In Mod 2, there is no refusal process (η̄ = 0).
In Mod 1, the randomly-selected packet from the queue
does not leave node i with a constant probability η̄ if theoccupation number m( j) of packets is greater than a threshold m∗ , while in Mod 2, after passing this refusal check, it
is removed with a constant probability μ. Note that constant arrival was assumed to theoretically predict the criticalpoint of traﬃc congestion in the mean-field approximation
as N → ∞ [8]. With packet generation, we can perform the
ZRP as an extension of the model in Ref. [8]. In particular,
the case of δ = 0 corresponds to node capacity ci = 1 for all
nodes i; only one packet is transferable from a node at eachtime.
For a variable generation rate p, we investigate the appearance of congestion by using the order parameter [8],[14]op = limt→∞

Fig. 7 The mean number of trappings at nodes (top) and the mean wait
time per node (bottom). The , +, ∗, ×, and  marks correspond to α =1.0, 0.5, 0.0, −0.5, and −1.0, respectively. The simulation conditions are thesame as in Fig. 5.

traﬃc-aware routing [14] at α = 0 [8]. Table 5 summarizes
a combination of the basic processes: with or without (Yesor No) the refusal of forwarding, n-search, and a constantarrival with probability μ. The other processes for choosing
a forwarding node j with probability ∝ K αj and for jumpingout a packet from its resident node i at the rate mδ(i) are common.
Mod 1: With probability η(m( j) ) = η̄Θ(m( j) − m∗ ), the selected packet is not transfered to j ∈ Ni , but is refused at node i, where Θ(x) is the step function, m∗
is a threshold, and a parameter 0 < η̄ ≤ 1.
Here, node j is chosen deterministically by n-search if
j is the terminal node, otherwise it is chosen with aprobability proportional to K αj .
Mod 2: Moreover, instead of n-search, the selected packet
is removed with probability μ, or it enters the queueM(t + τ) − M(t),τpN

where M(t) denotes the sum of existing packets in queues
over network (practically for a large t), and τ is the observed
interval. The value of op represents level of congestion, e.g.
op ≈ 0 indicates a free-flow regime, while op ≈ 1 indicatesa congested regime.
In the following, we set η̄ = 0.7 and m∗ = 5 for therefusal process. As shown in Fig. 8, in the cases in which
n-search takes place, the value of op rapidly grows with theincreasing of the generation rate p, since the removal of apacket arriving at the terminal node is rare, especially fora small δ. Here, the marks and color lines indicates different values of δ and α. By comparing the corresponding
curves of the same color and marks in the top and the bottom figures, we notice that the ZRP suppresses congestion insmaller ops than Mod 1, in particular, for δ = 0.5, 0.8 (blueand magenta lines). At the top of Fig. 8, the magenta lines
indicate the existence of a free-flow regime around a small
p for δ = 0.8 as high forwarding performance. Thus, therefusal process does not work eﬀectively in the cases withn-search, at least for this parameter set. At both the top andthe bottom of Fig. 8, the diﬀerence for the same color lines
with three marks corresponding to α = ±1, 0 is small, except
for δ = 0.8 in Mod 1 (magenta lines at the bottom). However, the curves shift down as δ becomes larger; in otherwords, the congestion is suppressed by higher forwarding
performance. Note that a uniformly random walk at α = 0(asterisk marks) yields better performance for each value ofδ.
When a constant arrival with probability μ is appliedinstead of the realistic n-search, the behavior changes. Figure 9 shows that the refusal process works eﬀectively, since
Mod 2 with the refusal process (at the bottom) has smaller
op than Mod 3 without the refusal process (at the top). The
gap between three marks for the lines of each color for Mod
2 at the bottom of Fig. 9 resembles to that at the top of Fig. 8,
however the gap appears remarkably at δ = 0.8 (magenta

HAYASHI and ONO: TRAFFIC PROP. FOR STOCHASTIC ROUTING ON SF

1319

Fig. 8 The values of op for the ZRP (top) and Mod 1 (bottom) using
n-search. The open , ∗, and  marks correspond to α = 1.0, 0.0, and−1.0, respectively. The red, green, blue, and magenta lines correspond toδ = 0.0, 0.2, 0.5, and 0.8, respectively.

Fig. 9 The values of op for Mod 3 (top) and Mod 2 (bottom) at a constantarrival with probability μ = 0.01, instead of using n-search. The filled ,×, and  marks correspond to α = 1.0, 0.0, and −1.0, respectively. The
red, green, blue, and magenta lines correspond to δ = 0.0, 0.2, 0.5, and 0.8,
respectively.

lines) for Mod 3 in the top of Fig. 9. Although n-searchleads to a low arrival (lower than μ = 0.01) as shown in
Fig. 5, and reachability is not 100% even in the case of persistent packets after restarting, in the meaning of smaller op,
the ZRP is better than other models, by comparison with thecorresponding curves in Figs. 8 and 9.
We consider the other stochastic routing method inwhich a forwarding node k ∈ Ni is chosen with probabilityΠk ∝ Kk (m(k) + 1)−β ,(9)where β = 3 yields the maximum generation rate in a freeflow regime [13]. As shown in Fig. 10, in this optimal case,the behavior is similar to that in Mod 3 without the refusal
process at the top of Fig. 9, although it has better performance than Mod 3. There is a free-flow regime in the casewhen δ = 0.8 (the magenta line with filled upward-pointing
triangle marks) at a constant arrival rate. In this method, aforwarding node is dynamically selected in a balance between reducing distance by passing through large degree
nodes, and avoiding congestion. Thus, a further improve-

Fig. 10 The values of op for a traﬃc-aware routing [13] in which a forwarding node k is chosen by applying Eq. (9) in the cases of n-search (openmarks), and of a constant arrival with probability μ = 0.01 (filled marks).
The red, green, blue, and magenta lines correspond to δ = 0.0, 0.2, 0.5, and0.8, respectively.

IEICE TRANS. COMMUN., VOL.E94–B, NO.5 MAY 2011

1320

ment may be potentially expected in the tuning of the balance for α-random walks and other modifications.
5.

Conclusion

For a SF network, whose topology is found in many real systems, we have studied extensions of the ZRP [6], [7], [15],[20] which controls both the routing strategies in the preferential [9]–[11] and congestion-aware [12] walks, and thenode performance for packet transfers. Under the assumption of persistent packets, we have approximately analyzed
the phase transition between condensation of packets at hubs
and uncondensation on SF networks by another straightforward approach [6], [7] instead of the mean-field approximation in the preferential walk for α > 0 [16]. In particular,
we have found that uncondensation is maintained in a wide
rage of δ > δc ≈ (1 + α)/(γ − 1) for α < 0.
Moreover, we have numerically investigated the traffic properties when the practical n-search into a terminal
node at the last step takes place. The phase transition has
been consistently observed in the cases both with/without
n-search. The obtained results are summarized in Table 6.
We conclude that the wandering path for α < 0 better reduces mean travel time of a packet with high reachability
in the low-performance regime at a small δ, while in thehigh-performance regime at a large δ, neither the wandering long path with short wait trapped at nodes (α = −1),
nor the short hopping path with long wait trapped at hubs
(α = 1) is advisable. A uniformly random walk (α = 0)
yields slightly better performance. This optimality at α = 0
in a high-performance regime is consistent with the results
obtained for the critical generation rate in other traﬃc model[10] on a SF network with node capacity (corresponding
to the forwarding performance) proportional to its degree.
However, in the details for our traﬃc model, the optimalcase depends on a combination of the values of α and δ related to the condensation transition at δc . We emphasize
that, for high reachability, small number of hops, and shorttravel or wait time, such traﬃc properties summarized in Table 6 as the trade-oﬀ between a detour wandering path andlong wait at hubs cannot be obtained from only the theoretically predicted phase transition between condensation anduncondensation in Ref. [6], [7], [15], [16]. Concerning thefundamental traﬃc properties, we have investigated the congestion phenomenon with packet generation, compared withother models related to the traﬃc-aware routing [8], [13],[14]. We suggest that the high-forwarding performance ata large δ is more dominant than the refusal process in order to suppress congestion in a small op, and that the difference of op is small when the values of α are varied (thecase of α = 0 is slightly better for n-search). The above results only show qualitative tendencies. In further research,more complex and quantitative properties should be carefully discussed for many combinations of parameters α, δ,μ, η̄, m∗ , etc., although such simulations may be intractable
due to huge computation load and memory consumption forthe processing of millions of packets in very long iterations.

Table 6

Qualitative summary of the traﬃc properties.

Mean Value

α>0

α<0

for larger δReachability
Num. of Hops
Travel Time T a
One Wait T w / Nw
Num. of Wait Nw

low
small
long
long
small

high
large
short
short

increased 
increased 
decreased 
decreased 
increased 
decreased 

large
Characteristics
of a Path

condensation
at hubs

uniformly
wanderingThis direction of research on stochastic routing may be
the first step to reveal complex traﬃc dynamics such as thetrade-oﬀ between the selection of a short path and long wait(delay) at some particular nodes related to the underlying
network structure. We will investigate this problem, including the eﬀects of more realistic selections of the source andthe terminal nodes which depend on geographical positions
or population density, the queue discipline such as FIFO or
LIFO, and other topologies to develop the optimal routing
schemes [22] for advanced sensor or ad hoc networks.
Acknowledgment
The authors would like to thank anonymous meta-reviewer
and reviewers for their valuable comments. This research is
supported in part by a Grant-in-Aid for Scientific Researchin Japan, No. 21500072.
References[1] R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks,” Rev. Mod. Phys., vol.74, pp.47–97, 2002.
[2] K.-I. Goh, B. Kahng, and D. Kim, “Universal behavior of load distribution in scale-free networks,” Phys. Rev. Lett., vol.87, 278701,
2001.
[3] J. Urrutia, Handbook of Wireless Networks and Mobile Computing,ed. I. Stojmenović, Chap. 18, John Wiley & Sons, 2002.
[4] Z. Liu, W, Ma, H. Zhang, Y. Sun, and P.M. Hui, “An eﬃcientapproach of controlling traﬃc congestion in scale-free networks,”
Physica A, vol.370, pp.843–853, 2006.
[5] L. Zhao, Y.-C. Lai, K. Park, and N. Ye, “Onset of traﬃc congestionin complex networks,” Phys. Rev. E, vol.71, 026125, 2005.
[6] J.D. Noh, G.M. Shim, and H. Lee, “Complete condensation in azero range process on scale-free networks,” Phys. Rev. Lett., vol.94,
198701, 2005.
[7] J.D. Noh, “Stationary and dynamical properties of a zero-range process on scale-free networks,” Phys. Rev. E, vol.72, 056123, 2005.
[8] D. De Martino, L. Dall’Asta, G. Bianconi, and M. Marsili, “Congestion phenomena on complex networks,” Phys. Rev. E, vol.79,
015101(R), 2009.
[9] S. Ikeda, I. Kubo, N. Okumoto, and M. Yamashita, “ Impact of local
topological information on random walks on finite graphs,” Lect.
Notes Comput. Sci., vol.2719, pp.1054–1067, 2003.
[10] W.-X. Wang, B.-H. Wang, C.-Y. Yin, Y.-B. Xie, and T. Zhou, “Traffic dynamics based on local routing protocol on a scale-free network,” Phys. Rev. E, vol.73, 026111, 2006.
[11] G. Yan, T. Zhou, B. Hu, Z.-Q. Fu, and B.-H. Wang, “Eﬃcient routing
on complex networks,” Phys. Rev. E, vol.73, 046108, 2006.
[12] B. Danila, Y. Yu, S. Earl, J.A. Marsh, Z. Toroczkai, and K.E. Bassler,“Congestion-gradient driven transport on complex networks,” Phys.
Rev. E, vol.74, 046114, 2006.

HAYASHI and ONO: TRAFFIC PROP. FOR STOCHASTIC ROUTING ON SF

1321[13] W.-X. Wang, C.-Y. Yin, G. Yan, and B.-H. Wang, “Integrating local
static and dynamic information for routing traﬃc,” Phys. Rev. E,
vol.74, 016101, 2006.
[14] P. Echenique, J. Gómez-Gardeñes, and Y. Moreno, “Dynamics ofjamming transitions in complex networks,” Eupophys. Lett., vol.71,
pp.325–331, 2005.
[15] J.D. Noh, “Interacting particle systems in complex networks,”
arXiv:cond-mat/0701401, 2007.
[16] M. Tang, Z. Liu, and J. Zhou, “Condensation in a zero range process on weighted scale-free networks,” Phys. Rev. E, vol.74, 036101,
2006.
[17] A.E. Motter and Y.-C. Lai, “Cascade-based attacks on complex networks,” Phy. Rev. E, vol.66, 065102, 2002.
[18] A.E. Motter, “Cascade control and defense in complex networks,”
Phy. Rev. Lett., vol.93, 098701, 2004.
[19] J.J. Wu, Z.Y. Gao, and H.J. Sun, “Eﬀects of the cascading failures onscale-free traﬃc networks,” Physica A, vol.378, pp.505–511, 2007.
[20] J.D. Noh and H. Rieger, “Random Walks on Complex Networks,”
Phys. Rev. Lett., vol.92, no.11, 118701, 2004.
[21] M.R. Evans, “Phase Transitions in one-dimensional nonequilibrum
systems,” J. Phys., vol.30, pp.42–57, 2000.
[22] B. Tadic, G.J. Rodgers, and S. Thurner, “Transport on Complex
Networks: Flow, Jamming & Optimization,” Int. J. Bifurcation and
Chaos, vol.17, no.7, pp.2363–2385, 2007.

=
=

∞

l=1
∞

l=1

1−zKi

m Ki =zKiβ→β

1 − zKi

Kiβ
β
Kmax
− Kiβ

β
1 zKmax
mhub
=
,
β
N
N 1 − zKmax
Kmax −1(A· 1)zK β
P(K)dK.
(A· 2)
1 − zK β
Kmin

1
l
= ∞
By using the relation 1−x
l=0 x for Eq. (A· 2), we derive
ρn =

zK β
P(K)dK
1 − zK β∞
(zK β )l P(K)dK
zK β

ρn =
=

=

β

∼

l=1

(zK β )l K −γ dK

×

∞
β

(zKmax)lll=1(−γ+1)Kmaxβ)]× [− ln(1 − zKmaxβ∼ N −1 × ln(1 + mhub ) → 0,=(−γ+1)∼
for a large size N → ∞. In the last terms, we apply Kmax∞
−1
N from K P(K)dK ∼ 1/N, and
max

ln

∞

1
xl
= − ln(1 − x) =
,
1−x
l
l=1

= 1 + ρ s N = 1 + mhub > 0,from Eq. (A· 1). Since only ρ s remains, condensation occurs
at the hub for any α in case (D) at this uniform jumping rate
given by δ = 0.
In the general case where δ > 0, the infinite series inβ
Eq. (8) does not have a closed form, except for Fi (z) = ezKi
at δ = 1. We approximate the series as in [6], [7],The second term in the right-hand side is dominant forzKiβ ≥ 1. We can simply approximate it with a few lowestorder terms such as Fi (z) = 1+zKiβ +O((zKiβ )2 ) for zKiβ  1.
From Eq. (7) and ∂ ln Fi (z)/∂z for the above two casesof Fi (z), the mean occupation number is given bym Ki ≈zKiβ(zKiβ )1/δ

for
for

zKiβ  1
zKiβ ≥ 1.

Thus, the mean occupation number of a node increases
monotonically with its degree. Depending on a constantmagnitude of z, we consider the following two cases (i) and(ii).
(i) We assume that the fugacity z is in such a rangethat zKiβ ≥ 1 for all nodes. From mKi = (zKiβ )1/δ for
all nodes and the self-consistent equation ρ = N1 i mKi =β 1/δ
1 1/δ δβ/δ δ
) is valid onlyi (Ki ) , the solution z = ρ /( K̄Nz Kmaxdefβ/δ
β/δ
= K K P(K)dK remains finite in the limit
when K̄
minof large N. By using P(K) ∼ K −γ , at N → ∞, we have
Kmax

l=0
∞


(Kmax − 1)(βl−γ+1)
βl − γ + 1

1
Fi (z) ≈ √ (2π(zKiβ )1/δ )(1−δ)/2 × exp(δ(zKiβ )1/δ ).
δ,is divergent for the hub with the maximum degree Kmax asβin the range z < zc , because thez approaches zc = 1/Kmax
denominator becomes zero in the first term of the right-handside, equivalently to the case in which node i has the maximum degree in the second term. It is convenient to decompose the density into two terms such that ρ = ρ s + ρn forthe hub with the maximum degree and for the other nodes.
These two terms are given by
ρs =

zl

l=1
(−γ+1)Kmaxβ
1 − zKmax

As a modification to Refs. [6], [7], we briefly review thederivation of the results presented in Table 3.
For δ = 0: case (D), we have a constant jumping rateqi (ω) = 1 independent of the occupation number ω andω
Fi (z) = ω zKiβ = 1 β . Then, from Eq. (7),K βl−γ dK

⎫
⎧
∞ ⎪
β
(−γ+1)
⎪⎪⎬⎨ (zKmax )l × (Kmax ) ⎪
∼
⎪
⎪
⎪
⎪
⎭
⎩
βl

1
Appendixzl

K β/δ P(K)dK ∼(β/δ−γ+1)
K β/δ−γ dK → Kmax.

Kmin

From the negative exponent, this finite condition imposes

IEICE TRANS. COMMUN., VOL.E94–B, NO.5 MAY 20111322

that δ > δc with
def

δc =

β
.
γ−1

In this regime, we find mKi ∼ Kiβ/δ for all nodes. The occupation number at the hub with the maximum degree Kmax ∼N 1/(γ−1) scales sublinearly as mhub ∼ N β/δ(γ−1) = N δc /δ withthe exponent β/δ(γ − 1) = δc /δ < 1. Therefore, the extreme
condensation of almost all packets at the hub with Kmax is
avoided when δ > δc : case (A).
(ii) We assume that the fugacity z is defined as Kcβ =Then, the self1/z in the interval Kmin < Kc < Kmax . 
consistent equation becomes ρ = ρn + ρ s = i mKi , where
ρn =

Kc


zK β = Kc−β

Kc

K β P(K)dK,(A· 3)Kmin

Kmin

is the density for the nodes with K < Kc : zK β < 1, and
ρs =

K
max


(zK β )1/δ = Kc−β/δ

Kmax

K β/δ P(K)dK,(A· 4)Kc

Kc

is the density for the nodes with K > Kc : zK β > 1. Since
the integral part in Eq. (A· 3) is smaller than the average βpower of the degree, ρn vanishes as Kc−β in the limit of large
N. In order to have a finite value of ρ s = ρ, the integral partin Eq. (A· 4) should be divergent, which yields that δ ≤ δc =β/(γ−1). This integral should be of the same order as Kc−β/δ ,which yields
Kc ∼(ln Kmax )δc /β(Kmax )1−δ/δc

for
for

δ = δcδ < δc .

in cases (B) and (C), respectively.

Yukio Hayashi
was born in 1962. He received the B.E. and M.E. degrees in electricaland electronic engineering from Toyohashi University of Technology in 1985 and 1987, andDr. of Engineering degree in applied mathematics and physics from Kyoto University in 1995.
In 1987, he joined the Fuji Xerox Corporation.
From 1991 to 1994, he was with the ATR Auditory and Visual Perception Research Labs., andATR Human Information Processing ResearchLabs. Since 1997 he has been an Associate Professor in the School of Knowledge Science, Japan Advanced Institute of
Science and Technology. His current research interests include network
science, especially, evolutionary networks, distributed systems, ad hoc networks, P2P, social networking, community analysis, webology, and so on.
He is a member of JSIAM and IPSJ.

Yasumasa Ono
was born in 1981. He isa doctoral student in the School of Knowledge
Science, Japan Advanced Institute of Scienceand Technology. His research work is in complex network science. He is a student memberof IPSJ.