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

17. Multifractal Networks

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

My power flurries through the air into the ground

My soul is spiraling in frozen fractals all around

And one thought crystallizes like an icy blast

I’m never going back

The past is in the past

Lyrics from the song “Let It Go”, from the 2013 movie “Frozen”. Music and lyrics by Kristen Anderson-Lopez and Robert Lopez.

In Chap. 16 we presented the theory of generalized dimensions for a geometric object Ω, and discussed several methods for computing the generalized dimensions of Ω. In this chapter we draw upon the content of Chap. 16 to show how generalized dimensions can be defined and computed for a complex network $$\mathbb {G}$$ .

17.1 Lexico Minimal Coverings

In Chap. 15, we showed that the definition proposed in [Wei 14a] of the information dimension d I of a network $$\mathbb {G}$$ is ambiguous, since d I is computed from a minimal s-covering of $$\mathbb {G}$$ , for a range of s, and there are in general multiple minimal s-coverings of $$\mathbb {G}$$ , yielding different values of d I. Using the maximal entropy principle of [Jaynes 57], we resolved the ambiguity for each s by maximizing the entropy over the set of minimal s-coverings. We face the same ambiguity when using box counting to compute D q, since the different minimal s-coverings of $$\mathbb {G}$$ can yield different values of D q. In this section we illustrate this indeterminacy and show how it can be resolved by computing lexico minimal summary vectors, and this computation requires only negligible additional work beyond what is required to compute a minimal covering.

To begin, recall from Chap. 16 that, for $$q \in {\mathbb {R}}$$ , the partition function obtained from an s-covering $${\mathcal {B}}(s)$$ of a geometric object Ω is
$$\displaystyle \begin{aligned} \begin{array}{rcl} Z_q\big( {\mathcal{B}}(s) \big) = \sum_{B_{{j}} \in {\mathcal{B}}(s)} [p_{{j}}(s)]^{q} {} \end{array} \end{aligned} $$
(17.1)
and for q ≠ 1 the generalized dimension D q of Ω is given by
$$\displaystyle \begin{aligned} D_q = \frac{1}{q-1} \lim_{s \rightarrow 0} \frac{\log Z_q \big({\mathcal{B}}(s) \big)}{ {\log s} }\, . \end{aligned}$$
Considering now network $$\mathbb {G}$$ , let $${\mathcal {B}}(s)$$ be an s-covering of $$\mathbb {G}$$ . For $$B_{{j}} \in {\mathcal {B}}(s)$$ , define p j(s) ≡ N j(s)∕N, where N j(s) is the number of nodes in B j. The partition function of $$\mathbb {G}$$ corresponding to $${\mathcal {B}}(s)$$ is also $$Z_q\big ({\mathcal {B}}(s)\big )$$ , as given by (17.1). However, since the box size s is always a positive integer, for q ≠ 1 we cannot define the generalized dimension D q of $$\mathbb {G}$$ to be
$$\displaystyle \begin{aligned} \frac{1}{q-1} \lim_{s \rightarrow 0} \frac{ \log Z_q \big({\mathcal{B}}(s) \big) }{ {\log s} } \, . \end{aligned}$$
Instead, we want D q of $$\mathbb {G}$$ to satisfy, over some range of s,
$$\displaystyle \begin{aligned} \begin{array}{rcl} D_q \approx \frac{1}{q-1} \frac{ \log Z_q \big({\mathcal{B}}(s) \big) } {\log s} \; . {} \end{array} \end{aligned} $$
(17.2)
This was the approach used by [Wang 11], who used radius-based boxes to cover $$\mathbb {G}$$ , and who for q ≠ 1 defined D q to be the generalized dimension of $$\mathbb {G}$$ if over some range of r and for some constant c,
$$\displaystyle \begin{aligned} \begin{array}{rcl} \log Z_q \big({\mathcal{B}}(r) \big) \approx (q-1){D_q} \log (r/\varDelta) + c \, , {} \end{array} \end{aligned} $$
(17.3)
where $$Z_q \big ({\mathcal {B}}(r) \big )$$ is the average partition function value obtained from a covering of $$\mathbb {G}$$ by radius-based boxes of radius r. (A randomized box counting heuristic was used in [Wang 11], and $$Z_q \big ( {\mathcal {B}}(r) \big )$$ was taken to be the average partition function value, averaged over some number of executions of the randomized heuristic.) However, definition (17.3) is ambiguous, since different minimal coverings can yield different values of $$Z_q \big ({\mathcal {B}}(r) \big )$$ and hence different values of D q.
Example 17.1 Consider the chair network of Fig. 17.1,
../images/487758_1_En_17_Chapter/487758_1_En_17_Fig1_HTML.png
Figure 17.1

Two minimal 3-coverings and a minimal 2-covering for the chair network

which shows two minimal 3-coverings and a minimal 2-covering. Choosing q = 2, for the covering $$\widetilde {{\mathcal {B}}}(3)$$ from (17.1) we have $$Z_2 \big ( \widetilde {{\mathcal {B}}}(3) \big ) = (\frac {3}{5})^2 + (\frac {2}{5})^2 = \frac {13}{25}$$ , while for $$\widehat {{\mathcal {B}}}(3)$$ we have $$Z_2 \big ( \widehat {{\mathcal {B}}}(3) \big ) = (\frac {4}{5})^2 + (\frac {1}{5})^2 = \frac {17}{25}$$ . For $${{\mathcal {B}}}(2)$$ we have $$Z_2 \big ( {{\mathcal {B}}}(2) \big ) = 2(\frac {2}{5})^2 + (\frac {1}{5})^2 = \frac {9}{25}$$ . If we use $$\widetilde {{\mathcal {B}}}(3)$$ , then from (17.3) and the range s ∈ [2, 3] we obtain $$D_2 = \big ( \log \frac {13}{25} - \log \frac {9}{25} \big )/ (\log 3 - \log 2) = 0.907$$ . If instead we use $$\widehat {{\mathcal {B}}}(3)$$ and the same range of s we obtain $$D_2 = \big ( \log \frac {17}{25} - \log \frac {9}{25} \big )/ (\log 3 - \log 2) = 1.569$$ . Thus the method of [Wang 11] can yield different values of D 2 depending on the minimal covering selected. □

To devise a computationally efficient method for selecting a unique minimal covering, first consider the maximal entropy criterion presented in Chap. 15. A maximal entropy minimal s-covering is a minimal s-covering for which the entropy $$-\sum _j p_{{j}}(s) \log p_{{j}}(s)$$ is largest. It is well-known that entropy is maximized when all the probabilities are equal. Theorem 17.1 below, concerning a continuous optimization problem, proves that the partition function is minimized when the probabilities are equal. For integer J ≥ 2, let $${\mathcal {P}}(q)$$ denote the continuous optimization problem
$$\displaystyle \begin{aligned} \mbox{minimize} \; \sum_{j=1}^J p_{{j}}^{\, q} \; \mbox{subject to} \; \sum_{j=1}^J p_{{j}} = 1 \mbox{ and } p_{{j}} \geq 0 \mbox{ for each } j \; . \end{aligned}$$
Theorem 17.1 For q > 1, the solution of $${\mathcal {P}}(q)$$ is p j = 1∕J for each j, and the optimal objective function value is J 1−q.

Proof [ Rosenberg 17b] If p j = 1 for some j, then for each other j we have p j = 0 and the objective function value is 1. Next, suppose each p j > 0 in the solution of $${\mathcal {P}}(q)$$ . Let λ be the Lagrange multiplier associated with the constraint $$\sum _{j=1}^J p_{{j}} = 1$$ . The first order optimality condition for p j is $$q p_{{j}}^{q-1} - \lambda = 0$$ . Thus each p j has the same value, which is 1∕J. The corresponding objective function value is $$\sum _{j=1}^J (1/J)^q = J^{1-q}$$ . This value is less than the value 1 (obtained when exactly one p j = 1) when J 1−q < 1, which holds for q > 1. For q > 1 and p > 0, the function p q is a strictly convex function of p, so p j = 1∕J is the unique global (as opposed to only a local) solution of $${\mathcal {P}}(q)$$ . Finally, suppose that for some solution of $${\mathcal {P}}(q)$$ we have p j ∈ [0, 1) for each j, but the number of positive p j is J 0, where J 0 < J. The above arguments show that the optimal objective function value is $$J_0^{1-q}$$ . Since for q > 1 we have $$J_0^{1-q} &gt; J^{1-q}$$ , any solution of $${\mathcal {P}}(q)$$ must have p j > 0 for each j. □

Applying Theorem 17.1 to $$\mathbb {G}$$ , minimizing the partition function $$Z_q\big ({\mathcal {B}}(s)\big )$$ over all minimal s-coverings of $$\mathbb {G}$$ yields a minimal s-covering for which all the probabilities p j(s) are approximately equal. Since p j(s) = N j(s)∕N, having the box probabilities almost equal means that all boxes in the minimal s-covering have approximately the same number of nodes. The following definition of an (s, q) minimal covering, for use in computing D q, is analogous to the definition in [Rosenberg 17a] of a maximal entropy minimal covering, for use in computing d I.

Definition 17.1 [ Rosenberg 17b] For $$q \in {\mathbb {R}}$$ , the covering $${\mathcal {B}}(s)$$ of $$\mathbb {G}$$ is an (s, q) minimal covering if (i) $${\mathcal {B}}(s)$$ is a minimal s-covering and (ii) for any other minimal s-covering $$\widetilde { {\mathcal {B}}}(s) $$ we have $$Z_q \big ({\mathcal {B}}(s) \big ) \leq Z_q \big ( \widetilde { {\mathcal {B}}}(s) \big )$$ . □

Procedure 17.1 below shows how an (s, q) minimal covering can be computed, for a given s and q, by a simple modification of whatever box-counting method is used to compute a minimal s-covering.

Procedure 17.1 Let $${\mathcal {B}}_{\min }(s)$$ be the best s-covering obtained over all executions of whatever box-counting method is utilized. Suppose we have executed box counting some number of times, and stored $${\mathcal {B}}_{\min }(s)$$ and $$Z_q^{\star }(s) \equiv Z_q \big ( {\mathcal {B}}_{\min }(s) \big )$$ , so $$Z_q^{\star }(s)$$ is the current best estimate of the minimal value of the partition function. Now suppose we execute box counting again, and generate a new s-covering $${\mathcal {B}}(s)$$ using B(s) boxes. Let $$Z_q \equiv Z_q \big ( {\mathcal {B}}(s) \big ) $$ be the partition function value associated with $${\mathcal {B}}(s)$$ . If $${B}(s) &lt; B_{\min }(s)$$ holds, or if $${B}(s) = B_{\min }(s)$$ and $$Z_q &lt; Z_q^{\star }(s)$$ hold, set $${\mathcal {B}}_{\min }(s) = {{\mathcal {B}}}(s)$$ and $$Z_q^{\star }(s) = Z_q$$ . □

Let s be fixed. Procedure 17.1 shows that we can easily modify any box-counting method to compute the (s, q) minimal covering for a given q. However, this approach to eliminating ambiguity in the computation of D q is not attractive, since it requires computing an (s, q) minimal covering for each value of q for which we wish to compute D q. Moreover, since there are only a finite number of minimal s-coverings, as q varies we will eventually rediscover some (s, q) minimal coverings, that is, for some q 1 and q 2 we will find that the (s, q 1) minimal covering is identical to the (s, q 2) minimal covering. An elegant alternative to computing an (s, q) minimal covering for each s and q, while still achieving our goal of unambiguously computing D q, is to use lexico minimal summary vectors.

For a given box size s, we summarize an s-covering $${\mathcal {B}}(s)$$ by the point $$x(s) \in {\mathbb {R}}^J$$ , where J ≡ B(s), where x j(s) = N j(s) for 1 ≤ j ≤ J, and where x 1(s) ≥ x 2(s) ≥⋯ ≥ x J(s). We say “summarize” since x(s) does not specify all the information in $${\mathcal {B}}(s)$$ ; in particular, $${\mathcal {B}}(s)$$ specifies exactly which nodes belong to each box, while x(s) specifies only the number of nodes in each box. We use the notation $$x(s) = \sum {\mathcal {B}}(s)$$ to mean that x(s) summarizes the s-covering $${\mathcal {B}}(s)$$ and that x 1(s) ≥ x 2(s) ≥⋯ ≥ x J(s). For example, if N = 37, s = 3, and B(3) = 5, then we might have $$x(s) = \sum {\mathcal {B}}(3)$$ for x(s) = (18, 7, 5, 5, 2). However, we cannot have $$x(s) = \sum {\mathcal {B}}(3)$$ for x(s) = (7, 18, 5, 5, 2) since the components of x(s) are not ordered correctly. If $$x(s) = \sum {\mathcal {B}}(s)$$ , then each x j(s) is positive, since x j(s) is the number of nodes in box B j. We call $$x(s) = \sum {\mathcal {B}}(s)$$ a summary vector of $${\mathcal {B}}(s)$$ . By “x(s) is a summary vector” we mean x(s) summarizes some $${\mathcal {B}}(s)$$ .

Let $$x \in {\mathbb {R}}^K$$ for some positive integer K. Let $$right(x) \in {\mathbb {R}}^{K-1}$$ be the point obtained by deleting the first component of x. For example, if x = (18, 7, 5, 5, 2), then right(x) = (7, 5, 5, 2). Similarly, we define right 2(x) ≡ right(right(x)), so right 2(7, 7, 5, 2) = (5, 2). Let $$u \in {\mathbb {R}}$$ and $$v \in {\mathbb {R}}$$ be numbers. We say that u ≽ v (in words, u is lexico greater than or equal to v) if ordinary inequality holds, that is, u ≽ v if u ≥ v. (We use lexico instead of the longer lexicographically.) Thus 6 ≽ 3 and 3 ≽ 3. Now let $$x \in {\mathbb {R}}^K$$ and $$y \in {\mathbb {R}}^K$$ . We define lexico inequality recursively. We say that y ≽ x if either (i) y 1 > x 1 or (ii) y 1 = x 1 and right(y) ≽ right(x). For example, for x = (9, 6, 5, 5, 2), y = (9, 6, 4, 6, 2), and z = (8, 7, 5, 5, 2), we have x ≽ y and x ≽ z and y ≽ z.

Definition 17.2 Let $$x(s) = \sum {\mathcal {B}}(s)$$ . Then x(s) is lexico minimal if (i) $${\mathcal {B}}(s)$$ is a minimal s-covering and (ii) if $$\widetilde { {\mathcal {B}}}(s) $$ is a minimal s-covering distinct from $${\mathcal {B}}(s)$$ and $$y(s) = \sum \widetilde { {\mathcal {B}}}(s)$$ , then y(s) ≽ x(s). □

Theorem 17.2 For each s there is a unique lexico minimal summary vector.

Proof [ Rosenberg 17b] Pick s. Since there are only a finite number of minimal s-coverings of $$\mathbb {G}$$ , and the corresponding summary vectors can be ordered using lexicographic ordering, then a lexico minimal summary vector exists. To show that there is unique lexico minimal summary vector, suppose that $$x(s) = \sum {\mathcal {B}}(s)$$ and $$y(s) = \sum \widetilde { {\mathcal {B}}}(s)$$ are both lexico minimal. Define J ≡ B(s), so J is the number of boxes in both $${\mathcal {B}}(s)$$ and in $$\widetilde { {\mathcal {B}}}(s)$$ . If J = 1, then a single box covers $$\mathbb {G}$$ , and that box must be $$\mathbb {G}$$ itself, so the theorem holds. So assume J > 1. If x 1(s) > y 1(s) or x 1(s) < y 1(s), then x(s) and y(s) cannot both be lexico minimal, so we must have x 1(s) = y 1(s). We apply the same reasoning to right(x(s)) and right(y(s)) to conclude that x 2(s) = y 2(s). If J = 2 we are done; the theorem is proved. If J > 2, we apply the same reasoning to right 2(x(s)) and right 2(y(s)) to conclude that x 3(s) = y 3(s). Continuing in this manner, we finally obtain x J(s) = y J(s), so x(s) = y(s). □

For $$x(s) = \sum {\mathcal {B}}(s)$$ and $$q \in {\mathbb {R}}$$ , define
$$\displaystyle \begin{aligned} \begin{array}{rcl} Z\big(x(s),q \big) \equiv \sum_{B_{{j}} \in {\mathcal{B}}(s)} \left(\frac{x_{{j}}(s)}{N} \right)^q \, . {} \end{array} \end{aligned} $$
(17.4)

Lemma 17.1 Let α, β, and γ be positive numbers. Then (α + β)∕(α + γ) > 1 if and only if β > γ.

Theorem 17.3 Let $$x(s) = \sum {\mathcal {B}}(s)$$ . If x(s) is lexico minimal, then $${\mathcal {B}}(s)$$ is (s, q) minimal for all sufficiently large q.

Proof [ Rosenberg 17b] Pick s and let $$x(s) = \sum {\mathcal {B}}(s)$$ be lexico minimal. Let $$\widetilde { {\mathcal {B}}}(s)$$ be a minimal s-covering distinct from $${\mathcal {B}}(s)$$ , and let $$y(s) = \sum \widetilde { {\mathcal {B}}}(s)$$ . By Theorem 17.2, y(s) ≠ x(s). Define J ≡ B(s). Consider the ratio
$$\displaystyle \begin{aligned} \begin{array}{rcl} F \equiv \frac{Z\big(y(s),q\big)}{Z\big(x(s),q\big)} = \frac {\sum_{j=1}^J \big(y_{{j}}(s)/N \big)^q } {\sum_{j=1}^J \big(x_{{j}}(s)/N \big)^q } \, . \end{array} \end{aligned} $$
Let k be the smallest index such that y j(s) ≠ x j(s). For example, if x(s) = (8, 8, 7, 3, 2) and y(s) = (8, 8, 7, 4, 1), then k = 4. Since x j(s) ≤ x k(s) for k ≤ j ≤ J, for q > 1 we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} \sum_{j=k}^J \left( \frac{x_{{j}}(s)}{x_{{k}}(s)} \right)^{ q} &lt; \sum_{j=k}^J \left( \frac{x_{{j}}(s)}{x_{{k}}(s)} \right) \leq J-k+1 \, . {} \end{array} \end{aligned} $$
(17.5)
By Lemma 17.1, F > 1 if and only if $${\sum _{j=k}^J \big (y_{{j}}(s)/N \big )^q } &gt; {\sum _{j=k}^J \big (x_{{j}}(s)/N \big )^q }$$ . Since $${\mathcal {B}}(s)$$ and $$\widetilde { {\mathcal {B}}}(s)$$ are minimal s-coverings, and since x(s) is lexico minimal, then y k(s) > x k(s). We have
$$\displaystyle \begin{aligned} \begin{array}{rcl} \frac{\sum_{j=k}^J \big(y_{{j}}(s)/N \big)^q }{\sum_{j=k}^J \big(x_{{j}}(s)/N \big)^q } &amp;\displaystyle = &amp;\displaystyle \frac{N^q \big( x_{{k}}(s)\big)^{-q} \sum_{j=k}^J \big(y_{{j}}(s)/N \big)^q} {N^q \big( x_{{k}}(s)\big)^{-q} \sum_{j=k}^J \big(x_{{j}}(s)/N \big)^q} \\ &amp;\displaystyle = &amp;\displaystyle \frac {\sum_{j=k}^J \big(y_{{j}}(s)/x_{{k}}(s) \big)^q } {\sum_{j=k}^J \big(x_{{j}}(s)/x_{{k}}(s) \big)^q } \\ &amp;\displaystyle &gt; &amp;\displaystyle \frac {\big(y_{{k}}(s)/x_{{k}}(s) \big)^q } {\sum_{j=k}^J \big(x_{{j}}(s)/x_{{k}}(s) \big)^q } \geq \frac { \big(y_{{k}}(s)/x_{{k}}(s) \big)^q } {J -k + 1} \, , \end{array} \end{aligned} $$
where the final inequality holds by (17.5). Since y k(s) > x k(s) then for all sufficiently large q we have F > 1. □

Analogous to Procedure 17.1, Procedure 17.2 below shows how, for a given s, the lexico minimal x(s) can be computed by a simple modification of whatever box-counting method is used to compute a minimal s-covering.

Procedure 17.2 Let $${\mathcal {B}}_{\min }(s)$$ be the best s-covering obtained over all executions of whatever box-counting method is utilized. Suppose we have executed box counting some number of times, and stored $${\mathcal {B}}_{\min }(s)$$ and $$x_{\min }(s) = \sum {\mathcal {B}}_{\min }(s)$$ , so $$x_{\min }(s)$$ is the current best estimate of a lexico minimal summary vector. Now suppose we execute box counting again, and generate a new s-covering $${\mathcal {B}}(s)$$ using B(s) boxes. Let $$x(s) = \sum {\mathcal {B}}(s)$$ . If $${B}(s) &lt; B_{\min }(s)$$ holds, or if $${B}(s) = B_{\min }(s)$$ and $$x_{\min }(s) \succeq x(s)$$ hold, set $${\mathcal {B}}_{\min }(s) = {{\mathcal {B}}}(s)$$ and $$x_{\min }(s) = x(s)$$ . □

Procedure 17.2 shows that the only additional steps, beyond the box- counting method itself, needed to compute x(s) are lexicographic comparisons, and no evaluations of the partition function $$Z_q \big ({\mathcal {B}}(s) \big )$$ are required. Theorem 17.2 proved that x(s) is unique. Theorem 17.3 proved that x(s) is “optimal” (i.e., (s, q) minimal) for all sufficiently large q. Thus an attractive way to unambiguously compute D q is to compute x(s) for a range of s and use the x(s) summary vectors to compute D q, using Definition 17.3 below.

Definition 17.3 For q ≠ 1, the network $$\mathbb {G}$$ has the generalized dimension D q if for some constant c, for some positive integers L and U satisfying 2 ≤ L < U ≤ Δ, and for each integer s ∈ [L, U],
../images/487758_1_En_17_Chapter/487758_1_En_17_Equ8_HTML.png
(17.6)
where Z(x(s), q) is defined by (17.4) and where $$x(s) = \sum {\mathcal {B}}(s)$$ is lexico minimal. □

Other than the minor detail that (17.3) is formulated using radius-based boxes rather than diameter-based boxes, (17.6) is identical to (17.3). Definition 17.3 modifies the definition of D q in [Wang 11] to ensure uniqueness of D q. Since x(s) summarizes a minimal s-covering, using x(s) to compute D q, even when q is not sufficiently large as required by Theorem 17.3, introduces no error in the computation of D q. By using the summary vectors x(s) we can unambiguously compute D q, with negligible extra computational burden.

Example 17. 1 (Continued) Consider again the chair network of Fig. 17.1. Choose q = 2. For s = 2 we have $$x(2) = \sum {{\mathcal {B}}}(2) = (2, 2, 1)$$ and $$Z\big ( x(2), 2 \big ) = \frac {9}{25}$$ . For s = 3 we have $$x(3) = \sum \widetilde {{\mathcal {B}}}(3) = (3,2)$$ and $$Z \big ( x(3), 2 \big ) = \frac {13}{25}$$ . Choose L = 2 and U = 3. From Definition 17.3 we have $$D_2 = \log (13/9)/\log (3/2) = 0.907$$ . □

Definition 17.4 If for some constant d we have D q = d for $$q \in \mathbb {R}$$ , then $$\mathbb {G}$$ is monofractal; if $$\mathbb {G}$$ is not monofractal, then $$\mathbb {G}$$ is multifractal. □

For the final topic in this section, we show how to use the x(s) summary vectors to compute D ∞≡limq→∞D q. Let $$x(s) = \sum {\mathcal {B}}(s)$$ be lexico minimal and let x 1(s) be the first element of x(s). Let m(s) be the multiplicity of x 1(s), defined to be the number of occurrences of x 1(s) in x(s). (For example, if x(s) = (7, 7, 6, 5, 4), then x 1(s) = 7 and m(s) = 2 since there are two occurrences of 7.) Then x 1(s) > x j(s) for j > m(s). Using (17.4), we have
$$\displaystyle \begin{aligned} \lim_{q \rightarrow \infty} \frac {\log Z\big( x(s), q \big)} {q-1} &amp;= \lim_{q \rightarrow \infty} \left\{ \frac{1}{q-1} \log \left( m(s) \left( \frac{ x_{{1}}(s)}{N} \right)^q \right.\right. \\ &amp;+ \left.\left.\sum_{j = m(s)+1}^{B(s)} \left( \frac{ x_{{j}}(s)}{N} \right)^q \right) \right\} \\ &amp;= \lim_{q \rightarrow \infty} \left\{ \frac{1}{q-1} \log \left( m(s) \left( \frac{ x_{{1}}(s)}{N} \right)^q \right) \right\} \\ &amp;= \lim_{q \rightarrow \infty} \frac { \log m(s) + q \log \big( x_{{1}}(s)/N \big) } {q-1} \\ &amp; = \log \left( \frac{x_{{1}}(s)}{N} \right) \, . {} \end{aligned} $$
(17.7)
Rewriting (17.6) yields
$$\displaystyle \begin{aligned} \begin{array}{rcl} \frac {\log Z(x(s),q)}{q-1} \approx {D_q} \log \left( \frac{s}{\varDelta} \right) + \frac{c}{q-1} \, . {} \end{array} \end{aligned} $$
(17.8)
Taking the limit of both sides of (17.8) as q →∞, and using (17.7), we obtain
$$\displaystyle \begin{aligned} \begin{array}{rcl} \log \left( {x_{{1}}(s)}/{N} \right) \approx D_{\infty} \log \left( {s}/{\varDelta} \right) \, . {} \end{array} \end{aligned} $$
(17.9)
We can use (17.9) to compute D ∞ without having to compute any partition function values. It is well-known [Peitgen 92] that, for geometric multifractals, D ∞ corresponds to the densest part of the fractal. Similarly, (17.9) shows that, for a network, D ∞ is the factor that relates the box size s to x 1(s), the number of nodes in the box with the highest probability.
Using Procedure 17.2, the box counting dimension d B and D ∞ were compared in [Rosenberg 17b] for three networks. The reason for comparing d B to D ∞ is that for geometric multifractals we have d B = D 0 ≥ D ∞ (Theorem 16.1). Procedure 17.2 can be used with any box-counting method; [Rosenberg 17b] used the greedy heuristic of [Song 07], described in Sect. 8.​1. Recall that this greedy heuristic first creates the auxiliary graph $$\widetilde {\mathbb {G}}_s = ( {\mathbb {N}}, \widetilde {{\mathbb {A}}}_s)$$ . Having constructed $$\widetilde {{\mathbb {G}}}_s$$ , the task is to color the nodes of $$\widetilde {{\mathbb {G}}}_s$$ , using the minimal number of colors, such that no arc in $$\widetilde {{\mathbb {A}}}_s$$ connects nodes assigned the same color. The heuristic used to color $${\widetilde {{\mathbb {G}}} }_s$$ is the following. Suppose we have ordered the $$N = \vert {\mathbb {N}} \vert $$ nodes in some order n 1, n 2, …, n N. Define $$\mathbb {N} \equiv \{ 1, 2, \ldots , N \}$$ . For $$i \in {\mathbb {N}}$$ , let $${\widetilde {\mathbb {N}}}(n_{{\, i}})$$ be the set of nodes in $${\widetilde {{\mathbb {G}}} }_s$$ that are adjacent to node n i. (This set is empty if n i is an isolated node.) Let c(n) be the color assigned to node n. Initialize c(n 1) = 1 and c(n) = 0 for all other nodes. For i = 2, 3, …, N, the color c(n i) assigned to n i is the smallest color not assigned to any neighbor of n i:
$$\displaystyle \begin{aligned} c(n_{{\, i}}) = \min\{ k \in {\mathbb{N}} \, \vert \, k \neq c(n) \mbox{ for } n \in {\widetilde{\mathbb{N}}}(n_{{\, i}}) \} \, . \end{aligned}$$
The estimate of the chromatic number $${\chi }({\widetilde {{\mathbb {G}}} }_s)$$ , which is also the estimate of B(s), is $$\max \{ c(n) \, \vert \, n \in {\mathbb {N}} \}$$ , the number of colors used to color the auxiliary graph. All nodes with the same color belong to the same box.

This node coloring heuristic assumes some given ordering of the nodes. Many random orderings of the nodes were generated: for the dolphins and jazz networks 10N random orderings of the nodes were generated, and for the C. elegans network N random orderings were generated. The node coloring heuristic was executed for each random ordering. Random orderings were obtained by starting with the permutation array π(n) = n, picking two random integers $$i,j \in {\mathbb {N}}$$ , and swapping the contents of π in positions i and j. For the dolphins and jazz networks 10N swaps were executed to generate each random ordering, and for the C. elegans network N swaps were executed. In the plots for these three networks, the horizontal axis is $$\log (s/\varDelta )$$ , the red line plots $$\log (x_{{1}}(s)/N)$$ versus $$\log (s/\varDelta )$$ , and the blue line plots $$-\log B(s)$$ versus $$\log (s/\varDelta )$$ .

Example 17.2 Figure 17.2 (left) provides results for the jazz network, with 198 nodes, 2742 arcs, and Δ = 6; see Example 15.5.
../images/487758_1_En_17_Chapter/487758_1_En_17_Fig2_HTML.png
Figure 17.2

D ∞ for three networks

The red and blue plots are over the range 2 ≤ s ≤ 6. Over this range, a linear fit to the red plot yields, from (17.9), D ∞ = 1.55, and a linear fit to the blue plot yields d B = 1.87. Since d B = D 0, we have D 0 > D ∞.

Example 17.3 Figure 17.2 (middle) provides results for the dolphins network (introduced in Example 7.2), with 62 nodes, 159 arcs, and Δ = 8. The red and blue plots are over the range 2 ≤ s ≤ 8. Using (17.9), a linear fit to the red plot over 2 ≤ s ≤ 6 (the portion of the plots that appears roughly linear) yields D ∞ = 2.29, and a linear fit to the blue plot over 2 ≤ s ≤ 6 yields d B = 2.27, so D ∞ very slightly exceeds d B.

Example 17.4 Figure 17.2 (right) provides results for the C. elegans network, with 453 nodes, 2040 arcs, and Δ = 7. This is the unweighted, undirected version of the neural network of C. elegans [Newman]. The red and blue plots are over the range 2 ≤ s ≤ 7. Using (17.9), a linear fit to the red plot over 3 ≤ s ≤ 7 (the portion of the plots that appears roughly linear) yields D ∞ = 1.52, and a linear fit to the blue plot over 3 ≤ s ≤ 7 yields d B = 1.73, so D 0 > D ∞.

In each of the three figures, the two lines roughly begin to intersect as s∕Δ increases. This occurs since x 1(s) is non-decreasing in s and x 1(s)∕N = 1 for s > Δ; similarly B(s) is non-increasing in s and B(s) = 1 for s > Δ.

Exercise 17.1 An arc-covering based approach, e.g., [Jalan 17, Zhou 07], can be used to define D q, where p j(s) is the fraction of all arcs contained in box $$B_{{j}} \subset {\mathcal {B}}(s)$$ . Compare the D q values obtained using arc-coverings with the D q values obtained using node-coverings. □

Exercise 17.2 Compute D q for integer q in [−10, 10] for the hub and spoke with a tail network of Example 15.2. □

17.2 Non-monotonicity of the Generalized Dimensions

For a geometric object, we showed (Theorem 16.1) that the generalized dimensions D q are monotone non-increasing in q. In this section we show that, for a network, the generalized dimensions can fail to be monotone non-increasing in q, even when D q is computed using the lexico minimal summary vectors x(s). (The fact that D q can be increasing in q for q < 0, or for small positive values of q, was observed in [Wang 11]. For example, for the protein-protein interaction networks studied in [Wang 11], D q is increasing in q for q ∈ [0, 1], and D q peaks at q ≈ 2.) Moreover, in this section we show that D q versus q curve can assume different shapes, depending on the range of box sizes used to compute D q.

Recall that Z(x(s), q) is defined by (17.4), where $$x(s) = \sum {\mathcal {B}}(s)$$ is a lexico minimal summary vector for box size s. In Sect. 17.1, we showed that to compute D q for a given q, we identify a range [L, U] of box sizes, where L < U, such that $$\log Z\big (x(s), q \big )$$ is approximately linear in $$\log s$$ for s ∈ [L, U]. The estimate of D q is 1∕(q − 1) times the slope of the linear approximation. More formally, Definition 17.3 required D q to satisfy
../images/487758_1_En_17_Chapter/487758_1_En_17_Equ12_HTML.png
(17.10)
for integer s ∈ [L, U]. For the remainder of this section, assume that (17.10) holds as a strict equality.
Example 17.5 To illustrate how different minimal s-coverings can yield very different D q versus q curves, consider again the chair network of Fig. 17.1, which shows two minimal 3-coverings and a minimal 2-covering. We have $$x(2) = \sum {\mathcal {B}}(2) = (2, 2, 1)$$ and $$Z\big (x(2), q \big ) = 2(\frac {2}{5})^q + (\frac {1}{5})^q$$ . For the 3-covering $$\widetilde {{\mathcal {B}}}(3)$$ we have $$\widetilde {x}(3) \equiv \sum {\widetilde {{\mathcal {B}}}}(3) = (3, 2)$$ and $$Z\big ( \widetilde {x}(3), q \big ) = (\frac {3}{5})^q + (\frac {2}{5})^q$$ . With L = 2 and U = 3, from (17.6) we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} \widetilde{D}_q \equiv \left( \frac{1}{q-1} \right) \left( \frac { \log \left( \frac{3^q + 2^q}{5^q} \right) - \log \left( \frac{(2)(2^q)+1}{5^q} \right) } { \log (3/\varDelta) - \log (2/\varDelta) } \right)\!\!\! &amp;\displaystyle =&amp;\displaystyle \!\!\! \frac { \log \left( \frac{3^q + 2^q}{(2)(2^q)+1} \right) } {\log(3/2) (q-1) } \, . \end{array} \end{aligned} $$
(17.11)
If instead for s = 3 we choose the covering $$\widehat {{\mathcal {B}}}(3)$$ then $$\widehat {x}(3) \equiv \sum {\widehat {{\mathcal {B}}}}(3) = (4, 1)$$ and $$Z\big ( \widehat {x}(3), q \big ) = (\frac {4}{5})^q + (\frac {1}{5})^q$$ . With L = 2 and U = 3, but now using $$\widehat {x}(3)$$ instead of $$\widetilde {x}(3)$$ , we obtain
$$\displaystyle \begin{aligned} \begin{array}{rcl} \widehat{D}_q \equiv \left( \frac{1}{q-1} \right) \left( \frac { \log \left( \frac{4^q + 1^q}{5^q} \right) - \log \left( \frac{(2)(2^q)+1}{5^q} \right) } { \log (3/\varDelta) - \log (2/\varDelta) } \right)\!\!\! &amp;\displaystyle =&amp;\displaystyle \!\!\! \frac { \log \left( \frac{4^q + 1}{(2)(2^q)+1} \right) } {\log(3/2) (q-1) } \, . \end{array} \end{aligned} $$
(17.12)
Figure 17.3 plots $$\widetilde {D}_q$$ versus q, and $$\widehat {D}_q$$ versus q over the range 0 ≤ q ≤ 15.
../images/487758_1_En_17_Chapter/487758_1_En_17_Fig3_HTML.png
Figure 17.3

Two plots of the generalized dimensions of the chair network

Neither curve is monotone non-increasing: the $$\widetilde {D}_q$$ curve is unimodal, with a local minimum at q ≈ 4.1, and the $$\widehat {D}_q$$ curve is monotone increasing. □

In Example 17.5, since (4, 1) ≽ (3, 2) then x(3) = (3, 2) is the lexico minimal summary vector for s = 3. Using the x(s) vectors eliminates one source of ambiguity in computing D q. However, there is yet another source of ambiguity: the selection of the range of box sizes used to compute D q. What has not been previously recognized is that for a network the choice of L and U can dramatically change the shape of the D q versus q curve [Rosenberg 17c]; this is the subject of the remainder of this section.

As frequently discussed in previous chapters, the computation of a fractal dimension, whether for a geometric object or for a network, typically involves picking a region of box sizes over which the plot (in double logarithmic coordinates) looks approximately linear. Thus one way to compute D q for a given q is to determine a range [L q, U q] of s values over which $$\log Z\big (x(s), q\big )$$ is approximately linear in $$\log s$$ , and then use (17.10) to estimate D q, e.g., using linear regression. With this approach, to report computational results to other researchers it would be necessary to specify, for each q, the range of box sizes used to estimate D q. This is certainly not the protocol currently followed in research on generalized dimensions. Instead, the approach taken in [Wang 11] and [Rosenberg 17c] was to pick a single L and U and estimate D q for all q with this L and U. Moreover, rather than using a technique such as linear regression to estimate D q over the range [L, U] of box sizes, in [Rosenberg 17c] D q was estimated using only the two box sizes L and U.1 With this two-point approach, the estimate of D q is the slope of the secant line connecting the point $$\Big ( \log L, \log Z\big (x(L), q\big ) \Big )$$ to the point $$\Big ( \log U, \log Z\big (x(U), q\big ) \Big )$$ , where x(L) and x(U) are the lexico minimal summary vectors for box sizes L and U, respectively. Using (17.4) and (17.10), the estimate of D q is D q(L, U), defined by
$$\displaystyle \begin{aligned} D_q(L, U) &amp;\equiv \frac { \log Z\big(x(U), q\big) - \log Z\big(x(L), q\big) } { (q-1)\big( \log(U/\varDelta) - \log(L/\varDelta) \big) }\\ &amp;= \frac{1} {\log(U/L) (q-1) } \log \left( \frac{\sum_{B_{{j}} \in {\mathcal{B}}(U)} [x_{{j}}(U)]^q } {\sum_{B_{{j}} \in {\mathcal{B}}(L)} [x_{{j}}(L)]^q } \right) \, . {} \end{aligned} $$
(17.13)
Example 17.6 Figure 17.4 (left) plots box counting results for the dolphins network. This figure shows that the $$\big ( -\log (s/\varDelta ), \log B(s) \big )$$ curve is approximately linear for 2 ≤ s ≤ 6.
../images/487758_1_En_17_Chapter/487758_1_En_17_Fig4_HTML.png
Figure 17.4

Box counting and $$\log Z \big (x(s), q \big )$$ versus $$\log (s/\varDelta )$$ for the dolphins network

Figure 17.4 (right) plots $$\log Z\big (x(s), q\big )$$ versus $$\log (s/\varDelta )$$ for 2 ≤ s ≤ 6 and for q = 2, 4, 6, 8, 10 (q = 2 is the top curve, and q = 10 is the bottom curve). This figure shows that, although the $$\log Z\big (x(s), q\big )$$ versus $$\log (s/\varDelta )$$ curves are less linear as q increases, a linear approximation is quite reasonable. Moreover, we are particularly interested, in the next section, in the behavior of the $$\log Z\big (x(s), q\big )$$ versus $$\log (s/\varDelta )$$ curve for small positive q, the region where the linear approximation is best. Using (17.13), Fig. 17.5 plots the secant estimate D q(L, U) versus q for various choices of L and U.
../images/487758_1_En_17_Chapter/487758_1_En_17_Fig5_HTML.png
Figure 17.5

Secant estimate of D q for the dolphins network for different L and U

Since the D q versus q curve for a geometric multifractal is monotone non-increasing, it is remarkable that different choices of L and U lead to such different shapes for the D q(L, U) versus q curve.

Recalling that D q(L, U), defined by (17.13), is the secant estimate of D q using the box sizes L and U, let $$D^{\prime }_0(L,U)$$ denote the first derivative with respect to q of D q(L, U), evaluated at q = 0. A simple closed-form expression for $$D^{\prime }_0(L,U)$$ was derived in [Rosenberg 17c]. For box size s, let $$x(s) = \sum {\mathcal {B}}(s)$$ summarize the minimal s-covering $${\mathcal {B}}(s)$$ . Define
$$\displaystyle \begin{aligned} {G}(s) &amp;\equiv \left( \prod_{j=1}^{B(s)} x_{{j}}(s) \right)^{\negthinspace \negthinspace 1/B(s)} \\ {A}(s) &amp;\equiv \frac{1}{B(s)}\sum_{j=1}^{B(s)} x_{{j}}(s) \\ {R}(s) &amp;\equiv \frac{G(s)}{A(s)} {} \end{aligned} $$
(17.14)
so G(s) is the geometric mean of the box masses summarized by x(s), A(s) is the arithmetic mean of the box masses summarized by x(s), and R(s) is the ratio of the geometric mean to the arithmetic mean. By the classical arithmetic-geometric inequality, for each s we have R(s) ≤ 1. Since $$\sum _{j=1}^{B(s)} x_{{j}}(s) = N$$ , then
$$\displaystyle \begin{aligned} \begin{array}{rcl} B(s) \, {A}(s) = N \, . {} \end{array} \end{aligned} $$
(17.15)
Theorem 17.4
$$\displaystyle \begin{aligned} D^{\prime}_0(L,U) = \frac{1}{\log (U/L)} \log \frac { {R}(L)} { {R}(U)} \, . \end{aligned}$$
Proof [ Rosenberg 17c] Define J ≡ B(L) (the number of boxes in the minimal L-covering $${\mathcal {B}}(L)$$ ) and define K ≡ B(U). For simplicity of notation, by ∑j we mean $$\sum _{j=1}^J$$ and by ∑k we mean $$\sum _{k=1}^K$$ . Similarly, by ∏j we mean $$\prod _{j=1}^J$$ and by ∏k we mean $$\prod _{k=1}^K$$ . Assume that $$\log $$ means the natural log. For 1 ≤ j ≤ J, define a j ≡ x j(L) and $${\alpha }_{{j}} \equiv \log a_{{j}}$$ . For 1 ≤ k ≤ K, define b k ≡ x k(U) and $${\beta }_{{k}} \equiv \log b_{{k}}$$ . Define $$\omega \equiv 1/\log (U/L)$$ . For simplicity of notation, define F(q) ≡ D q(L, U). By F ′(0) we mean the first derivative of F(q) evaluated at q = 0, so $$F^{\prime }(0) = D^{\prime }_0(L,U)$$ . Using the above notation and definitions, from (17.13) we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} F(q) = \frac{\omega} {(q-1) } \log \left( \frac{\sum_k e^{{\beta}_{{k}} q} } {\sum_j e^{{\alpha}_{{j}} q} } \right) \, . {} \end{array} \end{aligned} $$
(17.16)
Define α = (1∕J)∑jα j. Consider the functions f 1(q) ≡ Je αq and $$f_{{\, 2}}(q) \equiv \sum _j e^{{\alpha }_{{j}} q}$$ . We have f 1(0) = f 2(0) = J. Evaluating the first derivatives at q = 0, we have $$f_{{\, 1}}^{\prime }(0) = J \alpha = \sum _j {\alpha }_{{j}}$$ and $$f_{{\, 2}}^{\prime }(0) = \sum _j {\alpha }_{{j}}$$ . Since f 1(q) and f 2(q) have the same function values and first derivatives at q = 0, then F(0) = M(0) and F ′(0) = M ′(0), where M(q) is defined by
$$\displaystyle \begin{aligned} \begin{array}{rcl} M(q) \equiv \frac{\omega} {(q-1) } \log \left( \frac{\sum_k e^{{\beta}_{{k}} q} } {J e^{\alpha q} } \right) \, . {} \end{array} \end{aligned} $$
(17.17)
Simplifying (17.17) yields
$$\displaystyle \begin{aligned} \begin{array}{rcl} M(q) = \frac{\omega} {(q-1) } \log \left( \frac{1}{J} \sum_k e^{({\beta}_{{k}}-\alpha) q} \right) \, . \end{array} \end{aligned} $$
Taking the first derivative with respect to q,
$$\displaystyle \begin{aligned} \begin{array}{rcl} M^{\prime}(q) {=} \frac{\omega} {(q-1)^2 } \left[ \frac {(q-1) (1/J) \sum_k [ e^{({\beta}_{{k}}-\alpha) q}({\beta}_{{k}} - \alpha)]} { (1/J) \sum_k e^{({\beta}_{{k}}-\alpha) q} } {-}\log \left( \frac{1}{J} \sum_k e^{({\beta}_{{k}}-\alpha) q} \right) \right] \, . \end{array} \end{aligned} $$
Plugging in q = 0 and using the definition of α yields
$$\displaystyle \begin{aligned} \begin{array}{rcl} M^{\prime}(0) &amp;\displaystyle =&amp;\displaystyle \omega \left( -\frac{1}{K} \sum_k ({\beta}_{{k}} - \alpha) - \log \frac{K}{J} \right) \\ &amp;\displaystyle =&amp;\displaystyle \omega \left( -\frac{1}{K} \sum_k \log b_{{k}} + \frac{1}{J} \sum_j \log a_{{j}} - \log \frac{K}{J} \right) \\ &amp;\displaystyle =&amp;\displaystyle \omega \left( -\log \Big( \big( \prod_k b_{{k}} \big)^{1/K} \Big) + \log \Big( \big( \prod_j a_{{j}} \big)^{1/J} \Big) - \log \frac{K}{J} \right) \\ &amp;\displaystyle =&amp;\displaystyle \omega \log \left( \frac { J \big( \prod_j a_{{j}} \big)^{1/J}} { K \big( \prod_k b_{{k}} \big)^{1/K} } \right) \\ &amp;\displaystyle =&amp;\displaystyle \frac{1}{\log (U/L)} \log \left( \frac { \frac{J \big( \prod_j a_{{j}} \big)^{1/J}}{J A(L)}} { \frac{K \big( \prod_k b_{{k}} \big)^{1/K}}{K A(U)} }\right) \;\;\;\; \big(\mbox{by } (\mbox{17.15}) \big) \\ &amp;\displaystyle =&amp;\displaystyle \frac{1}{\log (U/L)} \log \frac { R(L)} {R(U) } \;\;\;\; \big(\mbox{by } (\mbox{17.14}) \big). \; \; \end{array} \end{aligned} $$

□

Theorem 17.4 says that the slope of the secant estimate of D q at q = 0 depends on x(L) and x(U) only through the ratio of the geometric mean to the arithmetic mean of the components of x(L), and similarly for x(U). Note that the proof of Theorem 17.4 does not require x(s) to be lexico minimal. Since U > L, Theorem 17.4 immediately implies the following corollary.

Corollary 17.1 $$D^{\prime }_0(L,U) &gt; 0$$ if and only if R(L) > R(U), and $$D^{\prime }_0(L,U) &lt; 0$$ if and only if R(L) < R(U). □

For a given L and U, Theorem 17.5 below provides a sufficient condition for D q(L, U) to have a local maximum or minimum.

Theorem 17.5 [ Rosenberg 17c] Assume (17.10) holds as an equality. If x(s) is a lexico minimal summary vector summarizing the minimal s-covering $${\mathcal {B}}(s)$$ , then (i) if R(L) > R(U) and B(L)∕B(U) > x 1(U)∕x 1(L), then D q(L, U) has a local maximum at some q > 0. (ii) If R(L) < R(U) and B(L)∕B(U) < x 1(U)∕x 1(L), then D q(L, U) has a local minimum at some q > 0.

Proof We will prove (i); the proof of (ii) proceeds similarly. Since (17.10) is assumed to hold as an equality, then (17.9) holds as an equality, and D ∞ =limq→∞D q satisfies $$\log \left ( {x_{{1}}(s)}/{N} \right ) = D_{\infty } \log \left ( {s}/{\varDelta } \right )$$ , where x 1(s) is the first coordinate of the lexico minimal summary vector x(s). Defining $$\omega \equiv 1/\log (U/L)$$ , we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} D_{\infty} = \frac { \log \big( x_{{1}}(U)/N \big) - \log \big( x_{{1}}(L)/N \big) } {\log (U/\varDelta) - \log (L/\varDelta) } = \omega \log \frac{ x_{{1}}(U)}{x_{{1}}(L)} \, . {} \end{array} \end{aligned} $$
(17.18)
Since Z(x(s), 0) = B(s), from (17.10) with q = 0 we obtain
$$\displaystyle \begin{aligned} \begin{array}{rcl} D_0 = \frac { \log Z\big(x(L),0 \big) - \log Z\big(x(U),0 \big)} {\log (U/\varDelta) - \log (L/\varDelta) } = \omega \log \frac{ B(L)}{B(U)} \, . {} \end{array} \end{aligned} $$
(17.19)
If $$D^{\prime }_0(L,U) &gt; 0$$ and D 0 > D ∞, then D q(L, U) must have a local maximum at some positive q. By Corollary 17.1, if R(L) > R(U) then $$D^{\prime }_0(L,U) &gt; 0$$ . By (17.18) and (17.19), if B(L)∕B(U) > x 1(U)∕x 1(L), then D 0 > D ∞. □

Example 17.7 To illustrate Theorem 17.5, consider again the dolphins network of Example 17.2 with L = 3 and U = 5. We have B(3) = 13, B(5) = 4, x 1(3) = 10, and x 1(5) = 28, so $$D_0 = \log (13/4)/\log (5/3) = 2.307$$ and $$D_{\infty } = \log (28/10)/\log (5/3) = 2.106$$ . We have R(3) = 0.773, R(5) = 0.660, and $$D^{\prime }_0(L,U) = 0.311$$ , so D q(3, 5) has a local maximum, as seen in Fig. 17.5. Moreover, for the dolphins network, choosing L = 2 and U = 5 we have $$D_0 = \log (29/4)/\log (5/2) = 2.16$$ , and $$D_{\infty } = \log (28/3)/\log (5/2) = 2.44$$ , so D 0 < D ∞, as is evident from Fig. 17.5. Thus the inequality D 0 ≥ D ∞, which is valid for geometric multifractals, does not hold for the dolphins network with L = 2 and U = 5. □

If for s ∈{L, U} we can compute a minimal s-covering with equal box masses, then by Definition 17.3 the network $$\mathbb {G}$$ is a monofractal but not a multifractal. To see this, suppose all boxes in $${\mathcal {B}}(L)$$ have the same mass, and that all boxes in $${\mathcal {B}}(U)$$ have the same mass. Then for s ∈{L, U} we have x j(s) = N∕B(s) for 1 ≤ j ≤ B(s), and (17.4) yields
$$\displaystyle \begin{aligned} Z\big(x(s), q \big) = \sum_{B_{{j}} \in {\mathcal{B}}(s)} \left(\frac{x_{{j}}(s)}{N} \right)^q = \sum_{B_{{j}} \in {\mathcal{B}}(s)} \left( \frac{1}{B(s)} \right) ^{q} = [B(s)]^{1-q} \, . \end{aligned}$$
From (17.10), for q ≠ 1 we have
$$\displaystyle \begin{aligned} D_q &amp;= \frac{\log Z\big( (x(U), q \big)- \log Z\big(x(L), q \big)} {(q-1)\big( \log U - \log L \big)} \; = \; \frac{ \log \big( [B(U)]^{1-q} \big) {-} \log \big( [B(L)]^{1-q} \big)} {(q-1) \big( \log U - \log L \big)} \\ &amp;{=} \frac{ \log B(L) {-} \log B(U)} {\log U - \log L} \; = \; D_0 \; = \; d_{{B}} \, , {} \end{aligned} $$
(17.20)
so $$\mathbb {G}$$ is a monofractal. Thus equal box masses imply $$\mathbb {G}$$ is a monofractal, the simplest of all fractal structures.

There are several ways to try to obtain equal box masses in a minimal s-covering of $$\mathbb {G}$$ . As discussed in Chap. 15, ambiguity in the choice of minimal coverings used to compute d I is eliminated by maximizing entropy. Since the entropy of a probability distribution is maximized when all the probabilities are equal, a maximal entropy minimal covering equalizes (to the extent possible) the box masses. Similarly, ambiguity in the choice of minimal s-coverings used to compute D q is eliminated by minimizing the partition function $$Z_q \big ( {\mathcal {B}}(s) \big )$$ . Since, by Theorem 17.3, for all sufficiently large q the unique lexico minimal vector x(s) summarizes the s-covering that minimizes $$Z_q \big ( {\mathcal {B}}(s) \big )$$ , and since, by Theorem 17.1, for q > 1 a partition function is minimized when all the probabilities are equal, then x(s) also equalizes (to the extent possible) the box masses. Theorem 17.4 suggests a third way to try to equalize the masses of all boxes in a minimal s-covering: since G(s) ≤ A(s) and G(s) = A(s) when all boxes have the same mass, a minimal s-covering that maximizes G(s) will also equalize (to the extent possible) the box masses. The advantage of computing the lexico minimal summary vectors x(s), rather than maximizing the entropy or maximizing G(s), is that x(s) is provably unique. We now apply Theorem 17.4 to the chair network of Example 17.1, to the dolphins network of Example 17.3, and to two other networks.

Example 17.8 For the chair network we have L = 2, x(L) = (2, 2, 1), U = 3, and x(U) = (3, 2). We have $$D^{\prime }_0(2,3) = -0.070$$ , as shown in Fig. 17.3 by the slightly negative slope of the lower curve at q = 0. As illustrated in Fig. 17.3, this curve is not monotone non-increasing; it has a local minimum. □

Example 17.9 For the dolphins network, Table 17.1 provides $$D^{\prime }_0(L,U)$$ for various choices of L and U.
Table 17.1

$$D^{\prime }_0(L,U)$$ for the dolphins network

L, U

$$D^{\prime }_0(L,U)$$

2, 6

− 0.056

3, 5

0.311

2, 4

0.393

2, 5

0.367

The values in Table 17.1 are better understood using Fig. 17.6, which plots $$\log R(s)$$ versus $$\log s$$ . For example, for (L, U) = (2, 6) we have $$D^{\prime }_0(2,6) = \log \big ( R(2)/R(6) \big )/\big ( \log 6/2 \big ) = -0.056$$ , as illustrated by the slightly positive slope of the dashed red line in Fig. 17.6, since the slope of the dashed red line is $$-D^{\prime }_0(2,6)$$ . For the other choices of (L, U) in Table 17.1, the values of $$D^{\prime }_0(L,U)$$ are positive and roughly equal.
../images/487758_1_En_17_Chapter/487758_1_En_17_Fig6_HTML.png
Figure 17.6

$$\log R(s)$$ versus $$\log s$$ for the dolphins network

Figure 17.4 (right) visually suggests that $$\log Z\big (x(s), q\big )$$ is better approximated by a linear fit over s ∈ [2, 5] than over s ∈ [2, 6], and Fig. 17.6 clearly shows that s = 6 is an outlier in that using U = 6 dramatically changes $$D^{\prime }_0(L,U)$$ . □

Example 17.10 Figure 17.7 shows the results of box counting for the jazz network; the curve appears reasonably linear for s ∈ [2, 6]. Figure 17.7 also plots D q(L, U) versus q for four choices of L and U.
../images/487758_1_En_17_Chapter/487758_1_En_17_Fig7_HTML.png
Figure 17.7

jazz box counting (left) and D q versus q for various L, U (right)

Table 17.2 provides $$D^{\prime }_0(L,U)$$ , D 0, and D ∞ for nine choices of L and U; the rows are sorted by decreasing $$D^{\prime }_0(L,U)$$ .
Table 17.2

Results for the jazz network for various L and U

L, U

$$D^{\prime }_0(L,U)$$

D 0

D ∞

2, 3

1.576

2.77

2.16

2, 4

1.224

2.74

1.42

2, 5

0.826

2.51

1.51

3, 4

0.728

2.69

0.37

2, 6

0.485

2.73

1.68

3, 5

0.231

2.31

1.00

3, 6

− 0.154

2.70

1.40

4, 5

− 0.411

1.82

1.82

5, 6

− 1.232

3.80

2.52

It is even possible for the D q(L, U) versus q curve to exhibit both a local maximum and a local minimum, as Fig. 17.8 illustrates for the jazz network with L = 4 and U = 5. There is a local minimum at q ≈ 0.7 and a local maximum at q ≈ 12.8. The narrow ranges in the vertical axes were selected to better display these critical points.
../images/487758_1_En_17_Chapter/487758_1_En_17_Fig8_HTML.png
Figure 17.8

Local minimum and maximum of D q for the jazz network and L = 4, U = 5

Figure 17.9 plots $$\log R(s)$$ versus $$\log s$$ for the jazz network. □
../images/487758_1_En_17_Chapter/487758_1_En_17_Fig9_HTML.png
Figure 17.9

$$\log R(s)$$ versus $$\log s$$ for the jazz network

Example 17.11 This network, with 453 nodes, 2040 arcs, and diameter 7, is the unweighted, undirected version the neural network of C. elegans [Newman]. Figure 17.10 (left) shows the results of box counting, and Fig. 17.10 (right) plots D q(L, U) versus q for four choices of L and U. □
../images/487758_1_En_17_Chapter/487758_1_En_17_Fig10_HTML.png
Figure 17.10

C. elegans box counting (left) and D q(L, U) versus q for various L, U (right)

The results of this section, and of Sect. 17.1 above, show that two requirements should be met when reporting fractal dimensions of a network. First, since there are in general multiple minimal s-coverings, and these different coverings can yield different values of D q, computational results should specify the rule (e.g., a maximal entropy covering, or a covering yielding a lexico minimal summary vector) used to unambiguously select a minimal s-covering. Second, the lower bound L and upper bound U on the box sizes used to compute D q should also be reported. Published values of D q not meeting these two requirements cannot in general be considered benchmarks. As to the values of L and U yielding the most meaningful results, it is desirable to identify the largest range [L, U] over which $$\log Z$$ is approximately linear in $$\log s$$ ; this is a well-known principle in the estimation of fractal dimensions. Future research may uncover other criteria for selecting the “best” L and U.

The numerical results from [Rosenberg 17c] presented in this section suggest several additional avenues for investigation. (1) We conjecture that D q(L, U) can have at most one local maximum and one local minimum. (2) Under what conditions does D q(L, U) have two critical points? (3) Derive closed-form bounds q 1 and q 2, easily obtainable from x(L) and x(U), such that if q ⋆ is a critical point of D q(L, U) then q 1 ≤ q ⋆ ≤ q 2.

17.3 Multifractal Network Generator

A method for generating a network from a multifractal measure was proposed in [Palla 10], and the implementation of this method was considered in more detail in [Horváth 13]. The method has two parts: generating the multifractal measure, and generating the network from the measure. To generate the measure, start with the unit square [0, 1] × [0, 1], which for brevity we denote by [0, 1]2. Pick an integer m ≥ 2 and divide [0, 1]2 into m pieces, using m − 1 vertical slices. For example, with m = 3 we might slice [0, 1]2 at the x values $$\frac {1}{3}$$ and $$\frac {1}{2}$$ . Call this set of m − 1 numbers, e.g., $$\{\frac {1}{3}, \frac {1}{2}\}$$ , the “V-slicing ratios”. Now slice [0, 1]2 using m − 1 horizontal slices, where the spacing of the horizontal slices can differ from that of the vertical slices. For example, we might slice [0, 1]2 horizontally at the y values $$\frac {1}{5}$$ and $$\frac {2}{3}$$ . Call this set of m − 1 numbers, e.g., $$\{ \frac {1}{5}, \frac {2}{3} \}$$ , the “H-slicing ratios”. The net effect of these 2(m − 1) slices is to partition [0, 1]2 into m 2 “generation 1” rectangles.

For i = 0, 1, …, m − 1 and j = 0, 2, …, m − 1, we assign a positive probability P ij to each generation 1 rectangle, subject to the symmetry constraints that P ij = P ji and the normalization constraint $$\sum _{i=0}^{m-1} \sum _{j=0}^{m-1} P_{{ij}} = 1$$ . The probabilities need not have any relation to the values of the slicing ratios. This concludes the first iteration of the construction of the multifractal measure. Figure 17.11 (left) illustrates the generation-1 construction for m = 3 and for the case where the H-slicing ratios and V-slicing ratios are both $$\{ \frac {1}{3}, \frac {1}{2} \}$$ .
../images/487758_1_En_17_Chapter/487758_1_En_17_Fig11_HTML.png
Figure 17.11

Generation-1 (left) and generation-2 (right) rectangles and their probabilities

The next iteration of the construction subdivides each of the m 2 generation 1 rectangles into m 2 smaller generation 2 rectangles, using the same H-slicing and V-slicing ratios. Let R ij be the generation 1 rectangle associated with the probability P ij, and let w and h be the width and height, respectively, of R ij. If, for example, the H-slicing ratios are $$\{ \frac {1}{3}, \frac {1}{2} \}$$ , then we slice R ij vertically at a distance of $$\frac {w}{3}$$ from the left-hand edge of R ij and again at a distance of $$\frac {w}{2}$$ from the left-hand edge of R ij. The horizontal slices of R ij are similarly obtained from the V-slicing ratios and h. At the end of the generation 2 construction the original unit square [0, 1]2 has been subdivided into m 2 × m 2 rectangles, denoted by $$R_{ij}^{(2)}$$ for i = 0, 1, 2, …, m 2 − 1 and j = 0, 1, 2, …, m 2 − 1. Let $$P_{ij}^{(2)}$$ be the probability associated with $$R_{ij}^{(2)}$$ . Figure 17.11 (right) illustrates the generation-2 construction, where for space considerations only some of the probabilities are indicated. For example, the rectangle R 20 with probability P 20 in Fig. 17.11 (left) is partitioned into 32 rectangles, whose probabilities are shown in Fig. 17.12.
../images/487758_1_En_17_Chapter/487758_1_En_17_Fig12_HTML.png
Figure 17.12

The second generation probabilities $$P_{20}^{(T)}$$

This construction can be continued indefinitely. For t = 2, 3, …, let $$\{ P_{ij}^{(T)} \}$$ be the probabilities after generation T. The formula for calculating these probabilities is [Horváth 13]
$$\displaystyle \begin{aligned} P_{ij}^{(T)} = \prod_{t=1}^T P_{{i_{{\, t}}} {j_{{\, t}}}} \end{aligned}$$
where
$$\displaystyle \begin{aligned} {i_{{\, t}}} = \left \lfloor \frac{i \; \; mod \; \; m^{T-t+1}}{ m^{T-t}} \right \rfloor \end{aligned}$$
and similarly for j t. Here, if a and b are positive integers, a mod b means the remainder when a is divided by b, so a mod b is an integer between 0 and b − 1.

After calculating the probabilities $$\{ P_{ij}^{(T)}\}$$ for a given set of H-slicing and V-slicing ratios, and for a given T, we are ready to generate the network. We follow the presentation in [Horváth 13] which assumed that the H-slicing ratios and the V-slicing ratios are the same. As illustrated in Fig. 17.11 (right), since the m T rectangles $$R_{0j}^{(T)}$$ , j = 0, 1, ⋯ , m T − 1 are adjacent to the bottom edge of [0, 1] × [0, 1] then the bottom edges of these m T rectangles cover the interval [0, 1]. Let $$\mathbb {N} = \{ 1, 2, \ldots , N \}$$ denote the set of nodes. For $$n \in {\mathbb {N}}$$ , generate a random number γ(n) from the uniform distribution on [0, 1]. Assume that the point $$\bigl ( \gamma (n), 0 \bigr )$$ lies in exactly one of the rectangles $$\{ P_{0j}^{(T)}\}$$ , j = 0, 1, ⋯ , m T − 1. In the unlikely case that $$\bigl ( \gamma (n), 0 \bigr )$$ belongs to two rectangles, pick another random number for γ(n). Let β(n) be the index such that γ(n) lies in the rectangle $$P_{0, {\beta (n)}}^{(T)}$$ . Since the indices i and j start at 0, then β(n) is between 0 and m T − 1. (For example, for T = 1 and using the H-slicing and V-slicing ratios of $$\{\frac {1}{3}, \frac {1}{2}\}$$ , if for some $$n \in \mathbb {N}$$ we pick the random number γ(n) = 0.04, then β(n) = 0; if γ(n) = 0.4, then β(n) = 1; if γ(n) = 0.6, then β(n) = 2.) Performing this calculation for each node, we obtain β(n) for $$n \in {\mathbb {N}}$$ .

Consider the pair of nodes $$x \in {\mathbb {N}}$$ and $$y \in {\mathbb {N}}$$ . To determine if x and y will be connected, generate a random number p from the uniform distribution on [0, 1]. If $$p \leq P_{ \beta (x), \beta (y) }^{(T)}$$ we connect x and y by an undirected arc; otherwise, we do not connect x and y. Doing this for each pair of nodes generates the desired network. It is possible that this construction leaves some nodes isolated, and refinements to the method of [Palla 10] have been proposed [Palla 11] to eliminate this possibility.

Letting $$A_{ij}^{(T)}$$ be the area of the rectangle whose probability is $$P_{ij}^{(T)}$$ , the average node degree 〈δ〉 of the network is given by [Palla 10]
$$\displaystyle \begin{aligned} \langle \delta \rangle = N \sum_{i=0}^{m^T - 1} \; \sum_{j=0}^{m^T - 1} P_{ij}^{(T)} A_{ij}^{(T)} \, . \end{aligned}$$
For the special case in which each rectangle has the same size, we have $$A_{ij}^{(T)} = m^{-2T}$$ and from the normalization constraint on the probabilities we obtain 〈δ〉 = Nm −2T. Thus, to keep 〈δ〉 constant as T increases, the number N of nodes must increase exponentially with T.

Exercise 17.3 Implement this network construction, using the same H-slicing and V-slicing ratios. (The use of Python and C++ to implement this network construction was examined in [Horváth 13].) For various values of N, how do the fractal dimensions d B, d I, and d C vary as a function of T? □

The method can be modified so that the randomly generated network also exhibits a specified property, e.g., a desired degree distribution. This can be accomplished by using a simulated annealing approach, which attempts to minimize a suitably defined “energy” function. In simulated annealing, a small random change is made to the configuration, and the change is accepted if it lowers the energy. If the change increases the energy, the change is accepted with probability e −δ∕τ, where δ is the calculated increase in energy (δ > 0) and τ is a temperature which is gradually reduced. As applied to the multifractal network generator, the random change moves a rectangle boundary or changes one of the P ij values (if a change to some P ij value is accepted, then P ji must be changed by the same amount).

As the size of the networks generated by this construction increases, the networks become “topologically more structured” [Palla 10]. However, no claim was made in [Palla 10] or in [Horváth 13] that the networks constructed by this method actually exhibit multifractality. Yet this possibility was raised in [Palla 10], which suggested that this construction “is likely to result in networks displaying aspects of self-similarity in the spirit of the related findings” by [Song 05].

17.4 Computational Results for Multifractal Networks

In [Wang 11], Random Sequential Node Burning (Sect. 8.​3) was applied to four classes of networks, to determine if multifractality is exhibited. Random (Erdős–Rényi), small-world, scale-free, and protein-protein interaction (PPI) networks were analyzed. For each network studied, K executions of Random Sequential Node Burning were performed for each r value from 1 to Δ, for a total of KΔ executions; K = 200 was used in [Wang 11]. After the k-th execution of Random Sequential Node Burning has terminated for a given r, for q ≠ 1 the partition sum $$Z_q(k,r) = \sum _{p_{{j}} \neq 0} ( p_{{j}} )^q$$ was calculated; for q = 1 the partition sum is $$Z_1(k,r) = \sum _{p_{{j}} \neq 0} p_{{j}} \log p_{{j}}$$ . Then, for each q, Z q(k, r) was averaged over the K iterations, yielding $$Z_q(r) = \frac {1}{K} \sum _{k=1}^K Z_q(k,r)$$ . For q ≠ 1, the estimate of D q is 1∕(q − 1) times the slope, as determined by linear regression, of the $$\log Z_q(r)$$ versus $$\log (r/\varDelta )$$ plot; for q = 1 the estimate of D q is the slope of the Z 1(r) versus $$\log (r/\varDelta )$$ plot. To assess the extent to which the network is multifractal, define D min ≡min−∞<q<∞D q and D max ≡max−∞<q<∞D q. Then $$\mathbb {G}$$ is multifractal if φ ≡ D max − D min is sufficiently large [Wang 11].

Erdős–Rényi random networks were generated by starting with N isolated nodes and connecting each pair of nodes with probability p. Since in general this can yield a disconnected network, the largest connected component (as determined by [Cytoscape]) was analyzed. For the nine networks studied, with N ranging from 449 to 5620, D max ∈ [2.42, 3.78], D min ∈ [2.14, 3.41], φ ∈ [0.28, 0.45], and there was no clear correlation between D q and N. The D q curve was found to be an increasing function of q for q < 0, and [Wang 11] cited other researchers who have observed, and offered explanations for, this “anomalous” behavior (this anomalous behavior was discussed in Sect. 17.2 above). From the φ values, [Wang 11] concluded that the multifractality of these networks is not clear-cut.

The small-world networks studied in [Wang 11] were generated using the Newman–Watts model [Newman 99b]. Let k be the desired node degree, where k is an even integer, and let p be a given probability. First, a regular ring lattice of N nodes was constructed: labeling the nodes n 0, n 1, …, n N−1, there is an undirected arc between nodes n i and n j if |i − j|≤ k∕2. For example, with N = 10 and k = 4, node n 5 is connected to nodes n 3, n 4, n 6, and n 7. Then each pair of nodes was connected with probability p; these are the shortcuts. For a set of eight networks with N = 5000, with k = 100, and with about 25, 000 arcs, both D min and D max were in the range [2.28, 3.08], and φ was in the narrow range [0.0, 0.06], so these networks were deemed not multifractal.

The scale-free networks studied in [Wang 11] were generated using an initial network of 5 nodes, to which nodes were added and arcs generated using preferential attachment (Sect. 2.​4). Ten networks were generated with sizes ranging from 500 nodes and 499 arcs to 8000 nodes and 5999 arcs. The values of D min were in the range [1.36, 2.11], and D min generally (not always) increased with N. The values of D max were in the range [2.67, 3.39], and D max also generally increased with N. The values D min and D max increased with N since larger scale-free networks typically have more hubs which make the network structure more complex. The values of φ were in the range [1.22, 1.52], and there was no correlation of φ with N. The large values of φ, especially compared with D min, clearly indicated multifractality, which was the expected result, since in a scale-free network the density of arcs around the hubs is larger than the density of arcs elsewhere in the network.

Finally, the giant components of seven protein-protein interaction networks were analyzed in [Wang 11]. The data came from the [BioGRID] database of protein and genetic interactions, and from the Database of Interacting Proteins [DIP]. The giant components ranged in size from 1298 nodes and 2767 arcs to 8934 nodes and 41, 341 arcs. The values of D min were in the range [1.49, 2.87], and D min generally (not always) increased with N. The values of D min were achieved for q = 20. The values of D max were in the range [2.51, 4.89], and D max also generally increased with N. The D max values for these real-world networks were significantly higher than for the other three network classes examined in this study. The values of φ were in the range [0.89, 2.98], and there was no correlation of φ and N. The large values of φ, especially compared with D min, clearly indicated multifractality.

Exercise 17.4 ⋆ Is it possible to develop a statistically sound test that uses the D q values to determine whether a network should be classified as monofractal or multifractal? □

Exercise 17.5 Using the network construction method of [Li 14] (Sect. 12.​1) with α = 0.1 and α = 0.8, plot D q for integer q ∈ [−10, 10]. □

17.5 Sandbox Method for Multifractal Networks

In Sect. 10.​5, we introduced the sandbox method as a way of approximating the Grassberger–Procaccia algorithm for computing d C of a collection of particles. The essence of the sandbox method is to determine the masses of a set of boxes with radius r and with randomly selected centers, average the box masses for each r, and determine how the average mass scales with r. In Sect. 11.​3, we showed that the cluster growing method for computing the correlation dimension d C of a network can be viewed as the sandbox method applied to a network. Then in Sect. 16.​6 we presented the sandbox method for estimating the generalized dimensions D q of a geometric object. The estimation is based on approximating the partition function value ∑j[p j(s)]q (where the sum is over all non-empty boxes in the covering by boxes of size s) by the sum $$\sum _{n \in \widetilde {\mathbb {X}}} [M(n,r)/N]^{q-1}$$ , where the sum is over a set $${\widetilde {\mathbb {X}}}$$ of randomly chosen sandbox centers. The next logical step, to apply the sandbox method to calculate the generalized dimensions of unweighted networks, was taken by [Liu 15], and we now review those results.

The method of [Liu 15] did not specify a rule on the number of random centers to pick: [Liu 15] used $$\widetilde {N} \equiv \vert {\widetilde {\mathbb {X}}} \vert = 1000$$ random nodes, but suggested that $$\widetilde {N}$$ can depend on N. For q ≠ 1, define
$$\displaystyle \begin{aligned} \textit{avg}\big( {M}_{q-1}(r) \big) \equiv (1/ \widetilde{N}) \sum_{n \in {\widetilde{\mathbb{X}}}} M(n, r)^{q-1} \, . \end{aligned}$$
To compute the sandbox dimension of order q (for q ≠ 1) of $${\mathbb {G}}$$ , [Liu 15] started with this definition of the sandbox dimension of a geometric object:
$$\displaystyle \begin{aligned} {D_{q}^{\, \stackrel{ {\textit{sandbox}}}{}}} &amp;\equiv \frac{1}{q-1} \lim_{r \rightarrow 0} \left\{ \log \left[ \frac{1}{\widetilde{N}} \sum_{n \in {\widetilde{\mathbb{X}}}} \left( \frac{M(n, r)}{N}\right)^{q-1} \right] \frac{1} {\log (r/\varDelta) } \right\} \\ &amp;= \frac{1}{q-1} \lim_{r \rightarrow 0} \left\{ \left[ \log \frac{\textit{avg}\big( {M}_{q-1}(r) \big) }{N^{q-1}} \right] \frac{1} {\log (r/\varDelta) } \right\} \, . {} \end{aligned} $$
(17.21)
Definition (17.21) differs from definition (16.​57) of the sandbox dimension function in that (17.21) employs a limit as r → 0 while (16.​57) does not. Interestingly, [Liu 15] characterized the sandbox method as “an extension of the box counting algorithm”. Definition (17.21) was then rewritten in the computationally more convenient form
$$\displaystyle \begin{aligned} \begin{array}{rcl} \log {\textit{avg}\big( {M}_{q-1}(r) \big) } \propto (q-1) {D_{q}^{\, \stackrel{ {\textit{sandbox}}}{}}} \log (r/\varDelta) + (q-1) \log N \, . {} \end{array} \end{aligned} $$
(17.22)
For a given q ≠ 1, the estimate of $$D_{q}^{\, \stackrel { {\textit {sandbox}}}{}}$$ in [Liu 15] is 1∕(q − 1) times the slope of the $$\log {\textit {avg}\big ( {M}_{q-1}(r) \big ) }$$ versus $$\log (r/\varDelta )$$ plot over a range of r values, and linear regression was used to obtain this slope. The mass exponent τ(q) (Sect. 16.​4) for q ≠ 1 was obtained using $$\tau (q) = (q-1) D_{q}^{\, \stackrel { {\textit {sandbox}}}{}}$$ .

In [Liu 15], the sandbox method was compared to compact box burning (Sect. 8.​5) and to a variant of the box-counting method. First the comparison was made for three models of deterministic graphs, including (u, v)-flower networks (Sect. 12.​2). For each of these models, the sandbox method CPU time was tiny compared to the other two methods. Plots in [Liu 15] showed that, for q ∈ [−10, 10], the three methods determined essentially identical estimates of τ(q) for each of the three network models. For all three network models, the plots of τ(q) versus q over the range q ∈ [−10, 10] were not quite linear, but rather were very slightly concave.

The sandbox method was also applied in [Liu 15] to three “real-world” network models. For scale-free networks constructed using the Barabási–Albert preferential attachment model [Barabási 99], $$D_{q}^{\, \stackrel { {\textit {sandbox}}}{}}$$ ranged from about D −10 ≈ 3.5 to D 10 ≈ 1.6 (although the $$D_{q}^{\, \stackrel { {\textit {sandbox}}}{}}$$ versus q curves in [Liu 15] were characterized as convex, they do not appear to be convex for q ∈ [−10, 10]). For small-world networks constructed using the Watts-Strogatz model [Newman 99b], $$D_{q}^{\, \stackrel { {\textit {sandbox}}}{}}$$ decreased only slightly as q increased, with D −10 ≈ 4.7 and D 10 ≈ 4.2 for N = 104. The conclusion in [Liu 15] was that multifractality of these small-world networks is not obvious. Finally, Erdős–Rényi random networks were constructed in which pairs of nodes were connected with small probabilities, and the largest connected component was analyzed. For these random networks, the $$D_{q}^{\, \stackrel { {\textit {sandbox}}}{}}$$ versus q plot was a straight line with slope zero, so the networks are monofractal.

It was inevitable that the sandbox method would next be applied to multifractal weighted networks, and that step was taken in [Song 15], which also used (17.22) to calculate $${D_{q}^{\, \stackrel { {\textit {sandbox}}}{}}}$$ . The difference between the method of [Song 15] and the method of [Liu 15] described above is that whereas [Liu 15] used integer values of r, [Song 15] used possibly non-integer r values that are determined by the arc lengths. Let c ij be the nonnegative length of the arc connecting nodes i and j, with c ii = 0 for each i, and assume symmetric lengths (c ij = c ji). To determine the set of radius values to be used, order the arc lengths from smallest to largest. Represent these ordered A ≡ N(N − 1)∕2 arc lengths by $$\{ {c_{{k}}} \}_{k=1}^{A}$$ , where $${{c_{{{k_{{1}}}}}}} \leq {{c_{{{k_{{2}}}}}}}$$ for k 1 < k 2. Let K be the largest index such that K ≤ A and $$\sum _{k=1}^K c_{{k}} \leq \varDelta $$ , where Δ is the network diameter. Then the radius values to be used are c 1, c 1 + c 2, …, $$\sum _{k=1}^K c_{{k}}$$ . (A similar method for computing radii values was described in Sect. 8.​2 on node coloring for weighted networks.) In [Song 15], using 1000 random sandbox centers and integer q ∈ [10, 10], linear regression was used to estimate $${D_{q}^{\, \stackrel { {\textit {sandbox}}}{}}}$$ for three large collaboration networks.

The sandbox method was applied in [Rendon 17] to a network of payments in Estonia. The nodes are companies, and there is an arc between two nodes if there was at least one transaction, in the year 2014, between the two companies. Multifractal analysis was performed on the skeleton $$\textit {skel}(\mathbb {G})$$ (Sect. 2.​5) rather than on $$\mathbb {G}$$ , since “by looking at the properties of the skeleton it is easier to appreciate the topological organization of the original network”. The skeleton $$\textit {skel}(\mathbb {G})$$ was computed using the arcs with the highest betweenness (Sect. 2.​4); the skeleton has diameter 34, compared to Δ = 29 for $$\mathbb {G}$$ . The box counting dimensions of $$\mathbb {G}$$ and $$\textit {skel}(\mathbb {G})$$ were nearly the same: 2.39 for $$\mathbb {G}$$ and 2.32 for $$\textit {skel}(\mathbb {G})$$ . The range of r used was 2–29, and the range of q was [−7, 12]. Since D q ≈ 7.8 for q ∈ [−7, −4.5], at which point D q decreased rapidly, and since minqD q = 0.37, the conclusion in [Rendon 17] was that the network is multifractal.

The sandbox method is not always successful: [Wang 11] found that the sandbox results did not yield a satisfactory fit for linear regression, and instead the results of Random Sequential Node Burning (Sect. 17.4) were averaged.

Exercise 17.6 In Sect. 16.​6 we presented the barycentric variant of the sandbox method. Is there any way to adapt this method to a network? □

Exercise 17.7 In Sect. 16.​6 we presented the recommendation in [Panico 95] that the calculations of the fractal dimension of an object should use measurements only from the interior of the object. Does this principle have applicability when calculating $$D_{q}^{\, \stackrel { {\textit {sandbox}}}{}}$$ for a growing network? □

Exercise 17.8 Does the fact that $$\mathbb {G}$$ and $$\textit {skel}(\mathbb {G})$$ have very similar box counting dimensions imply that the multifractal spectra of $$\mathbb {G}$$ and $$\textit {skel}(\mathbb {G})$$ are very similar? Run some experiments to find out. □