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: