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

Title

Adaptive Fractal‑like Network Structure for
Efficient Search of Targets at Unknown Positions

Author(s)Hayashi, Yukio

Citation

ADAPTIVE 2012 : The Fourth International
Conference on Adaptive and Self‑Adaptive Systems
and Applications: 63‑68

Issue Date

2012‑07‑22

Type

Conference Paper

Text version

publisher

URL

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

RightsCopyright (C) 2012 IARIA. Yukio Hayashi, ADAPTIVE
2012 : The Fourth International Conference on
Adaptive and Self‑Adaptive Systems andApplications, 2012, 63‑68.

Description

Japan Advanced Institute of Science and Technology

ADAPTIVE 2012 : The Fourth International Conference on Adaptive and Self-Adaptive Systems and Applications

Adaptive Fractal-like Network Structure for
Efficient Search of Targets at Unknown Positions
Yukio Hayashi
Graduate School of Knowledge Science
Japan Advanced Institute of Science and Technology
Nomi-city, Ishikawa-pref., Japan
Email: yhayashi@jaist.ac.jp

Abstract—Since a spatial distribution of communication
requests is inhomogeneous and related to a population, inconstructing a network, it is crucial for delivering packets on
short paths through the links between proximity nodes andfor distributing the load of nodes how to locate the nodes asbase-stations on a realistic wireless environment. In this paper,from viewpoints of complex network science and biologicalforaging, we propose a scalably self-organized geographicalnetwork, in which the proper positions of nodes and the
network topology are simultaneously determined according to
the population, by iterative divisions of rectangles for loadbalancing of nodes in the adaptive change of their territories.
In particular, we consider a decentralized routing by using only
local information, and show that, for searching targets aroundhigh population areas, the routing on the naturally embedded
fractal-like structure by population has higher efficiency thanthe conventionally optimal strategy on a square lattice.
Keywords-self-organised design; wide-area wireless communication; routing in ad hoc networks; random walk; Levy flight.

I. I NTRODUCTION
Many network infrastructures: power grids, airline networks, and the Internet, are embedded in a metric space,and long-range links are relatively restricted [1], [2] foreconomical reasons. The spatial distribution of nodes isneither uniformly at random nor on a regular lattice, which
is often assumed in the conventional network models. In
real data, a population density is mapped to the numberof router nodes on Earth [1]. Similar spatially inhomogeneous distributions of nodes are found in air transportation
networks [3] and in mobile communication networks [4].
Thus, it is not trivial how to locate nodes on a space ina pattern formation of points. Point processes in spatial
statistics [5] provide models for irregular patterns of points
in urban planing, astronomy, forestry, or ecology, such as
spatial distributions of rainfall, germinations, plants, andanimals. The processes assume homogeneous Poisson andGibbs distributions to generate a pattern of random packing
or independent clustering, and to estimate parameters ofcompetitive potential functions in a territory model for agiven statistical data, respectively. However, rather thanrandom pattern and statistical estimation, we focus on a

Copyright (c) IARIA, 2012.

ISBN: 978-1-61208-219-6

self-organized network infrastructure by taking into accountrealistic spatial distributions of nodes and communication
requests. In particular, we aim to develop adaptive andscalable ad hoc networks by adding the links between proximity nodes according to the increasing of communication
requests. Because a spatial distribution of communication
requests affect the proper positions of nodes, which control
both the load of requests assigned to each node (e.g.,assigned at the nearest access point of node as a base-stationfrom a user) and the communication efficiency depending on
the selection of routing paths.
For a routing in ad hoc networks, global information, e.g.,a routing table in the Internet, cannot be applied, because
many nodes and connections between them are likely tochange over time. In early works on computer science, somedecentralized routing methods were developed to reduceenergy consumption in sensor or mobile networks. However
they lead to the failure of guaranteed delivery [6]; in theflooding algorithm, multiple redundant copies of a message
are sent and cause congestion, while greedy and compass
routings may occasionally fall into infinite loops or intoa dead end. In complex network science, other efficient
decentralized routing methods have been also proposed.
The stochastic methods by using local information of thenode degrees and other measures are called preferential [7]and congestion-aware [8], [9] routings as extensions of a
uniformly random walk.
Decentralized routing has a potential performance tosearch a target whose position is unknown in advance. Since
this situation looks like foraging, the biological strategy may
be useful for the efficient search. We are interested in a
relation of the search and the routing on a spatially inhomogeneous network structure according to a population. Manyexperimental observations for biological foraging found theevidence in favor of anomalous diffusion in the movementof insects, fishes, birds, mammals and human being [10].
As the consistent result, it has been theoretically analyzed
for a continuous space model that an inverse square root
distribution of flight lengths is an optimal strategy to search
sparsely and randomly located targets on a homegeneous
space [11]. The discrete space models on a regular lattice63

ADAPTIVE 2012 : The Fourth International Conference on Adaptive and Self-Adaptive Systems and Applications[12] and the defective one [13] are also discussed. Suchbehavior is called Levy flight characterized by a distribution−µfunction P (lij ) ∼ lijwith 1 < µ ≤ 3, where lij isa flight length between nodes i and j in the stochastic
movement for any direction. The values of µ ≥ 3 leadto Brownian motions, while µ → 1 to ballistic motions.
The optimal case is µ ≈ 2 for maximizing the efficiencyof search. Here, we assume that the mobility of a nodeis ignored due to a sufficiently slow speed in comparison
with the communication process. In the current or futuretechnologies, wide-area wireless connections by directional
beams will be possible, the modeling of unit disk graphwith a constant transmission range is not necessary. Thus,
we propose a scalably self-organized geographical networkand show that the naturally embedded fractal-like structure
is suitable for searching inhomogeneously distributed targets
more efficiently than the square lattice tracked by the Levy
flights.
II. G EOGRAPHICAL N ETWORKS
We introduce geographical network models proposed incomplex network science.
A. Conventional Models
Geographical constructions of complex networks havebeen proposed so far. As a typical generation mechanismof scale-free (SF) networks that follow a power law degree
distribution found in many real systems [14], [15], a spatially
preferential attachment is applied in some extensions [16],[17], [18], [19], [20] from the topological degree basedmodel [21] to a combination of degree and distance basedmodel. On the other hand, geometric construction methods
have also been proposed. They have both small-world [22]and SF structures generated by a recursive growing rule
for the division of a chosen triangle [23], [24], [25], [26]or for the attachment aiming at a chosen edge [27], [28],[29] in random or hierarchical selections. These models
are proper for the analysis of degree distribution due tothe regularly recursive generation process. Although theposition of a newly added node is basically free as far
as the geometric operations are possible, it has no relation
to population. Considering the effects of population on ageographical network is necessary to self-organize a spatial
distribution of nodes that is suitable for socioeconomic
communication and transportation requests. Moreover, inthese geometric methods, narrow triangles with long links
tend to be constructed, and adding only one node per step
may lead to exclude other topologies from the SF structure.
Unfortunately, SF networks are extremely vulnerable against
the intentional hub attacks [30]. We should develop otherself-organizations of network apart from the conventionalmodels; e.g., a better network without long links can beconstructed by subdivisions of equilateral triangle, which is awell balanced (neither fat nor thin) shape for any directions.

Copyright (c) IARIA, 2012.

ISBN: 978-1-61208-219-6

B. Generalized Multi-Scale Quartered Network
Thus, we have considered the multi-scale quartered(MSQ) network model [31], [32]. It is based on a stochastic
construction by a self-similar tiling of primitive shape, suchas an equilateral triangle or square. The MSQ networks haveseveral advantages of the strong robustness of connectivity
against node removals by random failures and intentional
attacks, the bounded short path as t = 2-spanner [33], andthe efficient face routing by using only local information.
Furthermore, the MSQ networks are more efficient (economic) with shorter link lengths and more suitable (tolerant)with lower load for avoiding traffic congestion [32] than thestate-of-the-art geometric growing networks [23], [24], [25],[26], [27], [28], [29] and the spatially preferential attachment
models [16], [17], [18], [19], [20] with various topologies
ranging from river to SF geographical networks. However, in
the MSQ networks, the position of a new node is restrictedon the half-point of an edge of the chosen face, and the link
length is proportional to ( 12 )H where H is the depth numberof iterative divisions. Thus, from square to rectangle, we
generalize the division procedures as follows.
Step0: Set an initial square whose inside are the candidates of division axes as the segments of a L × L
lattice.
Step1: At each time step, a face is chosen with a probability proportional to the population counted in theface covered by mesh blocks of a census data.
Step2: Four smaller rectangles are created from the division of the chosen rectangle face by horizontal
and vertical axes. For the division, two axes arechosen by that their cross point is the nearest to
the population barycenter of the face.
Step3: Return to Step 1, while the network size (the total
number of nodes) N does not exceed a given size.
Note that the maximum size Nmax depends on the valueof L; the iteration of division is finitely stopped, since theextreme rectangle can not be divided any longer when oneof the edge lengths of rectangle is the initial lattice’s unit
length. We use the population data on a map in 80km2 of
160 × 160 mesh blocks (L = 160) provided by the Japan
Statistical Association. Of course, other data is possible.
It is worth noting that the positions of nodes and the
network topology are simultaneously determined by thedivisions of faces within the fractal-like structure. Thereexists a mixture of sparse and dense parts of nodes withsmall and large faces. Moreover, with the growing network,
the divisions of faces perform a load balancing of nodes intheir adaptively changed territories for the population. Weemphasize that such a network is constructed according to a
spatially inhomogeneous distribution of population, which is
proportional to communication requests in a realistic environment. In the following, we show the naturally embedded
fractal-like structure are suitable for searching targets.

64

ADAPTIVE 2012 : The Fourth International Conference on Adaptive and Self-Adaptive Systems and Applications

III. S EARCH P ERFORMANCE

Copyright (c) IARIA, 2012.

ISBN: 978-1-61208-219-6

Frequency P(lij)As a preliminary, we consider the preferential routing [7]which is also called α-random walk [34]; The forwarding
node j is chosen proportionally to Kjα by a walker in theconnected one hop neighbors Ni of its resident node i of awalker (packet), where Kj denotes the degree of node j andα is a real parameter. We assume that the start position ofwalker is set to the nearest node to the population barycenterof the initial square. Figure 1 shows the length distributionof visited links. The dashed lines in log-log plot suggest a
power law, for which the exponents estimated as the slopesby a mean-square-error method are 2.336, 2.315, and 2.296
for α = 1, 0, −1, respectively. These values are close to
the optimal exponent µ ≈ 2 [11], [12] in the Levy flighton a square lattice. The exponents for the α-random walks
slightly increase as the network size N becomes larger.
Here, the case of α = 0 shows the length distribution ofexisting links on a network. Since the stationary probabilityof incoming at node j is Pj∞ ∝ Kj1+α [35], especially at
α = 0, each of the connected links to j is chosen at random
by the probability 1/Kj for the leaving from j, therefore awalker visit each link at the same number. Figure 2 showsthat the frequency of visited links by the α-random walks
at α = ±1 is different even for the degrees 3 and 4 in a
generalized MSQ network. On the thick lines, a walker tends
to visit high population (diagonal) areas colored by orange
and red in the case of α = 1, while it tends to visit low
population peripheral (corner) areas in the case of α = −1.
Thus, the case of α = 1 is expected to selectively coverhigh population areas, which has a lot of communication
requests in cities. Note that the absolute value of α should
be not too large, since a walker is trapped between high/low
degree nodes in a long time as the ping-pong phenomenathat does not contribute to the search of targets.
We investigate the search efficiency for the α-random
walk on a generalized MSQ network, and compare theefficiency with that for Levy flights on a L × L squarelattice with periodic boundary conditions [12]. As shownin Fig. 3, a walker constantly looks for targets (destination
nodes of packets) scanning on a link between two nodes
in the generalized MSQ network. If a target exists in thevision area of rv hops for the up/down/left/right directions
from the center position, a walker gets it and return to theposition on the link for continuing the search on the same
direction. When more than one targets exit in the area, awalker gets all of them successively in each direction, andreturn to the position. Only at a node of rectangle, the search
direction is changeable along one of the connected links.
Thus, the search is restricted on the edges of rectangle in
the generalized MSQ network. While the search directionof a Levy flight on the square lattice [12] is selectable fromfour directions of horizontal and vertical at all times aftergetting a target in the scanning with the vision area of rv

10

0

10

-1

10

-2

10

-3

10

-4

α= 1
α= 0
α=-1

10-5
10

-6

10

0

1

10
Length lij

102

Figure 1. Length distribution of visited links on generalized MSQ networks
by an α-random walker in 106 time steps. The marks of blue diamond,black circle, and red triangle correspond to the cases of α = 1, 0, −1,
respectively. These results are obtained by the average of 100 networks for
N = 2000.

−µ
hops, moreover, the length of scan follows P (lij ) ∼ lij,
lij > rv . We set a target at the position chosen proportionallyto the population around a cross point in (L + 1)2 , forwhich the population is defined by the average of four values
in its contact mesh regions. In particular, we discuss thedestructive case [12]: once a target is detected by a walker,
then it is removed and a new target is created at a different
position chosen with the above probability.
The search efficiency [11], [12], [13] is defined by

1 X Nsη =,M m=1 LmM

defdef (L + 1)

λ =Nt 2rv

(1)

2

,

(2)

where Lm denotes the traversed distance counted by thelattice’s unit length until detecting Ns = 50 targets from thetotal Nt targets in the mth run. We consider a variety of
Nt = 60, 100, 200, 300, 400, and 500 for investigating thedependency of the search efficiency on the number Nt oftargets. The quantity λ represents the mean interval between
two targets for the scaling of efficiency by target density. We
set M = 103 and rv = 1 for the convenience of simulation.
Intuitively, the sparse and dense structures according to the
network size N have the advantage and disadvantage inorder to raise the search efficiency in the generalized MSQ
network. Although the scanned areas are limited by somelarge rectangle holes as N is small, a walker preferably visits
the high population areas that include many targets. While
the scanned areas are densely covered as N is large, the65ADAPTIVE 2012 : The Fourth International Conference on Adaptive and Self-Adaptive Systems and Applications

Figure 2. Visualization examples of the visited links by α-random walks
at α = 1 (Top) and α = −1 (Bottom) on a generalized MSQ network
for N = 500. The thickness of link indicates the frequency of visitingin 106 time steps. From light to dark: white, yellow, and orange to red,the color gradation on a mesh block is proportionally assigned to the
population. Many nodes represented as cross points of links concentrateon high population (dark: orange and red) areas on the diagonal direction.
In the upper left and lower right of square, corner triangle areas lighted byalmost white are the sea of Japan and the Hakusan mountain range.

targetx
rv

Figure 3. Searching in a generalized MSQ network. Each blue square
represents a vision area, and is scanned (from left to right, from top tobottom in this example) by the walker on an edge between two nodes(denoted by circles) of a rectangle. For a target in the area, the walker
moves to get it and returns on the link.

search direction is constrained on long links of a collapse
rectangle, therefore it is rather hard for a walker to escapefrom a local area in which targets are a few.
We compare the search efficiency of α-random walks in
the generalized MSQ networks with that of the Levy flights

Copyright (c) IARIA, 2012.

ISBN: 978-1-61208-219-6

Figure 4. Trajectories of a random walk (Top) at α = 0 on a generalized
MSQ network for N = 500 and of a Levy flight (Bottom) for µ = 1.8 on
the square lattice with periodic boundary conditions until detecting N s =50 targets in Nt = 200. Black circle, red circles, and gray rectangle marks
denote the start point at the population barycenter, the existing targets, andthe removed targets after the detections, respectively. Note that a walker
can travel back and forth on a link in the connected path.

in the square lattice. Figure 4 shows typical trajectories until
detecting Ns = 50 targets. On the generalized MSQ networkand the square lattice, a walker tends to cover a local areawith high population and a wider area, respectively. Without
wandering peripheral wasteful areas, the generalized MSQ
network has a more efficient structure than the square latticefor detecting many targets concentrated on the diagonal
areas. Here the exponent µ = 1.8 of Levy flight corresponds
to the slope of P (lij ) in the generalized MSQ network at the
optimal size N = 500 for the search efficiency. As shownin Fig. 5(a)(b), the generalized MSQ networks of N = 500(the diamond, circle, and triangle marks are sticking out
at the left) have higher efficiency than the square lattice(the rectangle mark). For the cases with many nodes ofN ≥ 1000, the efficiency is decreased more rapidly thanthat of the Levy flight, however this phenomenon meansthat many nodes are wasteful and unnecessary to get a highsearch performance in generalized MSQ networks. When thenumber Nt of targets increases in cases from Fig. 5(a) to(b), the curves are shift up, especially for the generalized
MSQ networks. The peak value for Nt = 200 is larger thanthe optimal case of the Levy flight at µ = 2.0. Therefore66ADAPTIVE 2012 : The Fourth International Conference on Adaptive and Self-Adaptive Systems and Applications

denser targets to that extent around Nt = 200 is suitable,
although a case of larger Nt > 300 brings down the searchefficiency even for inhomogeneously distributed targets.

1.3
1.2
1.1
λη

1.4
1.2

λη

1

0.9

0.8

α= 1
α= 0
α=-1
Lattice

0.8

0.6

0.7

0.4
0.2
0

1

0

200

400

600

Nt
1

1.5

2

2.5

3
Figure 6. The number Nt of targets vs. the scaled efficiency λη of αrandom walks on the generalized MSQ networks for N = 500 and of thecorresponding Levy flights for µ = 1.8 (see Fig. 5) on the square lattice.
The maximum (optimal) efficiency appears in Nt = 200 ∼ 300. These
results are obtained by the average of 100 networks.

µ(a) Nt = 100
1.4
1.2

λη

1
0.8
0.6
0.4
0.2
0

1

1.5

2

2.5

3

µ

(b) Nt = 200
Figure 5. The scaled efficiency λη vs. the exponent µ. The marks of blue
diamond, black circle, and red triangle correspond to the cases of α =1, 0, −1, respectively, in which the increasing values of µ are estimated forgeneralized MSQ networks at N = 500, 1000, 2000, 3000, 4000, 5000,
and 5649: Nmax from left to right. The magenta rectangle corresponds tothe case of Levy flights on the square lattice. These results are obtained by
the average of 100 networks.

In more details, Fig. 6 shows the effect of the number Ntof targets on the search efficiency λη. The efficiency firstly
increases, then reaches at a peak, and finally decreases forsetting more targets. This up-down phenomenon is caused
from a trade-off between Lm and Nt in Eqs. (1) and (2).
Note that the case of size N < 500 is omitted for thegeneralized MSQ networks. Because sometimes the process
for detecting targets until Ns is not completed, moreover, thevariety of link lengths is too little to estimate the exponent
as a slope of P (lij ) in the log-log scale. In other words, theestimation is inaccurate because of the short linear part.

Copyright (c) IARIA, 2012.

ISBN: 978-1-61208-219-6

IV. C ONCLUSION
We have considered a scalably self-organized geographical network by iterative divisions of rectangles for loadbalancing of nodes in the adaptive change of their territories
according to the increasing of communication requests.
In particular, the spatially inhomogeneous distributions of
population and the corresponding positions of nodes areimportant. For the proposed networks, we have investigatesthe search efficiency in the destructive case [12] with new
creations of target after the detections, and shown that the
α-random walks as decentralized routing on the networks
have higher search efficiency than the Levy flights known
as the optimal strategy [11], [12] on the square lattice withperiodic boundary conditions. One reason for the better
performance is the anisotropic covering of high population
areas. Thus, the naturally embedded fractal-like structure issuitable for searching targets in such a realistic situation. In
more rigorous discussions about the performance, statisticaltests [36] may be useful to clarify the applicability of the
proposed method.
ACKNOWLEDGMENT
The author would like to thank Mitsugu Matsushita (Chuo
University) for his valuable comments and Takayuki Komaki (JAIST) for helping the simulation. This research is
supported in part by Grant-in-Aide for Scientific Researchin Japan, No.21500072.
R EFERENCES[1] S. H. Yook, H. Jeong, and A.-L. Barabási, “Modeling theinternet’s large-scale topology,” PNAS, 99(21), 13382–13386,
2002.

67

ADAPTIVE 2012 : The Fourth International Conference on Adaptive and Self-Adaptive Systems and Applications[2] M. T. Gastner, and M. E. J. Newman, “The spatial structureof networks,” Eur. Phys. J. B, 49(2), 247–252, 2006.

[19] A. K. Nandi, and S. S. Manna, “A transition from river
networks to scale-free networks,” New J. Phys., 9, 30, 2007

[3] R. Guimerà, S. Mossa, A. Turtschi, and L. Amaral, “Theworldwide air transportation network: Anormalous centrality, community structure, and cities’ global roles,” PNAS,
102(22), 7794–7799, 2005.

[20] J. Wang, and G. Provan, “Topological analysis of specificspatial complex networks,” Advances in Complex Systems,
12(1), 45–71, 2009.

[4] R. Lambiotte, V. Blondel, C. de Kerchove, E. Huens, C.
Prieur, Z. Smoreda, and P. Dooren, “Geographical dispersalof mobile communication networks,” Physica A, 387, 5317–
5325, 2008.
[5] D. Stoyan, W. Kendall, and J. Mecke, Stochastic Geometry
and its Applications (2nd ed.), John Wiley & Sons, 1995.
[6] J. Urrutia, “Routing with Guaranteed Delivery in Geometricand Wireless Networks,” in Handbook of Wireless Networks
and Mobile Computing, I. Stojmenović(ed), Chapter 18, John
Wiley & Sons, 2002.
[7] W.-X. Wang, B.-H. Wang, C.-Y. Yin, Y.-B. Xie, and T. Zhou,
Traffic dynamics based on local routing protocol on a scalefree network. Phys. Rev. E, 73, 026111, 2006.
[8] B. Danila, Y. Yu, S. Earl, J. A. Marsh, Z. Toroczkai, and K. E.
Bassler, “Congestion-gradient driven transport on complex
networks,” Phys. Rev. E, 74, 046114, 2006.
[9] W.-X. Wang, C.-Y. Yin, C.-Y., G. Yan, and B.-H. Wang,“Integrating local static and dynamic information for routing
traffic,” Phys. Rev. E, 74, 016101, 2006.
[10] G. M. Viswanathan, M. G. E., Luz, E. P. Raposo, and H. E.
Stanley, The Physics of Foraging -An Introduction to Random
Searches and Biological Encounters, Cambridge University
Press, 2011.

[21] A.-L. Barabási, and R. Albert, “Emergence of scaling in
random networks,” Science, 286, 509–512, 1999.
[22] D. J. Watts, and S. H. Strogatz, “Collective dynamics of”small-world” networks,” Nature, 393, 440–442, 1998.
[23] Z. Zhang, S. Zhou, Z. Su, T. Zou, and J. Guan, “Random
sierpinski network with scale-free small-world and modular
structure,” Euro. Phys. J. B, 65, 141–148, 2008.
[24] T. Zhou, G. Yan, and B.-H. Wang, “Maximal planar networks
with large clustering coefficient and power-law degree distribution,” Phys. Rev. E, 71, 046141, 2005.
[25] Z. Zhang, and L. Rong, “High-dimensional random apollonian networks,” Physica A, 364, 610–618, 2006.
[26] J. P. K. Doye, and C. P. Massen, “Self-similar disk packings asmodel spatial scale-free networks,” Phys. Rev. E, 71, 016128,
2005.
[27] L. Wang, F. Du, H. P. Dai, and Y. X. Sun, “Random
pseudofractal scale-free networks with small-world effect,”Eur. Phys. J. B, 53, 361–366, 2006.
[28] H. D. Rozenfeld, S. Havlin, and D. ben Avraham, “Fractal andtransfractal scale-free nets,” New J. of Phys., 9, 175, 2007.
[29] S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes,“Pseudofractal scale-free web,” Phys. Rev. E, 65, 066122,
2002.

[11] G. M. Viswanathan, S. V. Buldyrev, S. Havlin, M. G. E.,
da Luz, E. P. Raposo, and H. E. Stanley, “Optimizing the
success of random searches,” Nature, 401, 911–914, 1999.

[30] R. Albert, and A.-L. Barabási, “Error and attack tolerance ofcomplex networks,” Nature, 406, 378–382, 2000.

[12] M. C. Santos, G. M. Viswanathan, E. P. Raposo, and M. E.
da Luz, “Optimization of random search on regular lattices,”
Phys. Rev. E, 72, 046143, 2005.

[31] Y. Hayashi, “Evolutionary construction of geographical networks with nearly optimal robustness and efficient routing
properties,” Physica A, 388, 991–998, 2009.

[13] M. C. Santos, G. M. Viswanathan, E. P. Raposo, and M. E.
da Luz, “Optimization of random searches on defective lattice
networks,” Phys. Rev. E, 77, 041101, 2008.

[32] Y. Hayashi, and Y. Ono, “Geographical networks stochastically constructed by a self-similar tiling according to population,” Phys. Rev. E, 82, 016108, 2010.

[14] R. Albert, and A.-L. Barabási, “Statistical mechanics ofcomplex networks,” Rev. Mod. Phys., 74(1), 47–97, 2002.

[33] M. I. Karavelas, and L. J. Guibas, “Static and kinetic geometric spanners with applications,” In Proc. of the 12th ACMSIAM Symposium on Discrete Algorithms, pp. 168–176, 2001.

[15] N. E. J. Newman, “The Structure and Function of Complex
Networks,” SIAM Review, 45(2), 167–256, 2003.
[16] R. Xulvi-Brunet, and I. Sokolov, “Evolving networks withdisadvantaged long-range connections,” Phys. Rev. E, 66,
026118, 2002.
[17] S. S.Manna, and P. Sen, “Modulated scale-free network ineuclidean space,” Phys. Rev. E, 66, 066114, 2002.
[18] P. Sen, and S. S. Manna, “Clustering properties of generalized
critical euclidean network,” Phys. Rev. E, 68, 026104, 2003.

Copyright (c) IARIA, 2012.

ISBN: 978-1-61208-219-6[34] Y. Hayashi, and Y. Ono, “Traffic properties for stochastic
routing on scale-free,” IEICE Trans. on Communication, E94B(5), 1311–1322, 2011.
[35] J. D. Noh, and H. Rieger, “Random walks on complex
networks,” Phys. Rev. Lett., 92(11), 118701, 2004.
[36] A. Clauset, C. R. Shalizi, M .E. J. Newman, “Power-Law
Distributions in Empirical Data,” SIAM Review, 51, 661–703,
2009.

68