Controllability of giant connected components in a directed network

When controlling a complex networked system it is not feasible to control the full network because many networks, including biological, technological, and social systems, are massive in size and complexity. But neither is it necessary to control the full network. In complex networks, the giant connected components provide the essential information about the entire system. How to control these giant connected components of a network remains an open question. We derive the mathematical expression of the degree distributions for four types of giant connected components and develop an analytic tool for studying the controllability of these giant connected components. We find that for both Erdős-Rényi (ER) networks and scale-free (SF) networks with $p$ fraction of remaining nodes, the minimum driver node density to control the giant component first increases and then decreases as $p$ increases from zero to one, showing a peak at a critical point $p=p_{\mathrm{m}}$. We find that, for ER networks, the peak value of the driver node density remains the same regardless of its average degree $\langle k\rangle$ and that it is determined by $p_{\mathrm{m}}\langle k\rangle$. In addition, we find that for SF networks the minimum driver node densities needed to control the giant components of networks decrease as the degree distribution exponents increase. Comparing the controllability of the giant components of ER networks and SF networks, we find that when the fraction of remaining nodes $p$ is low, the giant in-connected, out-connected, and strong-connected components in ER networks have lower controllability than those in SF networks.

Figure 1

The in- and out-degree distributions of the full network, and the four giant components of a network with the in-degrees Poisson distributed and the out-degrees power law distributed, after removing $p=0.5$ fraction nodes from the original network. (a), The in-degree distribution and (b) the out-degree distribution the remaining part after nodes removal (full) and the GWCC of a network with the average degree $\langle k\rangle =4$. The average degree of the original network of (c) and (d) is $\langle k\rangle =4$. From (c) and (d), we find that (1) the in-degree distribution of the GIN is the same as that of the full network $P^{\left(\mathrm{in}\right)}\left(k_{\mathrm{in}}\right)=P\left(k_{\mathrm{in}}\right)$; (2) the out-degree distribution of the GOUT is the same as that of the full network $P^{\left(\mathrm{out}\right)}\left(k_{\mathrm{out}}\right)=P\left(k_{\mathrm{out}}\right)$; (3) the in-degree distribution of the GSCC is the same as the in-degree distribution of the GOUT $P^{\left(\mathrm{s}\right)}\left(k_{\mathrm{in}}\right)=P^{\left(\mathrm{out}\right)}\left(k_{\mathrm{in}}\right)$; and (4) the out-degree distribution of GSCC is the same as the out-degree distribution of the GIN $P^{\left(\mathrm{s}\right)}\left(k_{\mathrm{out}}\right)=P^{\left(\mathrm{in}\right)}\left(k_{\mathrm{out}}\right)$. The out-degree distribution exponent of the network in (b) and (d) is $\lambda =2.5$. The lines represent theoretic results and they agree with the simulation results (denoted by symbols and the size of each network is $N={10}^6$).

Figure 2

The driver node densities of the GWCC, GIN(GOUT) and GSCC of ER networks. The driver node density $g_{\mathrm{D}}$ for each giant component first increases and then decreases, as (a) the fraction of the remaining nodes $p$ is increasing and (b) the average degree $\langle k\rangle$ is increasing, showing a peak. The solid lines represent the theoretic results, when $\langle k\rangle =6$ in (a) and $p=0.6$ in (b), and the symbols are simulation results where each network with the number of nodes $N={10}^6$. They agree well with each other.

Figure 3

Analysis of the peak value of driver node density for controlling the giant components of ER networks. The peak value $g_{\mathrm{Dm}}$ remains the same under different fraction of remaining nodes $p$ and different average $\langle k\rangle$ for (a) the GWCC, (b) the GIN/GOUT, and (c) the GSCC. (d) The critical point $p_{\mathrm{m}}$ in an ER network with average degree $\langle k\rangle$ where the driver node densities of the GWCC, GIN(GOUT) and GSCC reach their maximums: for the GWCC (solid line), the minimum driver node density reaches its maximal value $n_{pD}^{\left(\mathrm{w}\right)}=0.2888$ when $p_{\mathrm{m}}=\frac{2.2567}{\langle k\rangle }$; for the GIN(GOUT) (dot dash line), the minimum driver node density reaches its maximal value $n_{pD}^{\left(\mathrm{in}\right)}=0.1648$ when $p_{\mathrm{m}}=\frac{3.2385}{\langle k\rangle }$; for the GSCC (dash line), the minimum driver node density reaches its maximal value $n_{pD}^{\left(\mathrm{s}\right)}=0.0726$ when $p_{\mathrm{m}}=\frac{4.1234}{\langle k\rangle }$.

Figure 4

The minimum driver node densities of the giant components of SF networks. (a) As the fraction of remaining nodes $p$ changes from zero to one, for each giant component, the driver node density $g_{\mathrm{D}}$ increases and then decreases, displaying a peak. (b) The driver node density $g_{\mathrm{D}}$ decreases constantly as the degree distribution exponent $\lambda$ increases. The solid lines are the theoretic results when $\lambda =2.6$ for (a) and $p=0.6$ for (b). The symbols are simulation results where each network with the number of nodes $N={10}^6$ and agree well with each other.

Figure 5

The minimum driver node densities of the (a) GWCC, (b) GIN, and (c) GSCC of SF networks with different values of $\lambda$ and ER networks. For each giant component, the driver node densities first increase and then decrease as the remaining node fraction $p$ increases, showing a peak value at the critical point $p_m$. The peak values are different for different values of $\lambda$. For SF networks with different $\lambda$, the driver node densities $g_D$ for decrease as $\lambda$ increases. The average degrees of SF networks with $\lambda =2.6, \lambda =2.8$, and $\lambda =3.2$ are respectively equal to the average degrees of ER network with $\langle k\rangle =9.6, \langle k\rangle =8.1$, and $\langle k\rangle =6.5$. The GWCC in ER networks is easier to control than that in SF networks with the same average degree. For the GIN and GSCC, ER networks are not always easier to control than SF networks. When the fraction of remaining nodes $p$ is low, ER networks have lower controllability than SF networks.

Figure 6

Critical, redundant, and ordinary nodes based attack. Panels (a), (b), and (c) respectively show how the minimum driver node density $g_D^{\left(w\right)}$ required to control the GWCC changes when $1-p_{cr}$ fraction of critical nodes, $1-p_{or}$ fraction of ordinary nodes, and $1-p_{re}$ redundant nodes are removed from the network. Panels (d), (e), and (f) show the behavior of the minimum driver node density $g_D^{\left(\mathrm{in}\right)}$ or $g_D^{\left(\mathrm{out}\right)}$ required to control the GIN or GOUT. Panels (g), (h), and (i) show the behavior of the minimum driver node density $g_D^{\left(s\right)}$ required to control the GSCC. When we only remove critical nodes, $g_D$ may continuously increase, or continuously decrease for different densities of critical nodes among the network. When only redundant or ordinary nodes removed, $g_D$ may continuously increase, continuously decrease, or first increase and then decrease for different densities of redundant and ordinary nodes among the whole network.