Network Geometry Inference using Common Neighbors
Network Geometry Inference using Common Neighbors
复制标题
DOI：
10.1103/physreve.92.022807
复制
发表时间：
2015-02
期刊：
影响因子：
--
通讯作者：
Fragkiskos Papadopoulos;D. Krioukov
中科院分区：
文献类型：
--
作者：
Fragkiskos Papadopoulos;D. Krioukov
介绍并探索了一种基于节点间共有邻居数来推断复杂网络中节点隐藏几何坐标的方法。我们将此方法与HyperMap方法进行比较，HyperMap方法仅基于节点之间的连接（和断开），即节点具有（或不具有）的链接。我们发现，对于高节点，除非在后者中使用启发式周期性调整（或“校正步骤”），否则共同邻居方法比基于链接的方法产生更准确的推断。共邻居方法是计算密集型的，映射t个节点的网络需要O（t4）运行时间，而基于链路的方法需要O（t3）运行时间。但我们也开发了一种运行时间为O（t3）的混合方法，该方法结合了共同邻居和基于链路的方法，并且我们探索了一种启发式方法，该方法将其运行时间进一步减少到O(t2)，而不会显著降低映射精度。我们将这种方法应用于自治系统（as）互联网，并揭示了as的软社区如何在相似空间中随时间演变。我们通过预测as之间的未来链接进一步证明了该方法的预测能力。总的来说，我们的结果促进了我们对如何有效和准确地将真实网络映射到其潜在几何空间的理解，这是理解控制这些空间中节点动态的规律以及网络连接的细粒度动态的重要必要步骤。
We introduce and explore a method for inferring hidden geometric coordinates of nodes in complex networks based on the number of common neighbors between the nodes. We compare this approach to the HyperMap method, which is based only on the connections (and disconnections) between the nodes, i.e., on the links that the nodes have (or do not have). We find that for high degree nodes, the common-neighbors approach yields a more accurate inference than the link-based method, unless heuristic periodic adjustments (or "correction steps") are used in the latter. The common-neighbors approach is computationally intensive, requiring O(t4) running time to map a network of t nodes, versus O(t3) in the link-based method. But we also develop a hybrid method with O(t3) running time, which combines the common-neighbors and link-based approaches, and we explore a heuristic that reduces its running time further to O(t2), without significant reduction in the mapping accuracy. We apply this method to the autonomous systems (ASs) Internet, and we reveal how soft communities of ASs evolve over time in the similarity space. We further demonstrate the method's predictive power by forecasting future links between ASs. Taken altogether, our results advance our understanding of how to efficiently and accurately map real networks to their latent geometric spaces, which is an important necessary step toward understanding the laws that govern the dynamics of nodes in these spaces, and the fine-grained dynamics of network connections.