Network Mapping by Replaying Hyperbolic Growth
Journal
IEEE/ACM Transactions on Networking
Date Issued
February 1, 2015
DOI
10.1109/TNET.2013.2294052
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.
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.