Degree landscapes in scale-free networks

We generalize the degree-organizational view of real-world networks with broad degree distributions in a landscape analog with mountains (high-degree nodes) and valleys (low-degree nodes). For example, correlated degrees between adjacent nodes correspond to smooth landscapes (social networks), hierarchical networks to one-mountain landscapes (the Internet), and degree-disassortative networks without hierarchical features to rough landscapes with several mountains. To quantify the topology, we here measure the widths of the mountains and the separation between different mountains. We also generate ridge landscapes to model networks organized under constraints imposed by the space the networks are embedded in, associated to spatial or in molecular networks to functional localization.

Figure 1

(Color online) Degree landscape of a network with mountains and valleys, with the altitude of a node proportional to its degree. A route over one mountain corresponds to making a degree-hierarchical path [(a) to (b)] while climbing over more than one mountain breaks the degree-hierarchical path [(a) to (c)].

Figure 2

(Color online) Visualization of degree landscapes of networks organized from ridge landscapes (c), via random landscapes (e), to peaked one-mountain landscapes (g). The links are pairwise swapped to connect high-ranked nodes to organize the nodes globally according to their rank (color coded from dark red for high rank, to light white for low rank), with random swaps at different rates $\epsilon$. The rank is set randomly to the nodes, as in the swap example in (a), in (c) and (d), and proportional to the degree of the nodes, as in the swap example in (b), in (f) and (g). The random network in (e) corresponds to $\epsilon =1$. The corresponding visualization of the degree landscapes are color coded according to altitude from black (low) to white (high). The networks are scale-free with an exponent $\gamma =2.5$ and of size $N=400$, originally generated with the algorithm suggested [11]. The layout is generated with the Kamada-Kawai algorithm in Pajek [14].

Figure 3

Visualization of degree landscapes of real-world networks. The coloring of the altitudes are relative to the summit altitude. Yeast in (a) is the protein-protein interaction network in Saccharomyces Cerevisia [20], Manhattan in (b) is the dual map of Manhattan with streets as nodes and intersections as links [21], and the Internet in (c) is the network of autonomous systems [22]. The topological maps are not based on the real space the networks are embedded in, but the Kamada-Kawai algorithm in Pajek [14].

Figure 4

(Color online) The degree-hierarchical organization as a function of path length. $\mathcal{F}\left(\ell \right)$ is the fraction of pair of nodes, separated by a distance $\ell$, that are connected by a degree-hierarchical path. (a) shows the two model networks: The degree-rank hierarchy (degree-rank), the random-rank hierarchy (random-rank) for $\epsilon =0$ and 0.1, together with the random scale-free network (random). The real-world networks in (b)–(d) are the same as in Fig. 3. All networks are compared with their random counterparts (Rand).

Figure 5

(Color online) Hub separation in networks measured as the average longest distance $d\left(k_{\mathrm{hub}}\right)$ between all nodes of degree $k⩾k_{\mathrm{hub}}$, Eq. (1), for the same networks as in Fig. 4. The results are ${\log }_2$ binned.