Model-free hidden geometry of complex networks

The fundamental idea of embedding a network in a metric space is rooted in the principle of proximity preservation. Nodes are mapped into points of the space with pairwise distance that reflects their proximity in the network. Popular methods employed in network embedding either rely on implicit approximations of the principle of proximity preservation or implement it by enforcing the geometry of the embedding space, thus hindering geometric properties that networks may spontaneously exhibit. Here we take advantage of a model-free embedding method explicitly devised for preserving pairwise proximity and characterize the geometry emerging from the mapping of several networks, both real and synthetic. We show that the learned embedding has simple and intuitive interpretations: the distance of a node from the geometric center is representative for its closeness centrality, and the relative positions of nodes reflect the community structure of the network. Proximity can be preserved in relatively low-dimensional embedding spaces, and the hidden geometry displays optimal performance in guiding greedy navigation regardless of the specific network topology. We finally show that the mapping provides a natural description of contagion processes on networks, with complex spatiotemporal patterns represented by waves propagating from the geometric center to the periphery. The findings deepen our understanding of the model-free hidden geometry of complex networks.

Figure 1

Model-free maps of real-world networks. Two-dimensional MDS maps of the (a) European Road (ER) [28] and (b) European Air Transportation (EAT) [29] networks. For details on the two networks see Appendix pp2-s2. The size of nodes in the ER network is proportional to the square of their degrees. For the EAT network, the size of nodes is proportional to the square root of their degrees. Nodes in both figures are colored depending on the country they belong to. For sake of clarity, we label and color only nodes corresponding to a subset of European countries and display in gray nodes not belonging to this subset. Also, only nodes with degree centrality larger than one are shown. The black $\mathbf{x}$ symbol in both panels denotes the geometric center of the embedding space.

Figure 2

Geometric interpretation of network centrality metrics. Pairwise rank correlation between different network centrality metrics and the distance from the geometric center of the MDS embedding. Here the embedding dimension is $d=100$. Note that we take absolute value of correlation coefficients for convenient comparison. We compute the correlation coefficients for nine real-world networks (see Table 1 for details). Network centralities considered are closeness (C), eigenvector (EV), nonbacktracking (NB), Katz (K), k-core (KC), betweenness (B), PageRank (PR), and degree (D).

Figure 3

Preservation of graph distance in the embedding space. (a) Relative error between the shortest path length in the graph and the distance in the embedding space as a function of the embedding dimension. Relative error is averaged over all pairs of nodes in the network (see Appendix pp4-s1 for details). We consider different types of network models, either Poisson networks with average degree $\langle k\rangle =4$ or $m$-ary trees with $m=3$, and two different network sizes $N=100$ and $N=1000$. Continuous curves in the plot are obtained by fitting data points with power-law decaying functions towards an asymptotic relative error value (see Appendix pp5). (b) Same as in panel a but for real-world networks (see Table 1). (c) Optimal embedding dimension as a function of the network size $N$ (see Appendix pp5). For network models, we consider different sizes. Real-world networks are denoted by a single point in the plot. (d) Asymptotic value of the relative error as a function of the network size.

Figure 4

Routing protocols relying on network geometry. We compare (a) success rate and (b) efficiency of greedy routing in MDS and hyperbolic spaces for different real-world networks (acronyms and symbols are the same as in Fig. 3). We consider also three instances of PSOM with $N=5000,\langle k\rangle =5$, and degree exponent $\gamma =2.1$, and different values of the temperature parameter $T=0.1,T=0.5,T=0.9$ (respectively indicated as PSOM1, PSOM2, and PSOM3). The markers located in the upper triangle area represent the cases where success rate or efficiency in MDS space is higher than in hyperbolic space.

Figure 5

Geometric description of spreading in complex networks. In the main panel, we display the scatter plot of the average infection arrival time against the distance of nodes from the geometric center of the MDS map. Each point in the plot is a node of the network. The average infection arrival time is calculated based on $N$ independent instances of the susceptible-infected model simulated on the air transportation (AT) network with a random seed each time, where $N$ is network size. The network is embedded in $d=100$ dimensions. For illustrative purposes only, we display in the inset what spreading looks like in a two-dimensional MDS map. Nodes with larger size and darker color are infected earlier.

Figure 6

The performance of the landmark MDS algorithm on the IPv6 Internet network. (a) Running time, (b) relative error, (c) Pearson correlation, (d) greedy routing success rate, (e) greedy routing average path length, and (f) greedy routing efficiency as functions of the number of landmarks. The embedding dimension is $d=100$.

Figure 7

The performance of landmark MDS algorithm on the IPv6 Internet network. (a) Running time, (b) relative error, (c) Pearson correlation, (d) greedy routing success rate, (e) greedy routing average path length, and (f) greedy routing efficiency as functions of the embedding dimension $d$. The number of landmarks is $l=10d$.

Figure 8

Pairwise relation between different centralities and the distance of a node from the geometric center in MDS embedding space ($r$) for different real-world networks. Network centralities considered are closeness (C), eigenvector (EV), nonbacktracking (NB), Katz (K), k-core (KC), betweenness (B), PageRank (PR), and degree (D). The embedding dimension is 100. The results for IPv4 and AS2 are obtained by landmark MDS with the number of landmarks $l=1000$. For clarity, we show only 10% of all nodes if the network size is larger than 1000.

Figure 9

Same as Fig. 3, but with the Pearson correlation $\rho$ between the shortest path length and distance in the embedding space as the evaluation metric. For Poisson networks and P2P network, the continuous curves are obtained by fitting data points with exponential function $\rho \left(d\right)={\rho }_{\infty }-s{e}^{\beta d}$. For tree networks and other real-world networks, the data points are fitted with power-law function $\rho \left(d\right)={\rho }_{\infty }-s{d}^{\alpha }$. The optimal dimension is also calculated at the accuracy level $\epsilon =0.05$.

Figure 10

Same analysis as in Fig. 4, but the performance is measured by the GR-score.

Figure 11

The comparison of greedy routing success rate $p_s$, average path length $\langle R\rangle$, efficiency $\eta$, and GR-score on MDS and hyperbolic embedding for different real-world networks. The solid lines represent results based on MDS embedding, and the dashed lines are the results based on hyperbolic embedding.

Figure 12

Scatter plot of the average infection arrival time against the distance of nodes from the geometric center of the MDS map for different real-world networks and synthetic networks. Each point in the plot represents a node in the network. The average infection arrival time is calculated based on $N$ independent simulations of the susceptible-infected model with a random seed each time, where $N$ is the network size. The network is embedded with $d=100$. For illustrative purposes only, we display in the inset what the spreading looks like in a two-dimensional MDS map. Nodes with larger size and darker color are infected earlier.