Controllability of multiplex, multi-time-scale networks

The paradigm of layered networks is used to describe many real-world systems, from biological networks to social organizations and transportation systems. While recently there has been much progress in understanding the general properties of multilayer networks, our understanding of how to control such systems remains limited. One fundamental aspect that makes this endeavor challenging is that each layer can operate at a different time scale; thus, we cannot directly apply standard ideas from structural control theory of individual networks. Here we address the problem of controlling multilayer and multi-time-scale networks focusing on two-layer multiplex networks with one-to-one interlayer coupling. We investigate the practically relevant case when the control signal is applied to the nodes of one layer. We develop a theory based on disjoint path covers to determine the minimum number of inputs $\left(N_{\mathrm{i}}\right)$ necessary for full control. We show that if both layers operate on the same time scale, then the network structure of both layers equally affect controllability. In the presence of time-scale separation, controllability is enhanced if the controller interacts with the faster layer: $N_{\mathrm{i}}$ decreases as the time-scale difference increases up to a critical time-scale difference, above which $N_{\mathrm{i}}$ remains constant and is completely determined by the faster layer. We show that the critical time-scale difference is large if layer I is easy and layer II is hard to control in isolation. In contrast, control becomes increasingly difficult if the controller interacts with the layer operating on the slower time scale and increasing time-scale separation leads to increased $N_{\mathrm{i}}$, again up to a critical value, above which $N_{\mathrm{i}}$ still depends on the structure of both layers. This critical value is largely determined by the longest path in the faster layer that does not involve cycles. By identifying the underlying mechanisms that connect time-scale difference and controllability for a simplified model, we provide crucial insight into disentangling how our ability to control real interacting complex systems is affected by a variety of sources of complexity.

Figure 1

Structural controllability of two-layer multiplex networks. (a) A two-layer network. (b)–(d) To determine $N_{\mathrm{i}}$, we construct the dynamic graph representing the time evolution of the system from $t_0=0$ to $t_1=max({\tau }_{\mathrm{I}},{\tau }_{\mathrm{II}})$. The system is controllable only if all nodes at $t_1$ (blue) are connected to nodes at $t_0$ or nodes representing control signals (green) via disjoint paths (red). (b) In case of no time-scale separation $\left({\tau }_{\mathrm{I}}={\tau }_{\mathrm{II}}=1\right)$, each disjoint control path consists of a single link, yielding $N_{\mathrm{i}}=2$. (c) If layer I updates twice as frequently as layer II (${\tau }_{\mathrm{I}}=1,{\tau }_{\mathrm{II}}=2$), we are allowed to inject control signals at time steps $t=0$ and 1, reducing the number of inputs to $N_{\mathrm{i}}=1$. (d) On the other hand, if layer II is faster $({\tau }_{\mathrm{I}}=2,{\tau }_{\mathrm{II}}=1)$, layer II needs to support longer control paths, yielding $N_{\mathrm{i}}=3$.

Figure 2

Structural controllability of single-layer networks. (a) A single-layer network; we apply inputs to nodes $v_A$ and $v_B$. (b) The dynamic graph ${\mathcal{D}}_N$ representing the time evolution of the dynamics from $t=0$ to $t=N$. The system is controllable because we can connect the set of nodes representing control signals (green) to the set of nodes at $t=N$ (blue) via disjoint paths (red). (c) The dynamic graph ${\mathcal{D}}_1$ representing the time evolution of the dynamics from $t=0$ to $t=1$. The system is controllable, because we can connect the control signals and nodes at $t=0$ (green) to the set of nodes at $t=1$ (blue) via disjoint paths (red), and all nodes are accessible from control signals.

Figure 3

No time-scale separation. (a) Number of inputs $n_{\mathrm{i}}$ in function of $c_{\mathrm{I}}$ for ER-ER and SF-SF $\left({\gamma }_{\mathrm{I}}={\gamma }_{\mathrm{II}}=2.5\right)$ networks. The circles represent simulations, the continuous line is the analytical solution, and the dashed line is the analytical solution of $n_{\mathrm{i}}^{\mathrm{II}}$, the number of independent inputs necessary to control layer II in isolation [10]. (b) $n_{\mathrm{i}}$ for ER-ER networks with varying average degrees $c_{\mathrm{I}}$ and $c_{\mathrm{II}}$. In both layers $P\left(k\right)=P\left(k_{\mathrm{in}}\right)=P\left(k_{\mathrm{out}}\right)$; therefore, the heat map is symmetric with respect to the diagonal. Increasing $c$ in either layer enhances controllability. (c) $n_{\mathrm{i}}$ for SF-SF networks with $c_{\mathrm{I}}=c_{\mathrm{II}}=4.0$ and varying degree exponents ${\gamma }_{\mathrm{I}}$ and ${\gamma }_{\mathrm{II}}$. Increasing degree heterogeneity in either layer increases $n_{\mathrm{i}}$. Each data point is the average over ten randomly generated networks with $N=10000$. The standard deviation of the measurements remains below 0.01.

Figure 4

Layer I updates faster. (a) Number of inputs $n_{\mathrm{i}}$ for single ER-ER and SF-SF $\left({\gamma }_{\mathrm{I}}={\gamma }_{\mathrm{II}}=2.5\right)$ networks with $N=10000$ and varying time-scale parameter ${\tau }_{\mathrm{II}}$. The number of inputs $n_{\mathrm{i}}$ monotonically decreases with increasing ${\tau }_{\mathrm{II}}$, and for ${\tau }_{\mathrm{II}}\ge {\tau }_{\mathrm{II}}^{\mathrm{c}}$ and $n_{\mathrm{i}}=n_{\mathrm{i}}^{\mathrm{I}}$. (b) The critical time-scale parameter ${\tau }_{\mathrm{II}}^{\mathrm{c}}$ for ER-ER and SF-SF $\left({\gamma }_{\mathrm{I}}={\gamma }_{\mathrm{II}}=2.5\right)$ networks with varying average degree $c_{\mathrm{I}}$ and $c_{\mathrm{II}}$. The crosses represent direct measurements of ${\tau }_{\mathrm{II}}^{\mathrm{c}}$; the squares represent the approximation obtained by applying Eq. (7) to measurements of $n_{\mathrm{i}}({\tau }_{\mathrm{II}}=1)$ and $n_{\mathrm{i}}^{\mathrm{I}}$; and the dashed line is an approximation obtained using analytically calculated expectation values of $n_{\mathrm{i}}({\tau }_{\mathrm{II}}=1)$ and $n_{\mathrm{i}}^{\mathrm{I}}$. (c) We measure ${\tau }_{\mathrm{II}}^{\mathrm{c}}$ for SF-SF networks with the same $n_{\mathrm{i}}({\tau }_{\mathrm{II}}=1)$ and $n_{\mathrm{i}}^{\mathrm{I}}$ as a function of $\gamma ={\gamma }_{\mathrm{I}}={\gamma }_{\mathrm{II}}$. Equation (7) predicts that ${\tau }_{\mathrm{II}}^{\mathrm{c}}$ remains constant (dashed line), in line with our observations. For (b),(c), each data point is the average over ten randomly generated networks with $N=10000$ and error bars represent the standard deviation.

Figure 5

Layer II updates faster. (a) Number of inputs $n_{\mathrm{i}}$ for single ER-ER and SF-SF $\left({\gamma }_{\mathrm{I}}={\gamma }_{\mathrm{II}}=2.5\right)$ networks with $N=10000$ and varying time-scale parameter ${\tau }_{\mathrm{I}}$. The number of inputs $n_{\mathrm{i}}$ monotonically increases with increasing ${\tau }_{\mathrm{I}}$; for ${\tau }_{\mathrm{I}}\ge {\tau }_{\mathrm{I}}^{\mathrm{c}},n_{\mathrm{i}}=n_{\mathrm{i}}({\tau }_{\mathrm{I}}=\infty )$. (b) ${\tau }_{\mathrm{I}}^{\mathrm{c}}$ as a function of $c_{\mathrm{I}}$. For $c_{\mathrm{I}}\le 1,{\tau }_{\mathrm{I}}^{\mathrm{c}}$ quickly reaches its upper bound; for $c_{\mathrm{I}}>1$, the convergence is somewhat delayed. (c) $n_{\mathrm{i}}({\tau }_{\mathrm{I}}=\infty )$ as a function of $c_{\mathrm{I}}$. Increasing $c_{\mathrm{I}}$ facilitates control, until $n_{\mathrm{i}}$ reaches its lower bound. (d) ${\tau }_{\mathrm{I}}^{\mathrm{c}}$ as a function of $c_{\mathrm{II}}$ with fix $c_{\mathrm{I}}=4.0$. The peak of ${\tau }_{\mathrm{I}}^{\mathrm{c}}$ corresponds to the critical point where the giant strongly connected component in layer II emerges. (e) $n_{\mathrm{i}}({\tau }_{\mathrm{I}}=\infty )$ as a function of $c_{\mathrm{II}}$ with fix $c_{\mathrm{I}}=4.0$. For $c_{\mathrm{II}}<1$, layer II does not contain cycles; therefore, $n_{\mathrm{i}}({\tau }_{\mathrm{I}}=\infty )=1$. For large $c_{\mathrm{II}}$, layer II can be completely covered with cycles, and $n_{\mathrm{i}}({\tau }_{\mathrm{I}}=\infty )$ is determined by $n_{\mathrm{i}}^{\mathrm{I}}$. For (b)–(e), each data point is the average over ten randomly generated networks with $N=10000$ and error bars represent the standard deviation.

Figure 6

Layer II updates faster: network size effects. Critical time-scale parameter for ER-ER networks and SF-SF networks with varying network size $N$. (a) Layer II has no giant strongly connected component $\left(c_{\mathrm{II}}=0.5<1\right),l_{\max }$ equals the diameter $D$ of layer II, which scales as $D\sim logN$ for ER networks, and the diameter of SF networks is smaller than the diameter of ER networks with the same average degree. The fact that $l_{\max }+1\ge {\tau }_{\mathrm{I}}^{\mathrm{c}}$ suggests that ${\tau }_{\mathrm{I}}^{\mathrm{c}}\sim log\left(N\right)$. (b) At the critical point $c_{\mathrm{II}}=1.0$ the diameter of ER networks scales as $D\sim N^{1/3}$, suggesting that ${\tau }_{\mathrm{I}}^{\mathrm{c}}$ scales as a power law of $N$. (c) Above the critical point $\left(c_{\mathrm{II}}=4.0>1\right)$ there is no direct connection between $D$ and ${\tau }_{\mathrm{I}}^{\mathrm{c}}$; nonetheless, observations suggest ${\tau }_{\mathrm{I}}^{\mathrm{c}}\sim logN$. In contrast with the $c_{\mathrm{II}}\le 1$ case, ${\tau }_{\mathrm{I}}^{\mathrm{c}}$ increases more rapidly for SF-SF networks than for ER-ER networks. Each data point is the average over 100 randomly generated networks with $c_{\mathrm{I}}=4.0$ and error bars represent the standard deviation.

Figure 7

$l_{\max }$, example 1. (a) A directed network with tree structure, therefore not containing cycles. The diameter $D=2$ is the length of the longest path. (b) We count the maximum number of disjoint control paths $N_{\mathrm{path}}\left(l\right)$ which connect nodes at time step 0 with nodes at time step $l$. We find that $l^{\prime }=3$ is the smallest value of $l$ such that $N_{\mathrm{path}}\left(l\right)=N_{\mathrm{cycle}}=0$; therefore, $l_{\max }=2$. There are no cycles; therefore, $l_{\max }=D$.

Figure 8

$l_{\max }$, example 2. (a) A directed network containing a cycle. The size of the maximum cycle cover is $N_{\mathrm{cycle}}=1$. (b) We count the maximum number of disjoint control paths $N_{\mathrm{path}}\left(l\right)$ which connect nodes at time step 0 with nodes at time step $l$. We find that $l^{\prime }=2$ is the smallest value of $l$ such that $N_{\mathrm{path}}\left(l\right)=N_{\mathrm{cycle}}=1$; therefore, $l_{\max }=1$. $N_{\mathrm{path}}\left(l\right)$ remains nonzero for $l>l_{\max }$, showing that cycles can support control paths of any length.