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

An approximative calculation of the fractal
structure in self‑similar tilings

Author(s)Hayashi, Yukio

Citation

IEICE TRANSACTIONS on Fundamentals ofElectronics, Communications and Computer
Sciences, E94‑A(2): 846‑849

Issue Date

2011‑02‑01

Type

Journal Article

Text version

publisher

URL

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

RightsCopyright (C)2011 IEICE. Yukio Hayashi, IEICE
TRANSACTIONS on Fundamentals of Electronics,
Communications and Computer Sciences, E94‑A(2),2011, 846‑849.
http://www.ieice.org/jpn/trans̲online/Description

Japan Advanced Institute of Science and Technology

IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.2 FEBRUARY 2011846

LETTERAn Approximative Calculation of the Fractal Structurein Self-Similar Tilings
Yukio HAYASHI†a) , Member

SUMMARY
Fractal structures emerge from statistical and hierarchicalprocesses in urban development or network evolution. In a class of eﬃcientand robust geographical networks, we derive the size distribution of layered
areas, and estimate the fractal dimension by using the distribution withouthuge computations. This method can be applied to self-similar tilings basedon a stochastic process.
key words: complex network science, geographical network, random fractal, Markov chain, urban planningThis paper investigates the size distribution of faces iteratively divided in the generation process of a MSQ network. In particular, we derive an approximative equation
for the averaging behavior of random process, and apply it
to easily estimate the fractal dimension of such a self-similartiling.
2.

1.

MSQ Network

Introduction

Fractal nature is observed in our real-life infrastructuresof urban spatial organization and many technological networks. Indeed, the fractal dimensions of land-use and areaperimeter have been measured in real data of urban cities[1], [2]. Similar structures with mixing of dense and sparseareas of nodes have been found in router networks [3], airtransportation networks [4], and mobile communication networks [5]. These studies show that the spatial distributionof human activities is inhomogeneous and concerning withthe population density. Thus, there commonly exists a hierarchical structure based on statistical self-similarity beyond
regular mathematical models such as Sierpinski gasket andcarpet. In other words, fractal behavior is not limited to objects with a regular morphology, but can be introduced byiterative evolutionary processes of subdivision or growing
at diﬀerent levels of scaling.
Recently, a multi-scale quartered (MSQ) network,
which is stochastically constructed by a self-similar tiling,has been proposed [6], [7]. The geographical network embedded on a planar space has several advantages [6]: therobustness of connectivity against failures and attacks, thebounded short path lengths, and the decentralized routing
algorithm [8] in a distributed manner. Furthermore [7], itis more eﬃcient (economic) with shorter link lengths andmore suitable (tolerant) with lower load for avoiding traffic congestion than the state-of-the-art geometric growing
networks [9]–[15] and the spatially preferential attachment
models with various topologies ranging from river to scalefree geographical networks. These properties are useful forthe future self-organized design of wide-area wireless ad
hoc networks.
Manuscript received August 17, 2010.
Manuscript revised September 24, 2010.
†The author is with Japan Advanced Institute of Science andTechnology, Nomi-shi, 923-1292 Japan.
a) E-mail: yhayashi@jaist.ac.jp
DOI: 10.1587/transfun.E94.A.846

For generating a MSQ network, the following process is repeated from an initial tiling which consists of same shaped
faces. At each time step, a face is chosen, e.g., with a probability proportional to the population in the space of a face
for the load balancing of communication requests, or uniformly at random. Then, as shown in Fig. 1, four smaller
faces are created in the chosen face, and a planar network isself-organized on a geographical space. Such a fractal structure is also observed in urban road networks [16], [17]. Notethat the MSQ network includes a Sierpinski gasket obtainedby a special selection when each triangle, except the central
one, is hierarchically divided, however its fractal dimension
log 3/ log 2 ≈ 1.585 diﬀers to that in the average behaviorof the following random selection.
3.

Infinite State Markov Chain

For simplicity, we treat the uniformly random selection of aface, whose case corresponds to general positions of nodes
in the geographical network. In addition, even if a face inthe area of high population density tend to be chosen for thesubdivision, the assigned population to a node in its territory is asymptotically balanced, then the behavior closes tothe case of random selections in course of time. In this setting, the subdivision process makes an infinite state Markovchain as illustrated in Fig. 2. Here, we consider a vec-Fig. 1

Basic process of the division.

c 2011 The Institute of Electronics, Information and Communication Engineers
Copyright LETTER847

Fig. 2Fig. 3

Iterative division of a face chosen uniformly at random.

The distribution of pl .

tor (n1 (t), n2 (t), . . . , nl (t) . . .) as the state of Markov chain,whose element nl (t) represents the number of faces at time
step t on the layer l defined by decreasing order of size. A
face on the layer l is chosen with the probability pl (t) =nl (t)/N(t) at the next step t+1, then the sate is changed from(. . . , nl (t), nl+1 (t),
 . . .) to (. . . , nl (t + 1) − 1, nl+1 (t + 1) + 4, . . .),where N(t) = k nk (t) = N0 + 3t denotes the total numberof faces at t, and N0 is the initial number. Note that pl (t) is
time-dependent on a selected path for the decision tree fromthe top to the bottom in Fig. 2, equivalently on a selection
sequence of faces. Thus, the above Markov chain is diﬀerent from the Galton-Watson type branching process with atime-independent probability for generating oﬀsprings [18].
We obtain the averaging behavior fordef

Δnl = nl (t + 1) − nl (t).

Fig. 4(1)This can be written as
Δnl = 4pl−1 (t) − pl (t),(2)since a face on the layer l chosen with the probability pl (t)is divided into four smaller ones which belong to the layer
l+1, therefore a face on the layer l−1 contributes to increase
the number of faces on the layer l. For a large t, by noticing
nl (t) = N(t)pl (t) and substituting N(t) = N0 + 3t ≈ 3t into
the right-hand side of Eq. (1), it isΔnl = 3(t + 1)pl (t + 1) − 3tpl (t),= 3t[pl (t + 1) − pl (t)] + 3pl (t + 1).
Using pl (t + 1) ≈ pl (t) because of t + 1 ≈ t  1, Eq. (2) isrewritten to4
pl (t + 1) − pl (t) = − [pl (t) − pl−1 (t)].
(3)
3t
We numerically confirm that the average behavior of
the Markov chain is well fitting to the solution for Eq. (3) asshown in Fig. 3. Here, the cross, asterisk, open square, andclosed square marks correspond to the average of 100 states
reached at each time t = 102 , 103 , 104 , and 105 , respectively, on the decision tree from the initial state (3, 4, 0, . . .)Mean & variance of the distribution of pl .

in Fig. 2. The four types of dashed curves correspond to
the distributions calculated by Eq. (3) until these times. The
solid curve fitting with the closed square marks is the approximation by a normal distribution. Note that the averaged or calculated number nl of faces on each layer l at t
is normalized as the relative frequency pl . This bell-shaped
distribution means that there exist a mixing of dense andsparse areas with various sizes of faces whose majorities
have the intermediate sizes. Figure 4 shows the mean andthe variance of the distribution pl . The upper and lower triangle marks denote the mean and the variance of the distribution obtained for the Markov chain. The solid and dashedlines denote the corresponding results for Eq. (3). In Fig. 5,
the circle marks and dotted piecewise linear line denote theskewness of these distributions for the Markov chain andfor Eq. (3), respectively. The mean and the variance grow as
O(log t), while the skewness is almost constant around 0.2.
Although the pl is asymptotically a Poisson distribution witha same value for the mean and the variance as mentioned inthe Appendix, it is rather fitting with the approximation by
Eq. (3) in a finite size.
On the basis of the numerically obtained pl (t), the fractal dimension d f is estimated as 1.2 (a similar value is ob-

IEICE TRANS. FUNDAMENTALS, VOL.E94–A, NO.2 FEBRUARY 2011

848

Fig. 6 Illustration for a cover-based method. We count holes by thenumbers for n2 and the parenthesized numbers for n1 .
Fig. 5Skewness of the distribution of pl .

4.
tained for a chair or a sphinx tilling [19]) by using a coverbased method in the hierarchically coarse measure of doubling link length on each layer l until t = 108 . Figure 6
shows an example at the state (1, 11, 4, 0, . . .). The numberof covered areas (gray rectangles) is
N[2] = 2 × N[1] + 11 + 3 × (42 − (4 × 1 + 11)),
where we set the number of initial coverings N[1] = 12
for a square tiling. It depends on the primitive shape;
N[1] = 9 for a triangle tiling, and N[1] = 8 for a chairor a sphinx tiling. In general for a large l, we calculate
d f = log N/ log 2l from
2 × N[l − 1] + nl + 3 × (T l − S l ),(4)

the total number of faces in the completely recursive didef
vision T l = 4l , the number of holes without subdivisionsdef
S l = 4 × nl−1 + nl , and S 1 = n1 . Three terms in the righthand side of Eq. (4) correspond to thick, thin solid lines, anddashed lines in Fig. 6. Since there is one-to-one correspondence between the divided four faces and the cross-edges ina square at each layer l, e.g., by applying a clockwise mapping rule, nl represents this eﬀect on the covering. However,the 2nd and the 3rd terms are replaced by 3 × nl /4 fora triangle tiling, and by 8 × nl /4 for a chair or a sphinx
tiling. We emphasis that our method can be performed byonly using the calculated nl without both averaging and image processings in a box-counting method.
We should remark that the continuous approximation
with respect to time and space variables for both sides ofEq. (3)∂pl4 ∂pl=−∂t
3t ∂lgives an incorrect solution, which keeps the shape in thetraveling wave
pl (t) = F(l − v log t),
where a function F() is determined by the initial distribution,and v = 4/3.

Conclusion

Considering the stochastic network construction [6], [7] as aMarkov chain, the size distribution of the divided faces has
been investigated. We have shown, by numerically solving
Eq. (3) as the average behavior, that the mean and the variance are proportional to log t, while the skewness is smallpositive. In a realistic finite size N ∝ t ≤ 108 , this approximation of pl is fitting better than the asymptotical Poisson solution for the interactive particle system (see the Appendix). From the distribution nl = N pl , the fractal dimension is estimated as 1.2 without huge computations of
averaging and image processings in the conventional boxcounting method. The proposed method can be applied toother self-similar tilings based on a stochastic process. Furthermore, it would be interesting to discuss a self-similar
modeling which reproduces the fractal structures of urban
road [16], [17], air-sea transportation [4], communication[5] networks.
Acknowledgment
The author would like to thank Prof. Norio Konno in Yokohama National University for suggesting the theoreticalanalysis in the Appendix. This research is supported inpart by a Grant-in-Aid for Scientific Research in Japan, No.
21500072.
References[1] M. Batty and P.A. Longley, Fractal Cities: A Geometry of Form andFunction, Academic Press, London, 1994.
[2] P. Franlhauser, “The fractal approach: A new tool for the spatial
analysis of urban agglomerations,” Population: An English Selection, vol.10, pp.205–240, 1998.
[3] S.-H. Yook, H. Jeong, and A.-L. Barabási, “Modeling the Internet’s
large-scale topology,” PNAS, vol.99, no.21, pp.13382–13386, 2002.
[4] R. Guimerà, S. Mossa, A. Turtschi, and L.A.N. Amaral, “The worldwide air transportation network: Anomalous centrality, community
structure, and cites’ global roles,” PNAS, vol.102, no.22, pp.7794–7799, 2005.
[5] R. Lambiotte, V.D. Blondel, C. de Kerchove, E. Huens, C. Prieur, Z.
Smoreda, and P.V. Dooren, “Geographical dispersal of mobile communication networks,” Physica A, vol.387, pp.5317–5325, 2008.

LETTER

849[6] Y. Hayashi, “Evolutionary construction of geographical networks
with nearly optimal robustness and eﬃcient routing properties,”
Physica A, vol.388, pp.991–998, 2009.
[7] Y. Hayashi and Y. Ono, “Geographical networks stochastically constructed by a self-similar tiling according to population,” Phys. Rev.
E, vol.82, 016108-1–9, 2010.
[8] P. Bose, and P. Morin, “Competitive online routing in geometricgraphs,” Theor. Comput. Sci., vol.324, no.2-3, pp.273–288, 2004.
[9] Z. Zhang, S. Zhou, Z. Su, T. Zou, and J. Guan, “Random siepinski
network with scale-free small-world and modular structure,” Eur.
Phys. J. B, vol.65, pp.141–147, 2008.
[10] T. Zhou, G. Yan, and B.-H. Wang, “Maximal planar networks
with large clustering coeﬃcient and power-law degree distribution,”
Phys. Rev. E, vol.71, 046141-1–11, 2005.
[11] Z. Zhang and L. Rong, “High dimensional random Apollonian networks,” Physica A, vol.364, pp.610–618, 2006.
[12] J.P.K. Doye and C.P. Massen, “Self-similar disk packings as model
spatial scale-free networks,” Phys. Rev. E, vol.71, 016128-1–11,2005.
[13] L. Wang, F. Du, H.P. Dai, and Y.X. Sun, “Random pseudofractal
scale-free networks with small-world eﬀect,” Eur. Phys. J. B, vol.53,pp.361–366, 2006.
[14] H.D. Rozenfeld, S. Havlin, and D. ben-Avraham, “Fractal and transfractal recursive scale-free nets,” New J. Phys., vol.6, pp.175-1–15,
2006.
[15] S.N. Dorogovtsev, A.V. Goltsev, and J.F.F. Mendes, “Pseudofractal
scale-free web,” Phys. Rev. E, vol.65, 066122-1–4, 2002.
[16] V. Kalapala, V. Sanwalani, A. Clauset, and C. Moore, “Scaleinvariance in road networks,” Phys. Rev. E, vol.73, 026130-1–6,2006.
[17] A. Cardillo, S. Scellato, V. Latora, and S. Porta, “Structual properties of planar graphs of urban street patterns,” Phys. Rev. E, vol.73,066107-1–8, 2006.
[18] T.M. Liggett, Stochastic Interacting Systems: Contact, Voter andExclusion Processes, Springer, 1999.
[19] B. Solomyak, “Dynamics of self-similar tilings,” Ergod. Theory andDyn. Syst., vol.17, pp.695–738, 1997.

face in Sect. 3, therefore the number η(x) decreases by 1 atx and increases by m at x due to the contribution at x − 1. In
particular for f (η) = η(x), we havedn x (τ)= m × n x−1 (τ) − n x (τ), x ≥ 1,dτ
dn0 (τ)= −n0 (τ),
dτ(A· 1)
(A· 2)

where n x (τ) = E[ητ (x)] is the expectation of the number ofparticles at position x and at time τ, and the initial configuration is η0 = (m, 0, 0, . . .). We can solve (A· 1), (A· 2),n x (τ) = m x

τ x−1 −τe , x ≥ 1.
(x − 1)!

Also, the expectation of the total number of particles is givenbyN(τ) = me(m−1)τ .
Therefore, from p x (τ) = n x (τ)/N(τ), we obtain the Poisson
distribution with a parameter mτ
p x (τ) =(mτ) x−1 −mτ
e , x ≥ 1.
(x − 1)!

By the variable transformation between t and τ from the relation N(t) = N(0) + (m − 1)t ⇔ N(τ) = me(m−1)τ , themean and the variance follow mτ ∝ log t. This logarithmic
behavior is consistent with the numerical results in Sect. 3.
As another typical approach, if we consider a generating function
defH (t) (z) =∞pl (t)zl ,l=1

Appendix
Let us reformulate the subdivision process for generating
a MSQ network as a model in interacting infinite particle
systems. Then, according to the notation [18], we consider
the generator ΩH on Z+ = {1, 2, . . .},η(x)[ f (η x,x+1 ) − f (η)],ΩH f (η) =x∈Z+where we set m = 4 and define the following functions onη ∈ {0, 1, 2, . . .}Z+ ,⎧⎪η(x + 1) + m, y = x + 1,
⎪def ⎪⎨x,x+1
η(x)− 1,y = x,
η(y) = ⎪⎪⎪⎩ η(y),y  x, x + 1.
Note that the position x corresponds to the layer l of a chosen

by multiplying
zl to both sides of Eq. (3) and taking the sum
,weobtain
mation ∞l=1
4(1 − z) (t)H (t+1) (z) = 1 −H (z).
3tHere, we use l pl−1 (t)zl = zH (t) (z). The frequency pl (t) isonly formally calculated by the recursive diﬀerentials
pl (t) =1 ∂l H (t) (z).
l! ∂zl z=0

However, it is practically unsolvable because of involving
with a very complicated combinatorial explosion for a larget, equivalently for a large network size N ∝ t.