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

Title

Spatially self‑organized resilient networks by a
distributed cooperative mechanism

Author(s)Hayashi, Yukio

Citation

Physica A: Statistical Mechanics and its
Applications, 457: 255‑269

Issue Date

2016‑04‑06

Type

Journal Article

Text version

author

URL

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

RightsCopyright (C)2016, Elsevier. Licensed under theCreative Commons Attribution‑NonCommercial‑
NoDerivatives 4.0 International license (CC BY‑
NC‑ND 4.0).
[http://creativecommons.org/licenses/by‑nc‑
nd/4.0/] NOTICE: This is the author s version ofa work accepted for publication by Elsevier.
Changes resulting from the publishing process,including peer review, editing, corrections,structural formatting and other quality control
mechanisms, may not be reflected in thisdocument. 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, 457, 2016, 255‑269,
http://dx.doi.org/10.1016/j.physa.2016.03.090

Description

Japan Advanced Institute of Science and Technology

Spatially self-organized resilient networks

arXiv:1603.08329v2 [physics.soc-ph] 19 Apr 2016

by a distributed cooperative mechanism

Yukio Hayashi a,a Japan Advanced Institute of Science and Technology, Ishikawa 923-1292, Japan

Abstract
The robustness of connectivity and the efficiency of paths are incompatible in many
real networks. We propose a self-organization mechanism for incrementally generating onion-like networks with positive degree-degree correlations whose robustness
is nearly optimal. As a spatial extension of the generation model based on cooperative copying and adding shortcut, we show that the growing networks become
more robust and efficient through enhancing the onion-like topological structure
on a space. The reasonable constraint for locating nodes on the perimeter in typical surface growth as a self-propagation does not affect these properties of thetolerance and the path length. Moreover, the robustness can be recovered in the
random growth damaged by insistent sequential attacks even without any remedial
measures.
Key words: Self-Organization; Robust Onion-like Structure; Fractal Surface
Growth; Cooperative Multiplexing; Resilient System

Preprint submitted to Elsevier Science

20 April 2016

1

Introduction

In modern society, our daily activities depend on energy supply, communication, transportation, economic, and ecological networks, however their infrastructure systems are complex and not constructed by a central control.
Unfortunately, natural and man-made disasters occur at many locations in
the world, sometimes they bring to the crises of such network infrastructures.
For the improvements with robust connectivity, it is expected to study the admirable self-organizations appeared in natural and social systems [1]. In particular, several fundamental mechanisms: preferential attachment [2], copying[3,4], survival [5,6,7], subdivision (fragmentation) [8,9,10,11,12,13], or aggregation [13,14] are attractive for generating networks in the interdisciplinary
research fields of physics, biology, sociology, and computer science.

With the break of complex network science in the beginning of 21st century, it
is well known that in many social, technological, and biological networks there
exists a common scale-free (SF) structure whose power-law degree distribution
is generated by the preferential attachment [2] likened to “rich-get-richer”
rule. The SF networks have the efficient small-world (SW) property [15] thatthe path length counted by the hops through minimum intermediate nodes
between any two nodes is short even for a large network size, however they also
have an extreme vulnerability against intentional attacks in spite of having thetolerance of connectivity against random failures [16]. The vulnerability comesfrom a few existing of large degree hub nodes in a power-law distribution. Thus,
the efficiency of path and the robustness of connectivity are incompatible inmany real networks, such as Internet, power-grids, airline networks, metabolic
networks, and so on. If we do not persist the generation mechanism of real2

networks, we may find other more desirable mechanism to maintain both therobustness and the efficiency.
Since the natural design methods are not limited to only the selfish rule fora good network in efficiency, scalability, stability, adaptivity, or other criteria,
we consider a random copying process to generate complex networks as one ofother candidates for the design of future network infrastructure. We take into
account self-propagation in maintaining the robust network structure without
degrading the communication or transportation performance in the growth.
Although the duplication process has been so far considered to be fundamental
in a model of protein-protein interaction networks [3,4], its generation mechanism with some modifications may be applied to a self-organized design ofsocial and/or technological networks in urban planning, civil engineering, orinformation system science.
On the other hand, by numerical and theoretical analysis, it has been shownthat [17,18,19] onion-like topological structure with positive degree-degree correlations gives the optimal robustness against targeted attacks to hub nodes
in an SF network. For any degree distribution, the onion-like topology consists of a core of highly connected nodes hierarchically surrounded by rings ofnodes with decreasing degree. In a related generation method in a family of
SF networks, a deterministic model called as mandala network that consist ofrecurrently expanded intra- and inner-connections of ringed nodes has beenstudied [20]; the robustness is improved by rewiring or adding links applied
to the outmost two rings of nodes from the core of connected hub nodes. Furthermore, an efficient rewiring algorithm has been developed for generatinga network of onion-like topology with the nearly optimal robustness undera given degree distribution [21]. However, these constructions are based on
3

swapping endpoints of randomly chosen two links [17,18], expanding the ringsby simultaneously adding ni = 2ni−1 nodes for the i-th iterations [20], andentirely rewiring of links [21] like a configuration model [22], an incremental
generation method was not found for the networks with onion-like topology.
Recently, an incrementally growing method of such networks with onion-like
topology has been proposed [23] as a modification of the duplication-divergence(D-D) model [3,4] in enhancing the degree-degree correlations.

In this paper, we focus on a self-organized design for infrastructural communication and transportation network systems on a space, rather than the detailtechnologies and facilities. In particular, we consider a spatial growth of network with the robust onion-like topology. Although there are many types offailures and attacks, e.g. locally spreading damages in a disaster, this paper
treats typical random and targeted removal of nodes for investigating the fundamental property of robustness. Instead, we take notice of the uncertainty:
whether the robust structure can be maintained or not in a spatial growing of
network, because the embedding on a space imposes some kind of constraints
on the construction of network topology. The organization of this paper is asfollows. In Sec. 2, we introduce a biologically inspired basic model [23] for generating onion-like topological structure with strong robustness. Without lossof the robust onion-like topology, we extend it to spatial networks according tosurface growth. Such growth gives a hint for finding plausible self-propagation
mechanism in distributed network systems. In Sec. 3, we show good properties
for the robustness of connectivity and the efficiency of path on the growing
networks. In particular, it is attractive that the reasonable constraint on acontact area of surface for locating nodes in the growth does not affect theseproperties of robustness and efficiency. Moreover, we show the resilient connec4

tivity. Even without any remedial measures, the robustness can be recoveredin the growth damaged by sequential attacks. Resilience [24] is an importantconcept to heal over, repair, and recover the performance from a damaged
system, the recovery of robustness will give a first step to develop resilient
network systems. Some strategies for the resilient networks are discussed particularly in interdependent networks [25,26] recently. In Sec. 4, we summarize
these results, and mention several issues to make a more resilient network
system.

2

Spatially growing onion-like networks

2.1 Basic generation proceduresThis subsection introduces a basic model of incrementally growing networks
with onion-like topology [23]. In the next subsection, we extend it to a spatialmodel and explain how to locate a node on a space.
In the conventional D-D model [3,4], as the duplication process, a new node
added per time step links to connected neighbor nodes of a randomly chosen node. Then deletion of the duplication links occurs with probability δ.
We modify the duplication process by non-trivial discovering ideas; the differences of our proposed network [23] from the D-D model are the adding of amutual link between new and randomly chosen nodes, and the simultaneous
progress of copying and adding shortcut links at a time-interval to enhance theonion-like topological structure. We call the combination of a mutual link andduplication links as copying. Shortcut means an analogy to random connections in the SW model [15]. The outline of network generation consists of (1)5At each time step, a new node is added at a position on a square lattice. (2)As the copying process, the new node stochastically links to connected neighbor nodes of a chosen node limited on the perimeter (surface) of a spatiallygrowing network. (3) In order to enhance the robustness of connectivity, we
consider having positive degree-degree correlations in the copying and addingof shortcut links. These procedures are summarized as follows.
Step 0 Set an initial configuration of connected N0 nodes.
Step 1 At each time step t = 1, 2, . . ., a new node is added on a space. As
shown to the topological structure in Fig. 1(a), the new node i connects
to a randomly chosen node and to the neighbor nodes j with a probability(1 − δ) × p [21],
def

p=

1
,
1 + a | ki − kj |(1)

where δ is a rate of link deletion, a ≥ 0 is a parameter, and ki and kj denotethe degrees of nodes i and j. Since the linking is a stochastic process forthe new node i, unknown ki in Eq.(1) is anticipatorily set as (1 − δ)× thedegree of the chosen node.
Step 2 Moreover, at every time-interval IT , shortcut links until the number
psc M(t) are added between randomly chosen nodes i and j according to
the probability of Eq.(1) in prohibiting self-loops at a node and duplicate
connections between two nodes 1 . Here, psc is a rate of adding shortcut
links, M(t) denotes the number of links in the network at that time t =IT, 2IT, 3IT, . . ., and IT is defined by time steps greater than one.
Step 3 The above processes in Steps 1 and 2 are repeated up to a given size
N for N(t) = t + N0 .
1

In the prohibitive case, selections of other nodes are tried in the same way.

6

deletioni new+ mutual linkXjrandomly
chosenj’(b) Candidates of node’s location(a) Copying process

Fig. 1. Basic topological and spatial processes. (a) Thick black and gray lines show
the generated links by the copying process. Then deletion of dashed line occurs
with probability δ × p. Thin lines show the already existing links. We remark thatsuch a bypath of nodes j’-i-j is created for the path of nodes j’-chosen-j. (b) Opencircles are selectable nodes, but one with cross mark is not. Shaded sites show theperimeter as inserted locations of a new node.

We emphasize the following effects of copying and shortcut on the robustness.
• Local proxy function: by copying to make bypaths via another access pointof new node (see Fig. 1(a)) as a duplexing and the accumulated multiplexing
via other new nodes in the growth• Complementary function: by adding shortcut links especially between small
degree (homophily) nodes to enhance the robustness
Note that the local redundancy with bypaths is often used in distributed
computer communication systems. Our generation method is based on a cooperation mechanism that consists of the above functions and the linking ofsimilar degree nodes as homophily. Each part constructed by the copying andadding shortcut links helps each other with the division of roles to be a robust network in taking into account positive degree-degree correlations. Moreprecisely, we explain the roles as follows. Since the double random selections
7

for the neighbor nodes j contribute to an equivalent effect of preferential attachment [27,28], large degree nodes i and j tend to be connected together
when the chosen node has a large degree. However, such positive correlations
between small degree nodes are weak in the tree-like structure generated byonly the copying process [23]. Thus, in order to make an onion-like topologicalstructure, we further consider addition of shortcut links [15] between randomly chosen nodes i and j with the probability of Eq.(1). The adding pera time-interval IT instead of each time step is considered as non-dominant(complementary) but necessary process for generating an onion-like topology.
It has already been shown that adding some shortcut links between randomly
chosen nodes improves the robustness in the theory for the small-world model[29] and also in the numerical simulations for geographical networks: random Apollonian networks [30], multi-scale quartered networks [31], and linksurvival networks [7]. In addition, positive degree-degree correlations tend to
appear in randomly growing networks [32]. Therefore, in our network grownby the simultaneous progress of the copying and adding shortcut links, it
is expected that the robustness becomes stronger due to enhancing positive
degree-degree correlations for emerging the onion-like topology.

2.2 Spatial networks generated by surface growth with robustness

In this subsection, we explain how to locate a new node in the network according to typical models of surface growth.
There exist many complex pattern-formations far from equilibrium in nature[33] as living open systems. Several models of fractal growing random pattern
have been studied for the growth of biological cell colonies, fluid displacing in8

a porous medium, dendritic solidification, dielectric breakdown, snowflake formation, and bacterial colonies [33,34]. Some most important classes of surface
growth include Diffusion-Limited Aggregation (DLA) [35,36], Invasion Percolation (IP) [37], and Eden growth [38], which can be used as a basis forunderstanding a wide range of pattern-formation phenomena with disorderly
growth.
Thus, we consider diffusively growing networks on surface with both onion-like
topological and fractal spatial structures. In our network, the position of newnode is determined by DLA, IP, and Eden models on a square lattice. Exactly,
only DLA and IP models at the critical threshold generate a fractal structure.
These models have the following processes [33] and explanations to give a new
insight of the self-organized design of spatial network.
DLA model As an idealization of the irreversible aggregation, the following
process forms a growing diffusive cluster. It is motivated from several phenomena of biological interest for the surface growth with complicated shape,
which corresponds to a distributed local extension of technological or social
network system.
The initial configuration is a single occupied site on a lattice. At each generation step, the cluster of occupied sites is grown by launching a random
walker from outside of the occupied region, and allowing it to its random
walk path until it reaches a site that is adjacent to the occupied site. The
process is repeated with a new random walker.
IP model It is based on a transport process by the slow displacement of a
wetting fluid in a porous media. The percolation growth corresponds to an
extension in avoiding geographical obstacles engraved by longstanding rains
and winds for the network construction.
9

Initially, random numbers or thresholds are assigned to the sites of a lattice.
They represent the capillary pressures for penetrating through the porous
medium or the difficulties (low priorities) to install network connections on
a geographical space. At each generation step, an unoccupied site with thelowest threshold (smallest random number, highest priority) is selected as
an injection point on the perimeter, and occupied. Such process is repeated.
Eden model It imitates a cell division process, which corresponds to themost local extension to neighbor space in a simple way.
Starting with an occupied cell (site), an occupied cell on the perimeter ofthe cluster is randomly selected with equal probability. One of its nearest
neighbor unoccupied perimeter cell is selected and occupied. The cluster isgrown by adding the selected nearest neighbor at each generation step. Suchprocess is repeated for a new selection of cell with the division.
As a constraint in the surface growth, the inserted position of new node islimited on the perimeter of connected cluster. Figure 1(b) shows that the internal node(s) marked by × can’t be selected, since the only neighbors markedbyof shaded positions are the candidates. In other words, the selection ofa node is not uniformly at random (u.a.r) in the growing network. However,the limitation is rather reasonable, since the perimeter is a contact area fromthe outer world into the network through the growth. Moreover, althoughu.a.r selection is not equivalent to independent one, the perimeter sites cangrow simultaneously in distributed processes on several places. These sites
autonomously perform the processes initiated by diffusive growing, own local
timers corresponded to thresholds 2 , or random numbers. It is an important
2

The threshold may be related to the amount of potential communication or trans-

portation requests which are proportional to a population density.

10(a) DLA Model: δ = 0.3, psc = 0.015(b) IP Model: δ = 0.3, psc = 0.013(c) Eden Model: δ = 0.3, psc = 0.009
Fig. 2. (Color online) Growing spatial networks for N (t) = 200, 500, 1000 and 2000
from left to right with arranged scales. Gradually colored node is according to its
degree: 1-3(cyan), 4-6(blue), 7-9(green), 10-12(magenta), and the larger(red).

discussion point in this paper whether the constraint on the surface growthhardly affect the emergence of an onion-like topological structure.
Typical shapes of the growing spatial networks are shown in Fig. 2. Thesemodels form (a) dendritic, (b) porous, and (c) compact patterns, respectively,on a square lattice. Large degree (magenta and red) nodes are spontaneouslyinterspersed in constructing densely connected parts. The rate psc of adding
shortcut links is regulated to be a same condition of the connection density
as hki ≈ 5.6 at N = 2000 in all models. We also set initial complete graphof N0 = 4, IT = 50, and a = 0.3. Since we want to investigate the effectof the copying process with adding shortcut links on the robustness and theefficiency, we use a small value of a which is different from 3.0 in the rewiring11

algorithm [21]. Too large value of a restricts linking in the copying process,only the mutual link may be remained at each time step in the growing. This
point will be mentioned again in subsection 3.1.
Figures 3(a)-(c) show the degree distributions in the onion-like networks according to DLA, IP, and Eden models. We remark that the largest degree kmax
is bounded around 20 with the exponential tail for N = 2000 (see Inset). The
load at a node for maintaining links becomes smaller than that in SF networks, since there is no huge hubs. We compare Figs. 3(a)-(c) with the result
for the previous generation method of spatial growing networks [23] without
the constraint in the surface growth, in which a new node is located on random
radius between rmin and rmax with a random direction [39] from the positionof a uniformly randomly chosen node in order to make proximity connections
heuristically. Figure 3(d) shows the distribution with slightly larger kmax but
the exponential tail is more clear in the spatial growing networks without theconstraint in the surface growth. The smaller kmax in Fig 3(a)-(c) is probably
caused by the constraint.
We shows the average degree hknn i of the nearest neighbor nodes of nodewith degree k in Fig. 4. The increasing slope represents positive degree-degreecorrelations which are necessary to be onion-like topology. The drops in k ≥ 15
are ignorable because of finite-size effect (see the tails of p(k) in Fig. 3). Notethat the case of δ = 0.1 has also positive degree-degree correlations in spiteof the tree-like structure without onion-like topology. From top to bottom
in Fig. 5, we show examples of tree-like and onion-like topological structuresvisualized by Pajek [40] in ignoring the spatial positions of nodes on the surface
growth. In particular, from the 2nd row to the bottom for δ = 0.3, 0.5, 0.7,
and 0.9, high degree nodes concentrate on the center area while low degree
12

0.1
0.08

P(k)

0.06
0.04
0.02

10

-1

10

-2

10

-3

10

-4

10

-5

10

-6

5

10

0.12
0.1
0.08
0.06
0.04
0.02

0

5

10

0
0

δ = 0.1
δ = 0.3, psc=0.013
δ = 0.5, psc=0.025
δ = 0.7, psc=0.035
δ = 0.9, psc=0.042

0.14

P(k)

0.12
P(k)

0.16

δ = 0.1
δ = 0.3, psc=0.015
δ = 0.5, psc=0.026
δ = 0.7, psc=0.035
δ = 0.9, psc=0.042

0.14

P(k)

0.16

15

15
k

20

20

25

25

30

0

P(k)

5

10

0.04
0.02

-1

10

-2

10

-3

10

-4

10

-5

10

-6

0.16

5

10

-6

0

5

10

15
k

20

20

25

30

25

30

δ = 0.36
δ = 0.5, psc=0.010
δ = 0.7, psc=0.027
δ = 0.9, psc=0.040

0.14
0.12
0.1
0.08
0.06
0.04
0.02

0

5

10

0
0

-5

10

15

P(k)

0.06

10

-4

10

(b) IP model

P(k)

P(k)

0.1
0.08

-3

10

k

δ = 0.1
δ = 0.3, psc=0.009
δ = 0.5, psc=0.022
δ = 0.7, psc=0.034
δ = 0.9, psc=0.042

0.12

-2

10

0

(a) DLA model
0.14

-1

10

30

k

0.16

10

15

20

15
k

20

25

10

-1

10

-2

10

-3

10

-4

10

-5

10

-6

0

5

10

30

15
k

20

25

30

0
25

30

0

k

5

10

15

20

25

30

k

(c) Eden model(d) Spatial growing modelFig. 3. (Color online) Degree distribution in the networks according to (a) DLA, (b)IP, (c) Eden, and (d) Spatial growing models for N = 2000 with hki ≈ 5.6. Inset
shows the exponential decay of tail part approximated by a straight line in semi-log
plot. These results are averaged over 100 samples.

nodes surround them.

3

Robustness and efficiency on the growing networks

We investigate the robustness against random failures and malicious attacks
in subsection 3.1, the growing behavior in subsection 3.2, and the efficiencyof path in subsection 3.3. In the malicious attack, nodes are removed in decreasing order of the current degrees through the recalculations [41]. We also
discuss the resilience against sequential attacks in subsection 3.4.
13

10

8

6

12

δ = 0.1
δ = 0.3, psc=0.013
δ = 0.5, psc=0.025
δ = 0.7, psc=0.035
δ = 0.9, psc=0.042

10

<knn>

8
<knn>

12

δ = 0.1
δ = 0.3, psc=0.015
δ = 0.5, psc=0.026
δ = 0.7, psc=0.035
δ = 0.9, psc=0.042

8

6

6

4

4

4

2

2

2

0

0
0

5

10

15

20

25

30

0
0

5

10

k

(a) DLA modelδ = 0.1
δ = 0.3, psc=0.009
δ = 0.5, psc=0.022
δ = 0.7, psc=0.034
δ = 0.9, psc=0.042

10

<knn>

12

15

20

25

30

0

k

(b) IP model

5

10

15

20

25

k

(c) Eden modelFig. 4. (Color online) Distribution of the average degree hknn i of the nearest neighbornodes of node with degree k in the networks according to (a) DLA, (b) IP, and (c)Eden models from left to right for N = 2000 with hki ≈ 5.6. Positive degree-degreecorrelations appear except the tails with finite-size effect in all cases. These results
are averaged over 100 samples.

3.1 Robustness of connectivity on the growing networks

We consider following two measures for the robustness of connectivity and thedegree-degree correlation in a network. For the robustness, we investigate anindex [17,18,21]:
1
1 X
R=
S(q),
N q=1/N(2)

where S(q) denotes the number of nodes in the giant component (GC: largest
connected cluster) after removing qN nodes, q is a fraction of removed nodes
by random failures or malicious attacks. The range of R is [0, 0.5], where R = 0
corresponds to a completely disconnected network consisting of isolated nodes,
and R = 0.5 corresponds to the most robust network. As a measure of degreedegree correlation, we investigate the assortativity [42,43]r=

S1 Se − S22,
S1 S3 − S22
1430

(a) DLA model(b) IP model(c) Eden modelFig. 5. Visualization of the topological structures of the networks according to (a)DLA, (b) IP, and (c) Eden models from left to right. A tree-like structure appears at
the top for δ = 0.1, in otherwise onion-like structures with a core area of high degree
nodes surrounded by low degree nodes appear from the 2nd row to the bottom forδ = 0.3, 0.5, 0.7 and 0.9. The node size is proportional to its degree.

where S1 =Pi k i , S2

=

P

2
i ki

S3 =

P

3
i k i , Se=P

ij Aij ki kj , Aijdenotesthe i-j element of the adjacency matrix. The range of r is [−1, 1] as thePearson correlation coefficient for degrees. Nodes with similar degrees tend to15

be connected as r > 0 is larger. Note that onion structure and assortativenesswith a large r > 0 are distinct properties [17]: Not all assortative networks
have onion structure but all onion networks are assortative [21]. Therefore,
the value of r > 0 is relatively large in an onion-like network.

Table 1 shows the average values over 100 samples for our networks witha = 0.3 in the 4-6th columns and the corresponding rewired version reconstructed by Wu and Holme’s algorithm [21] with a = 3.0 in the 7-9th columns.
R:failures and R:attacks denote the robustness index defined by Eq. (2) against
random failures and malicious attacks, respectively. Note that the rate psc ofadding shortcut links is regulated to be hki ≈ 5.6 with a same connection
density. We remark that, with higher values of R, the robustness is improved
from the tree-like network generated by only the copying process for δ = 0.1 tothe networks for δ = 0.3 ∼ 0.9. These networks have an onion-like topologicalstructure with high assortativity r, since the values of R are slightly smaller
but almost coincide with R = 0.436 ∼ 0.444 against random failures and
R = 0.307 ∼ 0.326 against malicious attacks in the rewired version [21] to be
an onion-like network with the nearly optimal robustness. Although the assortativity r in the rewired version becomes larger in all cases, the improvementon the robustness from our networks is small. Table 2 shows the results forcomparison between the cases of a = 0.3 and a = 3.0. In order to be hki ≈ 5.6
in the case of a = 3.0, larger rates psc are necessary especially for large rates
δ of deletion. The setting of psc means that the effect of the copying process
becomes very weak within limited strong degree-degree correlations, because
almost all of duplication links are failed as deletion at each time step as similar
to the case of δ = 0.9. Not surprisingly, a larger assortativity r is obtained inTable 2 because of stronger degree-degree correlations by larger a than that
16

1
0.8

δ = 0.1
δ = 0.3, psc=0.015
δ = 0.5, psc=0.026
δ = 0.7, psc=0.035
δ = 0.9, psc=0.042

0.8

0.6

S(q)/N

S(q)/N1

δ = 0.1
δ = 0.3, psc=0.015
δ = 0.5, psc=0.026
δ = 0.7, psc=0.035
δ = 0.9, psc=0.042

0.4
0.2

0.6
0.4
0.2

0

0
0

0.2

0.4

0.6

0.8

1

0

0.2

0.4

0.6

q

(a) Relative size of GC for attacks

1(b) Relative size of GC for failures

4.5

2.5

4

120
100

3.5

2

<s(q)>

80

3

60
40

2.5

<s(q)><s(q)>

0.8

q

20

2

0
0

0.2

0.4

0.6

0.8

1

60
50

1

40
<s(q)>

q

1.5

1.5

30
20

1

0.5

10

0.5

0
0

0

0.2

0.4

0

0.2

0.4

0.6

0.8

1

0

q

0.6

0.8

1

q

0
0.2

0.4

0.6

0.8

1

q

(c) Ave. size of clusters for attacks(d) Ave. size of clusters for failures

Fig. 6. (Color online) Robustness against (a)(c) malicious attacks and (b)(d) random
failures in the networks according to DLA model for N = 2000 with hki ≈ 5.6.
The top:(a)(b) shows the relative size S(q)/N of the giant component (GC) versus
fraction q of removed nodes, and the bottom:(c)(d) shows the average size hs(q)iof isolated clusters except the GC. Similar graphs are obtained for IP and Edenmodels.

for each corresponding case in Table 1. However, the value of robustness index
R in Table 2 is at a same level as that for each corresponding case in Table
1. There are no notable differences among these results for DLA, IP, Edenmodels from top to bottom in both Tables. Thus, the setting of a = 0.3 does
not lose the intrinsic property for the robustness in our networks, moreover
the effect of the copying process remains.
In the following until the end of next section, we set a = 0.3 unless otherwise
noted. Figure 6 shows typical results of the robustness. Inset (cyan line) shows
17

0.3
7

0.4

6

0.25

5

0.2

0.2
δ = 0.1
δ = 0.3, psc = 0.015
δ = 0.5, psc = 0.026
δ = 0.7, psc = 0.035
δ = 0.9, psc = 0.042

0.1
0
0

1000
N(t)

R

<k>

r

0.3

4

0.15

3
0.1

2
1
2000

0.05
0

1000
N(t)

2000

0

1000
N(t)

2000

0

1000
N(t)

2000

0

1000
N(t)

2000

0.3
7

0.4

6

0.25

5

0.2

0.2
δ = 0.1
δ = 0.3, psc = 0.013
δ = 0.5, psc = 0.025
δ = 0.7, psc = 0.035
δ = 0.9, psc = 0.042

0.1
0
0

1000
N(t)

R

<k>

r

0.3

4

0.15

3
0.1

2
1
2000

0.05
0

1000
N(t)

2000

0.3
7

0.4

6

0.25

5

0.2

0.2
δ = 0.1
δ = 0.3, psc = 0.009
δ = 0.5, psc = 0.022
δ = 0.7, psc = 0.034
δ = 0.9, psc = 0.042

0.1
0
0

1000
N(t)

R

<k>

r

0.3

4

0.15

3
0.1

2
1
2000

0.05
0

1000
N(t)

2000

Fig. 7. (Color online) Time-courses of assortativity r, average degree hki, robustness index R against the malicious attacks in the growing networks according to(top) DLA, (middle) IP, (bottom) Eden models for the size N (t). These results areaveraged over 100 samples.

the vulnerability in the case of tree-like networks for δ = 0.1. Note that thevalue of R defined by Eq.(2) corresponds to the area under the line of S(q)/N.
The peak of hsi corresponds to the critical point qc at the breaking of the GC(dropping point of S(q)/N). Although a larger qc indicates a more robust
network, R is generally a more precise index than qc . Because different valuesof R can exist for a same value of qc depending on the steepness of dropping
curve of S(q)/N.
18

3.2 Growing behavior

We investigate the growing behavior of our proposed networks. In Fig. 7 left,
middle, and right, for the time-courses of assortativity r, average degree hki,
and robustness index R, we obtain similar results in the networks according
to DLA, IP, and Eden models. They are consistent with the behavior in thespatially growing model [23] without the constraint in the surface growth. As
shown at the left of Fig. 7 top, middle, and bottom, r is almost constantthrough the growing except the cases of δ = 0.7 and 0.9 denoted by dashed(blue) and dotted (magenta) lines. At the middle column of Fig. 7 top, middle,
and bottom, hki increases for the the growing size N(t) = t + 4. The slope(increasing rate) becomes steeper as the deletion rate δ is larger. At the rightof Fig. 7 top, middle, and bottom, while R also increases in the simultaneous
progress of the copying and adding shortcut links, it decreases in the casesof δ = 0.1 without shortcuts in the tree-like network denoted by the dashed(cyan) lines. In general, larger hki with more links tends to lead to higher
robustness. Indeed, the increasing of hki corresponds to the increasing of R in
Fig. 7 top, middle, and bottom. Note that the decrease of R in the first stageof small N(t) is due to the tree-like structure before shaping an onion-like
topological structure. Thus, our proposed networks become more robust in
the growth with the enhancement of onion-like topology. We remark that thecase of δ = 0.1 seems to be good with high R in the first stage of small N(t)while the cases of δ = 0.7 and 0.9 (blue and magenta lines) seem to be goodwith larger increasing around the last stage of large N(t). The case of δ = 0.3(red line) is comparatively stable with smaller fluctuation in the entire stage.
19

160

100

δ=0.1
δ=0.3, psc=0.013
δ=0.5, psc=0.025
δ=0.7, psc=0.035
δ=0.9, psc=0.042

140
120
Link length

120
Link length

160

δ=0.1
δ=0.3, psc=0.015
δ=0.5, psc=0.026
δ=0.7, psc=0.035
δ=0.9, psc=0.042

140

80
60

100
80
60

40

40

20

20

0

0
0

1000

2000

3000
Rank

4000

5000

6000

0

(a) DLA model
160

160

100

3000
Rank

4000

5000

6000

δ=0.36
δ=0.5, psc=0.010
δ=0.7, psc=0.027
δ=0.9, psc=0.040

140
120Link length

Link length

120

2000

(b) IP model

δ=0.1
δ=0.3, psc=0.009
δ=0.5, psc=0.022
δ=0.7, psc=0.034
δ=0.9, psc=0.042

140

1000

80
60

100
80
60

40

40

20

20

0

0
0

1000

2000

3000
Rank

4000

5000

6000

0

(c) Eden model

1000

2000

3000
Rank

4000

5000

6000

(d) Spatial growing modelFig. 8. (Color online) Rank plot of link lengths measured by the Euclidean distancein the networks for N = 2000 with hki ≈ 5.6. These results are averaged over 100
samples.

3.3 Efficiency of path on the growing networks

Next, we investigate the communication or transportation efficiency in thegrowing networks. Obviously, shorter links and paths are better with bothless construction and maintenance costs. Figure 8 shows the rank plot of link
lengths. The order of shorter links is (c) Eden model < (b) IP model < (a)DLA model < (d) Spatial growing model [23] without the constraint in thesurface growth, however the difference between (b) and (a) is very small. Thisorder of link lengths is reasonable because Eden model tends to be compact
while IP model tends to percolate making some holes as porous structure and
DLA model tends to spread widely along dendritic edges. The tops of Figs. 9,
10, and 11 show the average path length hLij i counted by hops between two
20

70
60
50

δ = 0.1
δ = 0.3, psc = 0.015
δ = 0.5, psc = 0.026
δ = 0.7, psc = 0.035
δ = 0.9, psc = 0.042

60
50

40

<Lij>

<Lij>

70

δ = 0.1
δ = 0.3, psc = 0.015
δ = 0.5, psc = 0.026
δ = 0.7, psc = 0.035
δ = 0.9, psc = 0.042

30

40
30

20

20

10

10

0

0
10

100

1000

10000

10

100

N(t)

1000

10000

N(t)

(a) Ave. hops on min. hop paths on(b) Ave. hops on shortest paths on

the nets according to DLA model

the nets according to DLA model

160

120

140

100

120
80
<Dij>

<Dij>

100
80
60

60
40

40
20

20
0

0
10

100

1000

10000

10

100

N(t)

1000

10000

N(t)

(c) Ave. dist. on min. hop paths on(d) Ave. dist. on shortest paths on

the nets according to DLA model

the nets according to DLA modelFig. 9. (Color online) Average path length hLij i counted by hops (top:(a)(b)) andthe average distance hDij i measured by Euclidean distance (bottom:(c)(d)) in thegrowing networks according to DLA model. The left:(a)(c) and right:(b)(d) show
the results for the minimum hop paths and the shortest distance paths between two
nodes, respectively. These results are averaged over 100 samples.

nodes on the paths of (left) minimum hop and (right) shortest distance. We
obtain in the tree-like networks (cyan line) monotone increasing curves, whilein the onion-like networks (other color lines) convex curves with up-down,
whose parts in decreasing the number of hops on both paths are related tothe increasing of hki with more links as shown at the middle column of Fig.
7. It is remarkable that almost constant path length even for the growing size
is better than O(log N) of the SW property.
21δ = 0.1
δ = 0.3, psc = 0.013
δ = 0.5, psc = 0.025
δ = 0.7, psc = 0.035
δ = 0.9, psc = 0.042
<Lij>

<Lij>

50
45
40
35
30
25
20
15
10
5
0
10

100

1000

10000

55
50
45
40
35
30
25
20
15
10
5
0

δ = 0.1
δ = 0.3, psc = 0.013
δ = 0.5, psc = 0.025
δ = 0.7, psc = 0.035
δ = 0.9, psc = 0.042

10

100

N(t)

1000

10000

N(t)

(b) Ave. hops on shortest paths on

the nets according to IP model

the nets according to IP model

100
90
80
70
60
50
40
30
20
10

<Dij>

<Dij>

(a) Ave. hops on min. hop paths on

0

100
90
80
70
60
50
40
30
20
10
0

10

100

1000

10000

10

N(t)

100

1000

10000

N(t)

(c) Ave. dist. on min. hop paths on(d) Ave. dist. on shortest paths on

the nets according to IP model

the nets according to IP modelFig. 10. (Color online) Average path length hLij i counted by hops (top:(a)(b)) andthe distance hDij i measured by Euclidean distance (bottom:(c)(d)) in the growing
networks according to IP model. The left:(a)(c) and right:(b)(d) show the results
for the minimum hop paths and the shortest distance paths between two nodes,
respectively. These results are averaged over 100 samples.

The bottoms of Figs. 9, 10, and 11 show the average path distance hDij i
measured by the sum of link lengths as Euclidean distances on the paths of(left) minimum hop and (right) shortest distance. We remark that evident
difference does not appear in hDij i for varying δ in each of Figs. 9, 10, and 11
except the tree-like networks for δ = 0.1 (cyan line).
The orders of efficient shorter paths are Fig. 11: Eden model < Fig. 10: IP
model < Fig. 9: DLA model in the measures of both hLij i and hDij i, however22δ = 0.1
δ = 0.3, psc = 0.009
δ = 0.5, psc = 0.022
δ = 0.7, psc = 0.034
δ = 0.9, psc = 0.042
<Lij>

<Lij>

22
20
18
16
14
12
10
8
6
4

22
20
18
16
14
12
10
8

δ = 0.1
δ = 0.3, psc = 0.009
δ = 0.5, psc = 0.022
δ = 0.7, psc = 0.034
δ = 0.9, psc = 0.042

6
4

2

2
10

100

1000

10000

10

100

N(t)

1000

10000

N(t)

(b) Ave. hops on shortest paths on

the nets according to Eden model

the nets according to Eden model

55
50
45
40
35
30
25
20
15
10
5
0

40
35
30
25
<Dij>

<Dij>

(a) Ave. hops on min. hop paths on

20
15
10
5
0

10

100

1000

10000

10

N(t)

100

1000

10000

N(t)

(c) Ave. dist. on min. hop paths on(d) Ave. dist. on shortest paths on

the nets according to Eden model

the nets according to Eden modelFig. 11. (Color online) Average path length hLij i counted by hops (top:(a)(b)) andthe distance hDij i measured by Euclidean distance (bottom:(c)(d)) in the growing
network according to Eden model. The left:(a)(c) and right:(b)(d) show the results
for the minimum hop paths and the shortest distance paths between two nodes,
respectively. These results are averaged over 100 samples.

the difference among them is small especially in hLij i for δ = 0.3 ∼ 0.9. In
addition, all of them in Figs. 9, 10, and 11 slightly deviate from straight linesof O(log N) in semi-log plot as the SW property, although the SW property
is obtained in the spatial growing networks [23] without the constraint in
the surface growth. Thus, our proposed networks are efficient because theincreasing rates of the average path lengths and distances are suppressed in
the growing size. Note that the length hLij i on the minimum hop path (left)
is shorter than that on the shortest distance path (right), while the distance23

hDij i on the minimum hop path (left) is longer than that on the shortest
distance path (right), in each figure.

3.4 Resilient connectivity against sequential attacks

Through this paper, we discuss dynamics of network configuration itself at
the most basic infrastructure for communication or transportation systems,
in which temporal and/or fixed (corresponding to wireless and/or wired) connections are possible depending on the time-scale for changing the connection
structure in a network. The quick change results in ad hoc networks, while
the slow change is treated as an incremental modification of network. Bothcases and the mixed one are not excluded, however we have assumed that eachnode or link is persisted once it is added unless removed by failures or attacks
to simplify the discussion. While other dynamics of information flows, rumor
spreading, opinion formation, synchronization, or logistics on a network, issignificant for applications in wireless, sensor, mobile communication systems
or autonomous transportation systems, in which operation protocols for birthand death of communication or transportation request, routing, avoidance ofcongestion, task allocation, queuing, awareness of location, monitoring of system’s states or conditions, and so on [44], are necessary. We have pointed out
the issues of rethinking packet generation according to population, decentralized routing strategy, and link hierarchy among long and short ranges withhigh and low transfer speeds [45] in the state-of-the-art network technologies.
In addition, although several models have been proposed for the coevolution of
network formation and opinion spreading [46,47] and for the coupled dynamics with network evolution and packet flows [6,7,48,49,50], they are beyond
24our current scope because of more complex dynamics between network generation and information flow in various protocols, device technologies, users,
and situations of utilization.
0.3

δ = 0.3, psc = 0.015
δ = 0.5, psc = 0.026
δ = 0.7, psc = 0.035
δ = 0.9, psc = 0.042

0.4
0.3

7
0.25

6

0.2

0.2
R

<k>

r

5
4

0.15

3

0.1

0.1

2

0

1
0

500

1000

1500

2000

0.05
0

500

Step: N(t)

0.3

1500

2000

1500

2000

0.25

6

0.2
R

0.2

1000

7

<k>

r

500

Step: N(t)

5
4

0.15

3

0.1

0.1

2

0

1
0

500

1000
Step: N(t)

1500

2000

0.3

0.05
0

500

1000
Step: N(t)

1500

2000

500

1000
Step: N(t)

1500

2000

0

500

1000
Step: N(t)

1500

2000

7
0.25

6

0.2
R

<k>

5
0.2

0

0.3

δ = 0.3, psc = 0.0009
δ = 0.5, psc = 0.022
δ = 0.7, psc = 0.034
δ = 0.9, psc = 0.042

0.4

r

0

0.3

δ = 0.3, psc = 0.013
δ = 0.5, psc = 0.025
δ = 0.7, psc = 0.035
δ = 0.9, psc = 0.042

0.4

1000
Step: N(t)

4

0.15

3

0.1

0.1

2

0

1
0

500

1000
Step: N(t)

1500

2000

0.05
0

500

1000
Step: N(t)

1500

2000

Fig. 12. (Color online) Time-courses of assortativity r, average degree hki, robustness
index R against the malicious attacks in the networks damaged by sequential attacks
at every 10 time steps. These results are averaged over 100 samples according to(top) DLA, (middle) IP, (bottom) Eden models.

On the other hand, we consider an interaction of network generation witha change of environment, especially in sequential attacks. We show that our
proposed networks have resilient connectivity even in the previously describedgrowing scheme of constant δ, psc , and IT , without any remedial measures forinsistent attacks. Figure 12 shows the time-courses of r, hki, and R against
the further attacks in the networks damaged by sequential attacks. We set
the same values of δ, psc , and IT in the previous subsection, and the largest
25degree node with its links is removed through the recalculation of degrees at
every 10 time steps. At the left of Fig. 12 top, middle, and bottom for DLA,
IP, and Eden models, respectively, the damaged networks by the sequential
attacks have positive degree-degree correlations around r ≈ 0.2 somehow orother. At the middle and right of Fig. 12, the robustness is recovered withslowly increasing hki, since R is decreasing in the first stage of small N(t) but
increasing after a time. We obtain similar behavior in these spatial growthmodels as shown in Fig. 12 from top to bottom, and the case of δ = 0.3(red line) with the stronger effect of the copying is better than other cases ofδ = 0.5, 0.7, and 0.9 (green, blue, and magenta lines). In particular, in thecase of δ = 0.9 (magenta line), R does not increase until N(t) ≈ 500 due
to the insistent attacks. All values of r, hki, and R in Fig. 12 are smaller,
as compared with the results for the pure growing networks in Fig. 7. Thus,
even the damaged networks maintain the robust onion-like topology in thegrowing scheme. We remark that in the sequential attacks the robustness isprotected locally by the copying, and enhanced globally in connecting isolated
clusters by adding shortcut links between randomly chosen nodes. Remember
the local proxy and complementary functions in subsection 2.1. When more
severe attacks in shorter interval at every 5 time steps are given, around therobustness index R ≈ 0.15 ∼ 0.2 against the further attacks, the networks
no longer have an onion-like topological structure because of the assortativityr ≈ 0.0 or r < 0.0 in this growing scheme of constant δ, psc , and IT without
any remedial measures.

26

4Conclusion

We have proposed a spatial design method of robust and efficient networks
with typical surface growth patterns. It is self-organized through the simultaneous progress of the copying and adding shortcut links [23] taking into
account linking homophily to make an onion-like topological structure withpositive degree-degree correlations. For the copying, the selection of node is
not uniformly at random but limited to the neighbors of the perimeter of connected cluster in the growing network on a space. In spite of the constraint
on the surface growth, we have obtained that the robustness against random
failures and malicious attacks is nearly optimal of slightly weaker than theentirely rewired version [21]. Moreover, the efficiency of path measured in the
hop count is better than O(log N) of the SW property but one measured in
the Euclidean distance slightly degraded from the SW property. In particular,
the growing network becomes more robust and efficient in time-course. However, we may have to consider a resource allocation problem for the increasingof hki required with more links. On the other hand, we have also found that
there are no huge hubs bounded by an exponential tail of degree distribution,and that large degree nodes are spontaneously interspersed on a space.

Moreover, we have shown that the robust onion-like topological structure remains even in the random growth damaged by the sequential attacks. When anode is removed by serious disasters or insistent attacks, more effective strategies than a constant random growth can be considered to repair the damaged
parts. If a new node is added near the removed node as the proxy of it insteadof the random location on a neighbor site on the perimeter in the surface
growth, the network is probably more effectively healed over. If the parame27

ters of δ, psc , and IT are regulated according to the damages, the network is
recovered to the original level of performance for the communication or thetransportation. These trials will require further study with healing and recovering processes, e.g. we should consider which parts of network have priorities
to prevent spreading damages in topological and spatial importance. In a realistic situation such as disaster or battle-field, resources for the strategies arelimited and should be allocated effectively in the priorities.

In summary, our growing network models suggest that robust and efficient
onion-like topological structure can emerge even when the positions of nodes
are limited in the contact area of the spatial network. In the cooperativegrowing mechanism, the local proxy and complementary robust functions by
the copying and adding shortcut links will be useful for temporal evolution ofresilient network and a repair strategy in large-scale disasters or system crises.
However, it is an issue in general what type of constraint for locating nodes
on a space is an obstacle to the emergence of onion-like topology. It may berelated to limited facilities from geographical and economical viewpoints.

Acknowledgment

The author would like to thank Mitsugu Matsushita for his valuable comments about fractal growth models on a space and to anonymous reviewers
for their suggestions to improve the readability of manuscript. This researchis supported in part by a Grant-in-Aid for Scientific Research in Japan, No.
25330100.
28

References[1] F. Dressler, Self-Organization in Sensor and Actor Networks, John Wiley &Sons, 2007.
[2] A.-L. Babarási, R. Albert, Science 286 (1999) 509–512.
[3] R. V. Sole, R. Pastor-Satorras, E. Smith, T. B. Kepler, Advances in Complex
Systems 5 (1) (2002) 43–54.
[4] R. Pastor-Satorras, E. Smith, R. V. Sole, Journal of Theoretical Biology 222 (2)(2003) 199–210.
[5] D. Helbing, J. Keltsch, P. Molnár, Nature 388 (1997) 47–50.
[6] A. Tero, S. Takagi, T. Saigusa, K. Ito, D. P. Bebber, M. D. Fricker, K. Yumiki,
R. Kobayashi, T. Nakagaki, Science 327 (5964) (2010) 439–442.
[7] Y. Hayashi, Y. Megumo, Physica A 391 (2012) 872–879.
[8] J. P. K. Doye, C. P. Massen, Physical Review E 71 (2005) 016128.
[9] T. Zhou, G. Yan, B.-H. Wang, Physical Review E 71 (2005) 046141.
[10] W. Nagel, J. Mecke, J. Ohser, V. Weiss, Image Analysis & Stereology 27 (2)(2008) 73–78.
[11] Y. Hayashi, Advances in Complex Systems 12 (1) (2009) 73–86.
[12] Y. Hayashi, Physica A 388 (1) (2007) 991–998, corrigendum (2011).
http://www.sciencedirect.com/science/article/pii/S0378437112002592[13] P. L. Krapivsky, S. Redner, E. Ben-Naim, A Kinetic View of Statistical Physics,
Cambridge University Press, 2010.
[14] M. J. Alava, S. Dorogovtsev, Physical Review E 71 (2005) 036107.

29

[15] D. J. Watts, S. H. Strogatz, Nature 393 (1998) 440–442.
[16] R. Albert, H. Jeong, A.-L. Barabási, Nature 406 (2000) 36–44.
[17] C. M. Schneider, A. A. Moreira, J. S. Andrade Jr., S. Havlin, H. J. Herrmann,
PNAS 810 (10) (2011) 3838–3841.
[18] H. J. Herrmann, C. M. Schneider, A. A. Moreira, J. S. Andrade Jr., S. Havlin,
Journal of Statistical Mechanics (2011) P01027.
[19] T. Tanizawa, S. Havlin, H. E. Physical Review E 85 (2012) 046109.
[20] C. I. N. S. Filho, A. A. Moreira, R. F. S. Andrade, H. J. Herrmann, J. S. Andrade
Jr., Scientific Report 5 (9082).
www.nature.com/articles/srep09082[21] Z.-X. Wu, P. Holme, Physical Review E 81 (2011) 026116.
[22] M.E.J. Newman, S.H. Strogatz, D.J. Watts, Physical Review E 64 (2001)
026118.
[23] Y. Hayashi, IEEE Xplore Digital Library Proc. of 2014 IEEE 8th Int.
Conf. on SASO: Self-Adaptive and Self-Organizing Systems (2014) 50–59,
http://arxiv.org/abs/1411.7719.
[24] A. Zolli, A. M. Healy, Resilience: Why Things Bounce Back, Simon & Schuster,
2013.
[25] C. M. Schneider, N. Yazdani, N.A.M. Araújo, S. Havlin, H.J. Herrmann,
Scientific Reports 3 (2013) 1969. http://www.nature.com/articles/srep01969[26] M. Stippinger, J. Kertész, Physica A 416 (2014) 431–487.
[27] X.-H. Yanga, S.-L. Lou, G. Chen, S.-Y. Chen, W. Huang, Physica A 392 (2013)
3531–3536.
[28] E. R. Colman, G. J. Rodgers, Physica A 392 (2013) 5501–5510.

30

[29] M. E. Newman, C. Moore, D. J. Watts, Physical Review Letters 84 (2000) 3201.
[30] Y. Hayashi, J. Matsukubo, Physica A 380 (2007) 552–562.
[31] Y. Hayashi, Y. Ono, Physical Review E 82 (2010) 016108.
[32] D. S. Callaway, J. E. Hopcroft, J. M. Kleinberg, M. E. J. Newman, S. H.
Strogatz, Physical Review E 64 (2001) 041902.
[33] P. Meakin, Fractals, scaling and growth far from equilibrium, Cambridge
University Press, 1998.
[34] E. Ben-Jacob, Contemporary Physics 38 (3) (1997) 205–241.
[35] D. Wilkinson, J. F. Willemsen, Journal of Physics A: Mathematical and General
16 (1983) 3365–3376.
[36] H. E. Stanley, A. Coniglio, S. Havlin, J. Lee, S. Schwarser, M. Wolf, Physica A
205 (1994) 254–271.
[37] T. A. Witten, L. M. Sander, Physical Review B 27 (9) (1983) 36–44.
[38] M. Eden, A two-dimensional growth process, in: J. Neyman (Ed.), Proceedingsof the 4tn Berkeley Symposium on Mathematical Statistics and Probability,
Vol. IV of IV, 1961, pp. 223–239.
[39] R. Xulvi-Brunet, I. M. Sokolov, Physical Review E 75 (2007) 46117.
[40] http://vlado.fmf.uni-lj.si/pub/networks/pajek/[41] P. Holme, B. J. Kim, C. N. Yoon, S. K. Han, Physical Review E 65 (2002)
056109.
[42] M. E. Newman, Physical Review Letters 89 (20) (2003) 208701.
[43] M. E. Newman, Networks -An Introduction-, Vol. 68, Oxford University Press,
New York, NY, 2010.

31

[44] M. Barbeau, E. Kranakis, Principles of Ad-hoc Networking, John Wiley & Sons,
2007.
[45] Y. Hayashi, Rethinking of communication requests, routing, and navigation
hierarchy on complex networks -for a biologically inspired efficient search ona geographical space-, in: I. Bilogrevic, A. Rezazadeh, L. Momeni (Eds.),
Networks -Emerging Topics in Computer Science, iConcept Press, 2012,
Chapter 4, pp. 67–88.

https://www.iconceptpress.com/book/networks--emerging-topics-in-computer-science/110000[46] P. Holme, M. E. Newman, Physical Review E 74 (2006) 056108.
[47] S. Gil, D. H. Zanette, Physics Letters A 356 (2) (2006) 89–94.
[48] S.-W. Kim, J. D. Noh, Physical Review Letters 100 (2008) 118702.
[49] S.-W. Kim, J. D. Noh, Physical Review E 80 (2009) 026119.
[50] Q. Xuan, F. Du, T.-J. Wu, G. Chen, Physical Review E 80 (2010) 046116.

32

Table 1
Average values over 100 samples in the networks for N = 2000 on the surface growthaccording to DLA, IP, and Eden models from top to bottom. The 4-6th columns
show the results for our networks with a = 0.3, and the 7-9th columns show theresults for the corresponding rewired version [21] with a = 3.0 from our networks
with a = 0.3.
DLA

our

networks

with a = 0.3

rewiredversionwith a = 3.0

δ

psc

hki

r

R:failures

R:attacksr

R:failures

R:attacks

0.1

0.0

5.663790

0.428085

0.11414846

0.08546072

0.570401

0.44257568

0.32097051

0.3

0.015

5.6931300.306182

0.42286182

0.27909878

0.563234

0.44446583

0.32624905

0.5

0.026

5.683880

0.315288

0.43330392

0.28798839

0.566574

0.44266511

0.32195528

0.7

0.035

5.560350

0.317886

0.43543737

0.28620190

0.568082

0.43890241

0.31470397

0.9

0.042

5.5921200.321879

0.43776842

0.28822588

0.573602

0.43836274

0.31299371

ournetworks

with a = 0.3

rewiredversionwith a = 3.0

IP
δ

psc

hki

r

R:failures

R:attacksr

R:failures

R:attacks

0.1

0.0

5.980630

0.394308

0.11528832

0.08374447

0.5771010.44597737

0.32535835

0.3

0.013

5.656150

0.277479

0.41909362

0.27702885

0.561372

0.44345529

0.32521399

0.5

0.025

5.691770

0.289450

0.4337521

0.28823022

0.569636

0.44294242

0.32367072

0.7

0.035

5.616860

0.301741

0.43641043

0.28870629

0.5741300.44029968

0.31788086

0.9

0.042

5.606670

0.305765

0.43796751

0.28855921

0.571790

0.43886147

0.31492539

ournetworks

with a = 0.3

rewiredversionwith a = 3.0

Eden
δ

psc

hki

r

R:failures

R:attacksr

R:failures

R:attacks

0.1

0.0

6.644020

0.420114

0.19868989

0.11501878

0.600332

0.45091269

0.33193373

0.3

0.009

5.635930

0.304668

0.41034536

0.25781734

0.567774

0.439060744

0.31314427

0.5

0.022

5.648480

0.285373

0.43086621

0.27727353

0.568454

0.43895619

0.31237012

0.7

0.034

5.657810

0.283205

0.43680778

0.28117685

0.572352

0.43777281

0.30982738

0.9

0.042

5.658680

0.290042

0.43891585

0.28344713

0.566763

0.43673314

0.30796406

33

Table 2
Average values over 100 samples in the networks for N = 2000 on the surface growthaccording to DLA, IP, and Eden models from top to bottom. The 4-6th columns
show the results for comparison between the cases of a = 0.3 and a = 3.0 that isdifferent parameter setting form Table 1, and the 7-9th columns show the results forthe corresponding rewired version [21] with a = 3.0 from our networks with a = 3.0.
DLA

our

networks

with a = 3.0

rewiredversionwith a = 3.0

δ

psc

hki

r

R:failures

R:attacksr

R:failures

R:attacks

0.1

0.0

2.834040

0.437167

0.04345627

0.03607689

0.437008

0.32199987

0.18107685

0.3

0.035

5.650160

0.457448

0.43313566

0.2979080

0.583822

0.43888272

0.31681199

0.5

0.039

5.629190

0.457572

0.43389278

0.29740136

0.579910

0.43849948

0.31413023

0.7

0.043

5.5941000.453034

0.43468667

0.29602458

0.585048

0.43675333

0.31164826

0.9

0.045

5.651210

0.454004

0.43586855

0.29712904

0.582588

0.43772334

0.31261318

ournetworks

with a = 3.0

rewiredversionwith a = 3.0

IP
δ

psc

hki

r

R:failures

R:attacksr

R:failures

R:attacks

0.1

0.0

2.970500

0.400235

0.04522621

0.03565373

0.435406

0.33601715

0.19365666

0.3

0.034

5.635630

0.436601

0.43351504

0.29754534

0.581092

0.43953115

0.31804051

0.5

0.038

5.561670

0.430161

0.43346665

0.29522308

0.582158

0.43758882

0.3138613

0.7

0.043

5.601620

0.430950

0.4351622

0.29589068

0.582668

0.43698282

0.31191742

0.9

0.045

5.662410

0.437168

0.43656923

0.2982953

0.585400

0.43781393

0.31344812

ournetworks

with a = 3.0

rewiredversionwith a = 3.0

Eden
δ

psc

hki

r

R:failures

R:attacksr

R:failures

R:attacks

0.1

0.0

3.167770

0.384913

0.07280454

0.0402646

0.445969

0.35275171

0.19681491

0.3

0.032

5.666700

0.425713

0.43319376

0.29233634

0.580907

0.43759013

0.31193571

0.5

0.037

5.629740

0.422828

0.4342548

0.29071317

0.582505

0.43608627

0.3089480

0.7

0.043

5.663520

0.419765

0.43617703

0.29168745

0.582820

0.43608627

0.30800115

0.9

0.045

5.664820

0.420572

0.43666387

0.2916347

0.579751

0.43535101

0.30689578

34