论文标题
在大型不完整网络中找到最短和几乎最短的路径节点
Finding shortest and nearly shortest path nodes in large substantially incomplete networks
论文作者
论文摘要
网络上的动态过程，无论是在互联网上的信息传输，在社交网络中传染的传播还是神经信号传导，都沿最短或几乎最短的路径发生。不幸的是，由于网络的高度动态性质，或网络测量的高成本，或两者兼而有之，我们的大多数大型网络的地图基本上是不完整的。我们发现，大型真实网络中的最短路径，例如蛋白质 - 蛋白质相互作用的网络（PPI）和自主系统（AS）级别的Internet，不是随机的，而是根据潜在的几何规则组织的。如果将这些网络的节点映射到潜在双曲线空间中的点，则它们的最短路径沿着连接端点节点的地球曲线对齐。我们发现，即使在基本不完整的网络的情况下，这种比对也足够强，可以识别最短路径节点。我们证明了潜在几何路径找到在蜂窝路径重建和通信安全性问题中的实用性。
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. 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 (PPI) and the Internet at the autonomous system (AS) 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. We demonstrate the utility of latent-geometric path-finding in problems of cellular pathway reconstruction and communication security.
