Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, 2600 GA, Delft, The Netherlands.
Network Science Institute, Northeastern University, 177 Huntington avenue, Boston, MA, 022115, USA.
Nat Commun. 2023 Jan 17;14(1):186. doi: 10.1038/s41467-022-35181-w.
Dynamic processes on networks, be it information transfer in the Internet, contagious spreading in a social network, or neural signaling, take place along shortest or nearly shortest paths. Computing shortest paths is a straightforward task when the network of interest is fully known, and there are a plethora of computational algorithms for this purpose. Unfortunately, our maps of most large networks are substantially incomplete due to either the highly dynamic nature of networks, or high cost of network measurements, or both, rendering traditional path finding methods inefficient. We find that shortest paths in large real networks, such as the network of protein-protein interactions and the Internet at the autonomous system level, are not random but are organized according to latent-geometric rules. If nodes of these networks are mapped to points in latent hyperbolic spaces, shortest paths in them align along geodesic curves connecting endpoint nodes. We find that this alignment is sufficiently strong to allow for the identification of shortest path nodes even in the case of substantially incomplete networks, where numbers of missing links exceed those of observable links. We demonstrate the utility of latent-geometric path finding in problems of cellular pathway reconstruction and communication security.
网络上的动态过程，无论是互联网中的信息传递、社交网络中的传染病传播，还是神经信号传递，都是沿着最短或几乎最短的路径进行的。当感兴趣的网络完全已知时，计算最短路径是一项直接的任务，为此有很多计算算法。不幸的是，由于网络的高度动态性、网络测量的高成本，或者两者兼而有之，我们对大多数大型网络的图谱都存在很大的不完整性，这使得传统的路径查找方法效率低下。我们发现，在大型真实网络（如蛋白质-蛋白质相互作用网络和自治系统级别的互联网）中，最短路径不是随机的，而是根据潜在的几何规则组织的。如果这些网络的节点被映射到潜在双曲空间中的点，那么它们的最短路径将沿着连接端点节点的测地线曲线对齐。我们发现，这种对齐程度非常强，即使在网络中缺失的链路数量超过可观察链路数量的情况下，也足以识别最短路径节点。我们展示了潜在几何路径查找在细胞途径重建和通信安全问题中的应用。
