Sensitivity of directed networks to the addition and pruning of edges and vertices

Directed networks have various topologically different extensive components, in contrast to a single giant component in undirected networks. We study the sensitivity (response) of the sizes of these extensive components in directed complex networks to the addition and pruning of edges and vertices. We introduce the susceptibility, which quantifies this sensitivity. We show that topologically different parts of a directed network have different sensitivity to the addition and pruning of edges and vertices and, therefore, they are characterized by different susceptibilities. These susceptibilities diverge at the critical point of the directed percolation transition, signaling the appearance (or disappearance) of the giant strongly connected component in the infinite size limit. We demonstrate this behavior in randomly damaged real and synthetic directed complex networks, such as the World Wide Web, Twitter, the Caenorhabditis elegans neural network, directed Erdős-Rényi graphs, and others. We reveal a nonmonotonic dependence of the sensitivity to random pruning of edges or vertices in the case of C. elegans and Twitter that manifests specific structural peculiarities of these networks. We propose the measurements of the susceptibilities during the addition or pruning of edges and vertices as a new method for studying structural peculiarities of directed networks.

Figure 1

Schematic view of the structure of a directed network. There are the giant strongly connected component $G_S$ (the core of the network), the sets $\text{IN}$ and $\text{OUT}$, the finite-directed components $F$ [tendrils and tubes shown as domains of different colors, and disconnected finite clusters (open ovals)]. The union of these parts is the giant weakly connected component $G_W$. Tendrils belonging to the same layer have the same color. Edge tubes of different layers are shown in corresponding colors. Only three tendril layers are shown.

Figure 2

The addition of the edge $(i\to j)$ directed from vertex $i$ to vertex $j$ increases the out-component $s_{\text{out}}\left(i\right)$ of $i$ by an amount $s_{\text{out}}\left(j\right)$ and also increases the in-component $s_{\text{in}}\left(j\right)$ of $j$ by an amount $s_{\text{in}}\left(i\right)$. (a) In- and out-components of $i$ and $j$ do not intersect each other. (b) There are intersections between the in- and out-components.

Figure 3

Addition of the edge ($i\to j$) from vertex $i\in \text{OUT}$ (or $G_S$) to vertex $j\in F$ and the edge ($j\to i$) from vertex $j\in F$ to vertex $i\in \text{IN}$ (or $G_S$). (a) There are no intersections between the in- and out-component of vertex $j\in F$ and $\text{IN}$ and $\text{OUT}$. (b) The in- and out-components of vertex $j$ intersect $\text{IN}$ and $\text{OUT}$ (the shaded regions).

Figure 4

(a) The addition of an edge directed from vertex $j\in G_S$ to vertex $i\in \text{IN}$ increases the size of the giant strongly connected component $G_S$ due to vertices $l\in \text{IN}$ reachable from $i$. (b) The addition of an edge directed from vertex $i\in \text{OUT}$ to vertex $j\in G_S$ increases $G_S$ due to vertices $l\in \text{OUT}$ from which $i$ can be reached.

Figure 5

The addition of an edge directed from vertex $j\in \text{OUT}$ to vertex $i\in \text{IN}$ increases the size of the giant strongly connected component $G_S$ at the expense of vertices $l\in \text{IN}$ reachable from $i$ and vertices $m\in \text{OUT,}$ which can reach $j$ by following edge directions.

Figure 6

(a) Susceptibilities ${\chi }_d$, ${\chi }_{\text{in}}^{\left(S\right)}$, and ${\chi }_{\text{out}}^{\left(S\right)}$ versus the occupation probability $p$ in an Erdős-Rényi network of size $N={10}^6$ and the mean in- and out-degrees $\langle q_i\rangle =\langle q_o\rangle =2$. (b) Reciprocal susceptibilities: $1/{\chi }_d$, $1/{\chi }_{\text{in}}^{\left(S\right)}$, and $1/{\chi }_{\text{out}}^{\left(S\right)}$ versus $p$. (c) The ratio ${\chi }_{\text{in}}^{\left(S\right)}/{\chi }_d$ above $p_c$. 100 network realizations were used for each value of $p$, and in each realization $10\%$ of the vertices were sampled randomly. The dashed vertical line marks the percolation critical point, $p_c=1/2$. The curves corresponding to ${\chi }_{\text{in}}^{\left(S\right)}$ and ${\chi }_{\text{out}}^{\left(S\right)}$ in panels (a) and (b) must overlap in the infinite-size limit, as explained in the text. Observable differences near $p_c$ are only finite-size effects. The small mismatch between the positions of the maxima of these curves and $p_c$ is also due to finite size.

Figure 7

Susceptibilities ${\chi }_d$, ${\chi }_{\text{in}}^{\left(S\right)}$, and ${\chi }_{\text{out}}^{\left(S\right)}$, and the relative sizes of $\text{IN}$, $\text{OUT,}$ and $G_{\text{IO}}$ versus the occupation probability $p$: (a) an Erdős-Rényi network of size $N={10}^4$, mean total degree $\langle q_{\text{tot}}\rangle =5$; (b) the Gnutella p2p file sharing network ($N=62586,\langle q_{\text{tot}}\rangle =4.726$ [37, 38]); (c) the neural network of C. elegans ($N=495,\langle q_{\text{tot}}\rangle =32.073$ [30]). The vertical dashed lines correspond to $p_c$ determined by the message passing method of Ref. [20].

Figure 8

Susceptibilities ${\chi }_d$, ${\chi }_{\text{in}}^{\left(S\right)}$, and ${\chi }_{\text{out}}^{\left(S\right)}$, and the relative sizes of $\text{IN}$, $\text{OUT,}$ and $G_{\text{IO}}$ versus the occupation probability $p$: (a) a sample of the World Wide Web ($N=875713,\langle q_{\text{in}}\rangle =5.83$ [39, 40]), (b) a sample of Twitter ($N=456631,\langle q_{\text{in}}\rangle =32.53$ [6]).