Models and average properties of scale-free directed networks

We extend the merging model for undirected networks by Kim et al. [Eur. Phys. J. B 43, 369 (2004)] to directed networks and investigate the emerging scale-free networks. Two versions of the directed merging model, friendly and hostile merging, give rise to two distinct network types. We uncover that some nontrivial features of these two network types resemble two levels of a certain randomization/nonspecificity in the link reshuffling during network evolution. Furthermore, the same features show up, respectively, in metabolic networks and transcriptional networks. We introduce measures that single out the distinguishing features between the two prototype networks, as well as point out features that are beyond the prototypes.

Figure 1

(Color online) Friendly merging: (a) Node $i$ is randomly picked to merge with one of its out-link neighbors, $j$. (b) Node $i$ gets all the links that are connected to $j$ except the ones they have in common and the ones pointing to each other ($N_{\text{common},\text{in}}$ and $N_{\text{common},\text{out}}$), so one node and two links are taken away from the system shown in the figure. Node $i$ thus gets the in- and out-degree, ${\tilde{k}}_{i,\text{in}}=k_{i,\text{in}}+k_{j,\text{in}}-N_{\text{common},\text{in}}$ and ${\tilde{k}}_{i,\text{out}}=k_{i,\text{out}}+k_{j,\text{out}}-N_{\text{common},\text{out}}$, respectively. (c) One node and two links are put in at random to keep the system size constant.

Figure 2

(Color online) Friendly merging. (a) Cumulative degree distribution $P(⩾k)={\int }_k^{\infty }dkP\left(k\right)$ for $\gamma \approx 2.3$ and $⟨k_{\text{in}}⟩=⟨k_{\text{out}}⟩\approx 4.0$ (corresponding to $r=3$ in the update rule). (b) Demonstration that ${⟨k_{\text{in}}⟩}_{\text{out}}=k_{\text{out}}$ to good approximation. (c) Demonstration that the spread goes as $S_{\text{in}}\left(k_{\text{out}}\right)\propto k_{\text{out}}^{-1∕2}$ to good approximation; full line Eq. (3) and data points from simulations. The cutoff for large $k_{\text{out}}$ is a finite-size effect. (d) Proportion of links with in-, out-, and both in- and out-links.

Figure 3

(Color online) Hostile merging. (a) Node $i$ is randomly picked to merge with one of its out-links neighbors, $j$. (b) Node $i$ gets all the out-links that are connected to $j$ except the ones $i$ and $j$ have in common neighbors. The in-links to $j$ are randomly rewired to other nodes (excluding $i$). This means that one node and two links are taken away from the system. Node $i$ thus gets the in- and out-degree, ${\tilde{k}}_{i,\text{in}}=k_{i,\text{in}}$ and ${\tilde{k}}_{i,\text{out}}=k_{i,\text{out}}+k_{j,\text{out}}-N_{\text{common},\text{out}}$. (c) One node and two links are put in at random to keep the system size constant.

Figure 4

(Color online) Hostile merging. (a) Cumulative degree distribution $P_{\text{out}}(⩾k_{\text{out}})$ and $P_{\text{in}}(⩾k_{\text{in}})$ obtained for $⟨k⟩\approx 3.8$ (this particular value was chosen in order to facilitate comparison with the yeast network in Fig. 8), which corresponds to $r=1.5$ in the local update (the dotted straight line has the slope $-1.7$). (b) No correlations between ${⟨k_{\text{in}}⟩}_{\text{out}}$ and $k_{\text{out}}$ for the $k_{\text{out}}$ nodes because ${⟨k_{\text{in}}⟩}_{\text{out}}=⟨k_{\text{in}}⟩$ independent of $k_{\text{out}}$. (c) Also the spread $S_{\text{in}}\left(k_{\text{out}}\right)$ is independent of $k_{\text{out}}$. (d) Proportion of links with in-, out-, and both in- and out-links.

Figure 5

(Color online) Model A. (a) Cumulative degree distribution $P(⩾k)={\int }_k^{\infty }dkP\left(k\right)$ for $\gamma \approx 2.3$ and $⟨k⟩\approx 1.9$. (b) Demonstration that ${⟨k_{\text{in}}⟩}_{\text{out}}=k_{\text{out}}$. (An ER network has instead ${⟨k_{\text{in}}⟩}_{\text{out}}=⟨k⟩∕2$.) (c) Demonstration that the spread goes as $S_{\text{in}}\left(k_{\text{out}}\right)\propto k_{\text{out}}^{-1∕2}$. Full line, Eq. (3) and data points from simulations. The cutoff for large $k_{\text{out}}$ is a finite-size effect. (d) Proportion of links with in-, out-, and both in- and out-links.

Figure 6

(Color online) Model B. (a) Cumulative scale-free degree distribution $P_{\text{out}}(⩾k_{\text{out}})$ for $\gamma \approx 1.7$ and $⟨k_{\text{out}}⟩\approx 3.8$ together with the ER-like $P_{\text{in}}(⩾k_{\text{in}})$. (b) No correlations because ${⟨k_{\text{in}}⟩}_{\text{out}}=⟨k_{\text{in}}⟩$ independent of $k_{\text{out}}$. (c) The spread $S_{\text{in}}\left(k_{\text{out}}\right)$ independent of $k_{\text{out}}$ for the same reason. (d) Proportion of links with in-, out-, and both in- and out-links.

Figure 7

(Color online) Metabolic networks. Average over 107 metabolic networks with data obtained from Ref. 8. The same characteristics as for model A and friendly merging. (a) Cumulative degree distribution $P(⩾k)$. The dashed straight line has a slope $\gamma =2.3$ and $⟨k_{\text{in}}⟩=⟨k_{\text{out}}⟩\approx 4.3$. (b) Plot of ${⟨k_{\text{in}}⟩}_{\text{out}}$ vs $k_{\text{out}}$ showing that the data are consistent with ${⟨k_{\text{in}}⟩}_{\text{out}}=k_{\text{out}}$. (c) Demonstration that the spread goes as $S_{\text{in}}\left(k_{\text{out}}\right)\propto k_{\text{out}}^{-1∕2}$ to a reasonable approximation, full line from Eq. (3) and data points from simulations. The cutoff for large $k_{\text{out}}$ is a finite-size effect. (d) Proportion of links with in-, out-, and both in- and out-links.

Figure 8

(Color online) Transcription networks for yeast (data from Refs. 11, 12). The same characteristics as for model B and hostile merging. (a) Cumulative degree distribution $P_{\text{out}}(⩾k_{\text{out}})$ and $P_{\text{in}}(⩾k_{\text{in}})$ showing a broad distribution for the out-degrees (the dotted line is for comparison with hostile merging and has the slope $\gamma \approx 1.7$) and an ER-like distribution of in-links. (b) Shows that there are no correlations between ${⟨k_{\text{in}}⟩}_{\text{out}}$ and $k_{\text{out}}$ for the $k_{\text{out}}$ nodes. (c) Also the spread $S_{\text{in}}\left(k_{\text{out}}\right)$ is independent of $k_{\text{out}}$. (d) Proportion of links with in-, out-, and both in- and out-links.