Network geometry inference using common neighbors

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\left(t^4\right)$ running time to map a network of $t$ nodes, versus $O\left(t^3\right)$ in the link-based method. But we also develop a hybrid method with $O\left(t^3\right)$ running time, which combines the common-neighbors and link-based approaches, and we explore a heuristic that reduces its running time further to $O\left(t^2\right)$, 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.

Figure 1

The HyperMap embedding algorithm.

Figure 2

Inferred vs real angles (in radians) for synthetic networks with $t=5000$ nodes and parameters $m=1.5$, $L=2.5$, $\gamma =2.1$, and $T$ as shown in the captions. The plots juxtapose the inferred against the real angles for the first 100 nodes, i.e., the nodes that appear at MLE times $1\le i\le 100$. In (a)–(c) the common-neighbors method is used, while in (d)–(f) the link-based method is used.

Figure 3

Likelihood landscapes for different nodes in a synthetic network with $t=5000$ nodes and parameters $m=1.5$, $L=2.5$, $\gamma =2.1$, and $T=0.4$. The plots show the likelihoods ${\mathcal{L}}_{CN}^i$, ${\mathcal{L}}_L^i$ [Eqs. (13) and (5)] and the log-likelihoods $ln{\mathcal{L}}_{CN}^i$, $ln{\mathcal{L}}_L^i$, for nodes appearing at MLE times $i=5$, 10, 25, 30, 35, and 40, as a function of the angular coordinate $\theta$ (in radians). The vertical line in each plot shows the inferred angle ${\theta }^{inferred}$ (in radians), which always corresponds to the global maximum of the likelihood.

Figure 4

Inferred vs real angles (in radians) for all the nodes in the synthetic networks of Fig. 2. In (a)–(c) the hybrid method is used, while in (d)–(f) the link-based method is used.

Figure 5

Connection probabilities with inferred (radial and angular) node coordinates obtained by the hybrid and link-based methods, and with real node coordinates. The results correspond to the mappings of Fig. 4.

Figure 6

Inferred vs real angles (in radians) for all nodes in the networks of Fig. 4. In (a)–(c) the hybrid method is used, while in (d)–(f) the link-based method is used. In both methods, the correction steps are run as described in the text.

Figure 7

Connection probabilities with inferred (radial and angular) node coordinates obtained by the hybrid and link-based methods, and with real node coordinates. The results correspond to the mappings of Fig. 6.

Figure 8

Likelihood landscapes for different nodes in a synthetic network with $t=5000$ nodes and parameters $m=1.5$, $L=2.5$, $\gamma =2.1$, and $T=0.4$. The plots show the log-likelihoods $ln{\mathcal{L}}_L^i$, $i=600$, 1000, and 2000, with the original version of the method that samples the likelihood over the whole $[0,2\pi ]$ domain (dashed red line), and with its fast version that samples the likelihood only over the $\theta$ region shown by the solid black line. The vertical line in each plot shows the initial estimate for the angle, ${\theta }^{init}$, while ${\theta }^{inferred}$ is the final inferred angle.

Figure 9

Inferred angles (in radians) with the original and fast versions of the hybrid method for synthetic networks with $t=5000$ nodes, $m=1.5$, $L=2.5$, $\gamma =2.1$, and $T$ as shown in the captions.

Figure 10

Logarithmic loss (${\text{LL}}^{inf}$), GR success ratio ($p_s$), and future-link probability in a mapped snapshot of the AS Internet (Sept. 2009 snapshot). In (a) and (b), the results are obtained by the fast hybrid and link-based methods, with and without correction steps. The results in (c) are obtained by the fast hybrid method with correction steps. In all cases $k_{speedup}=3$, and the results are shown for different values of the temperature parameter $T$.

Figure 11

Performance of future-link prediction in the AS Internet with the fast hybrid and link-based methods ($k_{speedup}=3$), and comparison to the preferential attachment (PA) and common-neighbors (CN) heuristics. In each case, the AS snapshot of Sept. 2009 is considered. In (a), the AUC is computed over all disconnected AS pairs and the new links that appear between them in Sept. 2009–Dec. 2010 ($48119$ new links); in (b), the AUC is computed only over the disconnected AS pairs that have no common neighbors ($95\%$ of all disconnected pairs) and the new links between them (9279 new links); and in (c), the AUC is computed only over the disconnected AS pairs with degrees $k,k^{\prime }<\overline{k}=5$ ($72\%$ of all disconnected pairs) and the new links between them (2050 new links).

Figure 12

Distributions of angular coordinates of ASs belonging to the same country during September 2009–December 2010 (a)–(f), and the evolution of the angular center of masses of the corresponding communities over time (g)–(i). For each snapshot in (a)–(f), the angular center of mass of each country is ${\theta }_{\text{c.m.}}=(1/n){\sum }_b\theta \left(b\right)n\left(b\right)$, where $n$ is the number of ASs belonging to the country, $n\left(b\right)$ is the number of such ASs falling within bin $b$, $\theta \left(b\right)$ is the value of $\theta$ in the bin, and the summation is over all the bins. For each country, ${\theta }_{\text{c.m.}}$ is shown (g)–(i) as a function of the network time $t$, i.e., as a function of the number of ASs in the snapshots (a)–(f), $t=24091$, 25 910, 26 307, 26 756, 28 353, and 29 333, respectively.

Figure 13

Distribution of the inferred AS angles (Sept. 2009 snapshot) with the fast hybrid method ($k_{speedup}=3$) and different values of the temperature parameter $T$.