© Springer Nature Switzerland AG 2020
E. RosenbergFractal Dimensions of Networkshttps://doi.org/10.1007/978-3-030-43169-3_12

12. Dimensions of Infinite Networks

Eric Rosenberg1 
(1)
AT&T Labs, Middletown, NJ, USA
 

Oh, what a tangled web do parents weave

When they think that their children are naive.

Ogden Nash (1902–1971), American poet.

There are two main ways to construct a geometric fractal, or equivalently, two main classes of geometric fractals [Tél 88]. The first class describes a bounded geometric object e.g., the middle-third Cantor set or the Sierpiński triangle, for which the distance between points, or the diameter of replicated self-similar patterns, vanishes. There is no smallest scale, and we “zoom in” on the object with a magnification scale that approaches infinity to view the object features which are growing infinitely small. To calculate a fractal dimension (e.g., the box counting dimension d B, the Hausdorff dimension d H, or the correlation dimension d C), we let the box size or radius approach zero.

The second class of fractals described in [Tél 88] describes geometric objects whose size increases to infinity. Such objects often are embedded in some regular lattice for which the inter-lattice spacing remains constant while the size of the object increases to infinity. This class characterizes objects such as aggregates constructed by a growth process, e.g., powder packing or DLA (Sect. 10.​4). For such objects, there is no largest scale, and we “zoom out” on the object with an ever-increasing window size to see the growing object. This second class also describes networks whose size grows to infinity. A simple example of such a network is the square rectilinear grid in $${\mathbb {R}}^E$$ studied in Sect. 11.​4, where we let the side length approach infinity.

The starting point for all our fractal dimensions has been the scaling relationship bulk ∼size d presented in the beginning of Chap. 1. In this chapter we consider this scaling for Tél’s second class, in particular for a sequence $$\{ {\mathbb {G}}_t \}_{t=1}^{\infty }$$ of networks such that $${\mathbb {G}}_t$$ grows infinitely large, where by “ $${\mathbb {G}}_t$$ grows infinitely large” we mean $$\mathit {diam}( {\mathbb {G}}_t ) \rightarrow \infty $$ as t →∞. For brevity we write $$ \{ {\mathbb {G}}_t \}$$ to denote $$\{ {\mathbb {G}}_t \}_{t=1}^{\infty }$$ .

One possible approach to developing a scaling law for $$\{ {\mathbb {G}}_t \}$$ is to compute a minimal cover $${\mathcal {B}}_t(s)$$ of $${\mathbb {G}}_t$$ by boxes of size s and study how the number of boxes in $${\mathcal {B}}_t(s)$$ scales as s →∞ and t →∞. Another possible approach is to study how the correlation sum of $${\mathbb {G}}_t$$ , defined by (9.​11), scales as r →∞ and t →∞. A third and much simpler approach is to study how the mass N t of $${\mathbb {G}}_t$$ , which we define to be the number of nodes in $${\mathbb {G}}_t$$ , scales with $$\mathit {diam}( {\mathbb {G}}_t)$$ . Defining
$$\displaystyle \begin{aligned} \begin{array}{rcl} \varDelta_t \equiv \mathit{diam}( {\mathbb{G}}_t) \, , {} \end{array} \end{aligned} $$
(12.1)
the fractal dimension proposed in [Zhang 08] to characterize $$\{ {\mathbb {G}}_t \}$$ is given by Definition 12.1 below.1
Definition 12.1 If
$$\displaystyle \begin{aligned} \begin{array}{rcl} {d_{{M}}} \equiv \lim_{t \rightarrow \infty} \frac {\log N_t} {\log \varDelta_{{t}}} \, {} \end{array} \end{aligned} $$
(12.2)
exists and is finite, then d M is the mass dimension of the sequence $$\{ {\mathbb {G}}_t \}$$ and $$\{ {\mathbb {G}}_t \}$$ is fractal. If the limit (12.2) is infinite, then $$\{ {\mathbb {G}}_t \}$$ is non-fractal. □

According to Definition 12.1, the sequence $$\{ {\mathbb {G}}_t \}$$ is fractal if d M exists and is finite; otherwise, $$\{ {\mathbb {G}}_t \}$$ is non-fractal. This is a very different meaning of “fractal” than given by Definition 7.5, which says that a given finite network is fractal if d B exists.

Although the scalings $$N_t \sim \varDelta _t^{d_{{M}}}$$ and ../images/487758_1_En_12_Chapter/487758_1_En_12_IEq23_HTML.gif (see (11.​8) in Sect. 11.​1) are similar, Definition 12.1 defines d M only for an infinite sequence of networks but not for a single finite network. An advantage of d M over the correlation dimension d C is that it is typically much easier to compute the network diameter than to compute C(n, r) for each n and r, as is required to compute C(r) using (11.​6).

Exercise 12.1 Can Definition 12.1 be adapted to define d M for a finite network? Would such a definition be useful? □

In the next two sections we examine three methods of constructing a sequence $$\{ {\mathbb {G}}_t \}$$ of networks such that Δ t →∞. The constructions are parameterized by a probability p ∈ [0, 1]. For the first two constructions studied in Sect. 12.1, $$\{ {\mathbb {G}}_t \}$$ is (using the terminology of Definition 12.1) fractal. For the third construction, studied in Sect. 12.2, $$\{ {\mathbb {G}}_t \}$$ is non-fractal, which leads to the definition of the transfractal dimension of the sequence $$\{ {\mathbb {G}}_t \}$$ . In the remaining sections of this chapter we present the pioneering results of Nowotny and Requardt [Nowotny 88] on the fractal dimension of infinite networks.

12.1 Mass Dimension

A procedure was presented in [Zhang 08] that uses a probability p to construct a sequence $$\{ {\mathbb {G}}_t \}$$ that exhibits a transition from fractal to non-fractal behavior as p increases from 0 to 1. For p = 0, the sequence $$\{ {\mathbb {G}}_t \}$$ does not exhibit the small-world property and has d M = 2, while for p = 1 the sequence does exhibit the small-world property and d M = ∞. The construction begins with $${\mathbb {G}}_0$$ , which is a single arc, and p ∈ [0, 1]. Let $${\mathbb {G}}_t$$ be the network after t steps. The network $${\mathbb {G}}_{t+1}$$ is derived from $${\mathbb {G}}_{t}$$ .

For each arc in $${\mathbb {G}}_{t}$$ , with probability p we replace the arc with a path of 3 hops (introducing the two nodes c and d, as illustrated by the top branch of Fig. 12.1), and with probability 1 − p we replace the arc with a path of 4 hops (introducing the three new nodes c, d, and e, as illustrated by the bottom branch of Fig. 12.1). For p = 1, the first three generations of this construction yield the networks of Fig. 12.2.
../images/487758_1_En_12_Chapter/487758_1_En_12_Fig1_HTML.png
Figure 12.1

Constructing $${ \mathbb {G}}_{t+1}$$ from $${ \mathbb {G}}_{t}$$

../images/487758_1_En_12_Chapter/487758_1_En_12_Fig2_HTML.png
Figure 12.2

Three generations with p = 1

Colored arcs in the networks for t = 1 and t = 2 show the construction with p = 1: the red arc in the t = 1 network becomes the center arc in a chain of three red arcs in the t = 2 network, the green arc in the t = 1 network becomes the center arc in a chain of three green arcs in the t = 2 network, and similarly for the blue arc in the t = 1 network. For p = 0, the first three generations of this construction yield the networks of Fig. 12.3. This construction builds upon the construction in [Rozenfeld 09] of (u, v) trees.
../images/487758_1_En_12_Chapter/487758_1_En_12_Fig3_HTML.png
Figure 12.3

Three generations with p = 0

Let N t be the expected number of nodes in $${\mathbb {G}}_t$$ , let A t be the expected number of arcs in $${\mathbb {G}}_t$$ , and let Δ t be the expected diameter of $${\mathbb {G}}_t$$ . The quantities N t, A t, and Δ t depend on p, but for notational simplicity we omit that dependence. Since each arc is replaced by three arcs with probability p, and by four arcs with probability 1 − p, for t ≥ 1 we have
$$\displaystyle \begin{aligned} A_{t} &= 3p A_{t-1} + 4 (1-p) A_{t-1} = (4-p)A_{t-1} \\ & = (4-p)^2 A_{t-2} = \cdots = (4-p)^t A_0 = (4-p)^t \, , {} \end{aligned} $$
(12.3)
where the final equality follows as A 0 = 1, since $${\mathbb {G}}_0$$ consists of a single arc.
Let x t be the number of new nodes created in the generation of $${\mathbb {G}}_t$$ . Since each existing arc spawns two new nodes with probability p and spawns three new nodes with probability 1 − p, from (12.3) we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} {x_{{t}}} = 2p A_{t-1} + 3 (1-p) A_{t-1} = (3-p) A_{t-1} = (3-p)(4-p)^{t-1} \, . {} \end{array} \end{aligned} $$
(12.4)
Since $${\mathbb {G}}_0$$ has 2 nodes, for t ≥ 1 we have
$$\displaystyle \begin{aligned} N_t &= 2 + \sum_{i=1}^{t} {x_{{i}}} \; = \; 2 + \sum_{i=1}^{t} (3-p)(4-p)^{i-1} \\ &= 2 + (3-p) \frac{ (4-p)^t -1}{(3-p)} \; = \; (4-p)^t + 1 \, . {} \end{aligned} $$
(12.5)

To compute the diameter Δ t of $${\mathbb {G}}_t$$ , first consider the case p = 1. For this case, distances between existing node pairs are not altered when new nodes are added. At each time step, the network diameter increases by two. Since Δ 0 = 1 then Δ t = 2t + 1. Since N t ∼ (4 − p)t, then the network diameter grows as the logarithm of the number of nodes, so $$\{ {\mathbb {G}}_t \}$$ exhibits the small-world property for p = 1. From (12.2) we have d M = ∞.

Now consider the case 0 ≤ p < 1. For this case, the distances between existing nodes are increased. Consider an arc in the network $${\mathbb {G}}_{t-1}$$ , and the endpoints i and j of this arc. With probability p, the distance between i and j in $${\mathbb {G}}_{t}$$ is 1, and with probability 1 − p, the distance between i and j in $${\mathbb {G}}_{t}$$ is 2. The expected distance between i and j in $${\mathbb {G}}_{t}$$ is therefore p + 2(1 − p) = 2 − p. Since each $${\mathbb {G}}_{t}$$ is a tree, for t ≥ 1 we have
$$\displaystyle \begin{aligned} \varDelta_{{t}} = p \varDelta_{t-1} + 2 (1-p) \varDelta_{t-1} + 2 = (2-p) \varDelta_{t-1} + 2 \end{aligned}$$
and Δ 0 = 1. This yields [Zhang 08]
$$\displaystyle \begin{aligned} \begin{array}{rcl} \varDelta_{{t}} = \left( 1 + \frac{2}{1-p} \right)(2-p)^t - \frac{2}{1-p} \, . {} \end{array} \end{aligned} $$
(12.6)
From (12.2), (12.5), and (12.6),
$$\displaystyle \begin{aligned} \begin{array}{rcl} {d_{{M}}} = \lim_{t \rightarrow \infty} \frac {\log N_t} {\log \varDelta_{{t}}} = \lim_{t \rightarrow \infty} \frac {\log [(4-p)^t + 1] } {\log \left[ \left( 1 + \frac{2}{1-p} \right)(2-p)^t - \frac{2}{1-p} \right]} = \frac{ \log (4-p)} {\log (2-p) } \, , {} \end{array} \end{aligned} $$
(12.7)
so d M is finite, and $$\{ {\mathbb {G}}_t \}$$ does not exhibit the small-world property. For p = 0 we have $$d_{{M}} = \log 4/\log 2 = 2$$ . Also, $$\log (4-p)/\log (2-p) \rightarrow \infty $$ as p → 1.

Next we present the analysis in [Li 14] of the properties of the family of networks introduced in [Gallos 07a]. The parameters used to construct these networks are two positive integers m and x, where x ≤ m, and α ∈ [0, 1]. The network $${\mathbb {G}}_0$$ at time t = 0 consists of a single arc. The network $${\mathbb {G}}_{t+1}$$ is derived from $${\mathbb {G}}_t = ({\mathbb {N}}_t, {\mathbb {A}}_t)$$ as follows.

Step 1. For each arc in $${\mathbb {G}}_t$$ , connect each endpoint of the arc to m new nodes. This step creates a total of $$2 m \vert {\mathbb {A}}_t \vert $$ new nodes. This is illustrated, for a single arc, in Fig. 12.4 for m = 3. Node u spawns nodes c, e, and g, and node v spawns nodes d, f, and h.
../images/487758_1_En_12_Chapter/487758_1_En_12_Fig4_HTML.png
Figure 12.4

$$ \mathbb {G}_0$$ and $$ \mathbb {G}_1$$ for x = 2 and m = 3

Step 2. Generate a random number p, using the uniform distribution on [0, 1]. (Thus p will vary from generation to generation.)

Step 3. We consider two cases, both illustrated in Fig. 12.4 for m = 3 and x = 2. Case 1. If α ≤ p ≤ 1, none of the arcs in $${\mathbb {A}}_t$$ is an arc in $${\mathbb {A}}_{t+1}$$ . However, for each $$a \in {\mathbb {A}}_t$$ we create x new arcs as follows. Let u and v be the endpoints of a. We select x of the m nodes created in Step 1 that are attached to u, and x of the m nodes created in Step 1 that are attached to v, and connect these two sets of x nodes by x arcs. In Fig. 12.4, arc (u, v) is not preserved, and arcs (c, d) and (e, f) are created. Case 2. If 0 ≤ p < α, each $$a \in {\mathbb {A}}_t$$ is also an arc in $${\mathbb {A}}_{t+1}$$ . Additionally, for each $$a \in {\mathbb {A}}_t$$ we create x − 1 new arcs as follows. Let i and j be the endpoints of a. We select x − 1 of the m nodes created in Step 1 that are attached to u, and x − 1 of the m nodes created in Step 1 that are attached to v, and connect these two sets of x − 1 nodes by x − 1 arcs. In Fig. 12.4, arc (u, v) is preserved, and arc (e, f) is created. Figure 12.5 illustrates three generations when α = 0, m = 2, and x = 2. Since α = 0, we are always in Case 1 of Step 3.
../images/487758_1_En_12_Chapter/487758_1_En_12_Fig5_HTML.png
Figure 12.5

$$ \mathbb {G}_0$$ and $$ \mathbb {G}_1$$ and $$ \mathbb {G}_2$$ for α = 0 and x = 2 and m = 2

In general, for this construction we have $$A_{t+1} = \vert {\mathbb {A}}_{t+1} \vert = (2m+x) A_t$$ which implies A t = (2m + x)t. As for the number of nodes, each arc in $${\mathbb {A}}_t$$ spawns 2m new nodes, so
$$\displaystyle \begin{aligned} N_{t+1} = \vert {\mathbb{N}}_{t+1} \vert = N_t + 2m A_t = N_t + 2 m (2m+x)^t \, , \end{aligned}$$
which has the solution
$$\displaystyle \begin{aligned} \begin{array}{rcl} N_t = \left( 2 - \frac{2m}{2m+x-1} \right) + \left( \frac{2m}{2m+x-1}\right) (2m+x)^t \, . {} \end{array} \end{aligned} $$
(12.8)
Let H t be the hop count between two nodes of $${\mathbb {G}}_t$$ . From Fig. 12.4 we see that with probability 1 − α we have H t+1 = 3H p and with probability α we have H t+1 = H t. Thus H t+1 = (1 − α)3H t + αH t = (3 − 2α)H t, which implies Δ t+1 = (3 − 2α)Δ t. Since Δ 0 = 1 then Δ t = (3 − 2α)t. By (12.2) the mass dimension d M of the infinite sequence $$\{ {\mathbb {G}}_t \}$$ is
$$\displaystyle \begin{aligned} \begin{array}{rcl} \frac { \log (2m+x) } {\log (3 - 2 \alpha ) } \, . \end{array} \end{aligned} $$
(12.9)
Next we examine how the node degree changes each generation. For a given t, let n be any node in $${\mathbb {N}}_t$$ and consider the node degree δ n. Since n is the endpoint of δ n arcs, then in Step 1 node n gets mδ n new neighbors. In Step 3, if Case 1 occurs, which happens with probability 1 − α, node n loses each of the δ n arcs currently incident to n. If Case 2 occurs, which happens with probability α, the x − 1 new arcs created are not incident to n. Thus the node degree of n in $${\mathbb {G}}_{t+1}$$ is δ n + mδ n − (1 − α)δ n = δ n(m + α), so the degree of each node increases by the factor m + α. It was shown in [Song 06, Li 14] that $${\mathbb {G}}_t$$ is scale-free, with the node degree distribution p k ∼ k −γ, where
$$\displaystyle \begin{aligned} \begin{array}{rcl} \gamma = 1 + \frac{\log (2m+x)}{\log (m + \alpha)} \, . {} \end{array} \end{aligned} $$
(12.10)

12.2 Transfractal Networks

A deterministic recursive construction can be used to create a sequence $$\{ \mathbb {G}_t \}$$ of self-similar networks. Each $$\mathbb {G}_t$$ is called a (u, v)-flower, where u and v are positive integers [Rozenfeld 09]. By varying u and v, both fractal and non-fractal sequences $$\{ \mathbb {G}_t \}$$ can be generated. The construction starts at time t = 1 with a cyclic graph (a ring), with w ≡ u + v arcs and w nodes. At time t + 1, replace each arc of the time t network by two parallel paths, one with u arcs, and one with v arcs. Without loss of generality, assume u ≤ v. Figure 12.6 illustrates three generations of a (1, 3)-flower. The t = 1 network has 4 arcs. To generate the t = 2 network, arc a is replaced by the path {b} with one arc, and also by the path {c, d, e} with three arcs; the other three arcs in subfigure (i) are similarly replaced. To generate the t = 3 network, arc d is replaced by the path {p} with one arc, and also by the path {q, r, s} with three arcs; the other fifteen arcs in subfigure (ii) are similarly replaced. The self-similarity of the (u, v)-flowers follows from an equivalent method of construction: generate the time t + 1 network by making w copies of the time t network, and joining the copies at the hubs.
../images/487758_1_En_12_Chapter/487758_1_En_12_Fig6_HTML.png
Figure 12.6

Three generations of a (1, 3)-flower

Let $${\mathbb {G}}_t$$ denote the (u, v)-flower at time t. The number of arcs in $${\mathbb {G}}_t$$ is A t = w t = (u + v)t. The number N t of nodes in $${\mathbb {G}}_t$$ satisfies the recursion N t = wN t−1 − w. With the boundary condition N 1 = w we obtain [Rozenfeld 09]
$$\displaystyle \begin{aligned} \begin{array}{rcl} N_t = \left( \frac{w-2}{w-1} \right) w^{\, t} + \left( \frac{w}{w-1} \right) \, . {} \end{array} \end{aligned} $$
(12.11)
Consider the case u = 1. It can be shown [Rozenfeld 09] that for (1, v)-flowers and odd v we have
$$\displaystyle \begin{aligned} \varDelta_{{t}} = (v-1)t + (3-v)/2 \end{aligned}$$
while in general, for (1, v)-flowers and any v,
$$\displaystyle \begin{aligned} \begin{array}{rcl} \varDelta_{{t}} \sim (v-1)t \, . {} \end{array} \end{aligned} $$
(12.12)
Since N t ∼ w t then $$\varDelta _{{t}} \sim \log N_t$$ , so (1, v)-flowers enjoy the small-world property. By (12.2), (12.11), and (12.12), for (1, v)-flowers we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} {d_{{M}}} = \lim_{t \rightarrow \infty} \frac{\log N_t}{\log \varDelta_{{t}}} = \lim_{t \rightarrow \infty} \frac{\log w^{\, t}}{\log t} = \infty \, , {} \end{array} \end{aligned} $$
(12.13)
so by Definition 12.1 the sequence of (1, v)-flowers is non-fractal.
We want to define a new type of fractal dimension that is finite for the sequence of (1, v)-flowers and for other non-fractal sequences of networks. For (1, v)-flowers, from (12.11) we have
$$\displaystyle \begin{aligned} N_t \sim w^{\, t} = (1+v)^t \end{aligned}$$
as t →∞ and $$\log N_t \sim t \log (1+v)$$ . From (12.12) we have Δ t ∼ (v − 1)t as t →∞. Since both $$\log N_t$$ and Δ t behave like a linear function of t as t →∞, but with different slopes, let d E be the ratio of the slopes.2 Then
$$\displaystyle \begin{aligned} \begin{array}{rcl} {d_{{E}}} \equiv \frac{\log (1+v)}{v-1} \, . {} \end{array} \end{aligned} $$
(12.14)
From (12.14), (12.12), and (12.11), as t →∞ we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} {d_{{E}}} = \frac{t \log (1+v)}{t(v-1)} = \frac{ \log (1+v)^t}{t(v-1)} = \frac{ \log w^{\, t}}{t(v-1)} \sim \frac{\log N_t}{\varDelta_{{t}}} \, , {} \end{array} \end{aligned} $$
(12.15)
from which we obtain
$$\displaystyle \begin{aligned} \begin{array}{rcl} N_t \sim e^{d_{{E}} \varDelta_{{t}}} . {} \end{array} \end{aligned} $$
(12.16)
Define α t ≡ Δ t+1 − Δ t. From (12.16),
$$\displaystyle \begin{aligned} \begin{array}{rcl} \frac{N_{t+1}}{N_t} \sim \frac{ e^{d_{{E}} \varDelta_{t+1} } } { e^{d_{{E}} \varDelta_{{t}}} } = e^{d_{{E}} \alpha_{{t}} } . {} \end{array} \end{aligned} $$
(12.17)
Writing N t = N(Δ t) for some function N(⋅),
$$\displaystyle \begin{aligned} N_{t+1} = N(\varDelta_{t+1}) = N(\varDelta_{{t}} + \alpha_{{t}}) \, . \end{aligned}$$
From this and (12.17),
$$\displaystyle \begin{aligned} \begin{array}{rcl} N(\varDelta_{{t}} + \alpha_{{t}}) \sim N(\varDelta_{{t}}) e^{d_{{E}} \alpha_{{t}} } {} \end{array} \end{aligned} $$
(12.18)
which says that, for t ≫ 1, when the diameter increases by α t, the number of nodes increases by a factor which is exponential in d Eα t. As observed in [Rozenfeld 09], in (12.18) there is some arbitrariness in the selection of e as the base of the exponential term $$e^{{d_{{E}}} \alpha _{{t}} }$$ since from (12.14) the numerical value of d E depends on the logarithm base.

Definition 12.2 [Rozenfeld 09] If (12.18) holds as t →∞ for a sequence of self-similar graphs $$\{ {\mathbb {G}}_t \}$$ , then d E is called the transfinite fractal dimension. A sequence of self-similar networks whose mass dimension d M is infinite, but whose transfinite fractal dimension d E is finite, is called a transfinite fractal, or simply transfractal. □

The transfractal dimension “usefully distinguishes between different graphs of infinite dimensionality” [Rozenfeld 09]. Thus the sequence of (1, v)-flowers is transfractal with transfinite fractal dimension $$d_{{E}} = {\log (1+v)}/{(v-1)}$$ . Finally, consider (u, v)-flowers with u > 1. It can be shown [Rozenfeld 09] that Δ t ∼ u t. Using (12.11),
$$\displaystyle \begin{aligned} \lim_{t \rightarrow \infty} \frac {\log N_t } {\log \varDelta_{{t}}} = \lim_{t \rightarrow \infty} \frac {\log w^{\, t} } {\log u^t} = \frac {\log (u+v)} {\log u} \, , \end{aligned}$$
so
$$\displaystyle \begin{aligned} {d_{{M}}} = \frac{\log (u+v)}{\log u} \, . \end{aligned}$$
Since d M is finite, this sequence of networks is fractal, not transfractal, and these networks do not enjoy the small-world property. In [Komjáthy 19], the definition of the transfractal dimension was extended by considering the box counting dimension for infinite sequences of graphs.

12.3 Volume and Surface Dimensions

In this section we study two very early definitions in [Nowotny 88] of the dimension of an infinite network $$\mathbb {G}$$ . Unlike the previous two sections of this chapter, in this section we are not studying a sequence $$\{ \mathbb {G}_t \}$$ of networks such that Δ t →∞; rather, we are studying one network $$\mathbb {G}$$ whose diameter is infinite. It might be that $$\mathbb {G}$$ can be viewed as the limit of a sequence $$\{ \mathbb {G}_t \}$$ , e.g., an infinite rectilinear grid network embedded in $$\mathbb {R}^2$$ can be viewed as the limit, as K →∞, of a K × K rectilinear grid (as studied in Sect. 11.​4), but we do not assume that $$\mathbb {G}$$ is the limit of some sequence of networks. Since the two network dimensions of [Nowotny 88] are defined in terms of a limit as r →∞, these dimensions are related to the mass dimension d M.

The pioneering paper [Nowotny 88] is not well-known, and indeed has barely been mentioned in the bibliographies and reference lists of the bibliographic entries of this book.3 The motivation for the two dimensions proposed in [Nowotny 88] is a working philosophy that both physics and the corresponding mathematics are discrete, not continuous, at the “primordial” (i.e., Planck) scale. This discrete primordial substratum consists of elementary cells or modules, interacting with each other over a network of elementary interactions. The term “discrete” in this context does not necessarily imply a lattice or some other countable structure, but rather implies the absence of the usual continuum concepts [Requardt 06]. Restricting the analysis to countably infinite graphs is advantageous, since it facilitates modelling and technical analysis. The network studied in [Nowotny 88] was assumed to be dynamic and highly erratic, where even the distribution of links is dynamical. These networks could be represented using cellular autonoma models; however, such models typically are embedded in fixed and regular geometric arrays. In contrast, the approach of [Nowotny 88] ignored the embedding space and considered an irregular array of nodes and links which dynamically arrange themselves according to some given evolution law. The hope is that, under certain favorable conditions, the system will undergo a series of phase transitions from a disordered chaotic initial state to some kind of macroscopically ordered extended pattern, which can be associated with classical spacetime. From a discrete model, the continuum concepts of ordinary spacetime physics arises via a kind of geometric renormalization group process on the much coarser scale corresponding to the comparatively small energies of present high-energy physics. Spacetime possibly emerges via a dynamical process, perhaps resembling a phase transition, from a more chaotic and violent initial phase. The continuum limit is a fixed point of this process, and this idea has some “vague similarities” to the renormalization group process (Chap. 21) of statistical mechanics [Requardt 06]. Computing a dimension for this initial phase, which is discrete but perhaps with complicated interactions, appears to be extremely useful. A “collective geometric” property like dimension suggests that, after some coarse graining and/or scaling, the network displays global smoothness properties which may indicate the transition into a continuum-like macro state [Nowotny 07]. Nowotny and Requardt observed that their work is related to other research in quantum gravity, e.g., to “prophetic” work by Penrose who introduced spin networks, which can be viewed as a type of dynamic graph.

As additional motivation for their definitions of dimension, [Nowotny 07] noted that in the renormalization and coarse graining of the discrete primordial network, more and more nodes and arcs are absorbed into the infinitesimal neighborhoods of the emerging points of the continuum. Hence a local definition of dimension in the continuum is actually a large scale concept in the network, involving practically infinitely many nodes and their interconnections. They were motivated by wondering what intrinsic global property, independent of some dimension in which the network is embedded, is relevant for the occurrence of such phenomena as phase transitions and critical behavior. They wound up with the answer that the relevant property is the number of new nodes or degrees of freedom seen as the distance from a given node increases.

Assume that $${\mathbb {G}} = ({\mathbb {N}}, {\mathbb {A}})$$ is an unweighted and undirected network, where both $$\mathbb {N}$$ and $$\mathbb {A}$$ are countably infinite sets. Assume the node degree of each node is finite. For $$n \in {\mathbb {N}}$$ and for each nonnegative integer r, define
$$\displaystyle \begin{aligned} \begin{array}{rcl} {\mathbb{N}}(n, r) = \{ \; x \in {\mathbb{N}} \, \vert \, {\mathit{dist}} (n,x) \leq r \; \} \; , {} \end{array} \end{aligned} $$
(12.19)
so $${\mathbb {N}}(n, r)$$ is the set of nodes whose distance from n does not exceed r. Define
$$\displaystyle \begin{aligned} \begin{array}{rcl} M(n,r) &amp;\displaystyle \equiv &amp;\displaystyle \vert {\mathbb{N}}(n, r) \vert {} \end{array} \end{aligned} $$
(12.20)
$$\displaystyle \begin{aligned} \begin{array}{rcl} d_{{V}}^{\, i}(n) &amp;\displaystyle \equiv &amp;\displaystyle \liminf_{r \rightarrow \infty} \frac{\log M(n, r)}{ \log r} {} \end{array} \end{aligned} $$
(12.21)
$$\displaystyle \begin{aligned} \begin{array}{rcl} d_{{V}}^{\, s}(n) &amp;\displaystyle \equiv &amp;\displaystyle \limsup_{r \rightarrow \infty} \frac{\log M(n, r)}{ \log r} \, . {} \end{array} \end{aligned} $$
(12.22)
Definition 12.3 If for some $$n \in {\mathbb {N}}$$ we have $${d_{{V}}^{\, i}}(n) = {d_{{V}}^{\, s}}(n)$$ , we say that $$\mathbb {G}$$ has local volume dimension d V(n) at n, where $${d_{{V}}}(n) \equiv {d_{{V}}^{\, i}}(n) = {d_{{V}}^{\, s}}(n)$$ . If also d V(n) = d V for each n in $${\mathbb {N}}$$ , then we say that the volume dimension of $$\mathbb {G}$$ is d V. □

The dimension d V was called the “internal scaling dimension” in [Nowotny 88], but we prefer the term “volume dimension”. If d V exists then for $$n \in {\mathbb {N}}$$ we have $$M(n,r) \sim r^{{d_{{V}}}}$$ as r →∞. Note the similarity between the definition of d V(n) and definition (9.​3) of the pointwise mass dimension of a geometric object; the difference is that (12.21) and (12.22) use a limit as r →∞, while (9.​3) uses a limit as r → 0. The volume dimension d V(n) somewhat resembles the correlation dimension d C defined by (11.​8); the chief difference is that d C is defined in terms of the correlation sum (9.​11), which is an average fraction of mass, where the average is over all nodes in a finite network, while d V is defined in terms of an infimum and supremum over all nodes. The volume dimension d V also somewhat resembles the mass dimension d M defined by (12.2); the chief difference is that d M is defined in terms of the network diameter, while d V is defined in terms of the number of nodes within radius r of node n.

The second definition of a network dimension proposed in [Nowotny 88] is based on the boundary (i.e., surface) of $${\mathbb {N}}(n, r)$$ , rather than on the entire neighborhood $${\mathbb {N}}(n, r)$$ . For $$n \in {\mathbb {N}}$$ and for each nonnegative integer r, define
$$\displaystyle \begin{aligned} \begin{array}{rcl} \partial{\mathbb{N}}(n, r) \equiv \{ \; x \in {\mathbb{N}} \, \vert \, {\mathit{dist}} (n,x) = r \; \} \; , {} \end{array} \end{aligned} $$
(12.23)
so $$\partial {\mathbb {N}}(n, r)$$ is the set of nodes whose distance from n is exactly r. For each n we have
$$\displaystyle \begin{aligned} \partial{\mathbb{N}}(n, r) = {\mathbb{N}}(n, r) - {\mathbb{N}}(n, r-1) \end{aligned}$$
and $$\partial {\mathbb {N}}(n, 0) = \{n \}$$ . Define
$$\displaystyle \begin{aligned} \begin{array}{rcl} {d_{{U}}^{\, i}}(n) \equiv \liminf_{r \rightarrow \infty} \left( \frac{ \log \vert \partial{\mathbb{N}}(n, r) \vert }{ \log r} + 1 \right) {} \end{array} \end{aligned} $$
(12.24)
$$\displaystyle \begin{aligned} \begin{array}{rcl} {d_{{U}}^{\, s}}(n) \equiv \limsup_{r \rightarrow \infty} \left( \frac{ \log \vert \partial{\mathbb{N}}(n, r) \vert }{ \log r} + 1 \right) \, . {} \end{array} \end{aligned} $$
(12.25)
Definition 12.4 If $${d_{{U}}^{\, i}}(n) = {d_{{U}}^{\, s}}(n)$$ , we say that $$\mathbb {G}$$ has surface dimension d U(n) at n, where $${d_{{U}}}(n) \equiv {d_{{U}}^{\, i}}(n) = {d_{{U}}^{\, s}}(n)$$ . If for each n in $$\mathbb {N}$$ we have d U(n) = d U, then we say that the surface dimension of $$\mathbb {G}$$ is d U. □

This dimension was called the “connectivity dimension” in [Nowotny 88], since “it reflects to some extent the way the node states are interacting with each other over larger distances via the various bond sequences connecting them”, but we prefer the term “surface dimension”.4 If d U exists, then for $$n \in {\mathbb {N}}$$ we have $$\vert \partial {\mathbb {N}}(n, r) \vert \sim r^{{d_{{U}}}-1}$$ as r →∞. The volume dimension d V is “rather a mathematical concept and is related to well-known dimensional concepts in fractal geometry”, while the surface dimension d U “seems to be a more physical concept as it measures more precisely how the graph is connected and how nodes can influence each other”. The values of d V and d U are identical for “generic” networks, but are different on certain “exceptional” networks [Nowotny 88].

Example 12.1 Turning momentarily to Euclidean geometry in $${\mathbb {R}}^2$$ , for a circle with center x and radius r the quantity analogous to M(n, r) is area(x, r) = πr 2. We have $$\lim _{r \rightarrow \infty } \log \bigl ( {\textit {area}}(x, r)\bigr )/ \log r = 2$$ . The quantity analogous to $$ \partial {\mathbb {N}}(n, r)$$ is area(r) −area(r − 𝜖), where 𝜖 is a small positive number. Since area(r) −area(r − 𝜖) ≈ 2πr𝜖, we have $$\lim _{r \rightarrow \infty } \log \big ({\mathrm{area}}(r)-{\textit {area}}(r-\epsilon )\big ) / \log r = 1$$ , so this limit and $$\lim _{r \rightarrow \infty } \log \bigl ( {\textit {area}}(x, r)\bigr )/ \log r$$ differ by 1, as reflected by the constant 1 added in (12.24). □

Example 12.2 Let $$\mathbb {G}$$ be the infinite graph whose nodes lie on a straight line at locations ⋯ , − 3, − 2, − 1, 0, 1, 2, 3, ⋯ . Then M(n, r) = 2r + 1 for each n and r, so $${d_{{V}}} = \lim _{r \rightarrow \infty } \log (2r+1) / \log r = 1$$ . As for the surface dimension, we have $$\vert \partial {\mathbb {N}}(n, r) \vert = 2$$ for each n and r, so $${d_{{U}}} = \lim _{r \rightarrow \infty } [({\log 2}/{\log r}) + 1] = 1$$ . □

Example 12.3 Let $$\mathbb {G}$$ be the infinite 2-dimensional rectilinear lattice whose nodes have integer coordinates, and where node (i, j) is adjacent to (i − 1, j), (i + 1, j), (i, j − 1), and (i, j + 1). Using the L 1 (i.e., Manhattan) metric, the distance from the origin to node n = (n 1, n 2) is |n 1| + |n 2|. For integer r ≥ 1, the number $$\vert \partial {\mathbb {N}}(n, r) \vert $$ of nodes at a distance r from a given node n is 4r [Shanker 07b], so by (12.20 ) we have
$$\displaystyle \begin{aligned} M(n,r) = \vert {\mathbb{N}}(n, r) \vert = 1+ 4\sum_{i=1}^r i = 1 + 4r(r+1)/2 = 2r^2 +2r+1 \, . \end{aligned}$$
Hence
$$\displaystyle \begin{aligned} \begin{array}{rcl} {d_{{U}}} &amp;\displaystyle =&amp;\displaystyle \lim_{r \rightarrow \infty} [({\log 4r}/{\log r}) +1] = 2 \\ {d_{{V}}} &amp;\displaystyle =&amp;\displaystyle \lim_{r \rightarrow \infty} \log \bigl(2r^2 + 2r + 1 \bigr) / \log r = 2 \, . \;\;\; \end{array} \end{aligned} $$
□

Exercise 12.2 Let $${\mathbb {G}}$$ be an infinite rooted tree such that each node spawns k child nodes. Calculate d V(n) and d U(n). □

A construction and corresponding analysis in [Nowotny 88] generates an infinite network for which d V exists but d U does not exist. Thus the existence of the volume dimension d V, and its numerical value, do not provide much information about the behavior of $$\vert \partial {\mathbb {N}}(n, r) \vert $$ , although the inequality
../images/487758_1_En_12_Chapter/487758_1_En_12_Equj_HTML.png
is valid for all n. On the other hand, the following result proves that the existence of the surface dimension at n does imply the existence of the volume dimension at n, and the equality of these values.

Theorem 12.1 ( [Nowotny 88], Lemma 4.11) If d U(n) exists and if d U(n) > 1, then d V(n) exists and d V(n) = d U(n).

Proof Let d = d U(n), and let 𝜖 > 0 satisfy d − 1 > 𝜖. Since d U(n) exists, then there exists a value $$\widetilde {r}$$ such that for $$r \geq \widetilde {r}$$ we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} &amp;\displaystyle &amp;\displaystyle \left\vert \frac{\log \vert \partial {\mathbb{N}}(n,r) \vert }{\log r} - d +1 \right\vert &lt; \epsilon \\ &amp;\displaystyle &amp;\displaystyle \quad \Rightarrow -\epsilon &lt; \frac{\log \vert\partial {\mathbb{N}}(n, r)\vert}{\log r} - d +1 &lt; \epsilon \\ &amp;\displaystyle &amp;\displaystyle \quad \Rightarrow (d-1-\epsilon)\log r &lt; \log \vert\partial {\mathbb{N}}(n, r) \vert &lt; (d-1 + \epsilon)\log r \\ &amp;\displaystyle &amp;\displaystyle \quad \Rightarrow r^{d-1-\epsilon} &lt; \vert \partial {\mathbb{N}}(n, r) \vert &lt; r^{d-1+\epsilon} \; . \end{array} \end{aligned} $$
Defining
$$\displaystyle \begin{aligned} S({r}) \equiv \sum_{i=0}^{{r}} \vert \partial {\mathbb{N}}(n, i) \vert \; , \end{aligned}$$
for $$r \geq \widetilde {r}$$ we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} &amp;\displaystyle &amp;\displaystyle M(n,r) = \sum_{i=0}^r \vert \partial {\mathbb{N}}(n, i) \vert = S(\widetilde{r}) + \sum_{i={\widetilde{r}}+1}^r \vert \partial {\mathbb{N}}(n, i) \vert \end{array} \end{aligned} $$
(12.26)
$$\displaystyle \begin{aligned} \begin{array}{rcl} &amp;\displaystyle &amp;\displaystyle \Rightarrow S(\widetilde{r}) + \sum_{i=\widetilde{r}+1}^r i^{d-1-\epsilon} \leq M(n,r) \leq S(\widetilde{r}) + \sum_{i=\widetilde{r}+1}^r i^{d-1+\epsilon} \; . \end{array} \end{aligned} $$
(12.27)
Now we provide a lower bound for the sum on the left-hand side and an upper bound for the sum on the right-hand side by replacing them with integrals.
$$\displaystyle \begin{aligned} \begin{array}{rcl} \sum_{i=\widetilde{r}+1}^r i^{d-1-\epsilon} &amp;\displaystyle \geq&amp;\displaystyle \int_{\widetilde{r}}^r x^{d-1-\epsilon} \mathrm{d} x = \left . \frac{x^{d-\epsilon}}{d-\epsilon} \right\vert {}_{\widetilde{r}}^r \\ \sum_{i=\widetilde{r}+1}^r i^{d-1+\epsilon} &amp;\displaystyle \leq&amp;\displaystyle \int_{\widetilde{r}+1}^{r+1} x^{d-1+\epsilon} \mathrm{d} x = \left . \frac{x^{d+\epsilon}}{d+\epsilon} \right\vert {}_{\widetilde{r}+1}^{r+1} \, . \end{array} \end{aligned} $$
We now have
$$\displaystyle \begin{aligned} \begin{array}{rcl} \log \left( S(\widetilde{r}) {+} \frac{r^{d-\epsilon}- {\widetilde{r}}^{d-\epsilon}}{d-\epsilon} \right) \leq \log M(n, r) \leq \log \left( S(\widetilde{r}) {+} \frac { (r+1)^{d+\epsilon}{-} (\widetilde{r}+1)^{d+\epsilon} } {d+\epsilon} \right) \end{array} \end{aligned} $$
which implies
$$\displaystyle \begin{aligned} \begin{array}{rcl} &amp;\displaystyle &amp;\displaystyle \log(r^{d-\epsilon}) + \log \left( \frac{S(\widetilde{r})}{r^{d-\epsilon}} + \frac{1}{d-\epsilon} \left( 1- \frac{ {\widetilde{r}}^{d-\epsilon} }{ r^{d-\epsilon} } \right) \right) \leq \log M(n,r) \\ &amp;\displaystyle &amp;\displaystyle \quad \leq \log \bigl((r+1)^{d+\epsilon} \bigr) + \log \left( \frac{S(\widetilde{r})}{(r+1)^{d+\epsilon}} + \frac{1}{d+\epsilon} \left( 1- \frac{ ({\widetilde{r}}+1)^{d+\epsilon} }{ (r+1)^{d+\epsilon} } \right) \right) \, . \end{array} \end{aligned} $$
Since the arguments of the second logarithm on each side are uniformly bounded for each r, and since
$$\displaystyle \begin{aligned} \lim_{r \rightarrow \infty} \log(r+1)/\log r = 1 \, , \end{aligned}$$
we can find a value $$\hat {r}$$ , where $$\hat {r} &gt; \widetilde {r}$$ , such that whenever $$r \geq \hat {r}$$ we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} d-\epsilon + \frac { \log \left( \frac{S(\widetilde{r})}{r^{d-\epsilon}} - \frac{1}{d-\epsilon} \left( 1 - \frac {\widetilde{r}^{d-\epsilon}} {r^{d-\epsilon}} \right) \right) } { \log r } \geq d-2\epsilon \end{array} \end{aligned} $$
and
$$\displaystyle \begin{aligned} \begin{array}{rcl} (d+\epsilon)\frac{ \log(r+1)}{\log r} + \frac { \log \left( \frac{S(\widetilde{r})}{(r+1)^{d+\epsilon}} - \frac{1}{d+\epsilon} \left( 1 - \frac {(\widetilde{r}+1)^{d+\epsilon}} {(r+1)^{d+\epsilon}} \right) \right) } { \log r } \leq d+2\epsilon \; . \end{array} \end{aligned} $$
Therefore for $$r \geq \hat {r}$$ we have
$$\displaystyle \begin{aligned} \left\vert \frac{ \log M(n,r) }{ \log r} - d \right\vert \leq 2\epsilon \end{aligned}$$
which establishes the result. □

The following lemma shows that, under a suitable condition, the convergence of a subsequence of $$\log M(n,r)/\log r$$ implies convergence of the entire sequence.

Lemma 12.1 ( [Nowotny 88], Lemma 4.9) Suppose that for some node $$n \in {\mathbb {N}}$$ and for some number c ∈ (0, 1) the subsequence {r m} satisfies the condition r m∕r m+1 ≥ c for all sufficiently large m. Then
$$\displaystyle \begin{aligned} \begin{array}{rcl} \liminf_{m \rightarrow \infty} \frac{\log M(n, r_{{m}}) }{ \log {r_{{m}}}} = \liminf_{r \rightarrow \infty} \frac{\log M(n, r) }{ \log r} = d_{{V}}^{\, i}(n) \, , \end{array} \end{aligned} $$
(12.28)
and similarly for $$d_{{V}}^{\, s}(x)$$ .
Proof Let $$n \in {\mathbb {N}}$$ and c ∈ (0, 1) satisfy the conditions of the lemma. Let r be an arbitrary positive integer, and let m be such that r m ≤ r ≤ r m+1. Then $${\mathbb {N}}(n, r_{{m}}) \subseteq {\mathbb {N}}(n, r) \subseteq {\mathbb {N}}(n, r_{{m+1}})$$ . Since r m∕r m+1 ≥ c then (r∕r m) ≤ (r m+1∕r m) ≤ 1∕c and (r∕r m+1) ≥ (r m∕r m+1) ≥ c. Hence
$$\displaystyle \begin{aligned} \begin{array}{rcl} &amp;\displaystyle &amp;\displaystyle \frac{\log M(n, r_{{m}}) }{\log r} \leq \frac{\log M(n,r) }{\log r} \leq \frac{\log M(n, r_{{m+1}}) }{\log r} \\ &amp;\displaystyle &amp;\displaystyle \quad \Rightarrow \frac{\log M(n, r_{{m}}) }{\log r_{{m}} + \log (r/r_{{m}})} \leq \frac{\log M(n, r) }{\log r} \leq \frac{\log M(n, r_{{m+1}}) }{\log {r_{{m+1}}} + \log (r/{r_{{m+1}}})} \\ &amp;\displaystyle &amp;\displaystyle \quad \Rightarrow \frac{\log M(n, r_{{m}}) }{\log r_{{m}} + \log(1/c)} \leq \frac{\log M(n, r) }{\log r} \leq \frac{\log M(n, r_{{m+1}}) }{\log {r_{{m+1}}} + \log c} \\ &amp;\displaystyle &amp;\displaystyle \quad \Rightarrow \liminf_{r \rightarrow \infty} \, \frac{ \log M(n, r) }{ \log r} = \liminf_{i \rightarrow \infty} \, \frac{ \log M(n, r_{{m}}) }{ \log {r_{{m}}}} \; . \end{array} \end{aligned} $$
The same reasoning proves that
$$\displaystyle \begin{aligned} \limsup_{r \rightarrow \infty} \, \frac{ \log M(n, r) }{ \log r} = \limsup_{i \rightarrow \infty} \, \frac{ M(n, r_{{m}}) }{ \log {r_{{m}}}} \; . \; \; \end{aligned}$$
□

The following theorem shows that the volume dimension is “pretty much stable under any local changes” [Nowotny 88].

Theorem 12.2 ( [Nowotny 88], Lemma 4.10) Let n be a node in $$\mathbb {N}$$ and let h be a positive number. Then the insertion of arcs between arbitrarily many pairs of nodes (x, y), subject to the constraint that dist(x, y) ≤ h, does not change $$d_{{V}}^{\, i}(n)$$ and $$d_{{V}}^{\, s}(n)$$ .

Proof Let $${\mathbb {G}}$$ be the original network, with distances dist(x, y) between nodes x and y. Let $${\mathbb {G}}^+$$ be the modified network with arcs between arbitrarily many node pairs (x, y) such that dist(x, y) ≤ h. Let dist +(x, y) be the distance in $${\mathbb {G}}^+$$ between nodes x and y. Define $${\mathbb {N}}^+(n, r ) = \{ \; x \in {\mathbb {N}} \, \vert \, dist^+(n,x) \leq r \; \}$$ . If for some $$x \in {\mathbb {N}}$$ we have dist(n, x) = ⌊r∕h⌋, then the extra arcs in $${\mathbb {G}}^+$$ imply dist +(n, x) ≤⌊r∕h⌋. Thus
$$\displaystyle \begin{aligned} \begin{array}{rcl} {\mathbb{N}}(n,\lfloor r/h \rfloor) \subseteq {\mathbb{N}}^+(n,\lfloor r/h \rfloor) \; . {} \end{array} \end{aligned} $$
(12.29)
On the other hand, suppose that for some $$x \in {\mathbb {N}}$$ we have dist +(n, x) = ⌊r∕h⌋. Then dist(n, x) ≤ h⌊r∕h⌋, since the extra arcs in $${\mathbb {G}}^+$$ mean that a single arc in $${\mathbb {G}}^+$$ on the shortest path between nodes n and x corresponds to at most h arcs in $${\mathbb {G}}$$ on the shortest path between n and x. Since h⌊r∕h⌋≤ r we obtain
$$\displaystyle \begin{aligned} \begin{array}{rcl} {\mathbb{N}}^+(n,\lfloor r/h \rfloor) \subseteq {\mathbb{N}}(n, h \lfloor r/h \rfloor) \subseteq {\mathbb{N}}(n, r) \; . {} \end{array} \end{aligned} $$
(12.30)
From (12.29) and (12.30) we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} {\mathbb{N}}(n,\lfloor r/h \rfloor) \subseteq {\mathbb{N}}^+(n,\lfloor r/h \rfloor) \subseteq {\mathbb{N}}(n, r) \; . \end{array} \end{aligned} $$
Defining $$M^+(n, r) \equiv \vert {\mathbb {N}}^+(n,r) \vert $$ , it follows that
$$\displaystyle \begin{aligned} \begin{array}{rcl} &amp;\displaystyle &amp;\displaystyle \frac{\log M(n, {\lfloor r/h \rfloor}) } {\log \lfloor r/h \rfloor} \leq \frac{\log M^+(n, \lfloor r/h \rfloor) }{\log \lfloor r/h \rfloor} \leq \frac{\log M(n, r) }{\log \lfloor r/h \rfloor} \; . \end{array} \end{aligned} $$
For all sufficiently large r we have ⌊r∕h⌋ > r∕2h and thus
$$\displaystyle \begin{aligned} \begin{array}{rcl} &amp;\displaystyle &amp;\displaystyle \frac{\log M(n, {\lfloor r/h \rfloor}) } {\log \lfloor r/h \rfloor} \leq \frac{\log M^+(n, \lfloor r/h \rfloor) }{\log \lfloor r/h \rfloor} \leq \frac{\log M(n, r)}{\log r - \log (2h)} \\ &amp;\displaystyle &amp;\displaystyle \quad \Rightarrow \liminf_{r \rightarrow \infty} \frac{\log M^+(n, r)}{\log r} = \liminf_{r \rightarrow \infty} \frac{\log M(n, r) }{\log r} \; , \end{array} \end{aligned} $$
where the final equality follows from Lemma 12.1. The proof for $$\limsup $$ is the same. □

Exercise 12.3 How can we reconcile Theorem 12.2 with the Watts–Strogatz results (Sect. 2.​2) on the impact of adding some shortcut arcs to a network? □

12.4 Conical Graphs with Prescribed Dimension

Let d be an arbitrary number such that 1 < d ≤ 2. A method to construct a conical graph such that d V(n ⋆) = d, where n ⋆ is a specially chosen node, was provided in [Nowotny 88]. Graphs with higher volume dimension can be constructed using a nearly identical method. The construction is illustrated in Fig. 12.7 for the choice d = 5∕3. There are two types of nodes in this figure, small black circles and larger blue squares with a black border. Both types of nodes are nodes in $$\mathbb {G}$$ , but we distinguish these two types to facilitate calculating d V(n ⋆). From the figure we see that boxes connect level m to level m + 1, where the lower left and lower right corner of each box is a blue square, and the upper left and upper right corner of each box is a black circle. (These boxes have nothing to do with the boxes used to compute the box counting dimension.) For m ≥ 2, there are ⌊(2m − 1)d−1⌋ boxes connecting level m to level m + 1, so the number of blue squares at level m is 1 + ⌊(2m − 1)d−1⌋. Each blue square at level m has distance 2m − 1 to node n ⋆. Thus, for m ≥ 2, the set of blue squares at level m is the set $$\partial {\mathbb {N}}(n^{\star }, 2m-1)$$ , and
$$\displaystyle \begin{aligned} \vert \partial {\mathbb{N}}(n^{\star}, 2m-1) \vert = 1 + \lfloor ( 2m-1 )^{d-1}\rfloor \, . \end{aligned}$$
To compute d V(n ⋆), we first determine d U(n ⋆), the surface dimension at n ⋆. Since
$$\displaystyle \begin{aligned} ( 2m-1 )^{d-1} \leq 1 + \lfloor ( 2m-1 )^{d-1}\rfloor \leq 1 + ( 2m-1 )^{d-1} \end{aligned}$$
then
$$\displaystyle \begin{aligned}{{ \lim_{m \rightarrow \infty} \frac {\log \, (2m-1)^{d-1}}{\log \, (2m{-}1)} \leq \lim_{m \rightarrow \infty} \frac {\log \, \vert \partial {\mathbb{N}}(n^{\star}, 2m{-}1) \vert}{\log \, (2m{-}1) } \leq \lim_{m \rightarrow \infty} \frac {\log \,\left( 1 {+} (2m{-}1)^{d{-}1} \right)}{\log \, (2m{-}1)} \, .}} \end{aligned}$$
Since the first and third limits are both equal to d − 1, then so is the second limit. That is,
$$\displaystyle \begin{aligned} \begin{array}{rcl} \lim_{m \rightarrow \infty} \frac {\log \, \vert \partial {\mathbb{N}}(n^{\star}, 2m-1) \vert}{\log \, (2m-1) } = d-1 \; . {} \end{array} \end{aligned} $$
(12.31)
At this point we have shown that the limit exists along the subsequence of distances $$\{ r_{{m}} \}_{m=1}^{\infty }$$ , where r m ≡ 2m − 1. Since convergence of a subsequence does not imply convergence of the entire sequence, it must be shown that the limit exists for all sufficiently large distances, not just along a subsequence of distances. We require a lemma.
../images/487758_1_En_12_Chapter/487758_1_En_12_Fig7_HTML.png
Figure 12.7

Construction of a conical graph for which d V(n ⋆) = 5∕3

Lemma 12.2 ( [Nowotny 88], Lemma 4.8) If for some $$x,y \in {\mathbb {N}}$$ we have dist(x, y) < ∞, then $$d_{{V}}^{\, i}(x) = d_{{V}}^{\, i}(y)$$ and $$d_{{V}}^{\, s}(x) = d_{{V}}^{\, s}(y)$$ .

Proof Let h = dist(x, y). If for some node z we have dist(y, z) ≤ r − h, then dist(x, z) ≤dist(x, y) + dist(y, z) ≤ h + (r − h) = r, so $${\mathbb {N}}(y, r-h) \subseteq {\mathbb {N}}(x, r)$$ . Similarly, if for some node z we have dist(x, z) ≤ r, then dist(y, z) ≤dist(y, x) + dist(x, z) ≤ h + r, so $${\mathbb {N}}(x, r) \subseteq {\mathbb {N}}(y, r+h)$$ . Hence
$$\displaystyle \begin{aligned} \begin{array}{rcl} &amp;\displaystyle &amp;\displaystyle {\mathbb{N}}(y, r-h) \subseteq {\mathbb{N}}(x, r) \subseteq {\mathbb{N}}(y, r+h) \\ &amp;\displaystyle &amp;\displaystyle \quad \Rightarrow \frac{\log M(y, r-h)}{\log r} \leq \frac{\log M(x, r) }{\log r} \leq \frac{\log M(y, r+h)}{\log r} \\ &amp;\displaystyle &amp;\displaystyle \quad \Rightarrow \frac{\log M(y, r-h)} {\log (r-h) + \log\left(\frac{r}{r-h}\right)} \leq \frac{\log M(x, r) }{\log r} \leq \frac{\log M(y, r+h)} {\log (r+h) - \log\left(\frac{r+h}{r}\right)} \\ &amp;\displaystyle &amp;\displaystyle \quad \Rightarrow \liminf_{r \rightarrow \infty} \frac{\log M(y, r) }{\log r} \leq \liminf_{r \rightarrow \infty} \frac{\log M(x, r) }{\log r} \leq \liminf_{r \rightarrow \infty} \frac{\log M(y, r) }{\log r} \; , \end{array} \end{aligned} $$
so $$d_{{V}}^{\, i}(x) = d_{{V}}^{\, i}(y)$$ . Similarly, we obtain $$d_{{V}}^{\, s}(x) = d_{{V}}^{\, s}(y)$$ . □

Theorem 12.3 ( [Nowotny 88], Section 5.1) For the above conical graph construction, we have d V = d.

Proof For the subsequence r m = 2m − 1 the conditions of Lemma 12.1 are satisfied with c = 1∕2, since r m∕r m+1 = (2m − 1)∕(2m + 1) ≥ 1∕2 for m ≥ 2. By (12.31) and Lemma 12.1 we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} \lim_{r \rightarrow \infty} \frac {\log \, \vert \partial {\mathbb{N}}(n^{\star}, r) \vert}{\log r } = \lim_{m \rightarrow \infty} \frac {\log \, \vert \partial {\mathbb{N}}(n^{\star}, 2m-1) \vert}{\log \, (2m-1) } = d-1 \; , {} \end{array} \end{aligned} $$
(12.32)
so by Definition 12.4 we have d U(n ⋆) = d − 1. Since d > 1 it follows from Theorem 12.1 that d V(n ⋆) = d. Since the distance between each pair of nodes in the graph is finite, it follows from Lemma 12.2 that for each node n we have d V(n) = d. Thus d V = d. □

Exercise 12.4 Draw the conical graph for d = 1.01 and for d = 1.99. □

Connections between the above results and some results by Gromov on geometric group theory were explored in [Requardt 06]. The application of these techniques provides preliminary answers to such questions as characterizing the set of graphs having the same dimension.

12.5 Dimension of a Percolating Network

A percolating network (also called a percolation network) is a fundamental model for describing geometrical features of random systems. There are two main types of percolating networks: site and bond. Consider an infinite lattice in $${\mathbb {R}}^E$$ . The lattice need not be rectilinear; other possible geometries are triangle, honeycomb, and diamond. In a site-percolating network (SPN), each lattice point (called a site) is occupied at random with probability p. A site is not a node; a site is a position on a lattice, which may be occupied (populated) or empty. Two sites are connected by a bond (i.e., an arc) if they are adjacent along a principal direction (e.g., for a rectilinear lattice in $${\mathbb {R}}^3$$ , if they are adjacent along the x, y, or z axis.). In a bond-percolating network (BPN), all lattice sites are populated, and bonds between adjacent sites are occupied randomly with probability p. The occupation probability p for sites in a SPN, or for bonds in a BPN, has the same role as the temperature in thermal critical phenomena [Nakayama 94].

As p increases from 0, connected clusters of sites form. As p continues to increase, a critical p c value is reached. For p < p c, only finite clusters (i.e., clusters of finite size) exist. For p > p c, an infinite cluster (i.e., a cluster of infinite size) is present, as well as finite clusters. The critical value p c for the BPN is always smaller than the critical value for the SPN, due to the difference in the short range geometrical structure of the two types of lattices: a bond has more nearest neighbors than a site. For example, for a 2-dimensional rectilinear lattice, a given site has 4 adjacent sites, while a given bond is attached to 6 other bonds (3 at each end).

A 1976 paper of de Gennes was credited by Nakayama et al. [Nakayama 94] with sparking interest in the dynamics of a percolating network. That paper posed the following question: an ant parachutes down onto a site on the percolating network and executes a random walk. What is the mean square distance the ant traverses as a function of time?5 Stanley, in 1977, was the first to recognize that percolating networks exhibit self-similarity and could be characterized by a fractal dimension. Percolating networks have been used to describe a large variety of physical and chemical phenomena, such as gelation processes and conduction in semiconductors. Percolation theory also forms the basis for studies of the flow of liquids or gases through porous media, and has been applied to the stability of computer networks under random failures and under denial of service attacks, to the spread of viruses in computer networks and epidemics in populations, and to the immunization of these networks [Cohen 04].

Let m denote the size of a cluster, i.e., the number of occupied sites in the cluster. (Here “m” suggests “mass”.) Although m depends on p, for brevity we write m rather than m(p). Let s m be the average Euclidean distance between two sites in a cluster of size m. At p = p c we have, for some d pn (where “pn” denotes “percolating network”),
$$\displaystyle \begin{aligned} \begin{array}{rcl} m \propto s_{{m}}^{d_{{pn}}} \, . \end{array} \end{aligned} $$
The exponent d pn is the “fractal dimension” or “Hausdorff dimension” of the percolating network [Nakayama 94]. For a percolating network in $${\mathbb {R}}^E$$ , for E = 2 we have d pn = 91∕48, for E = 4 we have d pn ≈ 3.2, for E = 5 we have d pn ≈ 3.7, and for E ≥ 6 we have d pn = 4. For E = 3, the computed values of d pn, as reported in [Nakayama 94], span the range 0.875–2.48.
The chemical distance between two sites u and v in a percolating network is the minimal number of hops between u and v, subject to the constraint that each hop must be an existing bond between connected sites. The chemical dimension of a percolating network is d ch if the mass m within chemical distance s c obeys the scaling
$$\displaystyle \begin{aligned} \begin{array}{rcl} m \propto s_{{c}}^{d_{{ch}}} \, . \end{array} \end{aligned} $$
For 2-dimensional percolating networks, d ch ≈ 1.768; for 3-dimensional percolating networks, d ch ≈ 1.885 [Nakayama 94]. Finally, let chem(L) denote the chemical distance between two sites that are separated by the Euclidean distance L. Then
$$\displaystyle \begin{aligned} \begin{array}{rcl} \textit{chem}(L) \propto L^{d_{{pn}}/ d_{{ch}}} \, , \end{array} \end{aligned} $$
so d pn∕d ch is the fractal dimension that relates the chemical distance between two sites in a lattice to the Euclidean distance between two sites [Nakayama 94]. The fractal dimensions of percolating networks were also studied in [Cohen 04, Cohen 08].