Correlation dimension of complex networks

Abstract

We propose a new measure to characterize the dimension of complex networks based on the ergodic theory of dynamical systems. This measure is derived from the correlation sum of a trajectory generated by a random walker navigating the network, and extends the classical Grassberger-Procaccia algorithm to the context of complex networks. The method is validated with reliable results for both synthetic networks and real-world networks such as the world air-transportation network or urban networks, and provides a computationally fast way for estimating the dimensionality of networks which only relies on the local information provided by the walkers.

New version with a supplementary material attached, accepted for publication in Physical Review Letters

References in corpus (7)

• Maps of random walks on complex networks reveal community structure
• Spatial Networks
• Popularity versus Similarity in Growing Networks
• Sustaining the Internet with Hyperbolic Mapping
• How to calculate the fractal dimension of a complex network: the box covering algorithm
• Self-similarity of complex networks and hidden metric spaces
• Entropy Rate of Diffusion Processes on Complex Networks

Cited by in corpus (12)

• Information fractal dimension of mass function
• A new information dimension of complex networks
• Does the brain behave like a (complex) network? I. Dynamics
• Detecting the ultra low dimensionality of real networks
• Characteristic exponents of complex networks
• Multifractal Characterization of Protein Contact Networks
• Relative, local and global dimension in complex networks
• Connecting Network Science and Information Theory
• Concentric Network Symmetry
• Analytical estimation of the correlation dimension of integer lattices
• Strange Attractors in Complex Networks
• Correlation Dimension of Natural Language in a Statistical Manifold