Abstract
Routing information through networks is a universal phenomenon in both natural and man-made complex systems. When each node has full knowledge of the global network connectivity, finding short communication paths is merely a matter of distributed computation. However, in many real networks, nodes communicate efficiently even without such global intelligence. Here, we show that the peculiar structural characteristics of many complex networks support efficient communication without global knowledge. We also describe a general mechanism that explains this connection between network structure and function. This mechanism relies on the presence of a metric space hidden behind an observable network. Our findings suggest that real networks in nature have underlying metric spaces that remain undiscovered. Their discovery should have practical applications in a wide range of areas where networks are used to model complex systems.
This is a preview of subscription content, access via your institution
Access options
Subscribe to this journal
Receive 12 print issues and online access
$259.00 per year
only $21.58 per issue
Buy this article
- Purchase on SpringerLink
- Instant access to full article PDF
Prices may be subject to local taxes which are calculated during checkout
Similar content being viewed by others
References
Albert, R. & Barabási, A.-L. Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47–97 (2002).
Newman, M. E. J. The structure and function of complex networks. SIAM Rev. 45, 167–256 (2003).
Dorogovtsev, S. N. & Mendes, J. F. F. Evolution of Networks: From Biological Nets to the Internet and WWW. (Oxford Univ. Press, 2003).
Boccaletti, S., Latora, V., Moreno, Y., Chavez, M. & Hwang, D.-U. Complex networks: Structure and dynamics. Phys. Rep. 424, 175–308 (2006).
Castells, M. The Rise of the Network Society (Blackwell, 1996).
Pastor-Satorras, R. & Vespignani, A. Evolution and Structure of the Internet. A Statistical Physics Approach (Cambridge Univ. Press, 2004).
Watts, D. J., Dodds, P. S. & Newman, M. E. J. Identity and search in social networks. Science 296, 1302–1305 (2002).
Girvan, M. & Newman, M. E. J. Community structure in social and biological networks. Proc. Natl Acad. Sci. USA 99, 7821–7826 (2002).
Menczer, F. Growing and navigating the small world Web by local content. Proc. Natl Acad. Sci. USA 99, 14014–14019 (2002).
Leicht, E. A., Holme, P. & Newman, M. E. J. Vertex similarity in networks. Phys. Rev. E 73, 026120 (2006).
Crandall, D., Cosley, D., Huttenlocher, D., Kleinberg, J. & Suri, S. Proc. ACM Int. Conf. on Knowledge Discovery and Data Mining (ACM, 2008).
Clauset, A., Moore, C. & Newman, M. E. J. Hierarchical structure and the prediction of missing links in networks. Nature 453, 98–101 (2008).
Ángeles Serrano, M., Krioukov, D. & Boguñá, M. Self-similarity of complex networks and hidden metric spaces. Phys. Rev. Lett. 100, 078701 (2008).
Travers, J. & Milgram, S. An experimental study of the small world problem. Sociometry 32, 425–443 (1969).
Watts, D. J. & Strogatz, S. H. Collective dynamics of small-world networks. Nature 393, 440–442 (1998).
Kleinberg, J. Navigation in a small world. Nature 406, 845 (2000).
Kleinberg, J. STOC ’00: Proc. Thirty-Second Annual ACM Symp. on Theory of Computing 163–170 (ACM, 2000).
Kleinberg, J. M. in Small-World Phenomena and the Dynamics of Information (eds Dietterich, T. G., Becker, S. & Ghahramani, Z.) 431–438 (MIT Press, 2001).
Manku, G. S., Naor, M. & Wieder, U. Proc. 36th ACM Symp. on Theory of Computing (STOC) 54–63 (ACM, 2004).
Martel, C. 23rd ACM Symp. Principles of Distributed Computing (PODC) 179–188 (ACM, 2004).
Nguyen, V. & Martel, C. SODA ’05: Proc. Sixteenth Annual ACM-SIAM Symp. on Discrete Algorithms 311–320 (Society for Industrial and Applied Mathematics, 2005).
Nguyen, V. & Martel, C. Proc. Fourth Workshop on Analytic Algorithmics and Combinatorics 213–227 (SIAM, 2008).
Simsek, Ö. & Jensen, D. in Proc. Nineteenth Int. Joint Conf. in Artificial Intelligence (eds Kaelbling, L. P. & Saffiotti, A.) 304–310 (Professional Book Center, 2005).
Lebhar, E. & Schabanel, N. in Proc. 31st Int. Colloquium on Automata, Languages and Programming Vol. 3142 (eds Díaz, J., Karhumäki, J., Lepistö, A. & Sannella, D.) 894–905 (Lecture Notes in Computer Science, Springer, 2004).
Fraigniaud, P. in Proc of the 13th Annual European Symposium Vol. 3669 (eds Brodal, G. S. & Leonardi, S.) 791–802 (Lecture Notes in Computer Science, Springer, 2005).
Fraigniaud, P., Gavoille, C. & Paul, C. Eclecticism shrinks even small worlds. Distrib. Comput. 18, 279–291 (2006).
Fraigniaud, P., Gavoille, C., Kosowski, A., Lebhar, E. & Lotker, Z. in Proc. Nineteenth Annual ACM Symp. on Parallel Algorithms and Architectures (eds Gibbons, P. B. & Scheideler, C.) 1–7 (ACM, 2007).
Fraigniaud, P. & Gavoille, C. in Proc. Twentieth Annual Symposium on Parallelism in Algorithms and Architectures (eds auf der Heide, F. M. & Shavit, N.) 62–69 (ACM, 2008) SPAA.
Chaintreau, A., Fraigniaud, P. & Lebhar, E. in Automata, Languages and Programming Vol. 5125 (eds Aceto, L. et al.) 133–144 (Lecture Notes in Computer Science, Springer, 2008).
Kleinberg, J. Complex networks and decentralized search algorithms. Proc. Int. Congr. Math. (ICM) 3, 1019–1044 (2006).
Amaral, L. A. N., Scala, A., Barthélemy, M. & Stanley, H. E. Classes of small-world networks. Proc. Natl Acad. Sci. 97, 11149–11152 (2000).
Meyer, D., Zhang, L. & Fall, K. (eds). RFC4984 (The Internet Architecture Board, 2007).
Krioukov, D., claffy, kc, Fall, K. & Brady, A. On compact routing for the Internet. Comput. Commun. Rev. 37, 41–52 (2007).
Ravasz, E., Gnanakaran, S. & Toroczkai, Z. Network structure of protein folding pathways. Preprint at <http://arxiv.org/abs/0705.0912> (2007).
Toroczkai, Z., Kozma, B., Bassler, K. E., Hengartner, N. W. & Korniss, G. Gradient networks. J. Phys. A: Math. Theor. 41, 155103 (2008).
Krioukov, D., Papadopoulos, F., Boguñá, M. & Vahdat, A. Efficient navigation in scale-free networks embedded in hyperbolic metric spaces. Preprint at <http://arxiv.org/abs/0805.1266> (2008).
Boguñá, M. & Pastor-Satorras, R. Class of correlated random networks with hidden variables. Phys. Rev. E 68, 036112 (2003).
Giot, M. et al. A protein interaction map of Drosophila melanogaster. Science 302, 1727–1736 (2003).
Mahadevan, P. et al. The Internet AS-level topology: Three data sources and one definitive metric. Comput. Commun. Rev. 36, 17–26 (2006).
Boguñá, M., Pastor-Satorras, R., Díaz-Guilera, A. & Arenas, A. Models of social networks based on social distance attachment. Phys. Rev. E 70, 056122 (2004).
Jeong, H., Tombor, B., Albert, R., Oltvai, Z. N. & Barabási, A.-L. The large-scale organization of metabolic networks. Nature 407, 651–654 (2000).
Barrat, A., Barthélemy, M., Pastor-Satorras, R. & Vespignani, A. The architecture of complex weighted networks. Proc. Natl Acad. Sci. USA 101, 3747–3752 (2004).
<http://www.transtats.bts.gov/>
Acknowledgements
We thank M. Á. Serrano for useful comments and discussions. This work was supported in part by DGES grant FIS2007-66485-C02-02, Generalitat de Catalunya grant No. SGR00889, the Ramón y Cajal program of the Spanish Ministry of Science, by NSF CNS-0434996 and CNS-0722070, by DHS N66001-08-C-2029 and by Cisco Systems.
Author information
Authors and Affiliations
Corresponding author
Supplementary information
Supplementary Information
Supplementary Informations (PDF 2072 kb)
Rights and permissions
About this article
Cite this article
Boguñá, M., Krioukov, D. & Claffy, K. Navigability of complex networks. Nature Phys 5, 74–80 (2009). https://doi.org/10.1038/nphys1130
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1038/nphys1130