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

@misc{citeulike:1390521, abstract = {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 coloring 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 presented algorithms 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 1-week trip to our lab in New York (details in <a href="http://jamlab.org">this http URL</a>).}, archivePrefix = {arXiv}, author = {Song, Chaoming and Gallos, Lazaros K. and Havlin, Shlomo and Makse, Hernan A.}, citeulike-article-id = {1390521}, citeulike-linkout-0 = {http://arxiv.org/abs/cond-mat/0701216}, citeulike-linkout-1 = {http://arxiv.org/pdf/cond-mat/0701216}, day = {10}, eprint = {cond-mat/0701216}, keywords = {algorithm, complex\_network, dimension, fractal}, month = {Jan}, posted-at = {2007-06-14 19:23:42}, priority = {2}, title = {How to calculate the fractal dimension of a complex network: the box covering algorithm}, url = {http://arxiv.org/abs/cond-mat/0701216}, year = {2007} }

TY - ELEC ID - citeulike:1390521 L3 - citeulike-article-id:1390521 N2 - 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 coloring 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 presented algorithms 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 1-week trip to our lab in New York (details in <a href="http://jamlab.org">this http URL</a>). TI - How to calculate the fractal dimension of a complex network: the box covering algorithm KW - algorithm KW - complex_network KW - dimension KW - fractal AU - Song, Chaoming AU - Gallos, Lazaros AU - Havlin, Shlomo AU - Makse, Hernan PY - 2007/Jan/10/ UR - http://arxiv.org/abs/cond-mat/0701216 ER -