Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane
Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane
复制标题
DOI：
10.1109/tnet.2018.2810186
复制
发表时间：
2018-04-01
影响因子：
3.7
通讯作者：
Laue, Soeren
中科院分区：
文献类型：
--
作者：
Blaesius, Thomas;Friedrich, Tobias;Laue, Soeren
双曲几何似乎是许多大型真实的网络中固有的。我们构造并实现了一个新的极大似然估计算法，嵌入无标度图的双曲空间。所有以前的方法类似的嵌入算法需要至少一个二次运行时间。我们的算法实现了准线性的运行时间，这使得它成为第一个算法，可以嵌入网络与数十万个节点在不到一个小时。我们证明了我们的算法在人工和真实的网络上的性能。在所有典型的指标，如对数似然和贪婪路由，我们的算法发现嵌入是非常接近地面真相。
Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require at least a quadratic runtime. Our algorithm achieves quasi-linear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics, such as log-likelihood and greedy routing, our algorithm discovers embeddings that are very close to the ground truth.