Geometric detection of hierarchical backbones in real networks

Hierarchies permeate the structure of real networks, whose nodes can be ranked according to different features. However, networks are far from treelike structures and the detection of hierarchical ordering remains a challenge, hindered by the small-world property and the presence of a large number of cycles, in particular clustering. Here, we use geometric representations of undirected networks to achieve an enriched interpretation of hierarchy that integrates features defining the popularity of nodes and similarity between them, such that the more similar a node is to a less popular neighbor the higher the hierarchical load of the relationship. The geometric approach allows us to measure the local contribution of nodes and links to the hierarchy within a unified framework. Additionally, we propose a link filtering method, the similarity filter, able to extract hierarchical backbones containing the links that represent statistically significant deviations with respect to the maximum entropy null model for geometric heterogeneous networks. We applied our geometric approach to the detection of similarity backbones of real networks in different domains and found that the backbones preserve local topological features at all scales. Interestingly, we also found that similarity backbones favor cooperation in evolutionary dynamics modeling social dilemmas.

Figure 1

Hierarchy load in geometric networks. (a) Illustration of a geometric network in the hyperbolic disk. Node $p$ and its subordinates $l,m,n$ are highlighted inside a blue square. Notice node $p$ has a fourth neighbor which is not a subordinate since it lies at a smaller radial position from the center of the disk and thus has higher degree than node $p$. (b) Hierarchy load of a link, $h_{ij}$, between a generic node $i$ and a lower-status neighbor $j$ located at angular distance $\mathrm{\Delta }{\theta }_{ij}^{\mathrm{obs}}$. Notice in this example $h_{ij}$ is necessarily $h_{ij}<0.5$ as $j$ is located at an angular distance greater than the expected from the null model, which appears depicted in grey. The hierarchy load of node $i, h_i$, is obtained from averaging all link hierarchy loads corresponding to this node. (c) Hierarchy load of node $p$ from pannel A as the circular mean of the angular coordinates of lower-status neighbors $l,m,n$. Mean resultant vector is depicted by a black arrow of $|\overline{R}|<1$. Vectors added in the calculation of $h_p^{*}$ [see Eq. (2)] appear as arrows in yellow, orange and red inside a circle of unit radius.

Figure 2

Hierarchy load spectra of synthetic and real networks. [(a) and (b)] Hierarchy load spectrums for synthetic SCSS networks of size $N=1000$ nodes, generated with power-law degree distribution exponent $\gamma =2.50$, clustering parameter $\beta =2.50$ and variable attractiveness $\mathrm{\Lambda }$. Results are averaged over 10 network realizations for each choice of $\mathrm{\Lambda }$. [(c)–(f)] Hierarchy load spectra of 4 real networks. In all plots blue curves correspond to $h_i$ in Eq. (3) computed from the link hierarchy loads while red curves correspond to $h_i^{*}$ in Eq. (4) as given by the circular mean resultant vector. Dashed blue and dashed red lines indicate the corresponding average hierarchy load values for the whole network. Dashed black lines provide the reference level of the model, placed at hierarchy load $1/2$.

Figure 3

Link hierarchy loads of real networks. [(a) and (b)] Link hierarchy loads of the Enron and Metabolic networks, respectively. Each dot indicates the value of $h_{ij}$ of a link established between node $i$ and one of its lower-status neighbors $j$ with hidden degree ${\kappa }_j$ indicated by the color code. Notice node labels in the $x$ axis are sorted by increasing hidden degree ${\kappa }_i$, so that more popular $i$ nodes appear to the right.

Figure 4

Hierarchical similarity backbones. (a) A hierarchical similarity backbone of the World Trade Web [35] (in red) filtered with $\alpha =0.4$, on top of the complete network (pale blue). [(b)–(e)] Plots show in order: the relative number of nodes in the backbone, against the relative number of edges in the backbone (subindex 0 refers to the complete network); the relative number of nodes in the backbone giant connected component ($gcc$), against the relative number of edges in the backbone $gcc$; mean clustering coefficient of the backbone for increasing $\alpha$; number of disconnected components against increasing values of the significance $\alpha$ (f) Fraction of nodes considered hubs, for threshold value $\tau =0.25$, found in backbones obtained with increasing $\alpha$. [(g)–(i)] Topological features of the HSBs of the Music network, obtained for $\alpha$'s from 0.1 to 0.8. Value $\alpha =0.0$ corresponds to the original unaltered network, whereas in the most restrictive HSB ($\alpha =0.8$) $0.60\%$ of the nodes and $14\%$ of the links remain. From left to right: complementary cummulative probability distribution (CCP) of rescaled degrees, $k_{\mathrm{res}}=k/\langle k\rangle$, degree dependent clustering coefficient $\langle c\rangle$ over rescaled-degree classes, normalized average nearest-neighbor degree ${\langle k_{\mathrm{nn}}\rangle }_{\mathrm{res}}=\langle k_{\mathrm{nn}}\left(k_{\mathrm{res}}\right)\rangle \langle k\rangle /\langle k^2\rangle$.

Figure 5

Evolutionary game dynamics in HSBs of real networks. [(a)–(h)] Fraction of final cooperators against fraction of initial cooperators for similarity backbones of Enron, Internet, Music, and Metabolic networks. For every network we show two plots, each with the results of an HSB filtered with either ${\alpha }^{\mathrm{o}}$ or ${\alpha }^{▹}$ (see numeric values in Table 2). For an HSB (blue curve with symbols), the corresponding random surrogate appears as a grey dashed line together with the original network in black line for reference. [(i)–(l)] Relative number of nodes against relative number of edges in the $gcc$ of similarity backbones, and their corresponding surrogates, for the four networks under study. Blue lines correspond to backbones obtained using the similarity filter and red lines to surrogates obtained by random link removal. Blue circle and triangle symbols highlight the fraction of nodes and edges of the two similarity backbones filtered with ${\alpha }^{\mathrm{o}}$ and ${\alpha }^{▹}$, respectively. The same information is featured by red symbols for the random surrogates.

Figure 6

Hierarchy load spectrums for Geometric randomization (GR) model replicas of each of the 4 real networks under study. Each spectrum is the average over 10 independent realizations. Dashed lines indicate the average hierarchy load of the network, obtainded as ${\langle h\rangle }^{*}=N^{-1}{\sum }_{i=1}^N{h}_i^{*}$, yielding to the following values for each network: ${\langle h\rangle }_{\mathrm{Enron}}^{*}=0.82\pm 0.19, {\langle h\rangle }_{\mathrm{Internet}}^{*}=0.99\pm 0.02, {\langle h\rangle }_{\mathrm{Metabolic}}^{*}=0.99\pm 0.04$, and ${\langle h\rangle }_{\mathrm{Music}}^{*}=0.95\pm 0.11$.

Figure 7

Topological features of the hierarchical backbones of [(a)–(c)] Enron, [(d)–(f)] Internet, and [(g)–(i)] Metabolic, obtained for $\alpha \in [0.1–0.8]$. In each case, value $\alpha =0.0$ corresponds to the original network. The properties in each row, from left to right, are complementary cumulative distribution of rescaled degrees ($k_{\mathrm{res}}=k/\langle k\rangle$), degree dependent clustering coefficient over rescaled-degree classes, and normalized average nearest-neighbor degree ${\langle k_{\mathrm{nn}}\rangle }_{\mathrm{res}}=\langle k_{\mathrm{nn}}\left(k_{\mathrm{res}}\right)\rangle \langle k\rangle /\langle k^2\rangle$.

Figure 8

Topological properties of hierarchical backbones of the four real networks against increasingly restrictive filtering parameter ($\alpha$) values. Plots from (a) to (d) show, for increasing values of $\alpha$: the normalized number of nodes in the backbone; the normalized number of edges in the backbone; normalized average degree of the backbone and the HSB normalized maximum degree.

Figure 9

Fraction of nodes considered hubs for threshold values in range $\tau =[0.05–0.30]$, found in backbones obtained with increasing $\alpha$ for the real networks Enron, Internet, Metabolic, and Music.

Figure 10

Topological features of random surrogates and original network of [(a)–(c)] Enron, [(d)–(f)] Internet, [(g)–(i)] Metabolic, and [(j)–(l)] Music. In each case, value $LR$ indicates the number of links that have been removed at random to produce the surrogate backbone. The properties in each row, from left to right, are: complementary cumulative distribution of rescaled degrees $k_{\mathrm{res}}=k/\langle k\rangle$, degree dependent clustering coefficient over rescaled-degree classes, normalized average nearest-neighbor degree ${\langle k_{\mathrm{nn}}\rangle }_{\mathrm{res}}=\langle k_{\mathrm{nn}}\left(k_{\mathrm{res}}\right)\rangle \langle k\rangle /\langle k^2\rangle$.

Figure 11

Fraction of final cooperators against fraction of initial cooperators for similarity backbones and random surrogates of Music network under different payoffs. The results of the dynamics in each plot are obtained using the following payoff values for the evolutionary prisoner's dilemma game: (a) and (e) $T=1.0,R=0.5,P=-0.5,S=-1.0$ (b) and (f) $T=1.5,R=1.0,P=0.5,S=0.0$ (c) and (g) $T=2.0,R=1.5,P=0.5,S=0.0$ (d) and (h) $T=2.0,R=1.5,P=0.0,S=-0.5$. Results for the original network appear for reference, indicated by a black line. HSB filtered with $\alpha =0.53$ are shown as blue curves with circles whereas HSBs filterd with $\alpha =0.59$ correspond to blue curves with triangles in the second row. Results of random surrogates are displayed as grey dashed lines.