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

Title

Improvement of the robustness on geographicalnetworks by adding shortcuts

Author(s)Hayashi, Yukio; Matsukubo, Jun

Citation

Physica A: Statistical Mechanics and its
Applications, 380: 552‑562

Issue Date

2007‑07‑01

Type

Journal Article

Text version

author

URL

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

RightsNOTICE: This is the author s version of a work
accepted for publication by Elsevier. Changes
resulting from the publishing process, including
peer review, editing, corrections, structuralformatting and other quality control mechanisms,
may not be reflected in this document. Changes
may have been made to this work since it was
submitted for publication. A definitive version
was subsequently published in Yukio Hayashi, Jun
Matsukubo, Physica A: Statistical Mechanics andits Applications, 380, 2007, 552‑562,
http://dx.doi.org/10.1016/j.physa.2007.02.080

Description

Japan Advanced Institute of Science and Technology

arXiv:physics/0612065v1 [physics.comp-ph] 7 Dec 2006

Improvement of the robustness on
geographical networks by adding shortcuts
Yukio Hayashi a, Jun Matsukubo ba Japan Advanced Institute of Science and Technology, Ishikawa 923-1292, Japanb Kitakyusyu National College of Technology, Fukuoka 802-0985, Japan

Abstract
In a topological structure affected by geographical constraints on liking, the connectivity is weakened by constructing local stubs with small cycles, a somethingof randomness to bridge them is crucial for the robust network design. In this paper, we numerically investigate the effects of adding shortcuts on the robustness in
geographical scale-free network models under a similar degree distribution to theoriginal one. We show that a small fraction of shortcuts is highly contribute to improve the tolerance of connectivity especially for the intentional attacks on hubs.
The improvement is equivalent to the effect by fully rewirings without geographicalconstraints on linking. Even in the realistic Internet topologies, these effects are
virtually examined.
Key words: Complex network; Geographical constraint; Overhead bridge; Robust
connectivity; Efficient routing
PACS: 89.75.-k, 89.75.Fb, 05.10.-a1Introduction

In many social, technological, and biological networks, there exist several common topological characteristics which can be emerged by simple generation
mechanisms [1,2], and a small fraction of networks crucially influences thecommunication properties for the routing and the robustness of connectivity.
One of the sensational facts is the small-world (SW) phenomenon: each pairof nodes are connected through relatively small number of hops to a huge network size defined by the total number of nodes. This favorable phenomenon
has been explained by the SW model with a small fraction of random rewirings
on a one-dimensional lattice [3]. Another fact is the scale-free (SF) structurethat follows a power-law degree distribution P (k) ∼ k −γ , 2 < γ < 3, consists
Preprint submitted to Elsevier

1 December 2008

of many nodes with low degrees and a few hubs with high degrees. The heterogeneous networks are drastically broken into many isolated clusters, when onlya small fraction of high degree nodes are removed as the intentional attacks[4,5]. However, the SF structure is robust against random failures [4,6], andwell balanced in the meaning of both economical and efficient communication
by small number of hops in a connected network as few links as possible [7].
On the other hands, real complex networks, such as power-grid, airline flightconnection, and the Internet, are embedded in a metric space, and long-range
links are restricted [8,9] for economical reasons. Based on the connection probability according to a penalty of distance r between two nodes and on random
triangulation, the generation mechanisms of geographical SF networks havebeen proposed in lattice-embedded scale-free (LESF) [10] and random
Apollonian (RA) [11,12] network models. Unfortunately, the vulnerability ofconnectivity has been numerically found in both networks [13,14,15]. Moreover, it has been theoretically predicted [13] in a generating function approach
to more general networks with any degree distribution that a geographical constraint on linking decreases the tolerance to random failures, since the percolation threshold is increased by the majority of small-order cycles that locallyconnected with a few hops. As the smallest-order, triangular cycles tend to beparticularly constructed by a geographical constraint.
In contrast, it has been suggested that higher-order cycles connected withmany hops improve the robustness in the theoretical analysis on a one-dimensional
SW model modified by adding shortcuts between two nodes out of the connected neighbors [16,17]. Similarly, the expected delivery time of any decentralized search algorithm without global information is decreased on a twodimensional lattice whose each node has a shortcut with the connection probability proportional to the power of distance r −α , α > 0 [18]. These results
support the usefulness of shortcuts for maintaining both the robust connectivity and the communication efficiency, however the network structures arealmost regular and far from the realistic SF. Recently, it has been numerically shown [15] that the robustness is improved by fully random rewirings
under a same degree distribution [19] in typical geographical network models:Delaunay triangulation (DT) [20,21], RA, and Delaunay-like scale-free(DLSF) networks [15]. Instead of rewirings, we expect the shortcut effect on the
improvement of robustness in such geographical SF networks. Adding shortcuts is practically more natural rather than rewirings, because the alreadyconstructed links are not wastefully discarded. Thus, we investigate how large
connected component still remains at a rate of removed nodes as the random
failures and the targeted attacks on hubs in the geographical SF networks
with shortcuts, comparing the original ones without shortcuts. We show thata small quantity of geographical randomness highly contributes to maintainboth the communication efficiency and the robustness under almost invariant
degree distributions to the original ones. It is not trivial that the improvement2

of robustness is equivalent to the effect by fully random rewirings.
The organization of this paper is as follows. In Sec. 2, we briefly introduce
the geographical networks based on planar triangulation and embedding in a
lattice under a given power-law degree distribution. In Sec. 3, we numericallyinvestigate the effects of shortcuts on the optimal paths in two measures of
distance/hop and the robustness in the geographical networks. In particular,
we show that a degree cutoff enhances the improvement of the error and attack
tolerance. Moreover, we virtually examine the effects for realistic data of theInternet topologies. Finally, in Sec. 4 we summarize these results.

2

Geographical SF networks

2.1 Planar network models

Planar networks without crossing of links are suitable for efficient geographical routings, since we can easily find the shortest path from a set of edgesof the faces that intersect the straight line between the source and terminal.
In computer science, online routing algorithms [22] that guarantee delivery of
messages using only local information about positions of the source, terminal,
and the adjacent nodes to a current node are well-known. As a connection to
SF networks, we consider Delaunay triangulation (DT) and random Apollonian (RA) network models based on planar triangulation of a polygonal region.
DT is the optimal planar triangulation in some geometric criteria [20] withrespect to the maximin angle and the minimax circumcircle of triangles on
a two-dimensional space. In addition, the ratio of the shortest path length isbounded by a constant factor to the direct Euclidean distance between any
source and terminal [23], while RA network belongs to both SF and planar
networks [12,11], however long-range links inevitably appear near the edgesof an initial polygon. To reduce the long-range links, Delaunay-like scale-free(DLSF) network has been proposed [15].
On the preliminaries, just like overhead highways, we add shortcuts between
randomly chosen two nodes excluding self-loops and multi-links after constructing the above networks. For adding shortcuts, the routing algorithm canbe extended as mentioned in Appendix 1. Note that the added shortcuts contribute to create some higher-order cycles which consists of a long path andthe overhead bridge in the majority of triangular cycles. The original degree
distributions without shortcuts follow a power-law with the exponent nearly 3
in RA, log-normal in DT, and power-law with an exponential cutoff in DLSF
networks [15]. Note that the lognormal distribution has an unimodal shape as
similar to one in Erdös-Renyi random networks. Thus, RA and DLSF networks
3are vulnerable because of double constraints of planarity and geographical distances on the linkings, but DT networks are not so. We have confirmed thatthe degree distributions have only small deviation from the original ones at
shortcut rate up to the amount of 30% of the total links.

2.2 Lattice-embedded SF networks
Let us consider a d-dimensional lattice of size R with the periodic boundary
conditions. The LESF network model [10] combines the configuration model[24] for any degree distribution with a geographical constraint on a lattice.
Although the homogeneous positioning of nodes differs from a realistic spacial
distribution such as in the Internet routers according to the population density[8], it has been studied as a fundamental spacial model. Note that the spatial
distribution of nodes is restricted on the regular lattice, some links are crossed,
therefore LESF networks are not planar.
In the following simulation, we assign a degree taken from the distribution
P (k) ∼ k −3 to each node on a two-dimensional lattice of the network size
N = 32 × 32, where γ = 3, d = 2, and R = 32. The networks have the average
numbers M ≈ 1831 of the total links at A = 1 and M ≈ 2673 at A = 3 forcomparison. The case of A → ∞ is equivalent to the Warren-Sander-Sokolov
model [25] whose degree distribution follows a pure power-law, however a cutoff is rather natural in real networks with something of constraints on linkings[26]. As similar to the previously mentioned planar networks, there are little
deviation form the original power-law distributions with strong and weak cutoffs at A = 1 and A = 3, respectively. The detailed configuration proceduresfor RA, DT, DLSF, and LESF networks are summarized in Appendix 2.

3

Shortcut effects

3.1 Shortest distance and minimum hops
For the shortcut rates from 0% to 30%, we investigate four combinations of
distance/hops and two kinds of the optimal paths with respect to the shortest
distance and the minimum number (or called length) of hops: the average
distance hDi on the shortest paths, the distance hD ′ i on the paths of the minimum hops, the average number of hops hLi on these paths, and the numberof hops hL′ i on the shortest paths between any two nodes in the geographicalnetworks. The prime denotes the cross relation to the case of no prime inthe combinations of the measures and the two kinds of paths. The distance is4defined by a sum of link lengths on the path, and the average means a statistical ensemble over the optimal paths in the above two criteria. Note thatthe shortest path and the path of the minimum hops may be distinct, these
are related to the link cost or delay and the load for transfer of a message. It
is better to shorten both the distance and the number of hops, however theconstraints are generally conflicted.
<D> on shortest in RA<D’> on min. hops in RA<D> on shortest in DLSF
<D’> on min. hops in DLSF
<D> on shortest in DT<D’> on min. hops in DT<D> and <D’>

2
1.8
1.6

<L> on min. hops in RA<L’> on shortest in RA<L> on min. hops in DLSF
<L’> on shortest in DLSF
<L> on min. hops in DT<L’> on shortest in DT

20<L> and <L’>

2.2

1.4
1.2
1

15

10

5

0.8
0.6
0

5

10

15

20

25

0
0

30

5

10

15

20

25

30

Shortcutted Rate

Shortcutted Rate(a) average distance(b) average number of hops

Fig. 1. The average distance and the number of hops on two kinds of the optimal
paths in DT (triangle), RA (circle), DLSF (plus) networks. Solid lines guide thedecreasing or increasing of hDi and hL′ i on the shortest paths, dashed lines guidethat of hD ′ i and hLi on the paths of the minimum hops.
2.2

30<D> on shortest at A=1<D’> on min. hops at A=1<D> on shortest at A=3<D’> on min. hops at A=3

1.8
1.6
1.4
1.2
0

<L> on min. hops at A=1<L’> on shortest at A=1<L> on min. hops at A=3<L’> on shortest at A=3

25<L> and <L’>

<D> and <D’>

2

20
15
10
5

5

10

15

20

25

0
0

30

5

10

15

20

25

30

Shortcutted Rate

Shortcutted Rate(a) average distance(b) average number of hops

Fig. 2. The average distance and the number of hops on two kinds of the optimal
paths in LESF networks at A = 1 (open rectangle) and A = 3 (filled rectangle).
Solid lines guide the decreasing or increasing of hDi and hL′ i on the shortest paths,
dashed lines guide that of hD ′ i and hLi on the paths of the minimum hops.

In the original networks without shortcuts, we note the tendencies [15]: RA
networks have a path connected by a few hops but the path length tend to belong including some long-range links, while DT networks have a zig-zag pathconnected by many hops but each link is short, in addition, DLSF networks
have the intermediately balanced properties. Figure 1 shows numerical resultsin adding shortcuts to the planar networks. We find that, from the solid anddashed lines in Figs. 1(a)(b), the average distance hDi and the number ofhops hLi become shorter as increasing the shortcut rate. In particular, the5

shortcuts are effective for the distance in RA and DLSF (solid lines marked
with circles and pluses) networks, and also for the number of hops in DTs(dashed line marked with triangles). On another measures of hD ′ i and hL′ i, thedashed lines for DTs (marked with triangles) and RA (with circles) networks
in Fig. 1(a) and the solid lines for RA (with circles) and DLSF (with pluses)
networks in Fig. 1(b) approach to each other. Thus, the shortcuts even around
10% decrease both hDi and hLi, and maintain small hD ′ i and hL′ i. On theother hand, as shown in Fig. 2, the average distance and the number of hops
are almost constant in LESF networks. Probably, the links emanated fromhubs already act as shortcuts on the lattice. These results are obtained fromensembles over 100 realizations for each network model.

3.2 Robustness of connectivity

The fault tolerance and attack vulnerability are known as the typical properties of SF networks [4], which are further affected by geographical constraints.
We investigate the tolerance of connectivity in the giant component (GC) of
the geographical networks with shortcuts comparing with that of the originalones without shortcuts. The size S of GC and the average size hsi of isolated
clusters are obtained from ensembles over 100 realizations for each networkmodel. Figure 3 shows the typical results that a small fraction of shortcuts
suppresses the breaking of the GC against random failures. It seems to beenough in less than 10%. In other DLSF, LESF (A = 3) networks, the effects
are similar. Thus, the added shortcuts strengthen the tolerance in comparison
with each original network.
Figures 4 and 5 show the effect of shortcuts on the robustness against thetargeted attacks on hubs. In particular, around the shortcuts rate 10%, theextremely vulnerable RA and DLSF networks are improved up to the similarlevel to DTs. We compare the critical values of fraction fc of removed nodes atthe peak of the average size hsi, as the GC is broken off. As shown in Figure7(b), the critical values fc in RA and DLSF networks reach to 0.3 at the level ofthe original DTs without shortcuts. It is consistent with the effect in evolving
networks with local preferential attachment [27] that the tolerance becomes
higher as increasing the cutoff under the same average degree hki and size N.
We emphasize that, by adding shortcuts around 10% under almost invariant
degree distributions, the robustness against the intentional attacks can beconsiderably improved up to the similar level to the fully rewired networks byignoring the geographical constraints [15].
The effects on LESF networks by adding shortcuts are also obtained in Fig. 6.
The case of A = 3 is more robust because of less geographical constraint witha larger number M of the total links. Figures 7(c)(d) shows the improvement
6

1
0%
3%
5%
7%
10%
20%
30%

0.7
0.6

0.8

Relative size S/N

Relative size S/N

0.8

1

0%
3%
5%
7%
10%
20%
30%

0.9

0.5
0.4

0.7
0.6

0.8

0.5
0.4

0.7
0.6
0.5
0.4

0.3

0.3

0.3

0.2

0.2

0.2

0.1

0.1

0
0

0.2

0.4

0.6

0.8

0.1

0
0

1

0%
3%
5%
7%
10%
20%
30%

0.9

Relative size S/N

1
0.9

0.2

0.4

Fraction f of failures

0.6

0.8

0
0

1

0.2

0.4

Fraction f of failures(a) DT

0.6

0.8

1

Fraction f of failures(b) RA(b) LESF at A = 1

Fig. 3. (Color online) Typical results of the relative size S/N of the GC against
random failures in (a) DT, (b) RA, and (c) LESF (A = 1) networks at the shortcuts
rates in legend.

1
0%
3%
5%
7%
10%
20%
30%

0.7
0.6

0.8

Relative size S/N

Relative size S/N

0.8

1
0%
3%
5%
7%
10%
20%
30%

0.9

0.5
0.4

0.7
0.6

0.8

0.5
0.4

0.7
0.6
0.5
0.4

0.3

0.3

0.3

0.2

0.2

0.2

0.1

0.1

0
0

0.2

0.4

0.6

0.8

0.1

0
0

1

0%
3%
5%
7%
10%
20%
30%

0.9

Relative size S/N

1
0.9

0.2

0.4

Fraction f of attacks

0.6

0.8

0
0

1

0.2

0.4

Fraction f of attacks(a) DT

0.6

0.8

1

Fraction f of attacks(b) RA(c) DLSF

Fig. 4. (Color online) Relative size S/N of the GC against intentional attacks in (a)DT, (b) RA, and (c) DLSF networks at the shortcuts rates in legend.

1
0

0.2

0.4

0.6

Fraction f of attacks(a) DT

0.8

1

14
12
10
8
6

0%
3%
5%
7%
10%
20%
30%

2

Average size 
 of isolated clusters

1.5

16

Average size 
 of isolated clusters

2

25
2.5

18

1.5

1
0

0.2

0.4

0.6

0.8

1

Fraction f of attacks

4
2
0
0

0.2

0.4

0.6

Fraction f of attacks(b) RA

0.8

1

0%
3%
5%
7%
10%
20%
30%

2.5

20

15

10

5

0
0

Average size 
 of isolated clusters

20

0%
3%
5%
7%
10%
20%
30%

Average size 
 of isolated clusters

Average size 
 of isolated clusters

2.5

2

1.5

1
0

0.2

0.4

0.6

0.8

1

Fraction f of attacks

0.2

0.4

0.6

0.8

Fraction f of attacks(c) DLSF

Fig. 5. (Color online) Average size hsi of isolated clusters except the GC against
intentional attacks in (a) DT, (b) RA, and (c) DLSF networks at the shortcuts rates
in legend. Inset shows the peaks enlarged by other scale of the vertical axis.

of the critical values fc ; the increase is remarkable in less than the shortcuts
rate 10% as similar to Figs. 7(a)(b). These results are also obtained in the
LESF networks without the periodic boundary conditions.
7

1

1

1
0%
3%
5%
7%
10%
20%
30%

Relative size S/N

0.8
0.7
0.6

0.8

0.5
0.4

0.6
0.5
0.4
0.3

0.2

0.2

0.1

0.1
0.2

0.4

0.6

0.8

0
0

1

0.4

0.6

0.8

Fraction f of attacks(a) S/N at A = 1(b) S/N at A = 3

1

1.8

2.5

Average size 
 of isolated clusters

0%
3%
5%
7%
10%
20%
30%

3

2

1.5

1
0

0.2

Fraction f of attacks

3.5

Average size 
 of isolated clusters

0.7

0.3

0
0

0%
3%
5%
7%
10%
20%
30%

0.9

Relative size S/N

0.9

0.2

0.4

0.6

0.8

1.6
1.5
1.4
1.3
1.2
1.1
1
0

1

0%
3%
5%
7%
10%
20%
30%

1.7

0.2

0.4

0.6

0.8

Fraction f of attacks

Fraction f of attacks(c) hsi at A = 1(d) hsi at A = 3

1

Fig. 6. (Color online) Relative size S/N of the GC against intentional attacks in
LESF networks at (a) A = 1 and (b) A = 3. Average size hsi of isolated clusters
except the GC against intentional attacks in LESF networks at (c) A = 1 and (d)A = 3.

3.3 Simulation for AS networks

Historically, in the 1960s, the Internet was motivated to design a self-organizedcomputer network with the survival capability for communication that is
highly resilient to local failures [28]. Today, it evolves to one of the worldwide large scale systems, whose topology belongs to a SF network with apower-law degree distribution [29]. The SF nature of the Internet exhibits
both error tolerance and attack vulnerability [4,5,6,28]. Moreover, the geographical constraints on the topological linkings [8,9] implicitly affect the robustness, indeed, the numerical study [4] has been shown more serious resultin the Internet than that in a relational SF network called Barabási-Albert
model without geographical constraints. For the realistic case, we examine an
improvement of the robustness against the attacks in particular, when someshortcuts are virtually added to the Internet. We use the topology data [30]at the level of autonomous system (AS) derived from RouteViews BGP table
snapshots by CAIDA (Cooperative Association for Internet Data Analysis).
Figure 8(a) shows a power-law degree distribution in the AS networks with afew huge hubs. We also find small deviation P (k) for the shortcuts added into
8

1
0.9

0.8

0.8

0.7

0.7

Critical fraction f c

Critical fraction f c

1
0.9

0.6
0.5
RA
DLSF
DT

0.4
0.3

0.6
0.5
0.4
0.3

0.2

0.2

0.1

0.1

0
0

5

10

15

20

25

0
0

30

RA
DLSF
DT

5

Shortcut Rate

15

20

25

30

Shortcut Rate(a) random failures(b) intentional attacks

1

1

0.9

0.9

0.8

0.8

0.7

0.7

Critical fraction f c

Critical fraction f c

10

0.6
0.5
0.4
0.3
0.2

A=1
A=3

0.6
0.5
0.4
0.3
0.2

A=1
A=3

0.1
0
0

5

10

15

20

25

0.1
0
0

30

Shortcut Rate

5

10

15

20

25

30

Shortcut Rate(c) random failures(d) intentional attacks

Fig. 7. The critical value fc of removed nodes vs. shortcut rate in (a)(b) RA, DLSF,
DT, and (c)(d) LESF networks. The piece-wise linear lines guide the increasing.

these data, however the linearity in log-log plot is almost invariant. Figures8(b)(c) show the effect of shortcuts on the tolerance of connectivity against
the targeted attacks; the GC survives even in a double amount of attacks at
the breaking of the original networks without shortcuts, and the peak of hsi isslightly shifted to right. The breaking around the attack rate 3% is consistent
with the previous simulations [4,5,28]. Since a smaller average degree hki isimproper for maintaining the connectivity in spite of a small average clustering
coefficient hCi as shown in Table 1, these results may be related to a structuralvulnerability including tree-like stubs.

4

Conclusion

To improve the weakened connectivity by cycles in a theoretical prediction[13,14], we investigate effects of shortcuts on the robustness in geographicalSF networks. Something of randomness [16,17,18,15] is expected to relax thegeographical constraints that tend to make cycles locally. Since many realcomplex systems belong to SF networks [1,2] and are embedded in a metricspace [8,9], in addition, planar networks are suitable for efficient routings [22],we consider a family of planar SF network models called RA [12,11], DT
9

0

10

1

1

2004/7/5
2005/7/4
2006/7/3

0.8

Relative size S/N

10

0%

0%3%
3%5%
5%7%
7%10%
20%
10%
30%
20%
30%

0.8

−2

P(k)

10

−3

10

0.6
0.5
0.4

10

0.6
0.5
0.4
0.3
0.2

0.3
−4

0.7

0.7
S/N

−1

0.9

0.9

0.1

0.2

0
0

0.01

0.02

0.03

−5

10

0

1

10

2

10

3

10

0
0

4

10

10

0.04

0.05

f

0.1
0.2

0.4

0.6

0.8

1

Fraction f of attacksk(a) P (k)(b) GC

1.5
1.45
1.4

1.35
1.3

1.35




Average size 
 of isolated clusters

1.4

1.3

0%
3%
5%
7%
10%
20%
30%

0%
3%
5%
7%
10%
20%
30%

1.25
1.2

1.25

1.15

1.2

1.1
1.05

1.15

1
0

0.01

0.02

0.03

0.04

0.05

f

1.1
1.05
1
0

0.2

0.4

0.6

0.8

1

Fraction f of attacks(c) hsiFig. 8. (Color online) Results for the AS networks. (a) Degree distribution P (k).
Each mark corresponds the year/month/day. (b) Relative size S/N of the GC and(c) the average size hsi of isolated clusters except the GC against intentional attacks
on the network in 2006. Insets shows the enlarged parts for the small fraction f .
These are similar in other two years.

[20,21], and DLSF [15], a non-planar basic geographical model called LESF
[10], and a real data of the Internet at the AS level [30] as an example forthe virtual examination. Our numerical results show that the robustness is
improved by shortcuts around 10% rate maintaining the small distance hDi
and number of hops hLi on the optimal paths (with respect to the shortest andthe minimum number of hops, respectively) in each network, under similar
degree distributions to the original ones. In particular, the improvement isremarkable in the intentional attacks on hubs. However, some cases exhibit
weak effects which depend on the values of other topological characteristics
such as hki and hCi. We will further study for comprehending the properties.
On the other hand, these results give an insight for practical constructing ofa geographical network, since the robustness can be effectively increased byadding a small fraction of shortcuts.
10

Network

N

M

hki

hCi

hLi

P (k)

DT

1000

2993

5.986

0.441

9.02

lognormal

RA

1000

2993

5.986

0.767

4.13

power-law

DLSF

1000

2993

5.986

0.726

4.65

with cutoff(A = 1)

1024

1831

3.576

0.342

14.5

with cutoff(A = 3)

1024

2673

5.221

0.104

4.87

with cutoff

AS04

17509

35829

4.0926

0.234

3.77

power-law

AS05

19846

40485

4.0799

0.249

3.79

power-law

LESF

22456 45050 4.0123 0.219 3.87 power-law
AS06
Table 1
Summary of the topological characteristics: the network size N , the total number oflinks M , the average degree hki, the average clustering coefficient hCi, the averagepath length hLi based on the minimum number of hops, and the types of degree
distribution P (k).

Acknowledgment

The authors would like to thank CAIDA for using the AS relationship data[30]. This research is supported in part by Grant-in-Aide for Scientific Researchin Japan, No.18500049.

Fig. 9. (Color online) Illustration of the extended routing. The (red) thick route on
the edges of (cyan) shaded faces is the shortest path ls whose distance is the sameas the dashed (red) chord of the ellipsoid. The (blue) thick route is the optimal path
including a shortcut.

11

=

+

1st diagonal flip

2nd diagonal flip

Fig. 10. (Color online) Linking procedures in a Delaunay-like SF network. The
long-range links (black solid lines in the left) are exchanged to red ones in theshaded triangles by diagonal flips in the middle and right. The dashed lines are
new links from the barycenter, and form new five triangles with contours in the left
(The two black solid lines crossed with dashed lines are removed after the second
diagonal flip).

Appendix 1
For adding shortcuts, the efficient routing algorithm [22] on a planar network
can be extended as follows (see Figure 9) in the ellipsoid whose chord is definedby the distance of the shortest path ls on the edges of faces that intersect thestraight line between the source and terminal as the two focuses. We describe
the outline of procedures .
• Find the shortest path ls on the original planar network without shortcuts.
• Then search shorter one including shortcuts in the ellipsoid.
• Through backtrackings from the terminal to the source in the above process,prune the nodes that located out of the ellipsoid or on longer paths than ls
by using the positions.
We expect the additional steps for searching are not so much as visiting almost
all nodes, when the rate of shortcuts is low. Moreover, even in this case, therobustness of connectivity can be considerably improved.

Appendix 2
The geographical networks are constructed as follows.
Planar networks [15]Step 0: Set an initial planar triangulation on a space.
Step 1: At each time step, select a triangle at random and add a new nodeat the barycenter. For each model, different linking processes are applied.
RA: Then, connect the new node to its three nodes as the subdivision oftriangle.
DLSF: Moreover, by iteratively applying diagonal flips [20], connect it to12the nearest node within a radius defined by the distance between the newnode and the nearest node of the chosen triangle, as shown in Fig. 10.
If there is no nearest node within the radius, this flipping is skipped,
therefore the new node is connected to the three nodes.
DT: After the subdivision of the chosen triangle, diagonal flips are globally
applied to a pair of triangles until the minimum angle is not increased byany exchange of diagonal links in a quadrilateral.
Step 2: The above process is repeated until the required size N is reached.
LESF networks [10]Step 0: To each node on the lattice, assign a random degree k taken fromthe distribution P (k) = Ck −γ , m ≤ k ≤ K, γ > 2, where C ≈ (γ − 1)mγ−1
is the normalization constant for large K.
Step 1: Select a node i at random, and connect it to its nearest neighbors
until its connectivity ki is realized, or until all nodes up to a distance r(ki) =1/d
Aki have been explored: The connectivity quota kj of the target node j
is already filled in saturation. Here A > 0 is a constant.
Step 2: The above process is repeated for all nodes.

References[1] A.-L. Barabá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, and S.Strogatz, Nature 393, 440, (1988).
[4] R. Albert, and A.-L. Barabási, Nature 406, 378, (2000).
[5] R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, PRL 86, 3682, (2000).
[6] R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, PRL 85, 4626, (2000).
[7] R.F.i Cancho, and R.V. Solé, In Statistical Mechanics in Complex Networks,
edited by R. Pastor-Satorras, M. Rubi, and A. Diaz-Guilera, Lecture Notes inPhysics 625, (Springer, Berlin, 2003), Chap. 5.
[8] S.-H. Yook, H. Jeong, and A.-L. Barabási, PNAS 99(21),13382, (2002).
[9] M.T. Gastner, and M.E.J. Newman, Eur. Phys. J. B 49(2), 247, (2006).
[10] D. ben-Avraham, A.F. Rozenfeld, R. Cohen, and S. Havlin, Physica A 330,
107, (2003).
[11] T. Zhou, G. Yan, and B.-H. Wang, Phys. Rev. E 71, 046141, (2005).

13

[12] J.P.K. Doye, and C.P. Massen, Phys. Rev. E 71, 016128, (2005).
[13] L. Huang, L.Yang, and K. Yang, Europhys. Lett. 72(1), 144-150, (2005).
[14] L. Huang, L.Yang, and K. Yang, arXiv:physics/0503147, (2005).
[15] Y. Hayashi, and J. Matsukubo, Phys. Rev. E 73, 066113, (2006).
[16] C. Moore, and M.E.J. Newman, Phys. Rev. E 61, 5678, (2000).
[17] C. Moore, and M.E.J. Newman, Phys. Rev. E 62, 7059, (2000).
[18] J.M. Kleinberg, Nature 406, 2845, (2000).
[19] S. Maslov, K. Sneppen, and A. Zaliznyak, Physica A 333, 529, (2004).
[20] K. Imai, IEICE Trans. on Infor. and Syst. 83-D(3), 428, (2000).
[21] A. Okabe, B. Boots, K. Sugihara, and S.N. Chiu, Spatial Tessellations, 2nd ed.
(John Wiley, 2000).
[22] P. Bose, and P. Morin, SIAM J. of Computing 33(4), 937, (2004).
[23] J.M. Keil, and C.A. Gutwin, Discrete Compt. Geom. 7, 13, (1992).
[24] M.E.J. Newman, S.H. Strogatz, and D.J. Watts, Phys. Rev. E 64, 026118,(2001).
[25] C.P. Warren, L.M. Sander, and I.M. Sokolov, Phys. Rev. E 66, 056105, (2002).
[26] L.A.N. Amaral, A. Scala, M. Barthélemy, and H.E. Stanley, PNAS 97(21),11149, (2000).
[27] S. Sun, Z. Liu, Z. Chen, and Z. Yuan, Physica A 373, 851-860, (2006).
[28] R. Pastor-Satorras, and A. Vespignani, Evolution and Structure of the Internet,
Chapter 4: The Internet’s large-scale topology (Cambridge University Press,
2004).
[29] M. Faloutsos, P. Faloutsos, and C. Faloutsos, Compt. Commun. Rev. 29, 251,
(1999).
[30] http://as-rank.caida.org/data/,
http://www.caida.org/data/active/as-relationships/

14