Optimal traffic networks

被引:67
作者
Barthelemy, Marc
Flammini, Alessandro
机构
[1] Indiana Univ, Sch Informat, Bloomington, IN 47406 USA
[2] Indiana Univ, Biocomplex Ctr, Bloomington, IN 47406 USA
[3] Ctr Etud Bruyeres Le Chatel, CEA, Dept Phys Theor & Appl, F-91680 Bruyeres Le Chatel, France
来源
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT | 2006年
关键词
random graphs; networks; communication; supply and information networks;
D O I
10.1088/1742-5468/2006/07/L07002
中图分类号
O3 [力学];
学科分类号
08 ; 0801 ;
摘要
Inspired by studies on the airports' network and the physical Internet, we propose a general model of weighted networks via an optimization principle. The topology of the optimal network turns out to be a spanning tree that minimizes a combination of topological and metric quantities. It is characterized by strongly heterogeneous traffic, non-trivial correlations between distance and traffic and a broadly distributed centrality. A clear spatial hierarchical organization, with local hubs distributing traffic in smaller regions, emerges as a result of the optimization. Varying the parameters of the cost function, different classes of trees are recovered, including in particular the minimum spanning tree and the shortest path tree. These results suggest that a variational approach represents an alternative and possibly very meaningful path to the study of the structure of complex weighted networks.
引用
收藏
页数:8
相关论文
共 30 条
[1]  
Ahuja R.K., 1993, NETWORK FLOWS THEORY
[2]   Statistical mechanics of complex networks [J].
Albert, R ;
Barabási, AL .
REVIEWS OF MODERN PHYSICS, 2002, 74 (01) :47-97
[3]   Size and form in efficient transportation networks [J].
Banavar, JR ;
Maritan, A ;
Rinaldo, A .
NATURE, 1999, 399 (6732) :130-132
[4]   The effects of spatial constraints on the evolution of weighted complex networks -: art. no. P05003 [J].
Barrat, A ;
Barthélemy, M ;
Vespignani, A .
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2005, :49-68
[5]   The architecture of complex weighted networks [J].
Barrat, A ;
Barthélemy, M ;
Pastor-Satorras, R ;
Vespignani, A .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2004, 101 (11) :3747-3752
[6]   Correlated random networks -: art. no. 228701 [J].
Berg, J ;
Lässig, M .
PHYSICAL REVIEW LETTERS, 2002, 89 (22) :228701-228701
[7]  
Cancho RFI, 2003, LECT NOTES PHYS, V625, P114
[8]   Analytical and numerical study of optimal channel networks [J].
Colaiori, F ;
Flammini, A ;
Maritan, A ;
Banavar, JR .
PHYSICAL REVIEW E, 1997, 55 (02) :1298-1310
[9]   Network structures from selection principles [J].
Colizza, V ;
Banavar, JR ;
Maritan, A ;
Rinaldo, A .
PHYSICAL REVIEW LETTERS, 2004, 92 (19) :198701-1
[10]  
DOYLE PG, 1984, RANDOM WALKS ELECT N, P83