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

Abstract

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