Box-covering algorithm for fractal dimension of complex networks

被引：57

作者：

Schneider, Christian M. ^{[1
,2
]}

Kesselring, Tobias A. ^{[1
]}

Andrade, Jose S., Jr. ^{[3
]}

Herrmann, Hans J. ^{[1
,3
]}

机构：

[1] ETH, Inst Bldg Mat, CH-8093 Zurich, Switzerland

[2] MIT, Dept Civil & Environm Engn, Cambridge, MA 02139 USA

[3] Univ Fed Ceara, Dept Fis, BR-60451970 Fortaleza, Ceara, Brazil

来源：

PHYSICAL REVIEW E | 2012年 / 86卷 / 01期

基金：

瑞士国家科学基金会;

关键词：

SELF-SIMILARITY;

D O I：

10.1103/PhysRevE.86.016707

中图分类号：

O35 [流体力学]; O53 [等离子体物理学];

学科分类号：

070204 ; 080103 ; 080704 ;

摘要：

The self-similarity of complex networks is typically investigated through computational algorithms, the primary task of which is to cover the structure with a minimal number of boxes. Here we introduce a box-covering algorithm that outperforms previous ones in most cases. For the two benchmark cases tested, namely, the E. coli and the World Wide Web (WWW) networks, our results show that the improvement can be rather substantial, reaching up to 15% in the case of the WWW network.

引用

页数：5

共 31 条

[1] Internet -: Diameter of the World-Wide Web [J].

Albert, R ;

Jeong, H ;

Barabási, AL .

NATURE, 1999, 401 (6749) :130-131

[2] Velocity and hierarchical spread of epidemic outbreaks in scale-free networks -: art. no. 178701 [J].

Barthélemy, M ;

Barrat, A ;

Pastor-Satorras, R ;

Vespignani, A .

PHYSICAL REVIEW LETTERS, 2004, 92 (17) :178701-1

[3] Small-world networks:: Evidence for a crossover picture (vol. 82, Pg. 3180, 1999) [J].

Barthélémy, M ;

Amaral, LAN .

PHYSICAL REVIEW LETTERS, 1999, 82 (25) :5180-5180

[4]

Bunde A., 1995, Fractals in Science

[5] Efficient immunization strategies for computer networks and populations [J].

Cohen, R ;

Havlin, S ;

ben-Avraham, D .

PHYSICAL REVIEW LETTERS, 2003, 91 (24)

[6]

Cormen T., 2001, Introduction to Algorithms

[7]

Feder J., 1988, Fractals

[8] Scaling theory of transport in complex biological networks [J].

Gallos, Lazaros K. ;

Song, Chaoming ;

Havlin, Shlomo ;

Makse, Hernan A. .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2007, 104 (19) :7746-7751

[9]

Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness

[10] Skeleton and fractal scaling in complex networks [J].

Goh, KI ;

Salvi, G ;

Kahng, B ;

Kim, D .

PHYSICAL REVIEW LETTERS, 2006, 96 (01)

← 1 2 3 4 →