This project investigates the hypothesis that beneath the observable topology of every complex network, including the (AS) Internet, there exists a hidden hyperbolic metric space that can explain its structural and dynamical characteristics, and which can be used to efficiently guide information transport. While the main motivation in this project is the AS Internet, our work has a much broader impact with a range of interdisciplinary applications in both network science and engineering.

Complex networks are ubiquitous in all domains of science and engineering, and permeate many aspects of daily human life, from biological to social, economic, transportation, and communication. Our growing dependence on networks has inspired a burst of activity in the new field of network science, keeping researchers motivated to solve the difficult challenges that networks offer. Among these, the relation between network structure and function is perhaps the most important and fundamental.

The main objective of this project is to thoroughly investigate the hypothesis that beneath the observable topology of every complex network, including the Internet, there exists a hidden hyperbolic metric space that can be used to efficiently guide information transport, without the need for global topology knowledge and the associated overhead costs. While our main motivation in this project is scalable routing in the Internet, by elucidating the mysterious connection between network structure and function, our work implies impact far broader than the Internet, with a broad range of interdisciplinary applications in network science and engineering.

To accomplish the above main objective the project has been organised into three main inter-dependent tasks, each with its own objective:

• Task 1: Prove analytically that hyperbolic geometries are the most congruent with complex network topologies.
• Task 2: Measure geometric properties of metric spaces hidden under real networks.
• Task 3: Construct embeddings of real networks into the underlying hyperbolic spaces.In summary, in the first Task we pursue three results: (1) establish and prove explicit mathematical relationships between the properties of hyperbolic spaces and the properties of the resulting graphs; (2) calculate analytically the efficiency metrics of different greedy forwarding algorithms in these synthetic graphs; and (3) study how these efficiency metrics deteriorate under network dynamics. In the second Task we explore the reverse problem: starting with the finite metric space formed by the similarity distances between nodes in a real network, we want to infer the properties of the corresponding underlying continuous space and explicitly verify that it is hyperbolic. Finally, in the third Task we address the important problem of how nodes in a real network can compute their coordinates in the identified hyperbolic space, and study the performance of greedy forwarding mechanisms in the resulting embedded networks.The execution of the project has been a great success, leading to high impact publications. In summary, our main results are:1. We have found that hyperbolic geometries are indeed the most congruent with real network topologies. In particular, we have found that trade-offs between popularity and similarity shape the structure and dynamics of growing complex networks, casting these networks as random geometric graphs growing in hyperbolic spaces. We have also established and proved explicit mathematical relationships between the properties of hyperbolic spaces and the properties of the resulting graphs. Furthermore, we have studied the efficiency of various greedy forwarding mechanisms in synthetic networks embedded in hyperbolic spaces, verifying that the efficiency of information transport is indeed maximised in such spaces, even under dynamic network conditions (Objectives from Task 1).2. We have shown that our results apply not only to technological networks like Internet, but also to networks from other domains, such as biological and social networks. Specifically, we have found that combining popularity and similarity of nodes in any real network gives rise to an underlying hyperbolic geometry, where radial and angular coordinates in the law of hyperbolic cosines abstract popularity and similarity attributes of nodes. (Objectives from Task 2).3. Finally, we have derived a systematic framework, which maps (embeds) a given real network to a hyperbolic space (i.e., infers the coordinates of the nodes in the space). We have applied this framework to the topology of the real Internet and found that it produces meaningful results. The performance of greedy forwarding using this framework is close to 90% of the optimal performance. Furthermore, this framework can be used for predicting missing and future links in real networks, and for studying how network communities evolve over time in popularity-similarity spaces. Our framework has been applied in the context of Named Data Networking (NDN) that aims to develop a new Internet architecture (Objectives from Task 3).References:

  1. F. Papadopoulos et al. “Network Mapping by Replaying Hyperbolic Growth”, IEEE/ACM Transactions on Networking, Vol. 23, No. 1, February 2015.
  2. F. Papadopoulos et al. “Popularity versus Similarity in Growing Networks”, Nature, Vol. 489, No. 7417, September 2012.

  This project has been instrumental in facilitating the smooth re-integration and career development of the researcher, who currently holds a faculty position at the host. The project provided the opportunity to employ research personnel, perform travelling, purchase equipment, and engage into edge-cutting interdisciplinary research in collaboration with universities and research centers in US and Europe. Importantly, this project has also opened new and totally unexplored avenues for future work in the fascinating world of networks.

  Duration: 3/1/2011-2/1/2015.

  Funded by: EU’s Seventh Framework (FP7) Programme.

  Budget: €100000.

  More information at: https://cordis.europa.eu/result/rcn/164043_en.html.

  Related Workshops:

  – Workshop on Network Geometry, Limassol, Cyprus, 2011.

  – Network Geometry Workshop, San Diego, CA, 2013.