Special Issue: "Empirical Applications of Complex Systems Methodologies in Econcomics and Geography"; Guest Eds. K. Frenken (Utrecht University, The Netherlands) & G. Silverberg (IIASA, Austria & UNU-MERIT, The Netherlands)No Access

THE ROLE OF GEOGRAPHY AND TRAFFIC IN THE STRUCTURE OF COMPLEX NETWORKS

MARC BARTHÉLEMY

School of Informatics and Biocomplexity Center, Indiana University, Bloomington, IN 47406, USA

On leave of absence from CEA — Centre d'Etudes de Bruyères-le-Châtel, Département de Physique Théorique et Appliquée BP12, 91680 Bruyères-Le-Châtel, France.

Search for more papers by this author

ALAIN BARRAT

Laboratoire de Physique Théorique (UMR du CNRS 8627), Bâtiment 210, Université de Paris-Sud 91405 Orsay, France

Search for more papers by this author

, and

ALESSANDRO VESPIGNANI

School of Informatics and Biocomplexity Center, Indiana University, Bloomington, IN 47406, USA

Search for more papers by this author

https://doi.org/10.1142/S021952590700091XCited by:9 (Source: Crossref)

Abstract

We report a study of the correlations among topological, weighted and spatial properties of large infrastructure networks. We review the empirical results obtained for the air-transportation infrastructure that motivates a network modeling approach which integrates the various attributes of this network. In particular, we describe a class of models which include a weight-topology coupling and the introduction of geographical attributes during the network evolution. The inclusion of spatial features is able to capture the appearance of non-trivial correlations between the traffic flows, the connectivity pattern and the actual distances of vertices. The anomalous fluctuations in the betweenness-degree correlation function observed in empirical studies are also recovered in the model. The presented results suggest that the interplay between topology, weights and geographical constraints is a key ingredient in order to understand the structure and evolution of many real-world networks.

Keywords:

References

R. Albert, H. Jeong and A.-L. Barabási, Nature 406, 378 (2000), DOI: 10.1038/35019019. Web of Science, Google Scholar
R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47 (2002), DOI: 10.1103/RevModPhys.74.47. Web of Science, Google Scholar
E. Almaaset al., Nature 427, 839 (2004), DOI: 10.1038/nature02289. Web of Science, Google Scholar
L. A. N. Amaralet al., Proc. Natl. Acad. Sci. (USA) 97, 11149 (2000), DOI: 10.1073/pnas.200327197. Web of Science, Google Scholar
C. Andersson, A. Hellervik and K. Lindgren, Physica A 227, 345 (2005). Google Scholar
A.-L. Barabási and R. Albert, Science 286, 509 (1999), DOI: 10.1126/science.286.5439.509. Web of Science, Google Scholar
A. Barratet al., Proc. Natl. Acad. Sci. (USA) 101, 3747 (2004), DOI: 10.1073/pnas.0400087101. Web of Science, Google Scholar
A. Barrat, M. Barthélemy and A. Vespignani, Phys. Rev. Lett. 92, 228701 (2004), DOI: 10.1103/PhysRevLett.92.228701. Web of Science, Google Scholar
A. Barrat, M. Barthélemy and A. Vespignani, Phys. Rev. E 70, 066149 (2004), DOI: 10.1103/PhysRevE.70.066149. Web of Science, Google Scholar
A. Barrat, M. Barthélemy and A. Vespignani, Lecture Notes in Computer Science 3243 (Springer, 2004) p. 56. Google Scholar
A. Barrat and R. Pastor-Satorras, Phys. Rev. E 71, 036127 (2005), DOI: 10.1103/PhysRevE.71.036127. Web of Science, Google Scholar
M. Barthélemy, B. Gondran and E. Guichard, Physica A 319, 633 (2003), DOI: 10.1016/S0378-4371(02)01382-1. Web of Science, Google Scholar
M. Barthélemy, Europhys. Lett. 63, 915 (2003), DOI: 10.1209/epl/i2003-00600-6. Google Scholar
M. Barthélemy, Euro. Phys. J. B 38, 163 (2003), DOI: 10.1140/epjb/e2004-00111-4. Web of Science, Google Scholar
R. Cohenet al., Phys. Rev. Lett. 85, 4626 (2000), DOI: 10.1103/PhysRevLett.85.4626. Web of Science, Google Scholar
B. Derrida and H. Flyvbjerg, J. Phys. A 20, 5273 (1987), DOI: 10.1088/0305-4470/20/15/039. Google Scholar
S. N. Dorogovtsev and J. F. F. Mendes , Evolution of Networks: From Biological Nets to the Internet and WWW ( Oxford University Press , Oxford , 2003 ) . Google Scholar
L. C. Freeman, Sociometry 40, 35 (1977), DOI: 10.2307/3033543. Google Scholar
D. Garlaschelliet al., Physica A 350, 491 (2005), DOI: 10.1016/j.physa.2004.11.040. Web of Science, Google Scholar
Gastner, M. T. and Newman, M. E. J., The spatial structure of networks , cond-mat/0407680 . Google Scholar
Gastner, M. T. and Newman, M. E. J., Shape and efficiency in spatial distribution networks , cond-mat/0409702 . Google Scholar
K.-I. Goh, B. Kahng and D. Kim, Phys. Rev. Lett. 87, 278701 (2001), DOI: 10.1103/PhysRevLett.87.278701. Web of Science, Google Scholar
S. P. Gorman and R. Kulkarni, Environment and Planning Journal B (2003). Google Scholar
M. Granovetter, Am. J. Sociology 78(6), 1360 (1973), DOI: 10.1086/225469. Web of Science, Google Scholar
R. Guimerà and L. A. N. Amaral, Euro. Phys. J. B 38, 381 (2004), DOI: 10.1140/epjb/e2004-00131-0. Web of Science, Google Scholar
R. Guimeràet al., Proc. Natl. Acad. Sci. (USA) 102, 7794 (2005), DOI: 10.1073/pnas.0407994102. Web of Science, Google Scholar
Helmy, A., Small large-scale wireless networks: Mobility-assisted resource discovery , cs.NI/0207069 . Google Scholar
International Air Transport Association, http://www.iata.org . Google Scholar
A. E. Krauseet al., Nature 426, 282 (2003), DOI: 10.1038/nature02115. Web of Science, Google Scholar
Lakhina, A., Byers, J. B., Crovella, M. and Matta, I., On the geographic location of Internet resources, technical report, online version available at: http://www.cs.bu.edu/techreports/pdf/2002-015-internet-geography.pdf' . Google Scholar
W. Li and X. Cai, Phys. Rev. E 69, 046106 (2004), DOI: 10.1103/PhysRevE.69.046106. Web of Science, Google Scholar
Li, C. and Chen, G., Network connection strength: Another power-law?, (2003) , cond-mat/0311333 . Google Scholar
S. S. Manna and P. Sen, Phys. Rev. E 66, 066114 (2002), DOI: 10.1103/PhysRevE.66.066114. Web of Science, Google Scholar
N. Masuda, H. Miwa and N. Konno, Phys. Rev. E 71, 036108 (2005), DOI: 10.1103/PhysRevE.71.036108. Web of Science, Google Scholar
M. Molloy and B. Reed, Random Struct. Algorithms 6, 161 (1995). Web of Science, Google Scholar
Mukherjee, G. and Manna, S. S., Growing spatial scale-free graphs by selecting local edges , cond-mat/0503697 . Google Scholar
G. Nemeth and G. Vattay, Phys. Rev. E 67, 036110 (2003), DOI: 10.1103/PhysRevE.67.036110. Web of Science, Google Scholar
D. S. Callawayet al., Phys. Rev. Lett. 85, 5468 (2000), DOI: 10.1103/PhysRevLett.85.5468. Web of Science, Google Scholar
M. E. J. Newman, Phys. Rev. E 64, 016131 (2001), DOI: 10.1103/PhysRevE.64.016131. Web of Science, Google Scholar
M. E. J. Newman, Phys. Rev. E 64, 016132 (2001), DOI: 10.1103/PhysRevE.64.016132. Web of Science, Google Scholar
M. E. J. Newman, Phys. Rev. Lett. 89, 208701 (2002), DOI: 10.1103/PhysRevLett.89.208701. Web of Science, Google Scholar
Pandya, R. V. R., A note on "Weighted evolving networks: Coupling topology and weight dynamics", (2004) , cond-mat/0406644 . Google Scholar
R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett. 86, 3200 (2001), DOI: 10.1103/PhysRevLett.86.3200. Web of Science, Google Scholar
R. Pastor-Satorras and A. Vespignani , Evolution and Structure of the Internet: A Statistical Physics Approach ( Cambridge University Press , Cambridge , 2004 ) . Google Scholar
A. Vázquez, R. Pastor-Satorras and A. Vespignani, Phys. Rev. E 65, 066130 (2002), DOI: 10.1103/PhysRevE.65.066130. Web of Science, Google Scholar
D. J. Watts and S. H. Strogatz, Nature 393, 440 (1998), DOI: 10.1038/30918. Web of Science, Google Scholar
B. M. Waxman, IEEE J. Select. Areas. Commun. 6, 1617 (1988), DOI: 10.1109/49.12889. Web of Science, Google Scholar
R. Xulvi-Brunet and I. M. Sokolov, Phys. Rev. E 66, 026118 (2002), DOI: 10.1103/PhysRevE.66.026118. Web of Science, Google Scholar
S. H. Yooket al., Phys. Rev. Lett. 86, 5835 (2001), DOI: 10.1103/PhysRevLett.86.5835. Web of Science, Google Scholar
S.-H. Yook, H. Jeong and A.-L. Barabási, Proc. Natl. Acad. Sci. (USA) 99, 13382 (2002), DOI: 10.1073/pnas.172501399. Web of Science, Google Scholar
D. Zhenget al., Phys. Rev. E 67, 040102 (2003), DOI: 10.1103/PhysRevE.67.040102. Web of Science, Google Scholar