How to calculate the fractal dimension of a complex network: the box covering algorithm

By Chaoming Song, Lazaros K. Gallos, Shlomo Havlin, Hernán A. Makse. 2007

309 citations recorded by the source corpus.

Covering a network with the minimum possible number of boxes can reveal interesting features for the network structure, especially in terms of self-similar or fractal characteristics. Considerable attention has been recently devoted to this problem, with the finding that many real networks are self-similar fractals. Here we present, compare and study in detail a number of algorithms that we have used in previous papers towards this goal. We show that this problem can be mapped to the well-known graph colouring problem and then we simply can apply well-established algorithms. This seems to be the most efficient method, but we also present two other algorithms based on burning which provide a number of other benefits. We argue that the algorithms presented provide a solution close to optimal and that another algorithm that can significantly improve this result in an efficient way does not exist. We offer to anyone that finds such a method to cover his/her expenses for a one-week trip to our lab in New York (details in http://jamlab.org).

Subfields: Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/78e9b5ae3243c3bda29b874f7ec9d0d277dd370a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Statistical and Nonlinear Physics

Citations in the corpus

Critical phenomena in complex networks (2007, methodology): “For description of these networks, see Song et al. (2005, 2006, 2007) and also Goh et al. (2006).”