A Survey of Fractal Dimensions of Networks

1. Front Matter

   Pages i-xi

   PDF

2. Introduction

   • Eric Rosenberg

   Pages 1-6

3. Covering a Complex Network

   • Eric Rosenberg

   Pages 7-11

4. Network Box Counting Heuristics

   • Eric Rosenberg

   Pages 13-27

5. Lower Bounds on Box Counting

   • Eric Rosenberg

   Pages 29-37

6. Correlation Dimension

   • Eric Rosenberg

   Pages 39-44

7. Mass Dimension for Infinite Networks

   • Eric Rosenberg

   Pages 45-50

8. Volume and Surface Dimensions for Infinite Networks

   • Eric Rosenberg

   Pages 51-54

9. Information Dimension

   • Eric Rosenberg

   Pages 55-59

10. Generalized Dimensions

    • Eric Rosenberg

    Pages 61-67

11. Non-monotonicity of Generalized Dimensions

    • Eric Rosenberg

    Pages 69-75

12. Zeta Dimension

    • Eric Rosenberg

    Pages 77-79

13. Back Matter

    Pages 81-84

    PDF

Many different fractal dimensions have been proposed for networks. In A Survey of Fractal Dimensions of Networks the theory and computation of the most important of these dimensions are reviewed, including the box counting dimension, the correlation dimension, the mass dimension, the transfinite fractal dimension, the information dimension, the generalized dimensions (which provide a way to describe multifractals), and the sandbox method (for approximating the generalized dimensions). The book describes the use of diameter-based and radius-based boxes, and presents several heuristic methods for box counting, including greedy coloring, random sequential node burning, and a method for computing a lower bound. We also discuss very recent results on resolving ambiguity in the calculation of the information dimension and the generalized dimensions, and on the non-monotonicity of the generalized dimensions. 


Anyone interested in the theory and application of networks will want to read this Brief. This includes anyone studying, e.g., social networks, telecommunications networks, transportation networks, ecological networks, food chain networks, network models of the brain, or financial networks.

• complex network
• fractal
• multifractal
• fractal dimensions
• box counting
• generalized dimensions
• correlation dimension
• information dimension
• entropy
• partition function
• graph coloring

“This book presents an updated survey on the fractal dimensions of networks. It focuses on the theory and computation of some important fractal dimensions such as box counting dimension, correlation dimension, mass dimension, transfinite fractal dimension, information dimension, and generalized dimension. The book is suitable for readers with some basic knowledge on limit, derivatives, shortest path algorithm, as well as duality theory in linear programming. There are plenty of figures and sketches throughout the book, which make it fairly readable.” (Yilun Shang, zbMath 1414.05001, 2019)

• AT&T Labs, Middletown, USA

  Eric Rosenberg

Eric Rosenberg received a B.A. in Mathematics from Oberlin College and a Ph.D. in Operations Research from Stanford University. He works at AT&T Labs in Middletown, New Jersey (email: ericr@att.com). Dr. Rosenberg has taught undergraduate and graduate courses in optimization at Princeton University and New Jersey Institute of Technology. He has authored or co-authored 17 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 Briefs in Computer Science, 2012).

Policies and ethics