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

Title

Evolutionary Construction of GeographicalNetworks with Nearly Optimal Robustness andEfficient Routing Properties

Author(s)Hayashi, Yukio

Citation

Physica A: Statistical Mechanics and its
Applications, 388(6): 991‑998

Issue Date

2008‑11‑28

Type

Journal Article

Text version

author

URL

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

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,
Physica A: Statistical Mechanics and its
Applications, 388(6), 2008, 991‑998,
http://dx.doi.org/10.1016/j.physa.2008.11.027

Description

Japan Advanced Institute of Science and Technology

Evolutionary Construction of GeographicalNetworks with Nearly Optimal Robustness
and Efficient Routing Properties
Yukio Hayashi aa Japan Advanced Institute of Science and Technology, Ishikawa 923-1292, Japan

Abstract
Robust and efficient design of networks on a realistic geographical space is one of
the important issues for the realization of dependable communication systems. In
this paper, based on a percolation theory and a geometric graph property, we investigate such a design from the following viewpoints: 1) network evolution according
to a spatially heterogeneous population, 2) trimodal low degrees for the tolerant
connectivity against both failures and attacks, and 3) decentralized routing withinshort paths. Furthermore, we point out the weakened tolerance by geographical constraints on local cycles, and propose a practical strategy by adding a small fractionof shortcut links between randomly chosen nodes in order to improve the robustness√ to a similar level to that of the optimal bimodal networks with a larger degree
O( N ) for the network size N . These properties will be useful for constructing
future ad-hoc networks in wide-area communications.
Key words: Population density; Geometric Spanner; Decentralized routing;
Shortcut link; Wireless ad-hoc communication
PACS: 89.20.Ff, 89.65.Lm, 89.75.Fb, 05.10.-a1Introduction

Real complex networks, such as a power grid, an airline network, and the Internet, are embedded in a metric space, and long-range links are restricted [1,2]for economical reasons. Moreover, there exists a common topological characteristic called scale-free(SF) that follows a power-law degree distribution
P (k) ∼ k −γ , 2 < γ < 3, which consists of many nodes with low degrees anda few hubs with high degrees. The SF structure is quite different from theconventional simple regular lattices and random graphs (also from more complicated graphs, e.g. the Voronoi or Delaunay diagrams [3]), and extremely
vulnerable to intentional attacks on hubs [4]. By removing only about a few
Preprint submitted to Elsevier

8 December 2008

percent of high-degree nodes, a set of disconnected nodes leads to the global
malfunction of a communication network [5]. Thus, the design of more robust
networks than the SF structure, such as in the Internet or a Peer-to-Peer system, is important to reduce the threat of cyber-terrorism and of a natural
disaster to communication infrastructures.
Recently, it has been analytically and numerically shown [6] that the robustness against both random and targeted removals of nodes is improved as themodality of degree is smaller in the multimodal networks with a specific type ofdegree distribution P (ki) ∝ a−(i−1) , a > 1, i = 1, 2, . . . , m: maximum modality, which include the SF structure as the largest modality with m → ∞.
Although the bimodal network with only two types of degree is the optimal inthis class of networks under the assumption of uncorrelated tree-like structure,
we can consider any other types of degree. Even with a small modality, thebest allocation of degrees to nodes is generally unknown, and it may depend on
the geographical positions of nodes. Clearly, in real communication networks,
the position of node is not uniformly distributed [1] owing to the preferenceof crowded urbanism or geographical limitations on residences. Therefore, thespatial distribution is non-Poisson.
On the other hand, point processes give useful theoretical insights for themodeling of spatial distribution of nodes in wireless communication networks.
Some mathematical approaches have been developed [7], while studying models other than e.g. the Poisson Voronoi tessellations and the Gibbs point process for a decomposition into some territories or other tessellation model forcrack patterns [8] remains in an open and potential research field. In a different point process from the above models, we focus on the robustness ofconnectivity and on the efficiency of routing inspired by the progress in computer science and in complex network science [9,10]. The topological structure
and the traffic dynamics based on various routing protocols on complex networks have been studied actively to avoid the congestion of packets (e.g. see[11,12,13,14]).
In addition, we are motivated by some geometric constructions of spatiallygrown SF networks [15,16], in which newly added nodes and links are determined by the positions of already existing nodes. Our optimal policy is different from that in the growing complex networks by local linkings on a space[17,18] in which the emergence of various topological structures is mainly discussed instead of the robustness of connectivity and the efficiency of routing.
In computer science, geometric network models (e.g. Gabriel [19] and Θ-graphs[20] in restricted power consumption) have also been proposed. Most of the research has been devoted to algorithmic and graph theoretical issues [21] about
efficient routing and economical linking on a general (usually, uniformly random) position of node. However, percolation analysis in statistical physics
should be included in the discussion, because the robust infrastructure on a2

realistic space and the routing scheme are closely related [19] in the design of
network. The positions of nodes and the linkings strongly affect the distancesof optimal paths and the tolerance of connectivity. Thus, by including theissues of routing and robustness, we consider how to design a communication
network in realistic positions of nodes as base stations and linkings between
them on a heterogeneously distributed population.
The organization of this paper is as follows. In Section 2, we introduce a
new network construction according to a given distribution of a spatially heterogeneous population. We consider an incremental design of a communication network and a good property for decentralized routings. In Section 3, we
numerically investigate the robustness of connectivity against both random
failures and the intentional attacks on high degree nodes in the geographicalnetworks. In particular, we point out a more weakened tolerance by geographical constraints on local cycles than the random null model under the same
degree distribution, and propose a practical strategy to improve the tolerance
by adding a small fraction of shortcuts. In Section 4, we summarize the results
and briefly discuss the future studies.

2

Geographical network based on a population

We propose an evolutionary construction of geographical networks with good
properties of small modality of degree, short distance path, and decentralized
routing. The robustness of connectivity will be discussed in the later sections.

2.1 Geometric spanner

Let us consider the basic process of network evolution defined as follows. It
is based on a point process for load balancing of incremental communication
requests by stochastic subdivisions of a triangle. Each node of the triangle
corresponds to a base station for transferring messages and the link between
them corresponds to a wireless or wired communication line, however thetechnical details to distinguish them at the physical device level is beyond ourcurrent scope of network modeling.
Step0: Set an initial triangulation of any polygonal region which consists ofequilateral triangles.
Step1: At each time step, a triangle is chosen with a probability proportional to the population (by summing up the number of people) in thecorresponding space.
Step2: Then, as shown in Figs. 1(a) and 2(a), four smaller triangles are
3

(a) Re-assignment to nodes(b) Regulation of communication
range
Fig. 1. Basic division process. (a) Re-assignment of communication requests to nodes
as the nearest base stations. The arrows indicate the directions for transfered requests from users in the area. (b) Power of orientative wireless beam regulated by
the subdivision. Each circle represents the range.

(a) Subdivision(b) Example
Fig. 2. (Color online) Heterogeneous network configuration. (a) Subdivision from ashaded triangle in an initial hexagon at left into four smaller triangles at right. The
dashed circle represents the range of a wireless beam from each node. (b) Example ofa network on the Fukui-Kanazawa area in Japan. From light (yellow) to dark (red)color, the gradation is proportionally assigned to the population in each block. Notethat the white areas at the upper left and the lower right are the sea of Japan andthe Hakusan mountain range, respectively.

created by adding facility nodes at the intermediate points on the communication links of the chosen triangle. This procedure is for a division of theservice area.
Step3: Return to Step 1.
In the subdivision of this network, we use a mesh data of population statistics(82 × 102 × 4 = 25600 blocks for 80km2 in the Fukui-Kanazawa area, provided
by Japan Statistical Association), and recalculate the mapping between theblocks and each triangle to count the number of people in the triangle space.
It is natural that the amount of communication requests depends on the activities of people, therefore are estimated to be proportional to the population in4the area. We consider such a stochastic construction of geographical networks
for the general discussion, however a deterministic evolutionary constructionis also possible when the population inside the corresponding triangle locallyaccesses a certain threshold. We mention that, in the meaning of practicalconstruction, the subdivision is generated in a distributed manner according
to the increase of communication requests in individual areas. The detailed
procedures depend on technological issues in wide-area wireless communications.
According to the population, an example of randomly constructed networkwith a total number of nodes N = 100 is shown in Fig. 2(b). This configuration
resembles a heterogeneous random version of a Sierpinski gasket. For any
population, since it has a small modality with the trimodal degrees: k1 = 2(or 3 for the initial hexagon), k2 = 4, and k3 = 6 grown from the initial
triangle, a highly tolerant connectivity may be expected from Ref.[6] becauseof the small modality of degree. Note that the smallest degree k1 is fixed
on the initial nodes with the existing probability p1 = 3/N (or 6/N for the
initial hexagon) in this rule of geographical network generation, while in the
optimal bimodal networks, k1 with the probability p1 = 1 − p2 is uniformly
q



3/4

2

2

(hki−1) 1/3
A
and A = { 2hki2hki−1} under
determined by k2 = hkiN, p2 = hkiN
the assumption of an uncorrelated tree-like structure of large random networks
for N ≫ 1, then k2 ≫ 6 is obtained. Here, hki denotes a given average
degree. Since the differences are not only the number of modalities but also
the size of largest degree, the robustness should be carefully discussed. We will
numerically compare the robustness in the optimal bimodal networks with thatin our proposed geographical networks under the same hki at the end of next
section.
2

On the other hand, as a good graph property known in computer science,the proposed network becomes the t-spanner [22] with a maximum stretch
factor t = 2, since the equilateral property holds in spite of various sizesof the triangle. In other words, the network consists of the fattest triangles, then the length of the shortest distance path between any nodes u
and v is bounded by t times the direct Euclidean distance d(u, v). Since
narrow triangles as in random Apollonian networks [16] constructed by different geometric subdivisions from ours give rise to a long distance path,such a construction does not provide a suitable topology for routing paths
with as short distances as possible. In other geometric graphs, the stretch
factor becomes larger: t = 2π/(3cos(π/6))≈ 2.42 for Delaunay triangu√
lations [23] and t = 2α ≥ 4 3/3 ≈ 2.3094 for two-dimensional triangulations with an aspect ratio of hypotenuse/height less than α [19] whose
lower bound is given for the triangulation lattice that consists of the fattest
equilateral triangles. Although Θ-graphs [20] with K non-overlapping cones
have t = 1/(cos(2π/K) − sin(2π/K)) → 1 asymptotically as K → ∞, alarge amount of O(KN ) links is necessary, and the links may be crossed (as5non-planar) and give rise to interferences between wireless beams. In generalgraphs, even the existence of a bounded stretch factor is uncertain.
Figure 3 shows typical cases of the stretch factor on the shortest distance pathin our model. We numerically investigate the distributions of the link lengthand of the stretch factor as shown in Fig. 4. Many paths connected by the
majority of short links have small stretch factors. The average link lengths ¯lij
are less than half of the initial link length normalized with refer to the biggest
triangle, as 0.057 for N = 100 and 0.014 for N = 1000 in the Pop (¯lij = 0.05
for N = 100 and 0.01 for N = 1000 in the Ran), the average factors t̄ aresmall as 1.1512 for N = 100 and 1.1395 for N = 1000 (t̄ = 1.2008 for N = 100
and 1.2297 for N = 1000 in the Ran). Thus, our proposed networks have good
properties regarding path distance.

(a)

(c)

(b)

√
√
Fig. 3. Typical cases of the stretch factor: (a) t = 2 3/3 ≈ 1.15, (b) t = 3 ≈ 1.73,
and the maximum (c) t = 2. The dashed line is the shortest distance path between
the source and the terminal nodes marked by circles. Note that all the triangles ofdifferent sizes are equilateral in the configuration.

1

0.3

Relative Frequency

0.1

P(l_ij)N = 1000, Pop
N = 1000, Ran

0.25

0.01
N=1000, Pop
N=1000, Ran
N=500, Pop
N=500, Ran
N=100, Pop
N=100, Ranexp(- 10*x)0.001
0.00010.00001
0

0.1

0.2
0.15
0.1
0.05
0

0.2

0.3

0.4

0.5

1

l_ij

(a) Dist. of Link Length

1.2

1.4
1.6
Strech Factor: t

1.8(b) Histogram of t-value

Fig. 4. (Color online) Distance properties of the geographical networks with sizes
N = 100 ∼ 1000 according to the population in Fig. 2(b) and the uniformly random
choice of a triangle corresponded to the case of a general population. These cases
are denoted as abbreviations by Pop and Ran, respectively. (a) The distribution
P (lij ) of the link length lij decays nearly exponentially, as shown by the magenta
line defined by exp(−10 lij ). (b) High frequencies are observed for small stretch
factors t < 1.2, while low frequencies for large ones which are bounded by t = 2.

62

2.2 Decentralized face routing
For ad-hoc networks, a routing protocol should be simple to reduce energy consumption in keeping the reachability. However some of the routing schemes inearly work lead to the failure of guaranteed delivery [24], e.g., in the flooding
algorithm multiple redundant copies of a message are sent and cause network
congestion, while greedy and compass routings may occasionally fall into infinite loops. On the other hand, except for some class of graphs, it is costly
to seek the shortest path for a map in which connections are unknown inadvance.
Fortunately, since the proposed geographical networks belong to a specialclass of graph which is planar and consists of convex (equilaterally triangular)
faces, we can apply the efficient decentralized algorithm [25] that guarantees
the delivery of a message using only local information based on the positionsof the source, the terminal nodes, and the adjacencies of the current node ona path. In recent technologies, the positions are measured by means of a GPSor other methods, then the reachable path to a terminal node T e can be foundin a proper mixing of upper and lower chains extracted from the edges of thefaces as shown in Fig. 5. Without multiple copies of the message, the next
forwarding node from each node on the upper and lower chains is determined
only by the positions of adjacent nodes and the distance from a source node
So. In this class, with the property of routing called competitive, the lengthof the routing path is bounded in a constant factor to that of the shortest
path and also to the distance d(So, T e) on the straight line because of the
t-spanner.
This competitive algorithm [25] or a combination by greedy and face routings in asymptotically (at the lower bound) worst-case optimal traveling on a
general planar network [26] acts in a decentralized manner, therefore a global
information such as the static routing table in the Internet’s TCP/IP protocol is not necessary. Moreover, these algorithms can be extended (see the
Appendix of [28] and a related idea [27]) to add a small fraction of shortcuts
discussed in the next section. We emphasize that such geographical protocols
are not only successfully used for message delivery in social friendships [29]but are also very promising for constructing wireless networks with a higher
efficiency and scalability in a dynamic environment [30].

3

Numerical robustness analysis

We aim to maximize the sum of critical fractions fT = fr + ft to be optimal
network against both random failures and targeted attacks on nodes with
7

Source
Terminal

Fig. 5. (Color online) Efficient face routing on a planar network. The (red) reachable
shortest path through the nodes marked by open circles between the source and theterminal nodes can be found from the edges of the (blue) shaded faces that intersectthe (green) dashed straight line. The two paths on the edges above and below theline are the upper and the lower chains, respectively.

large degrees as robust as possible on a spatially heterogeneous distributionof population. Here, fr and ft denote the critical fractions of these damages
at the breaking of the giant component (GC).
For a preliminary, we numerically estimate the total numbers of nodes N(τ )and links M(τ ) at time step τ over 100 realizations of the geographical network. They grow as N(τ ) = N(0) + 2.35τ and M(τ ) = M(0) + 5.34τ ,where N(0) = 6 and M(0) = 9 for the initial triangle (or N(0) = 7 andM(0) = 12 for the initial hexagon). Thus, in the subdivision, two or threenodes per step are added with a high frequency, and the average degree ishki = 2M(τ )/N(τ ) ≈ 4.54. Since the total link hkiN/2 is more than twicethat of N − 1 links on a tree of N nodes, there possibly exist many cycles.
As the simulation result for the removals, Fig. 6 indicated with blue + andmagenta × marks show that the size S of the GC rapidly decreases at thefraction f ≈ 0.4. A similar vulnerability caused by geographical constraints
on local cycles has been found in a family of SF networks embedded in aplanar space [31] and SF networks on a lattice [32]. To clearly see the effectof constraints, we investigate the non-geographical rewired versions under thesame degree distribution (of course with the same average degree hki). In
the rewiring [33], two pairs of nodes at the ends of randomly chosen links
are exchanged in holding the degree of each node. Therefore, the geographicalconstraints are entirely reduced. In general, the rewired version of a network is
the null model that depend only on the degree distribution ignoring the other
topological structures: cycles, degree-degree correlation, fractal or hierarchicalsubstructure, diameter of graph, etc. The red △ and green ▽ marks shownin Fig. 6 indicate that the critical fractions at the peak of hsi increases tofr ≈ 0.7 and ft ≈ 0.6. Such improvement of the robustness is consistent withthe result obtained for the geographical SF networks [31].
Although the full rewiring is better in terms of the robustness, it completely
8
Relative size S/N

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Fraction f of Attacks or Failures(a) Giant Component

10
9
8
7
6
5
4
3
2
1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1f(b) Isolated Clusters

Fig. 6. (Color online) Comparison of the geographical and the non-geographicalrewired networks at N = 1000. (a) Relative size S/N of the GC after the removalof nodes. The plus(blue) and cross(magenta) marks indicate the corresponding results for the geographical networks against random failures and intentional attacks.
The upper triangle(red) and down triangle(green) marks indicate the corresponding results for the non-geographical rewired versions against them, respectively. (b)Average size hsi of isolated clusters except the GC. The peak indicates the criticalpoint at which the whole connectivity breaks. Each point is obtained from the average over 100 realizations of the geographical network constructed from the initial
triangle (× 100 samples of random rewirings).

ignores the positions of nodes and the distances of links. As another practicalstrategy, it is expected that adding a small fraction of shortcuts between randomly chosen nodes has a similar effect to the rewiring [28]. Indeed, Figs. 7
and 8 show the improvement of robustness against both random failures andintentional attacks. As the shortcut rate marked from red
to black ▽ increases, a larger GC remains, and the breaking point at the peak of hsi shifts
to a larger fraction f of the removal. Only about 10 % of the adding reaches
a similar level of fr ≈ 0.7 or ft ≈ 0.6 in the non-geographical rewired version(compare with Fig. 6 indicated with △ and ▽ marks). In addition, the finite
effect on the critical fractions is very small as shown in Table 1, however it
has occurred that the positioning of the node is inaccurate written a round-off
error in the very dense case of N = 105 , especially for 0% shortcuts.
We compare the above results shown in Figs. 7 and 8qwith the robustnessof the optimal bimodal network [6] defined by k2 = hkiN = 67.38 and


2

3/4

A
= 0.01445 for N = 1000 and hki = 4.54. Since the degree andp2 = hkiNthe number of nodes for each type of degree must be an integer, the appropriate
combination is k2 = 67 or 68, p2 = 0.014 or 0.015, k1 = (hki − k2 p2 )/p1 = 4
or 3, and p1 = 1 − p2 = 0.986 or 0.985; then, hki = 3.975 or 4.882 is theclosest to the value 4.54 in our geographical networks. On the two pairs ofdegree distributions, the bimodal networks are randomly constructed by fullrewirings from an initial configuration. As shown in Figs. 9 and 10, the critical
fractions fr and ft are slightly larger around 0.4 ∼ 0.7, however the effect of

9




Relative size S/N

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Fraction f of Failures

10
9
8
7
6
5
4
3
2
1

(a) Giant Component

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1f(b) Isolated Clusters

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0




Relative size S/NFig. 7. (Color online) Damages by random failures in the geographical networks
and the shortcut versions at N = 1000. (a) Relative size S/N of the GC. The open
circle(red), plus(green), cross(cyan), upper triangle(orange), diamond(magenta),
closed circle(yellow), and down triangle(black) marks indicate the corresponding
results for the shortcut rate of 0, 3, 5, 7, 10, 20, and 30 %, respectively. (b) Average
size hsi of isolated clusters except the GC. Each point is obtained from the average over 100 realizations of the geographical network constructed from the initial
triangle × 100 samples of random shortcuts.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Fraction f of Attacks(a) Giant Component

10
9
8
7
6
5
4
3
2
1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1f(b) Isolated Clusters

Fig. 8. (Color online) Damages by intentional attacks in the geographical networks
and the shortcut versions at N = 1000. (a) Relative size S/N of the GC. (b) Average
size hsi of isolated clusters except the GC. The marks are the same as in Fig. 7.
Each point is obtained from the average over 100 realizations of the geographicalnetwork constructed from the initial triangle × 100 samples of random shortcuts.

shortcuts barely works and is weaker than that in our geographical networks.

4

Conclusion

According to spatially distributed communication requests based on a given
population density, we have proposed an evolutionarily constructed geographical network by the iterative division of equilateral triangles. Through the10

Shortcut

frft

Rate %

N = 102

103

104

105

N = 102

103

104

105

0

0.352

0.348

0.386

0.058

0.351

0.335

0.384

0.100

3

0.474

0.443

0.499

0.469

0.469

0.481

0.425

0.468

5

0.529

0.501

0.542

0.502

0.509

0.499

0.540

0.503

7

0.525

0.537

0.554

0.538

0.520

0.525

0.503

0.535

10

0.545

0.542

0.566

0.568

0.568

0.552

0.571

0.565

20

0.600

0.605

0.627

0.639

0.619

0.596

0.635

0.638

30

0.646

0.641

0.671

0.682

0.651

0.641

0.663

0.680

Rewired

0.726

0.722

0.703

0.687

0.718

0.736

0.699

0.690

Table 1
Critical fractions fr and ft at the peak of hsi are consistent for different sizes Nof the geographical networks with shortcuts and the rewired versions. Each value
is obtained from the average over 100 realizations of the geographical network constructed from the initial triangle × 100 samples of random shortcuts and rewirings.

0.6

1.6

0.6

1.5

0.4
0.2
0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Fraction f of Failures

0.4

1.4




1.6

0.8




0.8

1.7

1

Relative size S/N

Relative size S/N

1

1.4
1.2
1

0

0.2 0.4 0.6 0.8
f

1

1.3
1.2

0.2

1.1

0

1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Fraction f of Failuresf(b) Isolated Clusters(a) Giant Component

Fig. 9. (Color online) Damages by random failures in the optimal bimodal networks
and the shortcut versions at N = 1000 with the over-estimated hki = 4.882 > 4.54,
k1 = 4, and k2 = 67. (a) Relative size S/N of the GC. (b) Average size hsi of
isolated clusters except the GC. Insets show the results with the under-estimatedhki = 3.975 < 4.54, k1 = 3, and k2 = 68. Each point is obtained from the averageover 100 realizations × 100 samples of random shortcuts. The marks are the sameas in Fig. 7.

numerical simulation for investigating the robustness, the obtained results are
summarized as follows. We note that they are consistent with other results on
population densities besides the example of Fig. 2(b), e.g. for the the geographical networks generated by the iterative choice of a triangle with a uniformly
random probability, the robustness is similar to that in Figs. 6-8.
11

1

1.7

1

1.5

0.4




1.6

0.6

1.4
1.2
1

0.2
0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Fraction f of Attacks

0.4




0.6

Relative size S/N

Relative size S/N

1.6

0.8

0.8

1.4

0

0.2 0.4 0.6 0.8
f

1

1.3
1.2

0.2

1.1

0

1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

Fraction f of Attacksf(a) Giant Component(b) Isolated Clusters

Fig. 10. (Color online) Damages by intentional attacks in the optimal bimodal
networks and the shortcut versions at N = 1000 with the over-estimatedhki = 4.882 > 4.54, k1 = 4, and k2 = 67. (a) Relative size S/N of the GC. (b)Average size hsi of isolated clusters except the GC. Insets show the results with theunder-estimated hki = 3.975 < 4.54, k1 = 3, and k2 = 68. Each point is obtained
from the average over 100 realizations × 100 samples of random shortcuts. The
marks are the same as in Fig. 7.

• The proposed networks have suitable properties of short paths as the tspanner [22] and efficient decentralized routing [25] for wireless communications. Moreover, the incremental construction can be implemented toaccommodate a growing activity or population.
• To improve the vulnerability caused by the geographical constraints [31,32],
we have considered a practical strategy by adding a small fraction of shortcuts between randomly chosen nodes [28], and numerically confirmed theeffect.
• The degree distribution becomes trimodal at most without hub nodes, therobustness of the connectivity is slightly weak but is maintained as similarlevel as the optimal bimodal networks with a larger maximum degree [6].
These results are useful for the design of ad-hoc networks with efficiency,
scalability, and tolerance of connectivity in wide-area communications.
Since our trimodal model has a maximum degree that is not extremely large
compared to other degrees, instead of hub attacks, a spatial cutting into several dense parts by removing a small number of nodes on lines of large triangles
may be considerable. Even in such cases, we expect that shortcuts effectively
work to bridge isolated clusters by the removals. More detailed analysis is the
subject of future study that includes how to find the structural vulnerable
points. Other important issues are the development of routing schemes taking
into account the structure layered by the size of the triangle, the analysis oftraffic dynamics with the phase transition between free flow and congestion according to the forwarding capacity at a node and queue discipline (FIFO etc.),
and considering various optimal policies in matching application requirements.
12

Acknowledgments
The author would like to thank anonymous reviewers for valuable comments
to improve the manuscript, and also Yasumasa Ono and Hironori Okumura
in my laboratory for helping with the simulation. This research is supported
in part by Grant-in-Aid for Scientific Research in Japan No.18500049.

References[1] S.-H. Yook, H. Jeong, and A.-L. Barabási, PNAS, 99(21), 13382, (2002).
[2] M.T. Gastner, and M.E.J. Newman, Eur. Phys. J. B, 49(2), 247, (2006).
[3] A. Okabe, B. Boots, K. Sugihara, and S.N. Chiu, Spatial Tessellations, 2nd ed.,John Wiley, 2000.
[4] R. Albert, and A.-L. Barabási, Nature, 406, 378, (2000).
[5] R. Pastor-Satorras, and A. Vespignani, Evolution and Structure of the Internet,
Cambridge University Press, 2004.
[6] T. Tanizawa, G. Paul, S. Havlin, and H.E. Stanley, Phys. Rev. E, 74, 016125,(2006).
[7] B. Blazsczyszyn, and R. Schott, Japan J. Ind. Appl. Math., 22(2), 179, (2005).
[8] W. Nagel, J. Mecke, J. Ohser, and V. Weiss, The 12th Int. Congress for Stereogy,(2007). http://icsxii.univ-st-etiene.fr/Pdfs/f14.pdf[9] A.-L. Barabási, LINKED: The New Science of Networks, Perseus, Cambridge,
MA, 2002.
[10] M. Buchanan, NEXUS: Small Worlds and the Groundbreaking Science of
Networks, W.W.Norton, New York, 2002.
[11] L. Zhao, Y.-C. Lai, K. Park, and N. Ye, Phys. Rev. E, 71, 026125, (2005).
[12] G. Yan, T. Zhou, B. Hu, Z.-Q. Fu, and B.-H. Wang, Phys. Rev. E, 73, 046108,(2006).
[13] W.-X. Wang, B.-H. Wang, C.-Y. Yin, Y.-B. Xie, and T. Zhou, Phys. Rev. E,
73, 026111, (2006).
[14] S. Sreenivasan, R. Cohen, E. Lórez, Z. Toroczkai, and H.E. Stanley, Phys. Rev.
E, 75, 036105, (2007).
[15] J.P.K. Doye, and C.P. Massen, Phys. Rev. E, 71, 016128, (2005).
[16] T. Zhou, G. Yan, and B.-H. Wang, Phys. Rev. E, 71, 046141, (2005).

13

[17] Y.-B. Xie, T. Zhou, W.-J. Bai, G. Chen, W.-K. Xiao, and B.-H. Wang, Phys.
Rev. E, 75, 036106, (2007).
[18] R. Xulxi.-Brunet, and I.M. Sokolov, Phys. Rev. E, 75, 046117, (2007).
[19] E. Kranakis, and L. Stacho, In Handbook of Algorithms for Wireless Networking
and Mobile Computing, edited by A. Boukerche, (Chapman & Hall/CRC, 2006),
Chap. 8.
[20] M. Farshi, and J. Gudmundsson, Proc. of the 13th European Symposium on
Algorithms, edited by G.S. Brodal and S. Leonardi, ESA 2005, LNCS, 3669,
556, (2005).
[21] X.-Y. Li, Wireless Computing and Mobile Computing, 3, 119, (2003).
[22] M.I. Karavelas, and L.J. Guibas, Proc. of the 12th ACM-SIAM Symposium on
Discrete Algorithms, (2001).
[23] J.M. Keil, and C.A. Gutwin, Discrete and Computational Geometry, 7, 13,(1992).
[24] J. Urrutia, In Handbook of Wireless Networks and Mobile Computing, edited
by I. Stojmenović, (John Wiley & Sons, 2002), Chap. 18.
[25] P. Bose, and P. Morin, Theoretical Computer Science, 324(2-3), 273, (2004).
[26] F. Kuhn, R. Wattenhofer, and A. Zollinger, Proc. of the 4th ACM International
Workshop on Mobile ad hoc Networking and Computing, (MObiHOc’03),
pp.267-278, (2003),[27] F. Kuhn, R. Wattenhofer, and A. Zollinger, Proc. of the 6th International
Workshop on Discrete Algorithms and Methods for Mobile Computing andCommunications, (DialM’02), pp.24-33, (2002).
[28] Y. Hayashi, and J. Matsukubo, Physica A, 380, 552, (2007).
[29] D. Liben-Nowell, J. Novak, R. Kumar, P. Raghaven, and A. Tomkins, PNAS,
102, 11623, (2005).
[30] K. Seada, and A. Helmy, In Handbook of Algorithms for Wireless Networking
and Mobile Computing, edited by A. Boukerche, (Chapman & Hall/CRC, 2006),
Chap. 15.
[31] Y. Hayashi, and J. Matsukubo, Phys. Rev. E, 73, 066113, (2006).
[32] L. Huang, L. Yang, and K. Yang, Europhys. Lett., 72(1), 144, (2005).
[33] S. Maslov, K. Sneppen, and A. Zaliznyak, Physica A 333, 529, (2004).

14