Sulyok Bendegúz, Palla Gergely
Department of Biological Physics, Eötvös Loránd University, Pázmány P. stny. 1/A, 1117, Budapest, Hungary.
Data-Driven Health Division of National Laboratory for Health Security, Health Services Management Training Centre, Semmelweis University, Kútvölgyi út 2, 1125, Budapest, Hungary.
Sci Rep. 2023 Dec 27;13(1):23026. doi: 10.1038/s41598-023-50244-8.
Finding the optimal embedding of networks into low-dimensional hyperbolic spaces is a challenge that received considerable interest in recent years, with several different approaches proposed in the literature. In general, these methods take advantage of the exponentially growing volume of the hyperbolic space as a function of the radius from the origin, allowing a (roughly) uniform spatial distribution of the nodes even for scale-free small-world networks, where the connection probability between pairs decays with hyperbolic distance. One of the motivations behind hyperbolic embedding is that optimal placement of the nodes in a hyperbolic space is widely thought to enable efficient navigation on top of the network. According to that, one of the measures that can be used to quantify the quality of different embeddings is given by the fraction of successful greedy paths following a simple navigation protocol based on the hyperbolic coordinates. In the present work, we develop an optimisation scheme for this score in the native disk representation of the hyperbolic space. This optimisation algorithm can be either used as an embedding method alone, or it can be applied to improve this score for embeddings obtained from other methods. According to our tests on synthetic and real networks, the proposed optimisation can considerably enhance the success rate of greedy paths in several cases, improving the given embedding from the point of view of navigability.
将网络最优嵌入低维双曲空间是一项近年来备受关注的挑战，文献中提出了几种不同的方法。一般来说，这些方法利用双曲空间体积随距原点半径呈指数增长的特性，即使对于无标度小世界网络，也能使节点实现（大致）均匀的空间分布，在这种网络中，节点对之间的连接概率随双曲距离衰减。双曲嵌入背后的一个动机是，人们普遍认为在双曲空间中节点的最优布局能够在网络之上实现高效导航。据此，可用于量化不同嵌入质量的一种度量方法是，基于双曲坐标的简单导航协议下成功贪婪路径的比例。在本工作中，我们针对双曲空间的原生圆盘表示形式开发了一种针对该得分的优化方案。这种优化算法既可以单独用作一种嵌入方法，也可以应用于提高从其他方法获得的嵌入的该得分。根据我们对合成网络和真实网络的测试，所提出的优化在几种情况下能够显著提高贪婪路径的成功率，从可导航性角度改进给定的嵌入。
