Controllability scores of linear time-varying network systems

Large-scale dynamical systems on networks are ubiquitous across various fields: power grids [1] and multi-agent systems [2] in engineering, brain networks [3] and ecosystems [4] in natural sciences, and opinion networks [5] in social sciences. Although nonengineering network systems are not necessarily controlled artificially, like engineering systems, they alter their dynamics in response to input signals and thus fall within the scope of modern control theory. For instance, the brain alters its dynamics for task demands [3], and ecosystems shift their dynamics in response to external disturbances [4]. Therefore, studying these networks from the perspective of modern control theory is crucial for performing efficient control or uncovering system properties, whether for engineering or nonengineering network systems, and has become an active area of research [6].

One approach to analyzing large-scale network systems is to identify key nodes in their dynamics. Among such approaches, a prominent method is the one proposed in [7], which is based on structural controllability [8], a qualitative concept. The method utilizes graph-theoretic tools and identifies a minimum set of nodes with which structural controllability is ensured when signals are applied. The selected nodes are considered key nodes for control. However, structural controllability is not necessarily a physically meaningful concept since structurally controllable systems may require a vast amount of energy for control [9], and thus controlling them is sometimes unrealistic. Consequently, as pointed out in [10], quantitative approaches are more favorable.

One of the prominent quantitative approaches is discussed in [11]. The method also identifies a set of key nodes by solving a combinatorial optimization problem based on a quantitative controllability metric. Alternatively, assessing network centrality quantitatively is also a frequently utilized way [11, 10]. For instance, ranking by centrality measure based on quantitative controllability is applied to brain networks [3]. The advantage of network centrality is that it provides a relative measure of importance rather than a binary assessment of whether being a key node or not. The controllability score is such a centrality index introduced in [12], and some numerical experiments show that it provides a more reasonable measure than other existing indices.

However, the controllability score still faces many challenges. One of them is that the applicability is limited to linear time-invariant (LTI) systems:

Although much effort for large-scale network systems has been focused on LTI systems [7, 11], there is an issue that they cannot capture dynamics on a network whose structure varies over time, such as temporal networks [13], unlike linear time-varying (LTV) systems:

Recent research reports that LTV systems on temporal networks and LTI systems exhibit qualitatively and quantitatively different properties, such as the minimum energy for control [14] and driver nodes [15]. Thus, the controllability score should be extended to apply to LTV systems. Moreover, the extension causes another challenge regarding reproducibility and interpretability. Since the controllability score is defined as an optimal solution to some optimization problem, it is not necessarily unique. Nevertheless, the uniqueness must be guaranteed to use it as a network centrality, as explained in more detail in Section II-D.

Another challenge is the requirement for knowledge of the system. Since the controllability score measures centrality quantitatively, the computation of it requires the value of the system matrix. Nevertheless, system identification is sometimes difficult, especially for LTV systems 2, since the system matrix $A(t)$ changes over time. Thus, a data-driven method should be developed to compute the controllability score using experimental data instead of the system matrix.

• •

  We extend the controllability score to apply to LTV systems. Furthermore, we prove that it is uniquely determined in two scenarios: the first for general systems and the second for temporal networks. The proof for general systems is similar to that in [16] but needs to be appropriately modified to suit the setting. Since the assumptions required for the proof are weak, we consider that the controllability score is unique in most practical cases. The uniqueness of the controllability score is critical for its use as a network centrality; thus, we can utilize it to measure the centrality of each node in networks. The second result is obtained by restricting the systems to temporal networks and modifying the assumptions. This leads to a stronger guarantee of uniqueness for temporal networks. Numerical experiments show different scores between LTI and LTV systems, which suggests the importance of the extension.

• •

  We propose a data-driven method to compute the controllability Gramian, which is required to calculate controllability scores. Although related work [17, 18] has proposed data-driven methods for the controllability Gramian, the methods are limited to LTI systems since they employ the Lyapunov equation, which applies to LTI systems but not LTV systems. In contrast, our proposed method can be applied to LTV systems since it relies on the integral representation. Moreover, we emphasize that the advantage of our proposed method is its applicability not only to temporal network systems, where the system matrix switches at certain times but remains piecewise constant, but also to general systems whose system matrices change continuously over time. Systems that are suitably modeled by the former are somewhat easier to identify [19]. However, for systems where the latter is appropriate, identification is significantly challenging, highlighting the advantage of this method. Numerical experiments show that our proposed method can accurately compute the controllability Gramian and the controllability scores.

The rest of the paper is organized as follows. In Section II, we introduce notations and summarize essential concepts such as temporal networks, the controllability Gramian, and the controllability score. In Section III, we extend the controllability score to apply to LTV systems and prove its uniqueness under some assumptions. In Section IV, we summarize the optimization algorithm to compute controllability scores and propose a data-driven method. In Section V, we show numerical experiments to compare controllability scores between LTI and LTV systems and to assess the performance of the proposed data-driven method. The concluding remarks are given in Section VI.

The set of all real numbers and the set of all complex numbers are denoted by $\mathbb{R}$ and $\mathbb{C}$, respectively. Let $n$ denote the number of nodes, and let $I$ and $O$ denote the identity matrix of order $n$ and the $n\times n$ zero matrix, respectively. Let $e_{i}\coloneq(0,\ldots,0,1,0,\ldots,0)^{\top}\in\mathbb{R}^{n}$ be a standard vector whose $i$th element is $1$ and other elements are $0$. For a vector $v=(v_{1},\ldots,v_{n})^{\top}\in\mathbb{R}^{n}$, $\left\|{v}\right\|\coloneq\sqrt{\sum_{i=1}^{n}v_{i}^{2}}$ denotes the standard Euclidean norm. The symbol $L^{2}[0,T]$ denotes the set of all square-integrable functions $u\colon[0,T]\to\mathbb{R}^{n}$, i.e., $L^{2}[0,T]\coloneq\left\{u\colon[0,T]\to\mathbb{R}^{n}\mid\int_{0}^{T}\left\|{u(t)}\right\|^{2}\mathrm{d}t<\infty\right\}$. For a square-integrable function $u\in L^{2}[0,T]$, $\left\|{u}\right\|_{L^{2}}\coloneq\sqrt{\int_{0}^{T}\left\|{u(t)}\right\|^{2}\mathrm{d}t}$ denotes the $L^{2}$ norm.

For a matrix $A\in\mathbb{R}^{n\times n}$, $\mathrm{e}^{A}$, $\det A$, and $\mathrm{tr}(A)$ denote the exponential of $A$, the determinant of $A$, and the trace of $A$, respectively. When $A$ is symmetric, we write $A\succ O$ to mean that $A$ is positive definite. For a vector $v=(v_{1},\ldots,v_{n})^{\top}\in\mathbb{R}^{n}$, let $\mathrm{diag}(v_{1},\ldots,v_{n})$ denote the diagonal matrix with the diagonal elements $v_{1},\ldots,v_{n}$. Instead of $\mathrm{diag}(v_{1},\ldots,v_{n})$, we also use $\mathrm{diag}(v)$. Let $S_{n}$ denote the symmetric group of order $n$. For $\sigma\in S_{n}$, $\mathrm{sgn}(\sigma)$ denotes the sign of the permutation $\sigma$. Let $\Delta$ be a standard simplex in $\mathbb{R}^{n}$, i.e., $\Delta\coloneq\left\{p\in\mathbb{R}^{n}\;\middle|\;p_{i}\geq 0\ (i=1,\ldots,n),\ \sum_{i=1}^{n}p_{i}=1\right\}$. Let $\mathbb{R}^{m}_{>0}\coloneq\{(t_{1},\ldots,t_{m})^{\top}\in\mathbb{R}^{m}\mid t_{k}>0\ (k=1,\ldots,m)\}$.

For an LTV system 2, $\Phi^{t}_{\tau}$ denotes the state transition matrix, which satisfies

As a caution, we often address cases where $A(t)$ is discontinuous, in which case we consider 3 in the sense of one-sided differentials at each discontinuous point.

Temporal networks [13] are an important subject targeted by this paper. A temporal network is represented by a chronologically ordered sequence of $m$ separate networks, where the node set is shared across all networks, but edge sets and edge weights vary in each network. Thus, each network can be expressed by a constant weighted adjacency matrix $A_{k}$. Let its duration be $\Delta t_{k}\ (k=1,\ldots,m)$.

Dynamical systems on temporal networks are modeled in [14] as LTV systems 2 with

where $t_{0}=0,\ t_{k}=\sum_{\ell=1}^{k}\Delta t_{\ell}$. In this paper, we also call the system 2 with 4 a temporal network, where the state transition matrix can be expressed as

where $t\in[t_{k-1},t_{k}],\ \tau\in[t_{\ell-1},t_{\ell}]$, and $\tau\leq t$.

In this subsection, we quickly review the controllability Gramian and then summarize the results of minimum-energy control.

We consider the following LTV system with control input:

The finite-time controllability Gramian for it is defined as

which is a symmetric positive semidefinite matrix. It is well-known that this matrix is related to the controllability of the system 6. The system is, for instance, controllable on the time interval $[0,T]$ if and only if $W_{\mathrm{LTV}}(T)\succ O$ [20].

Here, controllability itself is a concept that focuses solely on whether some control input can steer the state vector from the origin to any desired state within a finite time. The magnitude of the energy required for such a control input is not considered. That is, even if a system is controllable, achieving the desired state may be unrealistic since the required energy may be too large [9]. Thus, assessing the ability to control quantitatively is crucial when controlling a system. In this paper, we also refer to the quantitative control ability as “controllability”.

The controllability Gramian is also related to quantitative controllability, and the following result is known.

LTV systems 6 include LTI systems

as a special case. For an LTI system 7, let us specifically denote the controllability Gramian $W_{\mathrm{LTV}}(T)$ as $W_{\mathrm{LTI}}(T)$:

Obviously, the statement in Proposition 1, where the LTV system 6 is replaced by the LTI system 7 and $W_{\mathrm{LTV}}(T)$ by $W_{\mathrm{LTI}}(T)$, holds.

Therefore, by employing the controllability Gramian, we can quantitatively evaluate the controllability of LTI systems 7 and LTV systems 6. More specifically, we can utilize the following result, which follows from Proposition 1.

The reachable space $\mathcal{E}(T)$ is a set of all state vectors that can be achieved by some control input whose energy is less than or equal to $1$. We consider that the larger the volume of $\mathcal{E}(T)$ is, the easier the system is to control. Thus, we can use $\sqrt{\det W_{\mathrm{LTV}}(T)}$, or $\log\det W_{\mathrm{LTV}}(T)$, as a measure of controllability in the case of LTV systems 6. Since $\log\det W_{\mathrm{LTV}}(T)$ can often be computed more stably than $\sqrt{\det W_{\mathrm{LTV}}(T)}$ and its concavity is useful for optimization, we use $\log\det W_{\mathrm{LTV}}(T)$ rather than $\sqrt{\det W_{\mathrm{LTV}}(T)}$. Similarly, in the case of LTI systems 7, we use $\log\det W_{\mathrm{LTI}}(T)$ as a measure of controllability.

Alternatively, we can also utilize the following result.

The smaller the average of the minimum energy is, the more controllable we consider the system to be. Thus, in the case of LTV systems 6, we can regard $\mathrm{tr}\left(W_{\mathrm{LTV}}(T)^{-1}\right)$ as a measure of controllability, and in the case of LTI systems 7, $\mathrm{tr}\left(W_{\mathrm{LTI}}(T)^{-1}\right)$.

To define the controllability score, in [12], $\log\det W_{\mathrm{LTI}}(T)$ or $\mathrm{tr}\left(W_{\mathrm{LTI}}(T)^{-1}\right)$ is used to evaluate the controllability of LTI systems 7. Similarly, in this paper, we use $\log\det W_{\mathrm{LTV}}(T)$ or $\mathrm{tr}\left(W_{\mathrm{LTV}}(T)^{-1}\right)$ to evaluate the controllability of LTV systems 6.

The controllability score [12] is a network centrality measure that assesses the significance of each node in the dynamical system on the network. Previous studies [12, 16] have focused on LTI system models 1 of dynamical systems on large-scale networks. Here, $x(t)=(x_{1}(t),\ldots,x_{n}(t))^{\top}\in\mathbb{R}^{n}$ and $A$ in 1 represent the states of nodes and the structure of the network, respectively.

To define the controllability scores, we consider the following equation, which adds a hypothetical control input term to 1:

where $u(t)=(u_{1}(t),\ldots,u_{n}(t))^{\top}\in\mathbb{R}^{n}$ is a hypothetical control input and $p=(p_{1},\ldots,p_{n})^{\top}\in\mathbb{R}^{n}$ is assumed to satisfy

Equation 8 corresponds to an LTI system 7 where $B=\mathrm{diag}(\sqrt{p_{1}},\ldots,\sqrt{p_{n}})$. From 8, node $x_{i}$ and input $u_{i}$ correspond one-to-one. The larger $p_{i}$ is, the more significant the influence of control input $u_{i}$ on node $x_{i}$ can be.

Here, let us regard $p$ as a design variable and consider maximizing the controllability of the system 8 concerning some measure. When the optimal solution is $p^{*}=(p_{1}^{*},\ldots,p_{n}^{*})^{\top}$, if $p_{i}^{*}$ is large, it indicates that we can efficiently control the system 8 by actively influencing node $x_{i}$. Thus, we can consider node $x_{i}$ as a pivotal node. On the other hand, if $p_{i}^{*}$ is small, it suggests that we can control the system 8 without significantly influencing node $x_{i}$, meaning that node $x_{i}$ is not a critical node. Therefore, the optimal solution $p^{*}$ can be interpreted as the importance of each node, and the constraint 9 represents the importance distribution, where they are nonnegative and the sum equals $1$. The controllability score is defined as the optimal solution $p^{*}$.

As described in Section II-C, several indices for controllability are possible. Accordingly, let us consider the following two optimization problems.

Here,

is the controllability Gramian for the considered LTI system 8. The constant $T>0$ is the final time to evaluate the controllability, a parameter one must choose to meet their objective. Note that the constraint $p\in\Delta$ is equivalent to 9. The optimal solutions to Problems 1 and 2 are referred to as volumetric controllability score (VCS) and average energy controllability score (AECS), respectively.

However, there are two points to be noted when interpreting the controllability score as the importance of each node. The first point is that an optimal solution must exist, but this is not an issue since it has been shown that it exists for all LTI systems 1 and the final time $T>0$ [12]. The second point, a more significant issue, is that an optimal solution must be unique. If the optimal solution is not unique, a reproducibility issue arises since different researchers analyzing the same network may arrive at different conclusions. Additionally, from the perspective of interpretability, there is also an issue of how to determine node importance based on the solutions, which is not clear. For these reasons, the controllability score must be unique; however, there exists a case where both the optimal solutions to Problems 1 and 2 are not unique [12].

Therefore, clarifying the conditions under which controllability scores are uniquely determined is crucial for utilizing it as a centrality measure. The following results have been shown regarding this issue.

From Proposition 5, when considering LTI systems 1 on networks, the controllability score is unique in most practical cases.

Let us consider LTV system models 2 of dynamical systems on large-scale networks. Similar to the case of LTI systems, let $x(t)=(x_{1}(t),\ldots,x_{n}(t))^{\top}\in\mathbb{R}^{n}$ represent the states of nodes, and $A(t)$ represent the time-varying structure of the network. We consider the following assumption for $A(t)$.

Note that Assumption 1 is not restrictive at all. In fact, temporal networks, as described in Section II-B, satisfy Assumption 1, and any piecewise continuous matrix can be arbitrarily well approximated by $A(t)$ that satisfies Assumption 1. Thus, the range of systems that satisfy Assumption 1 is sufficiently broad for practical purposes.

The main idea of the controllability score for LTV systems is the same as that for LTI systems. Let us consider the following equation, which adds a hypothetical control input term to 2:

Similar to the case of LTI systems, $p=(p_{1},\ldots,p_{n})^{\top}\in\mathbb{R}^{n}$ is assumed to satisfy 9. Note that $p$ is not dependent on $t$, as detailed in Remark 1. Since 10 corresponds to the case where $B(t)\equiv\mathrm{diag}(\sqrt{p_{1}},\ldots,\sqrt{p_{n}})$ in 6, this assumption can be interpreted as $B(t)$ being a diagonal constant matrix.

For LTV systems 6, we can consider the optimal solutions to the following optimization problems similar to Problems 1 and 2 as the importance of each node.

Here,

is the controllability Gramian for the considered LTV system 10, and $T$ is a final time that satisfies $0=t_{0}<T\leq t_{\mathrm{f}}$. While $t_{\mathrm{f}}$ is the final time of the time interval over which $A(t)$ is defined, $T$ is the final time of the time interval for evaluating the controllability of the system 10. One must choose $T$ appropriately to meet their objective. Since the controllability score is unique in most cases as shown in Section III-B, we consider that setting $T=t_{\mathrm{f}}$ poses no practical issues.

Similar to the case of LTI systems, let us refer to the optimal solutions to Problems 3 and 4 as VCS and AECS, respectively. As discussed in Section II-D, their existence and uniqueness are crucial to utilize them as a centrality measure. Their existence can be easily proved without assuming Assumption 1, in the same manner as the case of LTI systems.

Proving the uniqueness is more complicated. For a certain system, the optimal solution is not unique at a specific final time $T$ [12]. However, the uniqueness at almost all final time $T$ is sufficient for practical use. We can prove it under Assumption 1 since we can utilize the identity theorem, as shown in Section III-B.

In addition, calculating controllability scores is also an important issue. A specific algorithm is described in Section IV. The convexity of the objective function, which can be proved in the same manner as the case of LTI systems, is crucial for computation.

Therefore, the optimal solution can be efficiently computed.

In this subsection, we describe the result of the uniqueness of controllability scores under Assumption 1. As stated in Section III-A, Assumption 1 is not restrictive and holds in practice. The main idea is to modify the proof of [16] to apply to systems that satisfy Assumption 1. In this process, Assumption 2, which will be described later, is additionally required; however, we consider that it is also sufficiently weak and that it does not cause a practical issue, as explained in Remark 2 later.

The following well-known lemma [21] plays an essential role in the proof, and Assumption 1 is required to use this lemma.

Moreover, the following lemma is also crucial, which can be proved in the same manner as [16]. Assumption 1 is not required to use this lemma.

Roughly speaking, the regularity of $R(T;s)$ is a sufficient condition that the objective functions in Problems 3 and 4 are strictly convex functions on the feasible region, which guarantees the uniqueness of the optimal solution. Although a similar matrix is introduced in [16], the major difference lies in the second variable $s$, which can be used to modify the technique in [16] to the setting in this paper.

Related to Lemma 2, we make the following assumption.

Assumption 2 is not restrictive, as detailed in Remark 2.

From Lemmas 1 and 2, we can prove the following theorem.

As mentioned repeatedly, the uniqueness of the controllability score is crucial to utilizing it as a centrality measure. From Theorem 3, we consider that the controllability score is unique in most practical cases.

In this subsection, we show the uniqueness of controllability scores for temporal networks, i.e., LTV systems 2 with 4. The main idea is to focus on the time parameters rather than the final time, unlike Section III-B. This discussion allows us to show that, without Assumption 2, the controllability scores are uniquely determined in most cases.

Throughout this subsection, we assume that $A(t)$ is expressed as 4. Let weight matrices $A_{1},\ldots,A_{m}$ in 4 be fixed in this subsection. Let us express the time constants of $A(t)$ by durations $\Delta t=(\Delta t_{1},\ldots,\Delta t_{m})^{\top}\in\mathbb{R}^{m}_{>0}$ rather than switching times $t_{0},\ldots,t_{m}$. Accordingly, we redefine the notation only in this subsection and represent the state transition matrix as $\Phi_{\tau}^{t}(\Delta t_{1},\ldots,\Delta t_{m})$ or $\Phi_{\tau}^{t}(\Delta t)$, which can be calculated as 5 and the controllability Gramian as

where $t_{\mathrm{f}}\coloneq\sum_{k=1}^{m}\Delta t_{k}$. Furthermore, let the final time $T$ to evaluate the controllability of the system 10 be fixed to $t_{\mathrm{f}}$. This assumption is merely for notational simplicity since the final time $t_{\mathrm{f}}$ can be altered by shortening the time over which the system is defined.

Under these settings, Problems 3 and 4 can be rewritten as follows.

Note that Problems 5 and 6 are the same problems as Problems 3 and 4, differing only in notation.

For temporal networks, the following lemma is important.

Note that $R_{k}(\Delta t)$ coincides with 11 when $T=s=t_{k}$. From Lemmas 1, 2, and 3, we can prove the following theorem.

The scope of Theorem 4 is narrower than that of Theorem 3, but it does not require Assumption 2 and guarantees uniqueness of the controllability score for almost all time parameters.

To calculate controllability scores, the optimal solutions to Problems 3 and 4, we can employ the projected gradient method (Algorithm 1), which is the same algorithm as the case of LTI systems [12]. Here, $f$ is the objective function, $\Pi_{\Delta}$ is a Euclidian projection onto $\Delta$, and $W_{i}$ is defined as