The Hierarchical Backbone of Complex Networks

Given any complex directed network, a set of acyclic subgraphs can be extracted that will provide valuable information about its hierarchical structure. This Letter presents how the interpretation of the network weight matrix as a transition matrix allows the hierarchical backbone to be identified and characterized in terms of the concepts of hierarchical degree, which expresses the total weights of virtual edges established along successive transitions. The potential of the proposed approach is illustrated with respect to simulated random and preferential-attachment networks as well as real data related to word associations and gene sequencing.

Figure 1

A simple network (a) and its hierarchical components for $k=1$ (b) and $10$ (c). One of the virtual edges in this graph, namely, that between nodes 1 and 3, is illustrated by the dashed edge with weight 8. We also have $D_1=4$, $D_{10}=2$, $N_1=8$, $N_{10}=2$, ${\overrightarrow{u}}_1^{(t)}=2,2,3,1$, ${\overrightarrow{u}}_{10}^{(t)}=1,1$, $h_1^{(t)}=4,14,42,48$ and $h_{10}^{(t)}=1,3$.

Figure 2

Hierarchical degrees obtained after 200 realizations of random networks (a), their respective two-conditional expansions (b), and Barabási-Albert networks (c).

Figure 3

The first three levels of the hierarchy of the largest cluster in the word associations experiment.

Figure 4

Log-log densities of hierarchical degrees for the inverse word association data.

Figure 5

Distribution of hierarchical degrees for the word association experiment considering $t=2,3$ (a) and $t=2,5$ (b), and the scatterplots of hierarchical degree and number of hierarchical successors for $t=1$ (c1) and hierarchical degrees for $t=1$ and 2 (c2).

Figure 6

Relative frequencies of depths $D_k$, and cluster sizes $N_k$ (inset), for the word association (filled diamond), inverse word association (diamond), and amino acids sequence (×) experiments.