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

Title

Geographical effects on the path length and therobustness in complex networks

Author(s)Hayashi, Y; Matsukubo, J

Citation

Physical Review E : Statistical, Nonlinear, andSoft Matter Physics, 73(6): 066113‑1‑066113‑9

Issue Date

2006‑06

Type

Journal Article

Text version

publisher

URL

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

RightsYukio Hayashi and Jun Matsukubo, Physical Review
E, 73(6), 066113, 2006. "Copyright 2006 by theAmerican Physical Society."
http://scitation.aip.org/getabs/servlet/GetabsSer
vlet?prog=normal&id=PLEEE800007300000606611300000
1&idtype=cvips&gifs=Yes

Description

Japan Advanced Institute of Science and Technology

PHYSICAL REVIEW E 73, 066113 共2006兲

Geographical effects on the path length and the robustness in complex networks
Yukio Hayashi
Japan Advanced Institute of Science and Technology, Ishikawa, 923-1292, Japan

Jun Matsukubo
Kitakyusyu National College of Technology, Fukuoka, 802-0985, Japan
共Received 27 January 2006; published 9 June 2006兲
The short paths between any two nodes and the robustness of connectivity are advanced properties ofscale-free 共SF兲 networks; however, they may be affected by geographical constraints in realistic situations. We
consider geographical networks with the SF structure based on planar triangulation for online routings, andsuggest scaling relations between the average distance or number of hops on the optimal paths and the network
size. We also show that the tolerance to random failures and attacks on hubs is weakened in geographicalnetworks, and that even then it is possible for the extremely vulnerable ones to be improved by adding with thelocal exchange of links.
DOI: 10.1103/PhysRevE.73.066113

PACS number共s兲: 89.75.Fb, 89.20.Ff, 89.75.Da, 05.10.⫺aI. INTRODUCTION

Complex networks have been studied with great interest
inspired from physics to biology, computer science, andother fields, since the surprisingly common topological structure called a small-world 共SW兲 and scale-free 共SF兲 network
has been found in many real systems 关1–3兴. Such structure ischaracterized by the SW property 关2,3兴 that the average pathas the hop count between any two nodes is as short as that in
random graphs, and that the clustering coefficient, defined by
the average ratio of the number of links connecting to its
nearest neighbors of a node to the number of possible links
between all these nearest neighbors, is as large as that inregular graphs. As to the scale-free property 关1,2兴, the degree
distribution follows a power law P共k兲 ⬃ k−␥, 2 ⬍ ␥ ⬍ 3; thefat-tail distribution consists of many nodes with low degrees
and a few hubs with very high degrees. The heterogeneous
SF network has good properties; economical and efficient
communication by a small number of hops in a connected
network with a few links 关4兴 and robustness against failures关5兴. Moreover, the restriction of link lengths has been observed, e.g., the internet at both router and autonomous system levels 关6兴, road networks, and flight connections in a
major airline 关7兴. Indeed, the distribution of link lengths wasinversely proportional to the lengths 关6兴 or exponentially decaying 关8兴 in geographical space.
In this paper, we consider geographical SF network models for a number of research fields including urban planning,
electric circuits, distributed robots, sensor networks, andcommunication networks. In particular, we discuss the dynamic configuration of planar networks for ad hoc communication not limited by wired connections. The planarity isimportant to avoid interference of the wireless beam, or toconstruct communication lines on the surface of the earth.
Geographical SF networks have attracted much attention
from researchers recently. The interest includes not only thestatic topological structure 关9兴 and the robustness 关10兴 but
also the dynamics on them, such as cascading breakdown
关11兴, random walks 关12兴, synchronization 关13,14兴, magnetic
1539-3755/2006/73共6兲/066113共9兲

models 关15兴, competitive clusters 关16兴, epidemic spreading关17兴, and immunization 关18兴. The geographical SF networkmodels are categorized into three classes: the modulated
Barabási-Albert 共BA兲 model that has a penalty on the distance between connecting nodes 关19,20兴, SF networks embedded in lattices 关21,22兴, and space-filling networks
关17,23,24兴. A brief review of these models has been reported
关8兴. Unfortunately, except for the third class, crossing oflinks exists, and the positions of nodes are uniformly randomor fixed on a lattice. On the other hand, as a typical model inthe third class, a random Apollonian 共RA兲 network 关17,23兴
has some long-range links which cause dissipation of thebeam power or the construction cost of links, although it isbased on planar triangulation without crossing of links. Thus,to reduce the long-range links, we consider a modification of
the RA network preserving the good properties of SF structure on a planar space. Moreover, we investigate the tolerance of the connectivity in geographical and nongeographical rewired networks. We emphasize the effects ofgeographical structures on the path length and the robustness.
The organization of this paper is as follows. In Sec. II weintroduce dynamic configurations of networks based on planar triangulation for ad hoc communication, and propose amodified one to reduce long-range links. In Sec. III we numerically investigate both the paths of the shortest distanceand the minimum hops between two nodes, and suggest scaling laws of these paths. In Sec. IV, we show the geographicaleffect on the robustness against random failures and attacks
on hubs. Finally, in Sec. V we summarize these results andsuggest further studies.
II. GEOGRAPHICAL NETWORK MODELS
A. Planar triangulation

Planar triangulation is a mathematical abstraction of sensor or ad hoc networks, in which the positions of nodes aretemporarily fixed as service centers of backbone networks.
Thus, the mobility of the nodes is out of our scope to sim-

066113-1©2006 The American Physical Society

PHYSICAL REVIEW E 73, 066113 共2006兲

Y. HAYASHI AND J. MATSUKUBO

plify the discussion. In addition, the assumptions of different
transmission ranges 关25兴 and directed antennas 关26兴 are also
reasonable from the technological viewpoint. On suchgraphs, online routing algorithms 关27兴 that guarantee delivery of messages using only local information about positionsof the source, destination, and the adjacent nodes to a current
node in the routing have been developed. To find a paththrough exploration is required in many cases, since knowledge about the environment in which routing takes place is
not available beforehand, especially in ad hoc configurations
with evolution of networks. In any case, since the optimalrouting path depends on both topological and spatial structures of networks, as measures of the communication efficiency, the number of hops for transfer of a message and thepath length measured by Euclidean distance are crucial.
On the other hand, Delaunay triangulation 共DT兲, which isthe dual of a Voronoi diagram, is the optimal planar triangulation in some geometric criteria 关28兴 with respect to the
maximin angle and the minimax circumcircle of triangles on
a two-dimensional space, and widely used in practical applications for facility location and computer graphics 关29兴. It is
well known as a good property that the shortest path length
between any two nodes on a Delaunay graph is of the sameorder as the direct Euclidean distance, since the ratio of thepath length to the direct distance is bounded by a constant关30兴. However, the average number of minimum hops on thatgraph is unknown. One of the fundamental techniques forequipping such properties is diagonal flipping. In a Delaunay
triangulation, diagonal flips are globally applied to the triangles until the minimum angle is not increased by any exchange of diagonal links in a quadrilateral. Such a global
process is unsuitable for ad hoc networks. In contrast, RA
networks can be constructed by local procedures for subdivision of a randomly chosen triangle. Thus, we study thecommunication efficiency and the robustness in the typical
network models based on planar triangulation: DT in computer science, RA networks in complex network science, anda modification to bridge them.
B. Delaunay-like SF network

We briefly explain the deterministic and random Apollonian networks. A random Apollonian network 关17兴 is constructed from an initial triangulation of a polygon. Then, at
each time step, a triangle is randomly chosen, and a newnode is added inside the triangle and linked to its threenodes. We assume the new node is set at the barycenter ofthe chosen triangle. When all triangle faces are chosen for
subdivision at each hierarchical level, it is called a deterministic Apollonian network 关23,24兴. We note that recursive
graphs 关31兴 divided from each q-clique subgraph by adding a
new node and linking it to all the nodes of this subgraphinclude the case of triangulation from an initial tetrahedron at
q = 3. In addition, higher-dimensional Apollonian networks
have been discussed 关14,32,33兴. The topological propertiesof power-law degree distributions with exponent nearly 3,large clustering coefficient, disassortative degree-degree correlation, and an average small number of minimum hops
between any two nodes have been theoretically and numeri-

FIG. 1. 共Color online兲 Linking procedures in a Delaunay-like SF
network. On the middle and right, the 共light green and cyan兲 longrange links are changed to the intersected shorter 共dark red兲 ones inthe shaded triangles by diagonal flips. The dashed lines are newlinks from the barycenter, and form five new triangles with contours
given on the left 共the two black solid lines are removed after thesecond diagonal flip兲.

cally analyzed 关17,23,24兴. Although RA networks have theabove advanced SF properties and the SW effect with a small
diameter of the graph, some long-range links naturally appear near the boundary edges. To reduce the long-range
links, we propose a modified model from RA networks. The
main idea is based on a local strategy for connecting nodes at
distances as short as possible by adding the diagonal flips in
DT. The configuration procedures of the proposed network
are as follows.
共0兲 Set an initial planar triangulation on a space.
共1兲 At each time step, select a triangle at random and add
a new node at the barycenter. Then, connect the new node to
its three nodes temporarily. Moreover, by iteratively applying
diagonal flips, connect it to the nearest node 共or more than
one of the neighbor nodes兲 within a radius defined by the
distance between the new node and the nearest node of thechosen triangle. If there is no nearest node within the radius,
this flipping is skipped; therefore the new node is connectedto the three nodes.
共2兲 The above process is repeated until the required size N
is reached.
We have two variations with one nearest node and allneighbors in the local circle. Note that these nodes are limited to the ones connected by applying iterative diagonal
flips. We call our model RA+ NN 共one/all兲 which means a
combination of the triangulation in the RA model and rewiring to one or all nearest neighbors as denoted in parentheses.
Figure 1 illustrates the linking procedures by iterative diagonal flips: in the quadrilateral of shaded triangles, the diagonal link is exchanged with the corresponding 共dark red兲link for maximizing the minimum angle. Clearly, our proposed model belongs in a class of the maximum planar network with fixed order like the RA models 关17兴, because thenumbers of nodes, links, and faces are invariant through the
diagonal flips. Figure 2 shows the topological characteristicthat our RA+ NN 共one兲 model has the intermediate structure
between those of RA and DT models. The case of all neighbors is the same as that for one. We find that a heterogeneous
structure with dense and sparse parts is constructed in the
RA+ NN 共one/all兲 model. The dense part is more condensed
in the generation process even with the random selection of atriangle. The assignment of many nodes to active areas isrational, since it can be covered by a sum of small regions
within limited communication power. The dense-get-denser
rule may correspond to the subdivision of a service area ac-

066113-2

PHYSICAL REVIEW E 73, 066113 共2006兲

GEOGRAPHICAL EFFECTS ON THE PATH LENGTH AND¼

FIG. 2. Examples of random Apollonian 共RA兲 network, Delaunay triangulation 共DT兲, and our model 共RA+ NN兲, including the
combination of random triangulation and diagonal flips to the nearest node. At each time step, a triangle is randomly chosen for thesubdivision in each network; however, the triangulated structure ischanged through rewiring with diagonal flips even from the same
initial configuration.

FIG. 4. 共Color online兲 Distributions of 共a兲 degree P共k兲 and 共b兲
degree-degree correlation knn共k兲 defined by the average degree ofnodes adjacent to the nodes with degree k.

cording to increasing of the population with preference foraggregation.
III. EFFICIENCY FOR COMMUNICATION

FIG. 3. 共Color online兲 Numerical estimation of the power-law
degree distribution with exponential cutoff. 共a兲 Degree distribution
P共k兲. The red and 共more curved兲 cyan dashed lines show the approximations in the form k−␥ exp共−ak兲 with ␥ = 共N䉭 + N兲 / N⬇ 2.994, a = 0.03 for RA+ NN 共one兲, and a = 0.12 for RA+ NN 共all兲.
The black dashed line indicates the slope of 3. The cyan line for
RA+ NN 共all兲 deviates slightly because of ignoring the complex
configuration procedures in the approximate analysis. 共b兲 The cumulative rate a共t兲 of diagonal flips as a function of time step t.

We discuss the shortest path lengths and the minimum
hops between any two nodes in the networks. Through simulations, each network model is numerically investigated in
the averaging of 100 random realizations at size N = 1000
generated from the initial configuration of a square graphpositioned at 共±1 , ± 1兲 on a plane, adding the center at 共0,0兲
and the four diagonal links. We have similarly obtained thefollowing results for the other initial configurations of triangle and hexagon.
A. Degree and correlation

Degree distribution is one of the important statistical characteristics related to SF properties. Using a rate-equation approach to our model, similar to that in the RA model 关17兴, we
derive an approximate form of a power law with exponential

066113-3

PHYSICAL REVIEW E 73, 066113 共2006兲

Y. HAYASHI AND J. MATSUKUBO

FIG. 5. 共Color online兲 The average 共a兲 distance 具D典 ⬃ 共ln N兲␤d and 共b兲 number of hops 具L典 ⬃ N␣l on the optimal paths between any two
nodes in each network over 100 realizations at size N = 500, 1 , 00, 3,000, 5,000, 10,000. 共c兲, 共d兲 具D⬘典 ⬃ 共ln N兲␤d⬘ and 具L⬘典 ⬃ N␣l⬘ on the pathsof minimum hops and the shortest path, respectively. The dashed lines correspond to the numerical estimations whose exponents are shownin Table I as a function of size N.

cutoff P共k兲 ⬃ k−␥ exp共−ak兲 in the Appendix, and estimate theexponent ␥ and the parameter a which corresponds to theaverage rate of multiple diagonal flips. The occurrence of
cutoffs also observed in real networks 关34兴 is rather naturalfrom the constraint on addition of new links to a node. Figure 3共a兲 shows the agreement of our approximation with theobserved degree distribution. The cumulative rate a is numerically estimated by the average convergent value asshown in Fig. 3共b兲. When we have no nearest node in thelocal circle or can only decrease the minimum angle of thetriangles by any exchange of links, the diagonal flip is
skipped; therefore the rate is smaller than 1. Note that thetime step t is equivalent to the network size N, because a newnode is added at each time step.
Figure 4共a兲 shows that the degree distributions in RA,
RA+ NN 共one/all兲 , and DT models follow power-law,
power-law with exponential cutoff, and lognormal distributions, respectively. In other words, DT models are not SF,
while the other models are. Figure 4共b兲 shows different
degree-degree correlations; RA models have a negative slopeof knn共k兲, a disassortative correlation, RA+ NN 共one/all兲 have

weaker ones, while DT models have a positive slope of
knn共k兲, an assortative correlation. Although our models resemble RA models in the shape of the correlation, there exists the structural difference that the strong connections of
stubs in RA models are relaxed in our models 共see the starlike stubs at the four corners and the center in Fig. 2兲.
B. Path lengths and hops

We investigate, as a function of the size N, the average
distance of path length 具D典 on the shortest paths, the distance
具D⬘典 on the paths of minimum hops, the average number ofhops 具L典 on these paths, and the number of hops 具L⬘典 on the
shortest paths between any two nodes in geographical networks. The distance is defined by the sum of link lengths on
the path, and the average means a statistical ensemble over
the optimal paths in the above two criteria 共with respect todistance and hop兲 for each size N. Figures 5共a兲–5共d兲 showthat RA+ NN 共one兲 has the shortest distance and the intermediate number of hops in these models. With the nearly double
hops compared to those in the RA+ NN 共one/all兲 , DT model

066113-4

PHYSICAL REVIEW E 73, 066113 共2006兲

GEOGRAPHICAL EFFECTS ON THE PATH LENGTH AND¼

FIG. 6. 共Color online兲 Scaling laws of the average path lengths and hops for different network size. The dashed lines show theestimations and the symbols correspond to RA, DT, and RA+ NN 共one/all兲 as in Fig. 5.

are no longer optimal using this criterion of minimum hops.
Note that the shortest path and the path of minimum hops
may be distinct, these measures are related to the link cost or
delay and the load for transfer of a message. It is better toshorten both the distance and the number of hops; however
their constraints are generally conflicted 共see Fig. 5兲.
Figures 6共a兲–6共d兲 show the dependencies of average
shortest distances and minimum hops on the size, 具D典⬃ 共ln N兲␤d, 具D⬘典 ⬃ 共ln N兲␤d⬘, 具L典 ⬃ 共ln N兲␤l, and 具L⬘典
⬃ 共ln N兲␤l⬘, as rescaled plots from Figs. 5共a兲–5共d兲. We also
investigate the fitting of other polynomial forms, 具L典 ⬃ N␣land 具L⬘典 ⬃ N␣l⬘ in Figs. 6共e兲 and 6共f兲. Each exponent is numerically estimated as shown in Table I by the mean-squareerror 共MSE兲 method. The values of ␤d and ␤d⬘ differ from␥ − 1 ⬇ 2 numerically, suggesting that at the strong-disorder
limit 关35兴 only the longest link is dominant in the shortest
paths, although the values of ␤l and ␤l⬘ are relatively close to
2. Since each network has various link lengths 关36兴, thestrength of disorder may affect these differences. In addition,
the values of ␣l and ␣l⬘ are close to 1 / 3 predicted at the limit
关35,37兴 for the Erdös-Rényi 共ER兲 model as the classical random network and the Watts-Strogatz 共WS兲 model as a SW

066113-5

PHYSICAL REVIEW E 73, 066113 共2006兲

Y. HAYASHI AND J. MATSUKUBOTABLE I. Estimated values of the exponents in the forms
具D典 ⬃ 共ln N兲␤d, 具D⬘典 ⬃ 共ln N兲␤d⬘, 具L典 ⬃ 共ln N兲␤l, 具L⬘典 ⬃ 共ln N兲␤l⬘,
具L典 ⬃ N␣l, 具L⬘典 ⬃ N␣l⬘ by the MSE method for each network.
Network model

␤d

␤⬘d

␣l

␣l⬘

␤l

␤l⬘

RA
DT
RA+ NN 共one兲
RA+ NN 共all兲

0.012−0.068−0.080−0.106−0.039
0.416
0.151
0.320

0.121
0.332
0.213
0.216

0.136
0.455
0.341
0.346

0.920
2.525
1.622
1.641

1.036
3.452
2.587
2.628

network 关3兴. The nearest ␣l is in the DT, probably because
the lognormal degree distribution resembles the unimodal
shapes in ER and WS models rather than a power law. In allcases of Figs. 6共a兲–6共f兲, we obtain straight lines suggesting
as the existence of the above scaling relations. The shortlines are due to the limitation of network size in our computational power, since the size needs to be enlarged on the
more than the order of 106 for the extension of lines in thelogarithmic form with small exponents.
IV. TOLERANCE TO FAILURE OR ATTACK

The fault tolerance and attack vulnerability are known as
typical SF properties 关5兴. We compare the tolerance in thegiant component 共GC兲 of geographical and nongeographicalrewired networks with the same degree distribution 关38兴 byignoring the planarity and the link length, when a small fraction f of nodes is removed. We should remark that all networks have the same average degree 具k典 = 2共3N − 7兲 / N= 5.986 and the minimum degree kmin = 3 at the initial state
before removal of nodes.
Figure 7共a兲 shows the relative size S / N for the fraction of
random failures in RA, DT, and our models, where S denotes
the average size of the GC over the 100 realizations. The
robustness in DT models is at the same level with the othersin spite of being a non-SF network. Figure 7共b兲 shows theresults in randomly rewired networks, whose high tolerance
is similar to that in the BA model 关5兴 without geographicalstructure. Figures 7共c兲 and 7共d兲 show the average sizes ofisolated clusters except for the GC. At the peak, the GC
breaks off and is divided into small clusters. The values of
the critical fraction f c are summarized in Table II. By thegeographical effect, it becomes weaker in the order of RA,
RA+ NN 共one/all兲, and DT models, in which the degree distribution varies from a pure power law to a strong cutoff.
These results are not contradictory to the theoretical prediction of a power-law degree distribution with exponential cutoff 关39兴, since the average degree 具k典 is not constant, but getssmaller as the cutoff gets stronger; therefore, the connectivity

FIG. 7. 共Color online兲 Relative sizes S / N of the GC against random failures in 共a兲 the geographical and 共b兲 the rewired networks. 共c兲, 共d兲
The corresponding average size 具s典 of isolated clusters other than the GC.
066113-6

GEOGRAPHICAL EFFECTS ON THE PATH LENGTH AND¼

PHYSICAL REVIEW E 73, 066113 共2006兲

TABLE II. The critical fraction f c of removed nodes in thegeographical and the nongeographical rewired networks 共denotedby geo. and rew., respectively兲. At the critical point, the average
size 具s典 of isolated clusters shows a peak, and the GC disappears.
See Figs. 7共c兲, 7共d兲, 8共c兲, and 8共d兲.

networks. By the geographical effect, each network also becomes more vulnerable than the rewired version. Thus, evenwith the same degree distribution, the robustness can be
drastically changed by geographical constraints such as thestrong connections of stubs that cover wide areas. Note thatthe weakly inhomogeneous DTs are different from a homogeneous random network, which has the same behavior
against failures and attacks at a fraction of removed nodes
关5兴.

Random failure

Hub attack

Removed-nodes
network model

geo.

rew.

geo.

rew.

RA
DT
RA+ NN 共one兲
RA+ NN 共all兲

0.36
0.58
0.5
0.52

0.8
0.78
0.8
0.8

0.005
0.3
0.03
0.04

0.25
0.58
0.48
0.52

is weaker; however, the corresponding strength of cutoff is in
the inverse order of our results.
On the other hand, against attacks on hubs selected indecreasing order of degree, Figs. 8共a兲–8共d兲 show the improvements in RA+ NN 关one 共all兲兴 from the extremely vulnerable RA model. Under a fixed 具k典, it is consistent with theprevious result 关17兴 that RA networks are less robust than a
SW network with a unimodal degree distribution as in DT

V. CONCLUSION

We study the communication efficiency and the robustness of geographical network RA 关17,23兴 and DT 关28,29兴
models based on planar triangulation for sensor or ad hoc
systems. In such networks, efficient online routing algorithms 关27兴 can be applied, and the delivery of a message isguaranteed by using only local information. Moreover, toreduce the long-range links in RA models, we propose amodified model whose degree distribution is approximately
derived as a power law with exponential cutoff.
We numerically investigate the shortest paths and theminimum hops between two nodes in these models, and sug-

FIG. 8. 共Color online兲 Relative sizes S / N of the GC against attack on hubs in 共a兲 the geographical and 共b兲 the rewired networks. 共c兲, 共d兲
The corresponding average size 具s典 of isolated clusters other than the GC.
066113-7

PHYSICAL REVIEW E 73, 066113 共2006兲

Y. HAYASHI AND J. MATSUKUBO

gest the universal scaling laws of the average shortest path
length 具D典 ⬃ 共ln N兲␤d and of the minimum hop 具L典 ⬃ N␣l,similar to the case at the strong-disorder limit 关35兴. However,
it is unclear what topological and spatial characteristics depend on the different values of exponents. A possible finitesize effect is also a further issue in comparing various network generation methods. From the simulation results, weconclude that RA networks have a path connected by a few
hops but the path lengths tend to be long, including somelong-range links, while DT networks have a zigzag path connected by many hops but each link is short. In contrast to thesuperior geometric properties 关28兴, DT networks are nolonger optimal in this criterion of the minimum hops. Ourmodel is totally balanced: the shortest path length is the best,with an intermediate number of hops; the good result may berelated to tradeoff optimization 关40兴. In addition, we find thatthe tolerance to failures and attacks is weakened by the geographical effect. In particular, RA models with a pure powerlaw degree distribution are extremely vulnerable. The geographical effect is consistent with the theoretical prediction
for a general class of networks and numerical simulations forlattice-embedded SF networks 关10兴. The improvement of robustness by random rewirings 关41兴 is probably based on acommon mechanism: the majority of small-order cycles
共connected with small hops兲 crucially influence the percolation threshold 关10兴.
On the other hand, although DT models are the most robust among those investigated, it requires global configuration procedures that are unsuitable for ad hoc communication. Thus, there is a tradeoff between the localization andthe robustness. However, the existence of robust non-SF networks is worth noting. We will further investigate the above
effect in wider classes related to a family of SF networks,
and also discuss a rapid recovery method by complementary
rewiring of the damaged parts.

When some links are removed from a node by multiple diagonal flips as shown in Fig. 1, the dynamical equation of thenumber of nodes n共k , N兲 with degree k at the size N is givenbyn共k + 1,N + 1兲 =

冉

冊

k+1
k
n共k,N兲 + 1 −n共k + 1,N兲
N䉭
N䉭
−a

k
n共k + 1,N兲,N䉭

where N䉭 and a denote the number of triangles and the average rate of multiple diagonal flips, respectively. The firstand second terms in the right-hand side correspond to thepreferential attachment through random selection of a triangle, and the third term is the statistical rewiring effect bymultiple diagonal flips. Note that there is no other reason for
decreasing the degrees. We neglect the other effects such asadditional links to nodes with low degrees, because we focus
on the tail of the degree distribution.
By using P共k兲 = n共k , N兲 / N, we haveN䉭 + N
P共k + 1兲 + k共P共k + 1兲 − P共k兲兲 + akP共k + 1兲 = 0.
N
From the continuous approximation dp / dk ⬇ P共k + 1兲 − P共k兲
defand ␥ = 共N䉭 + N兲 / N, it is rewritten askdp= − 共␥ + ak兲p.
dk

We approximately derive an exponential decay in the tailof the degree distribution for the proposed network model.

Thus, we obtain the solution p共k兲 ⬃ k−␥ exp共−ak兲 for large
N. Furthermore, the finite-size effect may be estimated more
precisely in the mean-field approximation by using generating function approaches 关42兴, and the random walk algorithm关43兴 to generate a network is useful for discussing the statistical fluctuation in the degree and the scaling law.

关1兴 A.-L. Barabási, Linked: The New Science of Networks 共Perseus, Cambridge, MA, 2002兲.
关2兴 M. Buchanan, Nexus: Small Worlds and the Groundbreaking
Theory of Networks 共W. W.Norton, New York, 2002兲.
关3兴 D. J. Watts, Six Degrees: The Science of a Connected Age
共W.W.Norton, New York, 2003兲.
关4兴 R. F. i Cancho and R. V. Solé, in Statistical Mechanics inComplex Networks, edited by R. Pastor-Satorras, M. Rubi, and
A. Diaz-Guilera, Lecture Notes in Physics Vol. 625 共Springer,
Berlin, 2003兲, Chap. 5.
关5兴 R. Albert and A.-L. Barabási, Nature 共London兲 406, 378
共2000兲.
关6兴 S.-H. Yook, H. Jeong, and A.-L. Barabási, Proc. Natl. Acad.
Sci. U.S.A. 99, 13382 共2002兲.
关7兴 M. T. Gastner and M. E. J. Newman, Eur. Phys. J. B 49共2兲,
247 共2006兲.
关8兴 Y. Hayashi, IPSJ Journal 47, 776 共2006兲. Special issue on

network ecology science, http://www.jstage.jst.go.jp/article/
ipsjdc/2/0/2_155
关9兴 C. Herrmann, M. Barthélemy, and P. Provero, Phys. Rev. E
68, 026128 共2003兲.
关10兴 L. Huang, L. Yang, and K. Yang, Europhys. Lett. 72, 144
共2005兲.
关11兴 L. Huang, L. Yang, and K. Yang, Phys. Rev. E 73, 036102
共2006兲.
关12兴 Z. G. Huang, X.-J. Xu, Z.-X. Wu, and Y.-H. Wang, e-printcond-mat/0601357.
关13兴 P. G. Lind, J. A. C. Gallas, and H. J. Herrmann, Phys. Rev. E
70, 056207 共2004兲.
关14兴 Z. Zhang, L. Rong, and F. Comellas, Physica A 364, 610
共2006兲.
关15兴 R. F. S. Andrade, and H. J. Herrmann, Phys. Rev. E 71,
056131 共2004兲.
关16兴 A. A. Moreria et al., e-print cond-mat/0603272.

APPENDIX

066113-8

GEOGRAPHICAL EFFECTS ON THE PATH LENGTH AND¼

PHYSICAL REVIEW E 73, 066113 共2006兲

关17兴 T. Zhou, G. Yan, and B.-H. Wang, Phys. Rev. E 71, 046141
共2005兲.
关18兴 L. Huang, L. Yang, and K. Yang, e-print physics/0503147.
关19兴 S. S. Manna and P. Sen, Phys. Rev. E 66, 066114 共2002兲.
关20兴 R. Xulvi-Brunet and I. M. Sokolov, Phys. Rev. E 66, 026118
共2002兲.
关21兴 C. P. Warren, L. M. Sander, and I. M. Sokolov, Phys. Rev. E
66, 056105 共2002兲.
关22兴 D. ben-Avraham, A. F. Rozenfeld, R. Cohen, and S. Havlin,
Physica A 330, 107 共2003兲.
关23兴 J. P. K. Doye and C. P. Massen, Phys. Rev. E 71, 016128
共2004兲.
关24兴 J. S. Andrade, Jr., H. J. Herrmann, R. F. S. Andrade, and L. R.
da Silva, Phys. Rev. Lett. 94, 018702 共2005兲.
关25兴 X.-Y. Li, W.-Z. Song, and Y. Wang, ACM Wireless Netw. 11,
255 共2005兲.
关26兴 Z. Huang, C.-C. Shen, C. Srisathapornphat, and C. Jaikaeo, inProceedings of the 11th International Conference on Computer
Communication and Networks 共IEEE, 2002兲 , pp. 16—21.
关27兴 P. Bose and P. Morin, SIAM J. Comput. 33 937 共2004兲.
关28兴 K. Imai, IEICE Trans. Inf. Syst., 83-D共3兲, 428 共2000兲.
关29兴 A. Okabe, B. Boots, K. Sugihara, and S. N. Chiu, Spatial
Tessellations, 2nd ed. 共John Wiley, New York, 2000兲.
关30兴 J. M. Keil and C. A. Gutwin, Discrete Comput. Geom. 7, 13
共1992兲.
关31兴 F. Comellas, G. Fertin, and A. Raspaud, Phys. Rev. E 69,
037104 共2004兲.

关32兴 Z. Zhang, F. Comellas, G. Fertin, and L. Rong, J. Phys. A 39,
1811 共2006兲.
关33兴 Z. Zhang and L. Rong, e-print cond-mat/0511609.
关34兴 L. A. N. Amaral, A. Scala, M. Barthélemy, and H. E. Stanley,Proc. Natl. Acad. Sci. U.S.A. 97共21兲, 11149 共2000兲.
关35兴 L. A. Braunstein, S. V. Buldyrev, R. Cohen, S. Havlin, and H.
E. Stanley, Phys. Rev. Lett. 91, 168701 共2003兲.
关36兴 Y. Hayashi and J. Matsukubo, in Proceedings of ICCS2006,
Lecture Notes in Computer Science Vol. 3993 共Springer, New
York, 2006兲, Part. III, pp. 1106–1113; in Proceedings of Adaptation in Artificial and Biological Systems 2006, Vol. 3, pp.
120–127.
关37兴 R. Cohen, S. Havlin, and D. ben-Avraham, in Handbook ofGraphs and Networks, edited by S. Bornholdts and H. G.
Shuster 共Wiely-VCH, New York, 2002兲, Chap. 4.
关38兴 S. Maslov, K. Sneppen, and A. Zaliznyak, Physica A 333, 529
共2004兲.
关39兴 D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J.
Watts, Phys. Rev. Lett. 85, 5468 共2000兲.
关40兴 J. I. Alvarez-Hamelin and N. Schabanel, Eur. Phys. J. B 38,
231 共2004兲.
关41兴 A. Beygelzimer, G. Grinstein, R. Linsker, and I. Rish, Physica
A 357, 593 共2005兲.
关42兴 P. L. Krapivsky, and S. Redner, J. Phys. A 35, 9517 共2002兲.
关43兴 T. S. Evans and J. P. Saramäki, Phys. Rev. E 72, 026138
共2005兲.

066113-9