Master’s Thesis

Title

Fractal Virtual Network Method
for Achieving Efficiency and Robustness

Supervisor
Professor Masayuki Murata

AuthorKoki Sakamoto

February 9th, 2018

Department of Information Networking
Graduate School of Information Science and Technology
Osaka University

Master’s Thesis

Fractal Virtual Network Method for Achieving Efficiency and Robustness
Koki Sakamoto

Abstract
In recent years, the types of network services provided through the Internet are increasing day
by day, especially Internet of Things (IoT) services have been developed. A large number of devices have connected to the Internet. Network virtualization has attracted attention as a technology
to flexibly accommodate various network services including IoT services. In order to provide IoT
services with sufficient communication quality and availability by network virtualization, it is important to design virtual networks with high communication efficiency and high robustness against
network failures. However, it is difficult to design virtual networks for IoT environment since there
are a great number of devices. To obtain a guideline for designing virtual networks with high communication efficiency and high robustness, our research group has focused on fractal property. Our
research group has preliminarily proposed a construction model of virtual networks with the fractal
property and have verified that the virtual network constructed by the model achieves robustness
against node failures. However, the previous construction model does not consider the physicaldistance between node pairs, which may lead to low communication efficiency on accommodating
actual services. In this thesis, we investigate a design guideline of fractal virtual networks withhigh communication efficiency and robustness considering physical distances for networks withvarious sizes. In the evaluation of communication efficiency and robustness of the virtual network
designed by our construction method, we show that the communication efficiency improves bymore than 30%.

1

Keywords
Internet of Things (IoT)
Virtual Network
Fractal Property
Fractal Dimension
Hierarchical Modular Network

2

Contents
1 Introduction

6

2 Related Work8

2.1Internet of Things . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.2

Network Virtualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

92.3

Virtual Networks for IoT Services . . . . . . . . . . . . . . . . . . . . . . . . .

93 Method for Constructing Virtual Network with Fractal Property

11

3.1

Relation between Fractal Dimension and Physical Distance . . . . . . . . . . . .

11

3.2

Procedure for Fractal Virtual Network Construction . . . . . . . . . . . . . . . .

12

3.3

Topological Properties of Fractal Virtual Networks . . . . . . . . . . . . . . . .

14

4 Efficiency and Robustness of Fractal Virtual Networks

19

4.1

Metrics for Efficiency and Robustness . . . . . . . . . . . . . . . . . . . . . . .

19

4.2

Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

4.2.1

Comparison with Random Network under Unified Cost Conditions . . .

20

4.2.2

Efficiency and Robustness of Networks with Different Fractal Dimensions

22

4.2.3

Efficiency and Robustness on Different Scale of Networks . . . . . . . .

29

5 Conclusion

38

Acknowledgements

39

References

40

3

List of Figures
1

Calculation examples of r and M for a square lattice network (a) and for a tree
network (b) [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2

Link length distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

3

The fractal dimension of networks generated by giving each δ to the algorithm . .

18

4Comparison of efficiency with both Fractal and Random networks . . . . . . . .

23

5Comparison of RSr with both Fractal and Random networks . . . . . . . . . . .

23

6Efficiency of a generated network with each δ . . . . . . . . . . . . . . . . . . .

25

7Relationship between δ and RSr . . . . . . . . . . . . . . . . . . . . . . . . . .

25

8Evaluation method for hierarchical modularity: An example of hierarchical module structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

926

Evaluation method for hierarchical modularity: An example of the adjacency matrix corresponding to the hierarchical module structure in Figure 8 . . . . . . . .

27

10Procedure to construct hierarchical modular structure . . . . . . . . . . . . . . .

28

11

Hierarchical modularity of the fractal network with δ = 1.1 . . . . . . . . . . . .

30

12Hierarchical modularity of the fractal network with δ = 4.5 . . . . . . . . . . . .

31

13

Hierarchical modularity of a random network . . . . . . . . . . . . . . . . . . .

32

14

Hierarchical modularity of a hierarchical modular network . . . . . . . . . . . .

33

15

Efficiency of the networks on each scale . . . . . . . . . . . . . . . . . . . . . .

36

16

Relationship between the network size and the sum of reciprocals of shortest path17

length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

Robustness of the networks on each scale . . . . . . . . . . . . . . . . . . . . .

37

4

List of Tables
1

Procedure to determine module ID . . . . . . . . . . . . . . . . . . . . . . . . .

526

1 Introduction
In recent years, the Internet has provided various network services as an IT infrastructure that
supports our daily lives. In network services, there are video streaming services, SNSs, cloud services and IoT services. Especially in IoT environment, the network scale is huge and different foreach service, and then it is difficult for network administrators to control the whole of networks.
Therefore, considering performance and management aspects of network services, demands of
network administrators such as separating the traffic for each service and efficiently using the network equipment are increasing. Network virtualization technology has gained attention as one oftechnologies to meet these requirements. The network virtualization technology is a technique oflogically dividing a physical network resource and constructing multiple virtual networks on a single physical network. By the network virtualization technology, physical infrastructure providers(InPs) provide an independent virtual network with different functions and performances to eachservice provider (SP), whereby the service providers can independently develop their own network
services using their own virtual networks [1].
Virtual networks need high efficiency and robustness to provide network services with sufficient communication quality and availability because in the case of low efficiency, users of a
network service can not enjoy the service with satisfactory communication quality and in the caseof low robustness, virtual node/link failures do not allow node pairs to communicate with eachother and unfortunately the service may result in failure. Hence, it is desirable that the virtual
network holds high efficiency and high robustness. However, at present, there is no design guidelines for virtual networks with high efficiency and high robustness, and it is not clear what kind of
virtual network SPs should build.
Then, we focus on fractal property as an approach for constructing large-scale virtual networks with high efficiency and high robustness. The fractal property is the property that the samestructure and properties are seen even if the scale for observing the object is changed. In network
science, when we assume that a certain node is a starting point and the hop length from that node
increases, the increase rate of the number of reachable nodes from that node becomes constant.
One of the criteria for quantitatively determining that a network has fractal property is that fractal
dimension df has a finite value. By hop length l and the number of nodes M reachable from6within l hops from a certain origin node, df is defined as
M ∼ l df .

(1)

Our research group has clarified that a topology with fractal property has a large number of redundant paths compared to a topology without fractal property and is robust against node failures [2].
Furthermore, we have devised a design model of a network topology with fractal property andconfirmed that the fractal network using the design model shows excellent performance of failure tolerance [3]. However, most of the existing studies on fractal networks including [3] does nottake physical aspects of networks into account when they devise network design model. Therefore,
there is a problem that it could be impossible to accommodate the virtual network configuration
based on the existing model on the physical network. For example, when you attempt to arrange
a lot of virtual nodes in one physical node, it is conceivable that the upper limit of the number ofvirtual nodes that the physical node can accommodate is exceeded. Besides, when many virtual
nodes are arranged between only nodes in distance on the physical network and the virtual links
are constructed, that leads not only to waste the usable bandwidth of the physical networks but
to make efficiency low even in communication of nearby nodes. Daqing et al. [4] suggest thatthe physical distance between nodes has strong relationship with df , and as the physical distance
between the nodes becomes shorter, df becomes smaller. That is, we can express the physicaldistance by df . Actually, since the physical distance is not taken into account in the network using
the model of the existing studies, its df takes a fixed value. Daqing et al. also suggest that df
is related to the physical diffusion phenomenon, and as df increases, the information spreading
speed in the information network, that is, the efficiency increases. For this reason, in the network
using the existing design model, the information spreading speed is constant, and the average hoplength and the diameter of the network increase as the scale increases, resulting in low efficiency.
In order to solve the problem, in this paper, we devise a virtual network design method with df
as the control parameter of cost, give the virtual network high efficiency and high robustness byconsidering the physical distance and the properties are kept high in IoT environment of different
scales.

7

2 Related Work
2.1 Internet of Things
Internet of Things (IoT) is the future Internet where not only people but things can connect eachother through the Internet [5]. IoT mainly consists of sensors, clouds, analytic systems and actuators. First, the sensors bring various information from circumstances around our lives such astemperature, sound or image. Second, the information is sent to the clouds through the Internet
and is stored as big data in the clouds. Third, analytic systems (often artificial intelligences) analyze the big data, and they exploit and organize meaningful data from a meaningless series ofnumbers and letters. Fourth, according to analysis results, actuators begin to work, and they feedback various information to us or do some work automatically. In this way, IoT can improve ourquality of lives.
In recent years, many SPs have developed own IoT services. Morandi et al. [6] focus on an
urban IoT environment and design it to follow the Smart City vision. In the paper, they provide a comprehensive survey of the enabling technologies, architectures and protocols to realize
the Smart City. Moreover, they mention the technical solutions for the Smart City and present
best-practice guidelines for the design of it. Piyare et al. [7] proposes an extensible and flexible
architecture for integrating wireless sensor networks with the cloud. As the testbed, they develop
a REST-based Web service and realize remote monitoring system. It enables data access fromanywhere and has the alert function that notifies users via email or tweets for monitoring data
numbers when they exceed a certain threshold. Gachet et al. [8] launches the project for the healthcare of the elder people, using technologies associated with IoT. The main concern of the elderlyis their health and its consequences depending on their self-rated ill health. Since the elderly havedifferent health problems, doctors need to accurately diagnose each patients. However, the diagnostics is often dependent on how well the patients understand their ill health and that may lead
incorrect results. Then, to correctly know the patients’ body states, Gachet et al. use the sensors
to quantitively calculate their states and develop the system that feeds back the state information
to doctors.
Here, note that the scale of each network service is different and especially in IoT environment,
the scale is often huge. The network of wireless sensor networks [7] is actually composed ofthousands of sensors while the one of the Smart City [6] consists of millions or more of devices.
8

Therefore, there is a problem that it is difficult for network administrators to control the whole ofa large and different scale of IoT networks and that causes inefficient network configuration.

2.2 Network Virtualization
Network virtualization is a technique that enables us to manage networks easily by dividing physical networks logically for each SP [9]. In detail, in the network virtualization, multiple virtual
machines (virtual nodes) are activated on a single general-purpose server, the virtual nodes areconnected by virtual links using a part of the bandwidth of the physical line and a virtual network
is constructed. Virtual networks can be established on a single physical network unless the capacity of the physical machine is insufficient and it is guaranteed by security protocols that the virtual
networks do not interfere with each other. Multiple virtual networks, therefore, can independently
co-exist on the single physical network and network managers can operate a lot of different virtual
networks for each SPs by system softwares for the operation such as OpenFlow [10].
Note that when SPs construct virtual networks, they need to consider the topologies of the
networks and what structures the topologies hold such as the scale-free [11], small-world [12],hierarchical or modular structures [13]. The worst case is that they selfishly construct a virtual
network ignoring the structure of it and that causes such low efficiency or low robustness that
network services cannot work well. Therefore, it is important that in order to provide a sufficientquality of network services to users, network designers understand the structures of the network
topologies and what effects given the network by the structures.

2.3 Virtual Networks for IoT Services
In this section, we introduce how virtual networks under IoT environment are designed in terms of
topologies. As noted above, since the scale of the IoT networks is huge, it is impossible for humans
to design the whole virtual network considering whether each link between all node pairs are
established or not. In addition, there are few guidelines for designing such a large-scale network.
Thus, network designers currently construct the large-scale network in their own way and theyoften do not comprehend what properties their networks have. In this paper, we present a new
design model for such a large-scale network and show the guidelines to the network designers.
As an approach for designing the large-scale virtual networks, Yoshinobu et al. [3] focus on a9

fractal property. The fractal property is also called a self-similar property and means a property
that a similar structure can be seen on any scale. In Yoshinobu’s design method, they prepare
an arbitrary network in advance and duplicate the same network as the first network. Then, thetwo networks are connected at some level of density, they further duplicate the same network as
the newly constructed network and connect these two networks. After that, the above procedure
is repeated. It is clear that the network designed in that way has the fractal property. However,
the model excludes the physical aspects of the virtual network, that is, the model does not take
into account the arrangement of virtual nodes in the physical network. As a result, when thevirtual network is embedded into the physical network, it is possible that the virtual network
is composed of a lot of long links from a viewpoint of the physical distance depending on thearrangement of virtual nodes and virtual links and the efficiency of the virtual network becomeslow. The lack of physical concepts of networks is true not only for the method in [3] but for
many of the existing studies, where the network topologies are built often based on only degree
properties [11, 12, 14, 15]. Thus, there are few guidelines for designing the large-scale virtual
networks currently and incorporating physical perspectives is a key point.

10

3 Method for Constructing Virtual Network with Fractal Property
In the existing model, since the physical distance is not taken into consideration, the fractal dimension, which is pointed out to be related to the communication efficiency in [4], is fixed, and thecommunication efficiency decreases as the network scale increases. Therefore, in a large-scale environment such as IoT, the efficiency of the network using the existing model is low. This chapter
shows a generation algorithm that obtains a network whose fractal dimension is arbitrary, thereby
confirming that arbitrary fractal dimensions can be actually obtained.

3.1 Relation between Fractal Dimension and Physical DistanceAs noted already, similar structures can be seen on different scales in the network showing the fractal property. However, even among the fractal networks, there are different structures in terms ofdiffusion [16]. For example, if many nodes are allowed to connect only adjacent nodes, the diffusion speed is slow, while if even a few nodes can connect nodes at a distance, the diffusion speed
rapidly gets faster. That sounds the small-world property but the difference between the smallworld and the fractal is that there is no bias in the fractal network from a viewpoint of the degree.
The small-world network often has the scale-free property and so-called ’hub nodes’ shrink the
diameter of the network. However, if the ’hub nodes’ are broken, the damage is very serious andit is possible that the entire network collapses. On the other hand, since the fractal network has
no bias in the degree distribution, the damage to a part of the network anywhere seldom causes
serious situations, as the objects with the fractal property in the natural world is robust [17]. Thatis, the fractal network has different efficiency by controlling link length distribution and is robust
against node failures at some level. The link length distribution of the fractal network, related tothe diffusion, is characterized by a fractal dimension.
As a method for quantitatively evaluating the fractal dimension, Box-Counting Algorithm orCluster-Growing Algorithm is widely used. In the Box-Counting Algorithm, nodes that can reacheach other within a certain hop length are called Boxes, and the number of Boxes for covering theentire network with non-overlapping Boxes is counted. However, since there are countless Box
patterns that can cover the entire network, various heuristic methods have been proposed [18],but since it is impossible to obtain a stable solution in a large-scale network, it is unsuitable forstrict fractal analysis. On the other hand, in the Cluster-Growing Algorithm, the number of nodes

11reachable from an origin node within a certain hop length is counted. Although different results
are obtained depending on the selection of the origin node, a method of obtaining a stable solution
by taking statistics of results at a lot of origin nodes is generally used in the complex network
field. Since it is mathematically proved that the result by Box-Counting Algorithm and the result
by Cluster-Growing Algorithm are equivalent, we assume fractal analysis using Cluster-Growing
Algorithm in the following.
Equation (1) is commonly used to obtain the fractal dimension, but since the focus is on the
hop length in the construction model of Chapter 3.2, It is necessary to redefine it as the link length
r instead of the hop length l as follows:M ∼ rdf .

(2)

Using Equation (2), we obtain df by following the procedure below.
1. Select a node to be an origin (hereinafter, the origin node).
2. Let the set of nodes adjacent to the origin node be shell 1, the node set adjacent to shell 1
and not included in the previous shell be shell 2, and repeat the procedure until it covers all
nodes.
3. Measure the following two.
(a) The average Euclidean distance r between the nodes in shell s and the origin node.
(b) The number of nodes M (s) in shell s.
We execute the above procedure on multiple origin nodes and average the results. By definition,s is the shortest path length between the origin node and any nodes in shell s. An example ofapplying this procedure to both a square lattice network and a tree network is shown in Figure 1.
The fractal dimension is determined from Equation (2).

3.2 Procedure for Fractal Virtual Network Construction
Daqing et al. [4] suggest that when the link length distribution, viewing the network in physicalspace, follows a power distribution, the fractal dimension is found in the scaling exponent of that
distribution. Therefore, we aim to generate a network showing the desired fractal dimension by
giving the scaling exponent as a parameter. A specific generation algorithm is shown below.
12(a)ͷ ൅ ͺ ൅ ͳʹ
ͷ൅ͺ
ͷ
Ͳ

‫ݎ‬ଵ

Ͳ

‫ݎ‬ଵ

‫ݎ‬ଶ ‫ݎ‬ଷ

‫ݎ‬

(b)

Ͷ ൅ ͹ ൅ ͳʹͶ൅͹Ͷ‫ݎ‬ଶ ‫ݎ‬ଷ‫ݎ‬Figure 1: Calculation examples of r and M for a square lattice network (a) and for a tree network(b) [4]

Parameters to be input to the algorithm The number of nodes n, the average degree λ of the
network to generate, the exponent δ of link length following power distribution.
Step 1. Arrangement of nodes Arrange n nodes in a two-dimensional square lattice, but do notconstruct any links here. Let the distance between the nearest nodes be 1. Let the node IDof each node be 0, 1, 2, ..., n − 1.
Step 2. Determination of the degree of each node Select node i (∈ {0, 1, 2, ..., n − 1}) randomly and repeat from Step 2.1 to Step 2.2. for all nodes below.
Step 2.1. Generate an integer random number pi according to Poisson distribution P (λ).
Step 2.2. Set pi as the degree of node i.
Step 3. Establishment of links Select node i (∈ {0, 1, 2, ..., n − 1}) randomly and check thenumber of nodes connected to i. If the number of nodes already connected to i is less thanpi , continue from Step 3.1. to Step 3.5. until the number of nodes connected to i is equal topi . Perform the above procedure for all nodes.

13

Step 3.1. Generate a random number q based on the probability distribution function Q(r)following a power distribution
Q(r) = crd−1 r−δ ,(3)where d = 2 since d is the dimension of Euclidean space that embeds the network∫L√into, c is a normalization factor to adjust to satisfy 1 Q(r)dr = 1 and L = nbecause L is the upper limit of the power distribution.
Step 3.2. Let q be the link length.
Step 3.3. Create the node group of the connection destination candidate of node i. Calculate
the node group excluding the node i itself from all the nodes and the node alreadyconnected to the node i as the node group of the connection destination candidate.
Step 3.4. Select the node closest to the link length q from the node i from the node group of
the connection destination candidate. If there are multiple nodes at the same distance,
select one at random. Let u be the selected node.
Step 3.5. Check the degree of u and the number of nodes already connected to u. If thenumber of nodes already connected to u is less than pu , build a link between node iand u. Otherwise, remove u from the connection destination candidate and return toStep 3.4.

3.3 Topological Properties of Fractal Virtual Networks
Degree Distribution Analysis
Since degrees of all nodes are referred to in Step 3 of the algorithm of Chapter 3.2, it is guaranteed that the degree distribution given to our model is the same as the degree distribution of thegenerated network.
Link Length Distribution Analysis
In the network construction algorithm of Chapter 3.2, the link length distribution (LD) of the network is strictly different from the LD given as an input to our model. The reason is why if it isrepeated multiple times that the node closest to the link length q from the node i is removed from14

the connection candidates in steps 3.4 to 3.5 in the algorithm of Chapter 3.2, a link having a link
length different from the original link length q is constructed. If the LD given to the generation
algorithm and the LD of the generated network are significantly different, it is impossible to obtain a network showing the fractal dimension to be expected by originally changing the scaling
exponent δ of the power distribution given as the LD. In addition, It is impossible to evaluate
the relationship between the fractal dimension and properties such as efficiency and robustness.
Therefore, the difference between the LD given to our model and the LD of the generated network
is evaluated and we verify that the difference is acceptable.
As the inputs of our model, we give the number of nodes n = 900 and the average degree
λ = 4, the exponent of the required LD δ = 1.0, 2.0, 3.0, 4.0, 5.0. The evaluation result is shownin Figure 2. The horizontal axis represents the distance r, and the vertical axis represents thecomplementary cumulative distribution function (CCDF) with the logarithmic scale of base 2.
The LD given as the input of our model is expressed by the blue line and the red line indicates the
LD of the generated network. Looking at Figure 2, there is no big difference in inclination of bothlines as a whole. Therefore, we believe that it is possible to control the fractal dimension by giving
various values of δ to our model. However, as the value of δ gets larger, there is a larger difference
between the values indicated by both lines. The reason for this is why if we give our model a large
value of δ, our model tries to construct more short-distance links, but there is a limit to the numberof short-distance links that can be constructed. Therefore, even if a value greater than δ = 5 isgiven to our model, it is considered that the LD of the generated network hardly changes.
The conclusion of this section is that although it is somewhat different depending on the valueof δ, it is verified that it is possible to change the slope of the generated network by changing δ.
Therefore, it is possible to control the fractal dimension using our model.
Fractal Dimension
We analyze whether the network using our model has fractal properties, and if so, how the fractal
dimension df correlates with the parameter δ. We prepare networks by giving the values of n =1024, λ = 4, δ = 1.1, 2.0, 2.5, 2.6, 3.0, 3.5, 4.5 to our model. For all the network we parepare, thefractal dimensions are calculated by the method of Chapter 3.1. By checking whether each fractal
dimension is different or not, we verify that a network showing arbitrary fractal dimension can beobtained by changing δ.

15The result of the analysis is shown in Figure 3. The horizontal axis of Figure 3 is the distancer, and the vertical axis is the number of reachable nodes M with r. By setting both axes to alogarithmic scale, the slope of the straight line composed of the obtained data points shows thefractal dimension. As a result, the fractal dimension of the network of δ = 1.1 is about 4.0,
the fractal dimension of the network of δ = 4.5 is about 2.0, and the fractal dimensions of theother networks increases as δ decreases. The relationship between δ and the slope is clear, whichshows that it is possible to evaluate the relationship between the fractal dimension and efficiency
or robustness in the next chapter.

16

212

212

Given LD
Generated Topology’s LD

10

2

2

28

CCDF

CCDF

28
26

26

24

24

22

22

20 0
2

Given LD
Generated Topology’s LD

10

21

22

23

24

25

20 0
2

26

21

22

23

r

2

212
2

CCDF

26

25

26

26

24

24

2

2

20 0
2

Given LD
Generated Topology’s LD

10

28

2

21

22

23

24

25

20 0
2

26

21

22

23

r

r

(c) δ = 3.0(d) δ = 2.0

212

Given LD
Generated Topology’s LD

10

2

28

CCDF

CCDF

28

2

26

(b) δ = 4.0

Given LD
Generated Topology’s LD

10

25

r

(a) δ = 5.0
212

24

26
24
22
0

2

20

21

22

23

24

25

r
(e) δ = 1.0

Figure 2: Link length distribution

17

26

24

104

3

M

10

102

101

100 0
10

101

δ = 1.1
δ = 2.0
δ = 2.5
δ = 2.6
δ = 3.0
δ = 3.5
δ = 4.5

102r
Figure 3: The fractal dimension of networks generated by giving each δ to the algorithm

18

4 Efficiency and Robustness of Fractal Virtual Networks
Through the evaluation in this chapter, we verify that our model is effective as a design guideline
for a large-scale network because the virtual network based on our model shows high efficiency(efficiency) and high robustness and shows high performance on various scales .

4.1 Metrics for Efficiency and Robustness
In the evaluation, the efficiency and robustness of each network is evaluated. To do this evaluation,
we refer to the information centrality CSI [19] expressed as
CSI =

∆E
E(G) − E(G0 )
=
,
E
E(G)

(4)

where C I is information centricity, S is a set of failure nodes, G is a pre-failure graph, G0 is apost-failure graph. E(G) is defined as
E(G) =∑ 1
1n(n − 1)dij

(5)

i6=j∈G

where n is the number of nodes in the graph G and dij is the shortest path length between i andj. The information centrality is an metric showing how much the node group included in a certain
range contributes to the entire network from a viewpoint of efficiency. If a network collapse due tonode failures, the shortest path length of two nodes between the divided subnetworks is assumed to
be ∞. In addition, since the deletion of a node leads to increasing the shortest path length between
multiple node pairs, E(G0 ) ≤ E(G) always holds.
However, the information centricity CSI is an metric indicating how much S contributes to theentire network from the viewpoint of efficiency by removing S from the network. That is, CSI
indicates the importance of the node group S, which is different from the meaning of robustness.
In this case, it is inappropriate to use CSI that focuses on the failed node group in order to evaluate
how much the remaining node group can maintain the communication function when the node∑group fails. Attention to the failed node group is expressed as i6=j∈G d1ij of Equation (5) and theefficiency before node failures contains the reciprocal of the shortest path length from/to the failed
node group. Therefore, the robustness metric RSr shown in Equation (6) and the partial Efficiency
ESr shown in Equation (7) are obtained by correcting the equations not to contain the reciprocal

19

of the shortest path length from/to the failed node group as following
RSr =

∆ESr
ESr (G) − ESr (G − Sr )=ESr
ESr (G)andESr (G) =1n(n − 1)∑i6=j∈G−Sr

1
dij (G)(6)(7)

where Sr is a node group included in the failure radius r. This makes it possible to calculate thechange of efficiency only in the nodes other than Sr .

4.2 Evaluations
In this chapter, we evaluate how efficient and robust the fractal virtual network is under node
failures.
4.2.1 Comparison with Random Network under Unified Cost Conditions
In this section, Efficiency and RSr are evaluated using a network that unifies link construction
costs. We verify that fractal networks is superior to non-fractal ones in terms of efficiency androbustness. Here, the cost means the sum of the physical link lengths and the number of links.
The network to compare and evaluate is a network of δ = 1.1 (hereinafter Fractalδ=1.1 ) and arandom network (hereinafter Random). The reason for using Random is to consider the advantagesof the link length distribution being a power distribution from the viewpoints of efficiency androbustness because the difference between Fractalδ=1.1 and Random is the power distribution or
the exponential distribution of the link length distribution.
Networks for Evaluation
The network to be evaluated is as follows.
• Fractalδ=1.1 : Fractalδ=1.1 is a network generated by giving n = 900, λ = 4, δ = 1.1 to thegeneration algorithm in Chapter 3.2.
• Random: Random is a random network based on ER model. As a method of constructing
Random, first, n nodes are set in a two-dimensional square lattice and then randomly selecttwo nodes in that network. Second, we calculate the Euclidean distance of the two nodes
and decide whether to construct the link using the probability density function according to20

the exponential distribution of the average µ. After that, we randomly select two nodes anddecide whether to build links until the number of links is equivalent to the number of links
in Fractalδ=1.1 . In order to unify the cost (the sum of the physical distances), µ is set to theaverage value of the physical distance of Fractalδ=1.1 , here µ is 8. Also, we construct links
avoiding self loops and overlapping links.

Failure Scenario
When a node is selected as a center of node failures, the nodes within the Euclidean radius r fromthe selected node and the associated links to the generation network are excluded (hereinafter
range failure). In this evaluation, all nodes are selected as the center of failed nodes O and range
failures occur for r = 0, 2, 4 from each node.
Result
The evaluation result of efficiency is shown in Figure 4. Labels of each network are appended tothe horizontal axis and the efficiency of Equation (5) is shown on the vertical axis. As a result, wefound that the network efficiency of Fractalδ=1.1 is about 0.05 higher than Random. Considering
this difference from the viewpoint of the hop length, in Fractalδ=1.1 , all node pairs can be reachedto each other with the efficiency of 0.22, that is, with an average hop length of about 5 hops, while
Random has the efficiency of 0.15, that is, an average of about 6.5 hops. The difference is about
1.5 hops.
Next, the evaluation result of RSr is shown in Figure 5. The horizontal axis shows the label ofeach network, and the vertical axis shows the distribution of RSr with a box-and-whisker. r is thefailure radius, and the box-whisker chart shows the distribution of RSr when range failures happen
in the network with the failure radius of each of (a), (b) and (c) for the center node of failure 900
nodes (all nodes). The points in each graph indicate average values. As a result, we find that
RSr of Fractalδ=1.1 is smaller when RSr is viewed as the maximum value or the average value,that is, Fractalδ=1.1 is more robust. The reason why the RSr of Fractalδ=1.1 becomes smaller isbecause the stable reachability of the shortest path between node pairs at short distance is greatly
different. Here, the stable reachability of the shortest path indicates such property that when nodes
fail, the shortest path of node pairs not including the failure nodes does not switch. The link length
distribution of Fractalδ=1.1 follows the power distribution of the scaling exponent −1.1 while the21link length distribution of Random follows the exponential distribution of the average 8. Thus,
there are many links around the link length 8 in Random, but in Fractalδ=1.1 the number of links
decreases as the link length becomes longer from 1. Therefore, in Fractalδ=1.1 , there are many
short-distance links physically and reachable to short-distance nodes with short-distance links, but
in Random, in order to reach short-distance nodes, medium distance is needed by passing throughmultiple nodes and links. As a result, the shortest path that physically arrives at a short distancenode when a failure occurs is almost unchanged at Fractalδ=1.1 , but it can be considered that the
shortest path varies greatly in Random.
4.2.2 Efficiency and Robustness of Networks with Different Fractal Dimensions
In this section, we evaluate the efficiency and robustness of networks with various fractal dimensions. This clarifies the relationship between cost, efficiency and robustness when the fractal
dimension is regarded as cost parameter for the network design.
Networks for Evaluation
We use networks generated by giving n = 1024, λ = 4, δ = 1.1, 2.0, 2.5, 2.6, 3.0, 3.5, 4.5 tothe generation algorithm of Chapter 3.2. Besides, we use a grid network Grid that accounts forδ = ∞.
Failure Scenario
We assume range failures for a center of all nodes as noted already. Also, range failures occur for
r = 0, 2, 4 from each node.
Result
The evaluation result of Efficiency is shown in Figure 6. The horizontal axis represents the exponent δ of the link length distribution to be given our model and the vertical axis represents theefficiency of Equation (5). Looking at figure 6, in the range of δ in [1, 3], there is a negative linear
relationship between δ and efficiency. However, in the range of δ in [3, 4.5], the slope becomesgentle. The reason is why as the value of δ increases, the network approaches the grid shape andthe sum of link lengths gradually approaches the minimum value at some δ value. In addition,compared with the fractal network of δ = 4.5 and Grid which is a two-dimensional lattice network, it is seen that the efficiency of the fractal network is more than twice as it can be achieved

22

0.25

Efficiency

0.2
0.15
0.1
0.05
0

FractalRandomFigure 4: Comparison of efficiency with both Fractal and Random networks

0.006

0.04
0.035

0.005

0.03
0.004
2

RS

0.003

0.02
0.015

0.002

0.01
0.001

Fractal0Random(a) r = 0.0

FractalRandom(b) r = 2.0

0.1
0.09
0.08
0.07
0.06
4

0

0.005

RS

RS

0

0.025

0.05
0.04
0.03
0.02
0.01
0

FractalRandom(c) r = 4.0

Figure 5: Comparison of RSr with both Fractal and Random networks
23

by only including a small number of long distance links. Since the shape of Grid’s network is
close to that when δ is increased, the results of Grid’s efficiency are displayed where the valueof δ is large. In conclusion, it turned out that the efficiency increases as δ decreases (the fractal
dimension increases).
The evaluation result of the relationship between δ and RSr in each r is shown in Figure 7. In
the evaluation, we calculate the robustness metric RSr when range failures occur for all nodes as
the center of failure O. Since RSr represents the change in efficiency other than the failure nodegroup Sr , it means that the smaller the value of RSr , the more robust it is. The horizontal axis
shows the distribution of the exponent δ of the required link length distribution of the generation
network and the vertical axis shows the distribution of RSr . The points in each δ mean the averagevalue. Looking at figure 7, the maximum value of RSr increases with the increase of δ. For thisreason, it can be seen that for networks close to the grid shape having a large value of δ, thenetwork is seriously damaged depending on the failure location compared with the failure scale.
The reason for this is that in a network where δ is large, there are few long-distance links inthe entire network, and if the node holding the long-distance link fails, the efficiency is greatly
reduced. Also, the result of Grid supports this idea. In other words, Grid without long distancelinks has low efficiency and there is no room for large change in RSr . Next, when looking at
Figure 7, RSr is not changed at all at any failure scale in (a), (b) and (c). We consider that thisstability against δ is brought by the fractal property that the fractal structure originally have. Thatis, since the fractal structure has the same structure anywhere at any scale, the same robustness isseen even if any nodes fail.
As a consideration, we evaluate hierarchical module property of what connection structure thehigh efficiency and high robustness of the network generated by our method (hereinafter generated
network) are brought about . As an evaluation means, the evaluation is performed referring to [13]and expressing a matrix relating to link density in a network by a temperature graph. We make aconcrete explanation using Figure 8 and Figure 9. Figure 9 is the adjacency matrix corresponding
to the network in Figure 8 and each element ρi (i = 1, 2, 3) is the link density, which is the value
obtained by normalizing the number of links in and between the modules with the number of all
the node pairs in and between the modules. For example, when looking at the hierarchy of l = 0,each module ID corresponds to row and column, and the link density in all modules is ρ1 . Next,
in the hierarchy of l = 1, the number of links of each module pair is 2, and the link density is
24

0.25

Efficiency

0.2
0.15
0.1
0.05
0

1.1

2.0 2.5
2.6 3.0 3.5

4.5

Grid

δ

0.07

0.012

0.06

0.01

0.05

0.008

0.04

RS

2

0.014

0.006

0.03

0.004

0.02

0.002

0.01
1.1

2.0 2.5
2.6 3.0 3.5

4.5

0

Grid

1.1

2.0 2.5
2.6 3.0 3.5δδ(a) r = 0.0(b) r = 2.0

0.12
0.1
0.08
4

0

RS

RS

0

Figure 6: Efficiency of a generated network with each δ

0.06
0.04
0.02
0

1.1

2.0 2.5
2.6 3.0 3.5

4.5

Grid

δ
(c) r = 4.0

Figure 7: Relationship between δ and RSr
25

4.5

Grid

݈ൌʹ

݈ൌͳ

݈ൌͲ

Figure 8: Evaluation method for hierarchical modularity: An example of hierarchical module
structure

Table 1: Procedure to determine module ID
0

1

2

3

ρ2 . The condition for being a hierarchical module structure is to satisfy ρ1 ≥ ρ2 ≥ ρ3 ≥ .... In
this evaluation, it is evaluated whether or not the generated network satisfies the above condition,compared with other networks.
As a method of determining the Module ID corresponding to the row and column of the adjacency matrix, the entire network is divided into four such as Table 1, and Module ID are determined in order from the upper left. In addition, the Module ID at the hierarchical level below isdivided into 4 sections of Table 1, which are 0, 1, 2 and 3 in the same way. Further, we divide one
section into four, and make it 4, 5, 6, and 7. In this way, Module IDs are allocated while repeating
recursively division, thereby the Module IDs are determined at each hierarchical level.
For hierarchical modularity evaluation, the following four networks are prepared.
• Fractalδ=1.1 : Fractalδ=1.1 is a network generated by giving n = 1024, λ = 4, δ = 1.1 tothe generation algorithm in Chapter 3.2.
26

࣋૚

࣋૛
࣋૜

࣋૚
࣋૛

࣋૚
࣋૚

࣋૛
࣋૚

࣋૜
࣋૛

࣋૚

Figure 9: Evaluation method for hierarchical modularity: An example of the adjacency matrix
corresponding to the hierarchical module structure in Figure 8• Fractalδ=4.5 : Fractalδ=4.5 is a network generated by giving n = 1024, λ = 4, δ = 4.5 tothe generation algorithm in Chapter 3.2.
• Random: Random is a random network based on ER model. As a method of constructing
Random, first, n nodes are set in a two-dimensional square lattice and then randomly selecttwo nodes in that network. Second, we calculate the Euclidean distance of the two nodes
and decide whether to construct the link using the probability density function according to
the exponential distribution of the average µ. After that, we randomly select two nodes anddecide whether to build links until the number of links is equivalent to the number of links
in Fractalδ=1.1 . In order to unify the cost (the sum of the physical distances), µ is set to theaverage value of the physical distance of Fractalδ=1.1 , here µ is 8. Also, we construct links
avoiding self loops and overlapping links.
• Pure: Pure is a network that has both scale-free and hierarchical properties [20]. By using
the network construction model of [20], it is possible to generate a network with a beautiful
hierarchical structure. By comparing with Pure, we know the upper limit of hierarchy that27

Figure 10: Procedure to construct hierarchical modular structure

Fractal can take. we explain the generation procedure of the hierarchical modular structurewith a refinement so that it can be applied to a network in which nodes are arranged in a
two-dimensional lattice using the Figure 10 . In Figure 10, n is the number of steps andN is the number of nodes. At the 0th step of (a), we connect four nodes so that the linkdensity becomes 1. Next, in the first step of (b), three new networks of the previous step(a) are duplicated and arranged in a two-dimensional square lattice. Besides, we construct
links from the other nodes to the node located at the top left so that they do not overlap.
Thereafter, the network of the previous step is newly duplicated and arranged in a twodimensional square lattice and the procedure of constructing a link from all the nodes to thenode located at the top left position is repeated until the number of nodes in the network
reached the number of given nodes.
The results of the evaluation are shown in Figure 11, 12, 13 and 14. First, comparing (a),(b), (c) and (d) of Figure 11 and 12, the proportion of yellow and black is more in Figure 11,
ant the difference in value clearly appears. This is because Fractalδ=4.5 is composed of shorterlink lengths and nodes at short distance are more densely connected while nodes at long distanceare more sparsely connected. In particular, paying attention to (c), it turns out that Fractalδ=4.5
is more modular than Fractalδ=1.1 , which indicates that the module structure can be seen at thelower hierarchical level. Next, looking at Figure 13, the value of link density between modules
at long distance frequently exceeds the link density between modules at short distance, so it does
not show hierarchical module property. In particular, as is clear from (d), no modular structure28

is taken at the low hierarchical level. In Random, a large number of links with an average link
length of 8 are constructed, but on the other hand, the number of links with a link length of 1 isvery small, and at a hierarchical level with a small module size such as (d), there frequently are
no links. Finally, looking at Figure 14, Module 0 and all the other modules are always connectedwith a constant link density, such a structure is seen locally, and we can see that the modularity
is high from the clear difference of colors. In other words, it turns out that the network takes thehierarchical module structure as expected. However, the hierarchical module structure regularly
constructed in this manner has scale-free property, and although it is robust against random node
failures, it is considered that it is weak against selective failures to hub nodes, which have a large
number of degrees. That is, in the worst case of failures, it is possible that the network is seriously
damaged. In conclusion, the fractal network takes the hierarchical modular structure and has
different modular size per fractal dimension.
4.2.3 Efficiency and Robustness on Different Scale of Networks
It is considered that the scale of the virtual network under the IoT environment is not only large,
but the scale differs for each IoT service. In the previous evaluations, we showed that the virtual
network with the fractal property has high efficiency and high robustness, but the network scaleat that time was always constant. Therefore, under the IoT network environment where various
scales are expected, the fractal network using our model is not always effective. Therefore, by
evaluating efficiency and robustness of the fractal networks which give various parameters of thenumber of nodes to our model, we show the fractal network is effective at any scale in terms ofefficiency and robustness.
Networks for Evaluation
We prepare the following networks for evaluation.
• Fractalδ=1.1 : Fractalδ=1.1 is generated by giving n = 256, 1024, 2304, 4096, 6400, 9216,
12544, 16384, λ = 4 and δ = 1.1 to the generation algorithm of Chapter 3.2.
• Random: Random is a random network based on ER model. As a method of constructing
Random, first, n nodes are set in a two-dimensional square lattice and then randomly selecttwo nodes in that network. Second, we calculate the Euclidean distance of the two nodes

29

0

0.012

0.5

0

0.01

4
0.008

1.5
2

0.006

2.5

0.004

Module ID

1Module ID

0.045
0.04
0.035
0.03
0.025
0.02
0.015
0.01
0.005
0

2

3

6
8
10
12

0.002

3.5
4

14

0
0

0.5

1

1.5

2

2.5

3

3.5

16

4

0

2

4

6

8

10

12

14

Module ID

Module ID(a) The number of modules = 4(b) The number of modules = 16

0

0.16

10

0.14

16

0

0.5

50

0.4

100

0.3

150

0.2

200

0.1

0.1
30

0.08

40

0.06

50

0.04

Module ID

Module ID

0.12
20

0.02
60

250

0
0

10

20

30

40

50

60

0
0

50

100

150

200

Module ID

Module ID(c) The number of modules = 64(d) The number of modules = 256

Figure 11: Hierarchical modularity of the fractal network with δ = 1.1

30

250

0

0.07

0.014

2

0.06

1

0.012

4

0.05

1.5

0.01

2

0.008

2.5

0.006

3

0.004

12

0.02

3.5

0.002

14

0.01

0

16

4
0

0.5

1

1.5

2

2.5

3

3.5

6

0.03

10

0
0

2

4

6

8

10

12

14

Module ID

Module ID(a) The number of modules = 4(b) The number of modules = 16

0

0

1

0.2

50

0.8

100

0.6

150

0.4
0.2

0.15
30
40

0.1

50

0.05

200

0

250

60
10

20

30

40

50

16

0.25

20

0

0.04

8

4

10

Module ID

Module ID

0.016

Module ID

Module ID

0
0.5

60

0
0

50

100

150

200

Module ID

Module ID(c) The number of modules = 64(d) The number of modules = 256

Figure 12: Hierarchical modularity of the fractal network with δ = 4.5

31

250

2

0.006

4

0.005
2

0.004
0.003

3

4
0

Module ID

0

0.007

1

2

3

0.018
0.016
0.014
0.012
0.01
0.008
0.006
0.004
0.002
0

6
8
10

0.002

12

0.001

14

0

16

4

0

2

4

6

8

10

12

14

Module ID

Module ID(a) The number of modules = 4(b) The number of modules = 16

0

0.07

10

0.06

20

0.05
0.04

30

0.03

40

0.02

16

0

0.35
0.3

50

Module ID

Module ID

1

0.008

Module ID

0

50

0.25
100

0.2

150

0.15
0.1

200
0.01

0.05

60

250

0
0

10

20

30

40

50

60

0
0

50

100

150

200

Module ID

Module ID(c) The number of modules = 64(d) The number of modules = 256

Figure 13: Hierarchical modularity of a random network

32

250

0

0.03

0

0.025

4
0.02

2

0.015
0.01

Module ID

Module ID

1

3

6
8
10
12

0.005
4

14

0
0

1

2

3

16

4

0

2

4

6

8

10

12

14

Module ID

Module ID(a) The number of modules = 4(b) The number of modules = 16

16

0

0.3

0

1

10

0.25

50

0.8

20

0.2

100

0.6

30

0.15

150

0.4

200

0.2

40

0.1

50

Module ID

Module ID

0.1
0.09
0.08
0.07
0.06
0.05
0.04
0.03
0.02
0.01
0

2

0.05

60

250

0
0

10

20

30

40

50

60

0
0

50

100

150

200

Module ID

Module ID(c) The number of modules = 64(d) The number of modules = 256

Figure 14: Hierarchical modularity of a hierarchical modular network

33

250

and decide whether to construct the link using the probability density function according to
the exponential distribution of the average µ. After that, we randomly select two nodes anddecide whether to build links until the number of links is equivalent to the number of links
in Fractalδ=1.1 . In order to unify the cost (the sum of the physical distances), µ is set to theaverage value of the physical distance of Fractalδ=1.1 . Also, we construct links avoiding selfloops and overlapping links.

Failure Scenario
The larger the scale of networks is, the larger range failures occur. In this evaluation, the scale of
networks is different. That is why when we assume range failures of the same scale, influencesof the failures decreases as the network scale is larger. Then, inevitably the larger network will
be robust, but it is a mistaken interpretation. Therefore, by making the scale of the network
proportional to the size of the range failures, robustness is evaluated so that the effects of range
failures are equal among networks of different scales. The failure radius r(n) of range failures is√assumed to be r(n) = n/c, using the number of nodes n and the constant c. In this evaluation,c = 8 is set. Also, the value of RSr(n) is calculated by selecting 100 failure centers O randomly
and we obtain RSr(n) .
Result
The evaluation result is shown in Figure 15. The horizontal axis of figure 15 represents the numberof nodes and the vertical axis represents efficiency. Compared with Random, Fractalδ=1.1 has highefficiency at any number of nodes. Fractalδ=1.1 holds more short-distance links while increasing
the maximum physical link length in proportion to the square root of the number of nodes when
the number of nodes increases according to the generation algorithm. On the other hand, Randomholds only medium-range links with an average of µ, so even if it is between short-distance nodes,
it needs many hops until the nodes reach from/to each other. For this reason, we believe that thedifference in hop length for reaching nodes at short distance appears as a difference in efficiency,
and the difference is larger as the number of nodes increases.
The result of Figure 15 is calculated using Equation (5) and the reciprocal of the shortest path
length of each node pair is averaged. That is, the efficiency indicated as the value of the y axis
represents efficiency per node pair. However, when constructing a large-scale virtual network,34

it is more important to see how much the performance of the entire network improves than tosee each node pair. Thus, we consider the sum of the reciprocal of the shortest path length byremoving the average part of Equation (5). The result is shown in Figure 16. The horizontal
axis of Figure 16 represents the number of nodes and the vertical axis represents the sum ofreciprocals of the shortest path length. Looking at Figure 16, as the number of nodes increases,
the difference between the sum of reciprocals of hop length expands between Fractalδ=1.1 andRandom, In 16384, Fractalδ=1.1 shows a larger value by about 5 million. When there is a differenceof 1 in the sum of reciprocals of hop lengths, there is at least a difference of 1 when converted into
the sum of hop lengths. Therefore, in the number of nodes 16384, it can be said that Fractalδ=1.1
succeeded in reducing extra communication equivalent to at least 5 million hops in the entire
network compared with Random.
The evaluation result on robustness is shown in Figure 17. The horizontal axis of Figure 17
is the number of nodes and the vertical axis is the robustness metric RSr(n) . From Figure 17,
Fractalδ=1.1 is always lower in value of RSr(n) than Random. In other words, Fractalδ=1.1 is morerobust than Random. In addition, the value of Fractalδ=1.1 is more stable. The reason for thisresult is that Fractalδ=1.1 may be less biased in the structure of the network. Even if you change
the scale, Fractalδ=1.1 has the same structure regardless of where you look in the network, so we
believe that robustness will be kept constant.

35

0.3

Fractalδ=1.1
RandomEfficiency

0.25
0.2
0.15
0.1
0.05
0

0

2500 5000 7500 10000 12500 15000 17500

Number of Nodes
Figure 15: Efficiency of the networks on each scale

4.0×1077

3.5×10Fractalδ=1.1
Random7

Sum of 1/H

3.0×10

2.5×1072.0×107
1.5×107
1.0×107
5.0×106
0.0×100 0

2500 5000 7500 10000 12500 15000 17500

Number of Nodes
Figure 16: Relationship between the network size and the sum of reciprocals of shortest path
length36

0.08

Fractalδ=1.1
Random

0.07
0.06

RS

0

0.05
0.04
0.03
0.02
0.01
0

0

2500 5000 7500 10000 12500 15000 17500

Number of Nodes
Figure 17: Robustness of the networks on each scale37

5 Conclusion
In this thesis, we showed the configuration method for large-scale virtual networks such as IoT
networks by focusing on the fractal property and improved the efficiency of the network by controlling the fractal dimension, maintaining high robustness that the fractal structures originally have.
Our method generates a fractal virtual network with arbitrary fractal dimension by controlling the
exponent of the link length distribution following the power distribution. We evaluated efficiency
and robustness of the fractal network in various conditions. First, we revealed that fractal networks
are more efficient and more robust than random networks, that is, non-fractal networks because
fractal networks have stable reachability between neighbor nodes. Second, as the fractal dimension is higher, long links appear in the network and the efficiency is improved more. Third, even if
the scale of the network is changed, the fractal network always shows higher efficiency and higher
robustness than the non-fractal network. In conclusion, we showed the guideline for designing alarge-scale virtual network with high efficiency and high robustness.
We just show the design method for large-scale virtual networks before services using the networks start to work but the method does not consider constant changes of the network environment
such as traffic changes or changes of scale. Therefore, we assume such changes and according to
the changes, control and manage the virtual network keeping the fractal property.

38

Acknowledgements
This thesis would not be accomplished without the supports of a great number of people. First ofall, I would like to express the deepest appreciation to my supervisor, Professor Masayuki Murata
of Osaka University, for his innumerable helps, valuable comments and giving me this worthwhile
research theme. I would like to express my gratitude to Associate Professor Shin’ichi Arakawa
of Osaka University, for his personal guidance and valuable discussion. Without his insightful
support, I could not finish writing this thesis. Moreover, he saw through the skills I should acquire
and instructed me those skills such as the way of thinking logically, writing papers and the importance of planning the direction of research. I have had greatly benefited from Assistant Professor
Yuichi Ohsita and Daichi Kominami of Osaka University, for their suggestions and discussions. I
received generous support from Dr. Suyong Eum of Osaka University, for encouraging me when
I was upset. I would like to offer my special thanks to Mr. Toshihiko Ohba, Mr. Koki Inoue,
Mr. Kodai Kanda and Mr. Yuki Tsukui. They supported me by discussion of my research theme.
Especially, I would like to express the deepest appreciation to Mr. Toshihiko Ohba for correcting
this thesis and for advising me from various viewpoints. My deepest appreciation also goes to Mr.
Yoshinobu Shijo not only for his helps to my research but for his mental supports. I could notfinish writing this thesis without him. I owe a very important debt to my friends, colleagues andsecretaries of the Advanced Network Architecture Research Laboratory of Osaka University, forgiving me the enjoyable time. Finally, I finish this acknowledgement after sincerely expressing mydeepest gratitude to my parents for letting me study in Graduate School of Information Scienceand Technology of Osaka University.

39References[1] N. M. K. Chowdhury and R. Boutaba, “A survey of network virtualization,” Computer Networks, vol. 54, pp. 862–876, Apr. 2010.
[2] Y. Shijo, S. Arakawa, and M. Murata, “Topological analysis of the brain functional networks,” in Proceedings of the 8th International Conference on Bioinspired Information andCommunications Technologies, pp. 352–358, ICST (Institute for Computer Sciences, SocialInformatics and Telecommunications Engineering), Dec. 2014.
[3] Y. Shijo, “A configuration method of virtual networks with hierarchical robustness inspiredby the fractality of brain functional networks,” Master’s thesis, Graduate School of Information Science and Technology, Osaka University, Feb. 2016.
[4] L. Daqing, K. Kosmidis, A. Bunde, and S. Havlin, “Dimension of spatially embedded networks,” Nature Physics, vol. 7, pp. 481–484, Feb. 2011.
[5] L. Atzori, A. Iera, and G. Morabito, “The Internet of Things: A survey,” Computer networks,
vol. 54, pp. 2787–2805, Oct. 2010.
[6] D. Miorandi, S. Sicari, F. De Pellegrini, and I. Chlamtac, “Internet of Things: Vision, applications and research challenges,” Ad hoc networks, vol. 10, pp. 1497–1516, Sept. 2012.
[7] R. Piyare and S. R. Lee, “Towards Internet of Things (IoTs): Integration of wireless sensor
network to cloud services for data collection and sharing,” arXiv preprint:1310.2095, Oct.
2013.
[8] D. Gachet, M. de Buenaga, F. Aparicio, and V. Padrón, “Integrating Internet of Thingsand cloud computing for health services provisioning: The virtual cloud carer project,” inProceedings of Innovative Mobile and Internet Services in Ubiquitous Computing (IMIS),
pp. 918–921, Sept. 2012.
[9] N. M. K. Chowdhury and R. Boutaba, “Network virtualization: state of the art and researchchallenges,” IEEE Communications magazine, vol. 47, July 2009.

40

[10] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford,
S. Shenker, and J. Turner, “OpenFlow: Enabling innovation in campus networks,” ACM
SIGCOMM Computer Communication Review, vol. 38, pp. 69–74, Apr. 2008.
[11] A.-L. Barabási and E. Bonabeau, “Scale-free networks,” Scientific american, vol. 288,
pp. 60–69, May 2003.
[12] D. J. Watts and S. H. Strogatz, “Collective dynamics of ’small-world’ networks,” Nature,
vol. 393, p. 440, June 1998.
[13] R. K. Pan and S. Sinha, “Modular networks with hierarchical organization: The dynamical
implications of complex structure,” Pramana, vol. 71, pp. 331–340, Aug. 2008.
[14] P. Erdős and A. Rényi, “On the evolution of random graphs,” Publ. Math. Inst. Hung. Acad.
Sci, vol. 5, pp. 17–61, 1960.
[15] H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger, “Network topology generators: Degree-based vs. structural,” in Proceedings of ACM SIGCOMM Computer
Communication Review, vol. 32, pp. 147–159, Aug. 2002.
[16] T. W. Valente, Network models of the diffusion of innovations. Cresskill New Jersey Hampton
Press 1995., 1995.
[17] E. Bullmore and O. Sporns, “The economy of brain network organization,” Nature Reviews
Neuroscience, vol. 13, p. 336, Apr. 2012.
[18] C. Song, L. K. Gallos, S. Havlin, and H. A. Makse, “How to calculate the fractal dimension of
a complex network: The box covering algorithm,” Journal of Statistical Mechanics: Theory
and Experiment, vol. 2007, p. P03006, Mar. 2007.
[19] V. Latora and M. Marchiori, “A measure of centrality based on network efficiency,” New
Journal of Physics, vol. 9, p. 188, June 2007.
[20] A. L. Barabási, Z. Dezső, E. Ravasz, S. H. Yook, and Z. Oltvai, “Scale-free and hierarchicalstructures in complex networks,” in Proceedings of AIP Conference, vol. 661, pp. 1–16, May
2003.

41