How to calculate the fractal dimension of a complex network: the box covering algorithm
How to calculate the fractal dimension of a complex network: the box covering algorithm
复制标题
DOI：
10.1088/1742-5468/2007/03/p03006
复制
发表时间：
2007-03-01
影响因子：
2.4
通讯作者：
Makse, Hernan A.
中科院分区：
文献类型：
--
作者：
Song, Chaoming;Gallos, Lazaros K.;Makse, Hernan A.
用尽可能少的盒子覆盖网络可以揭示网络结构的有趣特征，特别是在自相似或分形特征方面。最近，随着许多真实的网络是自相似分形的发现，人们对这个问题给予了相当大的关注。在这里，我们提出，比较和详细研究了一些算法，我们已经在以前的论文中使用到这个目标。我们表明，这个问题可以映射到著名的图着色问题，然后我们可以简单地应用完善的算法。这似乎是最有效的方法，但我们也提出了其他两个算法的基础上燃烧，提供了一些其他的贝内。ts.我们认为，所提出的算法提供了一个接近最优的解决方案，另一种算法，可以显着改善这一结果，在一个有效的方式不存在。我们为找到这种方法的任何人提供一周的费用，以支付他/她前往我们在纽约的实验室的费用（详见http://jamlab.org）。
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 selfsimilar 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 bene. ts. 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).