Network Mapping by Replaying Hyperbolic Growth

F. Papadopoulos, C. Psomas, and D. Krioukov
IEEE/ACM Transactions on Networking
v.23, n.1, p.198-211, 2015
January 20, 2014

Abstract

Recent years have  shown a promising progress in understanding geometric underpinnings behind  the structure, function, and dynamics of many complex networks in nature and  society. However these promises cannot be readily fulfilled and lead to  important practical applications, without a simple, reliable, and fast  network mapping method to infer the latent geometric coordinates of nodes in  a real network. Here we present HyperMap, a simple method to map a given real  network to its hyperbolic space. The method utilizes a recent geometric  theory of complex networks modeled as random geometric graphs in hyperbolic  spaces. The method replays the network's geometric growth, estimating at each  time step the hyperbolic coordinates of new nodes in a growing network by  maximizing the likelihood of the network snapshot in the model. We apply  HyperMap to the AS Internet, and find that: 1) the method produces meaningful  results, identifying soft communities of ASs belonging to the same geographic  region; 2) the method has a remarkable predictive power: using the resulting  map, we can predict missing links in the Internet with high precision,  outperforming popular existing methods; and 3) the resulting map is highly  navigable, meaning that a vast majority of greedy geometric routing paths are  successful and low-stretch. Even though the method is not without  limitations, and is open for improvement, it occupies a unique attractive  position in the space of trade-offs between simplicity, accuracy, and  computational complexity.

Related publications