Eric Rosenberg

Fractal Dimensions of Networks

Eric Rosenberg
AT&T Labs, Middletown, NJ, USA
ISBN 978-3-030-43168-6e-ISBN 978-3-030-43169-3
https://doi.org/10.1007/978-3-030-43169-3
© Springer Nature Switzerland AG 2020
This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed.
The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use.
The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This Springer imprint is published by the registered company Springer Nature Switzerland AG.

The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland

To David and Alexa

Acknowledgements

I gratefully acknowledge the comments and suggestions of Lazaros Gallos, Robert Kelley, Robert Murray, Erin Pearse, Curtis Provost, and Brendan Ruskey. Special thanks to Ron Levine for slogging through an early draft of this book and providing enormously helpful feedback. I am of course responsible for any remaining mistakes in this book, and I welcome corrections from readers: send email to FractalDimensionsOfNetworks@gmail.com. Many thanks to the artist Jug Cerovic for providing permission to reproduce their artwork, a beautiful map of the New York City subway system, in the cover of this book. Finally, many thanks to Paul Drougas, Senior Editor at Springer, for his encouragement and support.

Contents
1 Introduction 1
1.​1 Intended Readership 8
1.​2 Notation and Terminology 9
2 Networks:​ Introductory Material 17
2.​1 Basic Network Definitions 17
2.​2 Small-World Networks 25
2.​3 Random Networks 32
2.​4 Scale-Free Networks 33
2.​5 Skeleton of a Network 40
3 Fractals:​ Introductory Material 43
3.​1 Introduction to Fractals 43
3.​2 Fractals and Power Laws 49
3.​3 Iterated Function Systems 51
3.​4 Convergence of an IFS 54
4 Topological and Box Counting Dimensions 61
4.​1 Topological Dimension 61
4.​2 Box Counting Dimension 67
4.​3 A Deeper Dive into Box Counting 73
4.​4 Fuzzy Fractal Dimension 77
4.​5 Minkowski Dimension 78
5 Hausdorff, Similarity, and Packing Dimensions 83
5.​1 Hausdorff Dimension 84
5.​2 Similarity Dimension 89
5.​3 Fractal Trees and Tilings from an IFS 96
5.​4 Packing Dimension 99
5.​5 When Is an Object Fractal?​ 103
6 Computing the Box Counting Dimension 107
6.​1 Lower and Upper Box Sizes 107
6.​2 Computing the Minimal Box Size 111
6.​3 Coarse and Fine Grids 115
6.​4 Box Counting Dimension of a Spiral 119
6.​5 Some Applications of the Box Counting Dimension 122
7 Network Box Counting Dimension 131
7.​1 Node Coverings and Arc Coverings 132
7.​2 Diameter-Based and Radius-Based Boxes 135
7.​3 A Closer Look at Network Coverings 140
7.​4 The Origin of Fractal Networks 143
8 Network Box Counting Heuristics 145
8.​1 Node Coloring Formulation 145
8.​2 Node Coloring for Weighted Networks 148
8.​3 Random Sequential Node Burning 150
8.​4 Set Covering Formulation and a Greedy Method 154
8.​5 Box Burning 157
8.​6 Box Counting for Scale-Free Networks 161
8.​7 Other Box Counting Methods 163
8.​8 Lower Bounds on Box Counting 165
9 Correlation Dimension 177
9.​1 Dynamical Systems 177
9.​2 Pointwise Mass Dimension 182
9.​3 The Correlation Sum 183
9.​4 The Correlation Dimension 186
9.​5 Comparison with the Box Counting Dimension 191
10 Computing the Correlation Dimension 195
10.​1 How Many Points are Needed?​ 195
10.​2 Analysis of Time Series 201
10.​3 Constant Memory Implementation 204
10.​4 Applications of the Correlation Dimension 205
10.​5 The Sandbox Dimension 217
11 Network Correlation Dimension 221
11.​1 Basic Definitions 222
11.​2 Variants of the Correlation Dimension 226
11.​3 Cluster Growing and Random Walks 230
11.​4 Overall Slope Correlation Dimension 234
11.​5 Comparing the Box Counting and Correlation Dimensions 243
11.​6 Generalized Correlation Dimension 245
12 Dimensions of Infinite Networks 247
12.​1 Mass Dimension 249
12.​2 Transfractal Networks 253
12.​3 Volume and Surface Dimensions 256
12.​4 Conical Graphs with Prescribed Dimension 262
12.​5 Dimension of a Percolating Network 265
13 Similarity Dimension of Infinite Networks 267
13.​1 Generating Networks from an IFS 270
13.​2 Analysis of the Infinite Sequence 272
14 Information Dimension 279
14.​1 Shannon Entropy and Hartley Entropy 280
14.​2 Dimension of a Probability Distribution 286
14.​3 Information Dimension Bounds the Correlation Dimension 290
14.​4 Fixed Mass Approach 295
14.​5 Rényi and Tsallis Entropy 297
14.​6 Applications of the Information Dimension 300
15 Network Information Dimension 305
15.​1 Entropy of a Node and a Network 305
15.​2 Defining the Network Information Dimension 311
15.​3 Comparison with the Box Counting Dimension 317
15.​4 Maximal Entropy Minimal Coverings 318
15.​5 Binning 324
16 Generalized Dimensions and Multifractals 325
16.​1 Multifractal Cantor Set 327
16.​2 Generalized Dimensions 329
16.​3 Spectrum of the Multifractal Cantor Set 333
16.​4 Spectrum of a Multifractal 338
16.​5 Computing the Multifractal Spectrum and Generalized Dimensions 346
16.​6 The Sandbox Method for Geometric Multifractals 353
16.​7 Particle Counting Dimension 359
16.​8 Applications of Multifractals 361
16.​9 Generalized Hausdorff Dimensions 363
17 Multifractal Networks 365
17.​1 Lexico Minimal Coverings 365
17.​2 Non-monotonicity of the Generalized Dimensions 373
17.​3 Multifractal Network Generator 383
17.​4 Computational Results for Multifractal Networks 386
17.​5 Sandbox Method for Multifractal Networks 388
18 Generalized Hausdorff Dimensions of Networks 391
18.​1 Defining the Hausdorff Dimension of a Network 391
18.​2 Computing the Hausdorff Dimension of a Network 396
18.​3 Generalized Hausdorff Dimensions of a Network 407
19 Lacunarity 413
19.​1 Gliding Box Method 415
19.​2 Lacunarity Based on an Optimal Covering 420
19.​3 Applications of Lacunarity 421
20 Other Dimensions 425
20.​1 Spectral Dimension 425
20.​2 Lyapunov Dimension 427
20.​3 Three More Dimensions 429
20.​4 Uses and Abuses of Fractal Dimensions 431
21 Coarse Graining and Renormalization 437
21.​1 Renormalization Basics 438
21.​2 Renormalizing a Small-World Network 442
21.​3 Renormalizing Unweighted, Undirected Networks 445
21.​4 Renormalization of Scale-Free Networks 448
21.​5 Universality Classes for Networks 452
22 Other Network Dimensions 455
22.​1 Dimension of a Tree 455
22.​2 Area-Length Dimension 457
22.​3 Metric Dimension 458
22.​4 Embedding Dimension 459
22.​5 Zeta Dimension 461
22.​6 Dimensions Relating to Graph Curvature 465
22.​7 Spectral Dimension of Networks 467
22.​8 Other Avenues 468
23 Supplemental Material 471
23.​1 Rectifiable Arcs and Arc Length 471
23.​2 The Gamma Function and Hypersphere Volumes 473
23.​3 Laplace’s Method of Steepest Descent 474
23.​4 Stirling’s Approximation 475
23.​5 Convex Functions and the Legendre Transform 476
23.​6 Graph Spectra 480
Bibliography 485
Index 517
List of Figures
1.1 Four generations of the Sierpiński triangle evolution3
 
1.2 Convex and concave functions11
 
2.1 Complete graphs K 4 and K 5 20
 
2.2 Arc betweenness22
 
2.3 Network motifs23
 
2.4 Closing in on the target27
 
2.5 Regular lattice with N = 16 and k = 428
 
2.6 Commellas and Sampels first construction for N = 6 and k = 431
 
2.7 Preferential attachment35
 
2.8 IP alias resolution38
 
2.9 ATM cloud38
 
3.1 Length of the coast of Britain44
 
3.2 Three generations of the Cantor set46
 
3.3 IFS for the Sierpiński triangle52
 
3.4 Another IFS for the Sierpiński triangle53
 
3.5 The L 1, L 2, and L ∞ metrics55
 
3.6 Illustration of Hausdorff distance56
 
4.1 A set that is open, and a set that is not open63
 
4.2 Covering of a square by six open sets64
 
4.3 Line segment has d T = 165
 
4.4 Topological dimension of a square65
 
4.5 Covering a square by 4 sets66
 
4.6 Box counting for a line and for a square67
 
4.7 3E boxes cover the set69
 
4.8 Starfish box counting71
 
4.9 Six iterations of the Hilbert curve73
 
4.10 Two generations of the Sierpiński carpet74
 
4.11 Randomized Sierpiński carpet75
 
4.12 Cantor dust76
 
4.13 Minkowski sausage in two dimensions79
 
4.14 astrocytes82
 
5.1 Self-similarity with K = 8 and α = 1∕490
 
5.2 Three generations of a self-similar fractal90
 
5.3 Sierpiński triangle95
 
5.4 The Open Set Condition for the Sierpiński gasket95
 
5.5 Sinuosity generator $${\mathcal {I}}_U$$ based on the Koch fractal96
 
5.6 Topology generator $${\mathcal {I}}_T$$ 97
 
5.7 $${\mathcal {I}} \equiv {\mathcal {I}}_U {\mathcal {I}}_T$$ applied to a straight line initiator97
 
5.8 IFS for goose down98
 
5.9 Packing the diamond region with four balls100
 
5.10 Packing a square with long skinny rectangles100
 
5.11 Constructing the Lévy curve104
 
5.12 The Lévy curve after 12 iterations105
 
5.13 Pythagoras tree after 15 iterations105
 
6.1 Maximal box size for the Sierpiński carpet110
 
6.2 s max is reached when B(s max) = 1110
 
6.3 Python code for binary search114
 
6.4 % error in s min for N = 1000 and 𝜖 = 0.001, for 1 ≤ d B ≤ 2114
 
6.5 s min for N = 1000 and for three values of 𝜖, for 1 ≤ d B ≤ 2115
 
6.6 Coarse-grained and fine-grained images of clover116
 
6.7 Spiral (left) and spiral and line (right)119
 
6.8 Spiral radius for J = 4120
 
6.9 Clothoid double spiral122
 
7.1 A node 3-covering (i) and an arc 3-covering (ii)133
 
7.2 Arc s-coverings for s = 2, 3, 4134
 
7.3 A node covering which is not an arc covering134
 
7.4 An arc covering which is not a node covering134
 
7.5 Comparing B N(2) and B A(2)135
 
7.6 Optimal B D  (3) box (left), and optimal B D  (5) and B D  (7) boxes (right)136
 
7.7 Diameter-based versus radius-based boxes137
 
7.8 Frequent associations among 62 dolphins138
 
7.9 Node degrees for the dolphins network139
 
7.10 Diameter-based box counting results for the dolphins network139
 
7.11 Chain network140
 
7.12 $$\log \widetilde {B}(s)$$ versus $$\log s$$ using wide boxes140
 
7.13 Radius-based box141
 
7.14 Covering a 6 × 6 grid142
 
7.15 Fractal versus non-fractal scaling143
 
8.1 Example network for node coloring146
 
8.2 (i) Auxiliary graph with s=3, and (ii) its coloring146
 
8.3 Minimal covering for s = 3147
 
8.4 (i) Auxiliary graph with s=4, and (ii) minimalcovering for s=4147
 
8.5 A weighted network148
 
8.6 Auxiliary graph for box size s 1 = 0.85149
 
8.7 Two boxes are required for box size s 1 149
 
8.8 USAir97 network150
 
8.9 Random Sequential Node Burning 151
 
8.10 Covering using Random Sequential Node Burning 152
 
8.11 Random Sequential Node Burning applied to a hub and spoke network153
 
8.12 Double ring hub and spoke network153
 
8.13 Network with 7 nodes and 8 arcs154
 
8.14 Maximum Excluded Mass Burning 156
 
8.15 Box Burning 157
 
8.16 Network for illustrating box burning158
 
8.17 Box burning 2-covering and a minimal 2-covering158
 
8.18 Disconnected boxes in a minimal covering159
 
8.19 Compact Box Burning 160
 
8.20 Adjacent nodes only connected through a hub162
 
8.21 Overlapping boxes163
 
8.22 Example network with 7 nodes and 8 arcs166
 
8.23 Increasing u i to 1 blocks other dual variable increases169
 
8.24 Results of applying Dual Ascent to Zachary’s Karate Club network169
 
8.25 Closing nodes in Zachary’s Karate Club network172
 
8.26 Linear program results for Lada Adamic’s social network 174
 
8.27 BCLP is infeasible for C. elegans 174
 
10.1 Embedding dimension202
 
10.2 Packing of powder particles207
 
10.3 Radius of gyration216
 
11.1 1-dimensional grid with 8 nodes224
 
11.2 1-dimensional grid with K = 100225
 
11.3 Three examples of a Voronoi tessellation229
 
11.4 $${\mathbb {N}}^0_k({n})$$ for k = 0, 1, 2231
 
11.5 A hub and spoke network233
 
11.6 Non-truncated and truncated boxes in a 2-dimensional grid235
 
11.7 Neighbors in a 6 × 6 grid236
 
11.8 Correlation dimension of K × K grid versus K 239
 
11.9 Correlation dimension of K × K × K grid versus log10K 242
 
11.10 Triangulated hexagon243
 
12.1 Constructing $${\mathbb {G}}_{t+1}$$ from $${\mathbb {G}}_{t}$$ 249
 
12.2 Three generations with p = 1250
 
12.3 Three generations with p = 0250
 
12.4 $$\mathbb {G}_0$$ and $$\mathbb {G}_1$$ for x = 2 and m = 3252
 
12.5 $$\mathbb {G}_0$$ and $$\mathbb {G}_1$$ and $$\mathbb {G}_2$$ for α = 0 and x = 2 and m = 2253
 
12.6 Three generations of a (1, 3)-flower254
 
12.7 Construction of a conical graph for which d V(n ⋆) = 5∕3263
 
13.1 A network (i) and two ways to interconnect K copies (ii)268
 
13.2 $${\mathbb {G}}_0$$ has four border nodes268
 
13.3 Constructing $${\mathbb {G}}_2$$ from $${\mathbb {G}}_1$$ 269
 
13.4 Generating a network from the Maltese cross fractal270
 
13.5 A network satisfying Assumption 13.2 but not Assumption 13.3272
 
13.6 $${\mathbb {G}}_1$$ and $${\mathbb {G}}_2$$ for a chain network273
 
13.7 Another example of $${\mathbb {G}}_0$$ and $${\mathbb {G}}_1$$ 274
 
13.8 Ω 0 and $${\mathbb {G}}_0$$ for the Maltese cross274
 
13.9 Two invalid choices of Ω 0 275
 
13.10 Example for which 2R 0 + 1≠1∕α 275
 
13.11 $${\mathbb {G}}_0$$ has no center node277
 
13.12 Network generator $${\mathbb {G}}_0$$ (left) and $${\mathbb {G}}_2$$ (right)278
 
14.1 Shannon entropy for the distribution (p, 1 − p)282
 
14.2 Farmer’s shades of grey example290
 
14.3 H q versus q for four values of p 298
 
15.1 Networks (i) and (ii)308
 
15.2 Networks (iii) and (iv)308
 
15.3 Hub and spoke with a tail network314
 
15.4 Coverings for K = 6, for s = 3 and s = 5314
 
15.5 Results for the hub and spoke with a tail network316
 
15.6 Three hubs connected to a superhub316
 
15.7 $$\log B(s)$$ and H(s) for the hub and spoke with a tail network317
 
15.8 Network for which d I > d B: minimal coverings for s = 2 and s = 3318
 
15.9 Maximal entropy minimal 3-covering319
 
15.10 Erdős–Rényi network320
 
15.11 Results for the Erdős–Rényi network321
 
15.12 Results for the jazz network322
 
15.13 Results for Lada Adamic’s social network 322
 
15.14 Communications network323
 
15.15 Results for the communications network323
 
16.1 Two generations in a multifractal construction326
 
16.2 Generation 1 of the multifractal Cantor set327
 
16.3 Four generations of the multifractal Cantor set for p 1 = 0.2328
 
16.4 Logarithm of generation 4 probabilities for p 1 = 0.2329
 
16.5 Generalized dimensions of the multifractal Cantor set332
 
16.6 f q versus p 1 for the multifractal Cantor set336
 
16.7 f(α) spectrum for the multifractal Cantor set337
 
16.8 Geometry of the Legendre transform of f(α)344
 
16.9 The six points in the unit square349
 
16.10 Specifying to which box the boundaries belong350
 
16.11 Nine points covered by two boxes354
 
16.12 Two generations of the Tél-Viscek multifractal359
 
17.1 Two minimal 3-coverings and a minimal 2-covering for the chair network367
 
17.2 D ∞ for three networks372
 
17.3 Two plots of the generalized dimensions of the chair network374
 
17.4 Box counting and $$\log Z\big (x(s), q\big )$$ versus $$\log (s/\varDelta )$$ for the dolphins network375
 
17.5 Secant estimate of D q for the dolphins network for different L and U 376
 
17.6 $$\log R(s)$$ versus $$\log s$$ for the dolphins network381
 
17.7 jazz box counting (left) and D q versus q for variousL, U (right)381
 
17.8 Local minimum and maximum of D q for the jazz network and L = 4, U = 5382
 
17.9 $$\log R(s)$$ versus $$\log s$$ for the jazz network382
 
17.10 C. elegans box counting (left) and D q(L, U) versus q for various L, U (right)382
 
17.11 Generation-1 (left) and generation-2 (right) rectangles and their probabilities384
 
17.12 The second generation probabilities $$P_{20}^{(T)}$$ 385
 
18.1 Two minimal 3-coverings of a 7 node chain394
 
18.2 chair network (left) and d H calculation (right)397
 
18.3 Two 7 node networks with the same d B but different d H 397
 
18.4 Box counting results for s = 2 (left) and s = 3 (right)398
 
18.5 Box of radius r = 1 in a 6 × 6 rectilinear grid399
 
18.6 $$\log B(s)$$ versus $$\log s$$ for the dolphins network400
 
18.7 B(s)[s∕(Δ + 1)]d versus d for $$s \in \mathcal {S}$$ (left) and $$m({\mathbb {G}}, s, d)$$ versus d (right) for dolphins 400
 
18.8 $$\sigma ({\mathbb {G}}, {\mathcal {S}}, d)$$ versus d for dolphins for d ∈ [0, 3] (left) and d ∈ [2.26, 2.40] (right)401
 
18.9 $$\log B(s)$$ versus $$\log s$$ for the USAir97 network402
 
18.10 $$\log B(s)$$ versus $$\log s$$ (left) and $$m({\mathbb {G}}, s, d)$$ versus d (right) for the jazz network402
 
18.11 $$\log B(s)$$ versus $$\log s$$ (left) and $$m({\mathbb {G}}, s, d)$$ versus d (right) for the C. elegans network403
 
18.12 $$\sigma ({\mathbb {G}}, {\mathcal {S}}, d)$$ versus d for C. elegans for d ∈ [0, 5] (left) and d ∈ [2.26, 2.40] (right)404
 
18.13 $$\log B(s)$$ versus $$\log s$$ for s ∈ [4, 14] for the protein network404
 
18.14 Summary of d B and d H computations405
 
18.15 Perturbations of the jazz network406
 
18.16 d B and d H of a network growing with preferential attachment406
 
18.17 $$D_q^H$$ versus q for the network $${\mathbb {G}}_1$$ of Fig. 18.3409
 
18.18 $$D_q^H$$ versus q for the dolphins network409
 
18.19 $$D_q^H$$ versus q for the jazz network410
 
18.20 $$D_q^H$$ versus q for the C. elegans network410
 
19.1 Cantor dust lacunarity414
 
19.2 Lacunarity for a Cantor set414
 
19.3 Gliding box method for the top row416
 
19.4 Gliding box example continued416
 
19.5 Three degrees of lacunarity417
 
19.6 Lacunarity with three hierarchy levels418
 
19.7 A covering of Ω by balls420
 
19.8 Ω is partitioned into 16 identical smaller pieces424
 
20.1 Lyapunov numbers427
 
20.2 F maps a square to a parallelogram428
 
20.3 Cell structure432
 
21.1 Kadanoff’s block renormalization441
 
21.2 Renormalizing the small-world model for k = 1443
 
21.3 Two-site scaling446
 
21.4 Two different minimal 3-coverings of the same network447
 
21.5 Procedure Network Renormalization 447
 
21.6 Network renormalization with diameter-based boxes448
 
22.1 Horton’s ordering of streams455
 
22.2 Metric dimension example458
 
22.3 Tetrahedron and cube460
 
22.4 Wheel network and complete bicolored graph460
 
22.5 Computing $$S_r^E$$ by summing over cross sections463
 
22.6 Two-dimensional triangular lattice $$\mathcal {L}$$ 465
 
22.7 A finite graph $$\mathbb {G}$$ embedded in $$\mathcal {L}$$ 466
 
22.8 1-dimensional (left) and 2-dimensional (right) graphs466
 
22.9 A tree whose nodes have degree 1 or 3469
 
23.1 Rectifiable Arc472
 
23.2 Computing the length of a rectifiable arc472
 
23.3 A differentiable convex function lies above each tangent line477
 
23.4 Two supporting hyperplanes of a convex function477
 
23.5 The Legendre transform G of F 478
 
23.6 The conjugate F ⋆ of F 479
 
23.7 Small network to illustrate Hall’s method481
 
23.8 Small hub and spoke network483
 
About the Author
Eric Rosenberg

received a B.A. in Mathematics from Oberlin College and a Ph.D. in Operations Research from Stanford University. He recently retired from AT&T Labs in Middletown, New Jersey, and has joined the faculty of Georgian Court University in New Jersey. Dr. Rosenberg has taught undergraduate and graduate courses in modeling and optimization at Princeton University, New Jersey Institute of Technology, and Rutgers University. He has authored or co-authored 19 patents and has published in the areas of convex analysis and nonlinearly constrained optimization, computer-aided design of integrated circuits and printed wire boards, telecommunications network design and routing, and fractal dimensions of networks. He is the author of A Primer of Multicast Routing (Springer, 2012) and A Survey of Fractal Dimensions of Networks (Springer, 2018).