Link prediction with hyperbolic geometry
Link prediction with hyperbolic geometry
复制标题
DOI：
10.1103/physrevresearch.2.043113
复制
发表时间：
2020-10-21
影响因子：
4.2
通讯作者：
Krioukov, Dmitri
中科院分区：
文献类型：
--
作者：
Kitsak, Maksim;Voitalov, Ivan;Krioukov, Dmitri
链路预测是网络科学中的一个典型问题，具有广泛的应用。在潜在空间网络模型中，这个问题归结为按照节点之间潜在距离的增加顺序对节点对进行排序。具有双曲潜在空间的网络模型具有许多吸引人的性质，这表明它必须是预测链接的强大工具，但过去在这个方向上的工作报告了混合的结果。在这里，我们进行了系统的调查，潜在的双曲几何链接预测网络中的效用。我们首先表明，一些措施的链接预测精度是非常敏感的不准确性，在推理的潜在的双曲线坐标的节点。这一观察导致我们发展的双曲线网络嵌入方法，HYPERLINK嵌入器，我们最大限度地提高了这种推断的准确性，相比现有的双曲线嵌入方法。将此方法应用于合成和真实的网络，然后我们发现，当涉及到预测明显缺失的链接双曲线链接预测-简称，超链接-很少是最好的，但往往是有竞争力的，相比众多的其他方法。然而，当任务是预测真正难以预测的不太明显的缺失链接时，HYPERLINK似乎处于最佳状态，最大化其竞争力。这些链接包括具有大部分缺失链接的不完整网络中的缺失链接、没有任何共同邻居的节点之间的缺失链接以及潜在距离很大的不同节点之间的缺失链接。总的来说，这些结果表明，更难的一个特定的链接预测任务，更严重的是应该考虑使用双曲几何。
Link prediction is a paradigmatic problem in network science with a variety of applications. In latent space network models this problem boils down to ranking pairs of nodes in the order of increasing latent distances between them. The network model with hyperbolic latent spaces has a number of attractive properties suggesting it must be a powerful tool to predict links, but the past work in this direction reported mixed results. Here we perform a systematic investigation of the utility of latent hyperbolic geometry for link prediction in networks. We first show that some measures of link prediction accuracy are extremely sensitive with respect to inaccuracies in the inference of latent hyperbolic coordinates of nodes. This observation leads us to the development of a hyperbolic network embedding method, the HYPERLINK embedder, which we show maximizes the accuracy of such inference, compared to existing hyperbolic embedding methods. Applying this method to synthetic and real networks, we then find that when it comes to predicting obvious missing links hyperbolic link prediction-for short, HYPERLINK-is rarely the best but often competitive, compared to a multitude of other methods. However, HYPERLINK appears to be at its best, maximizing its competitive power, when the task is to predict less obvious missing links that are really hard to predict. These links include missing links in incomplete networks with large fractions of missing links, missing links between nodes that do not have any common neighbors, and missing links between dissimilar nodes at large latent distances. Overall these results suggest that the harder a specific link prediction task the more seriously one should consider using hyperbolic geometry.