The Hidden Hyperbolic Structure of the Internet
M.Boguna
Department of Fundamental Physics - University of Barcelona
Barcelona, Spain.
Abstract: In the age of Information Technology, the Internet has become our primary communication system. It is estimated that more than a billion users surf every day the web looking for information, sharing files, or developing new applications. The physical Internet is like a new world where all kind of new social and technological structures are constantly emerging. The Internet has thus become a common good, such as roads, railways, or airline connections and, as such, should be considered. The most surprising fact about the Internet is that, despite some preconceived ideas, its complex architecture is the result of a self-organized process where individual agents (Internet Service Providers or ISPs) interact locally without any central authority controlling its evolution. This turns the Internet into subject of truly scientific research.
The Internet is now facing a serious scalability problem with its routing architecture. To route information packets to a given destination, Internet routers must communicate to maintain a coherent view of the global Internet topology. The constantly increasing size and dynamics of the Internet thus leads to immense and quickly growing communication and information processing overhead, a major bottleneck in routing scalability causing concerns among Internet experts that the existing Internet routing architecture may not sustain even another decade. In our approach, we assume that the Internet (and other complex networks) lives in a hidden metric space that shapes its topology. Discovery of this hidden metric space can then be used to greedily route information without detailed global knowledge of the network structure or organization.
Following these ideas, we introduce a network model that combines the small-world effect, scale-free degree distributions, and high clustering coefficient with metric properties. The model is able to reproduce the main topological properties of the Internet graph and other complex networks with a high accuracy. By using it, we have shown that the metric and topologic requirements for a network to be (efficiently) navigable are met by the majority of real networks. We have also provided empirical evidence that the Internet, social and biological networks can be embedded in metric spaces, which justify our pursuit of metric properties in complex networks. We have also shown that if we are to associate a metric space to real networks like the Internet, this space must be negatively curved (hyperbolic) and that in this geometry, greedy routing strategies achieves the optimal performance.
The connection of our model with hyperbolic geometry has also unexpected consequences. Interestingly, in this geometric framework, our model can be understood as an ensemble of non-interacting fermions connecting points of the hyperbolic plane, which energy is "naturally" defined by the hyperbolic distance between these points.
References:
- Sustaining the Internet with hyperbolic mapping. Boguñá, M; Papadopoulos, F; Krioukov, D. Nature Communications, 1 (2010) 62.
- Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces. Papadopoulos, F; Krioukov, D; Boguna, M; Vahdat, A. IEEE INFOCOM 2010, San Diego, CA, March 2010, (2010).
- Hyperbolic geometry of complex networks. Krioukov, D; Papadopoulos, F; Kitsak, M; Vahdat, A; Boguna, M. PHYSICAL REVIEW E, 82 (2010) 36106.
- Greedy Forwarding in Scale-Free Networks Embedded in Hyperbolic Metric Spaces. Krioukov, D; Papadopoulos, F; Boguna, M; Vahdat, A. ACM SIGMETRICS Performance Evaluation Review, 37 (2009).
- Curvature and temperature of complex networks. Krioukov, D; Papadopoulos, F; Vahdat, A; Boguna, M. PHYSICAL REVIEW E, 80 (2009) 35101.
- Navigating Ultrasmall Worlds in Ultrashort Time. Boguna, M; Krioukov, D. PHYSICAL REVIEW LETTERS, 102 (2009) 58701.
- Navigability of complex networks. Boguna, M; Krioukov, D; Claffy, KC. NATURE PHYSICS, 5 (2009) 74-80.
- Self-similarity of complex networks and hidden metric spaces. Serrano, MA; Krioukov, D; Boguna, M. PHYSICAL REVIEW LETTERS, 100 (2008) 78701.