Inferring Topology of Networked Dynamical Systems by Active Excitations

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a directed graph that models the networked system, where $\mathcal{V}=\{1,\cdots,n\}$ is the finite set of nodes and $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the set of interaction edges. An edge $(i,j)\in\mathcal{E}$ indicates that $i$ will use information from $j$. The adjacency matrix $A=[a_{ij}]_{n\times n}$ of $\mathcal{G}$ is defined such that ${a}_{ij}\!>\!0$ if $(i,j)$ exists, and ${a}_{ij}\!=\!0$ otherwise. Denote ${\mathcal{N}_{i}}=\{j\in\mathcal{V}:a_{ij}>0\}$ as the in-neighbor set of $i$, and $d_{i}=\left|{\mathcal{N}_{i}}\right|$ as its in-degree. Throughout this paper, let $\bm{0}$ and $\bm{1}$ be all-zero and all-one matrices in compatible dimensions, $\rho_{\min}(M)$ and $\rho_{\max}(M)$ be the smallest and largest eigenvalues of the matrix $M$, respectively.

Consider the following networked dynamical model

where $x_{t}$ and $y_{t}$ represents the system state and corresponding observation at time $t$, $W=[w_{ij}]_{n\times n}$ is the interaction topology matrix related to the adjacent matrix $A$, and $\theta_{t}$ and $\upsilon$ represent the process and observation noises, satisfying the following Gauss-Markov assumption.

Next, we characterize the stability of (1) by defining

Then, $W$ is called asymptotically stable if $W\in\mathcal{S}_{a}$, or marginally stable matrix if $W\in\mathcal{S}_{m}$. Concerning its setup, popular choices include the Laplacian and Metropolis rules [24], which are given by

where the auxiliary parameter $\gamma$ satisfies $0<\gamma\leq 1$. Note that if $W$ is specified by either one of the two rules, then $W\in\mathcal{S}_{m}$. A typical matrix in $\mathcal{S}_{a}$ can be directly obtained via multiplying (3) and (4) by a factor $0<\alpha<1$, which is common in adaptive diffusion networks [25]. Based on (1), the observation $y_{t}$ can be recursively expanded as

Considering different stabilities, it holds that

where $\|W^{\infty}\|<\infty$. Therefore, if $W\in\mathcal{S}_{a}\cup\mathcal{S}_{m}$, $y_{t}$ is strictly bounded in the expectation sense.

Since the information flow between nodes is specified by the topology of NDSs, we first define the $h$-hop neighbor of a single node.

Note that when the topology is undirected, there is no need to differentiate the in/out-neighbors. If $j\in\mathcal{N}_{j,h}^{out}$, node $j$ is also called the $h$-hop in-neighbor of node $i$. Unless otherwise specified, we mainly focus on the $h$-hop out-neighbors of a node in the following. To present an explicit expression for $\mathcal{N}_{j,h}^{out}$, we first define $\mathcal{N}_{j,h}^{e}$ as the node set where all the nodes can reached from node $j$ within $h$ hops. Then, $\mathcal{N}_{j,h}^{out}$ is recursively formulated as

When $h=1$, $\mathcal{N}_{j,1}^{out}=\mathcal{N}_{j,1}^{e}$. The following assumption is made throughout this paper.

Finally, the problem of interest is formulated as follows. Consider that there are no sufficient observations of the NDS model (1) to support existing estimation or regression methods of inferring topology, e.g., the causality based estimator in [7]. Leveraging the characteristic that a NDS is easily subjected to various disturbances and exhibits state deviation, we aim to reduce the inference dependence on observation scales, and propose an active excitation based method to infer the topology from limited new observations. Mathematically, let $e_{t}^{j}$ be the excitation input on node $j$ at time $t$, and $\tilde{y}_{t+h}^{i}$ be the observation of $i$ at time $(t+h)$. Then, the goal of this paper is to find $\mathcal{N}_{j,h}^{out}$ from the limited observations $\{y_{t},\tilde{y}_{t+h^{\prime}},h^{\prime}=1,\cdots,h\}$.

The above problem is very challenging, as the stochastic process and measurement noises will also affect $\{\tilde{y}_{t+h^{\prime}},h^{\prime}=1,\cdots,h\}$ and even accumulate. We will address these issues from the following aspects.

• •

  To make the excitation’s impact differentiable, we resort to the tool of hypothesis testing to derive the conditions for excitation magnitude to guarantee arbitrary misjudgement probability of one-hop neighbor inference.

• •

  To overcome the decaying effects of excitations, we establish the probabilistic relationship between the one-shot excitation magnitude and the accuracy of $h$-hop neighbor inference.

• •

  We further extend the analysis to multiple excitations cases and illustrate how to use excitations to improve the accuracy of existing topology inference methods.

Since only $\{y_{t}\}_{t=0}^{T}$ are directly available, for every two adjacent observations, it follows that

where $\omega_{t}=-W\upsilon_{t-1}+\theta_{t-1}+\upsilon_{t}$, satisfying $N(0,\sigma_{\upsilon}^{2}WW^{\mathsf{T}}+\sigma_{\upsilon}^{2}I+\sigma_{\theta}^{2}I)$. Besides, $\omega_{t}$ is independent of all $\{x_{t^{\prime}}\}_{t^{\prime}<t}$ and $\{\theta_{t^{\prime}}\}_{t^{\prime}<t-1}$. We point out that (III-A) only represents the quantitative relationship between adjacent observations, not a causal dynamical process.

Similar to (III-A), the observation at time $t+h$ can be recursively written as

where $\Gamma(h)=W^{h}$ is the $h$-step translation matrix. For ease notation, let $\omega_{t,h}=v_{t+h}-\Gamma(h)v_{t}+\sum_{m=1}^{h}\Gamma(m-1)\theta_{t+h-m}$. Then, the deviation between $y_{t+h}^{i}$ and $y_{t}^{i}$ is represented by

where $\omega_{t,h}^{i}\!\sim\!N(0,\sigma_{\omega,h}^{2}(i))$ and $\sigma_{\omega,h}^{2}(i)$ is given by

which is obtained from the mutual independence of the process and observation noises.

Note under Assumption 2, it holds that $\Gamma(h)\bm{1}\!\leq\!\bm{1}$ and $\sum\nolimits_{j=1}^{n}\Gamma_{ij}^{2}(h)\!\leq\!1$. Leveraging the two properties, one can induce that

where the deviation bound $\Delta y_{t}^{\max}$ is given by

It is worth noting that $\Delta y_{t}^{\max}$ will fluctuate around zero as $t$ increases in either case of $\mathcal{S}_{m}$ and $\mathcal{S}_{a}$. For simplicity without loss of generality, consider node $j$ is injected with positive excitation input $e_{t}^{j}>0$ at time $t$. Then, the observation deviation is given by

Note that the term $\Gamma_{ij}e_{t}^{j}$ in (15) represents the influence of the excitation input $e_{j}$ over $i$ after $h$ steps. Hereafter, we will drop the subscript $t$ in the variables if it does not cause confusion.

After node $j$ is injected with excitation input $e_{t}^{j}$, the one-step observation deviation of node $i$ is given by

For legibility, we temporarily assume $\Delta y_{t}^{\max}=0$ and take its influence into consideration after the analysis. Since $\tilde{y}_{t,1}^{i,\Delta}$ is associated with the stochastic process and measurement noises, finding $\mathcal{N}_{j}^{out}$ can be modeled as a typical binary hypothesis testing. The null and alternative hypothesis are respectively defined as

Then, denote $\Pr\{{H_{0}}|\tilde{y}_{t,1}^{i,\Delta}\}$ ($\Pr\{{H_{1}}|\tilde{y}_{t,1}^{i,\Delta}\}$) as the probability that $H_{0}$ ($H_{1}$) holds given the observation $\tilde{y}_{t,1}^{i,\Delta}$. Then, we have the following decision criterion

which is also called the maximum posterior probability criterion. However, it is possible that (18) is misjudged in the test, for example, $H_{0}$ is true but $H_{1}$ is decided (Type I Error) or $H_{1}$ is true but $H_{0}$ is decided (Type II Error). Accordingly, let $\Pr\{D_{1}|H_{0}\}$ be the false alarm probability and $\Pr\{D_{0}|H_{1}\}$ be the missed detection probability, respectively. Therefore, the overall misjudgement probability is given by

Suppose the inference center has no prior information about $H_{1}$ and $H_{0}$, i.e., $\Pr(H_{1})=\Pr(H_{0})=0.5$. Under hypothesis testing (18), the following result presents the probabilistic relationship between the inference accuracy and the injected excitation magnitude.

Theorem 1 gives the lower magnitude bound of the excitation input to guarantee the specified misjudgment probability in a single time. Given the excitation input $e^{j}$ satisfying (20), one has with probability at least $(1-\bar{\delta}_{e})$ to accurately discriminate whether $i\in\mathcal{N}_{j}^{out}$. Note that the interaction weight $w_{ij}$ is not priorly known in reality. Thus the decision threshold in theory, $\frac{w_{ij}e^{j}}{2}$, is unavailable. However, we can enable the hypothesis test by specifying the least interaction weight that one wishes to discriminate between two nodes.

To practice, since $\|W\|_{F}\leq\sqrt{n}\|W\|\leq\sqrt{n}$, thus we have $\sum\limits_{j=1}^{n}w_{ij}^{2}\leq n$ and

Specifically, if $W$ is row-stochastic, then the upper bound $\bar{\sigma}_{\omega}^{2}$ can be further reduced to $2\sigma_{\upsilon}^{2}+\sigma_{\theta}^{2}$. Next, suppose that one aims to judge whether $i\in\mathcal{N}_{j}^{out}$ such that $w_{ij}>\underline{w}$, where $\underline{w}$ is the weight lower bound. Given the desired error probability bound $\bar{\delta}_{e}$ and the excitation input $e^{j}$ such that $e^{j}=\frac{2\sqrt{2}\bar{\sigma}_{\omega}}{\underline{w}}\text{erf}^{-1}(1-\bar{\delta}_{e})$, then with probability at $1-\bar{\delta}_{e}$ one can discriminate whether $i\in\mathcal{N}_{j}^{out}$ by

where the parameters in (30) are all computable or known. Applying (30) to all other node and one can obtain an estimated set of $\mathcal{N}_{j}^{out}$. Note that although the observation deviation $|(Wy_{t})^{i}-y_{t}^{i}|$ will affect the performance of excitation based topology inference, its influence is strictly bounded under Assumption 2. The whole procedures are summarized in Algorithm 1, where we use the lower bound $\underline{w}$ that is sufficient to guarantee the accuracy probability.

A direct result from Theorem 1 is $\mathop{\lim}\limits_{|e^{j}|\to\infty}\delta_{e}=0$, which corresponds to the common intuition. As long as the excitation input is large enough, the one-hop neighbors of $j$ can always be inferred. Under this situation, it is also very likely that the two-hop (even more) out-neighbors of the excited node can also be identified by just single excitation.

In this part, we will demonstrate how to identify multi-hop out-neighbors of a node by single excitation. Similar with the hypothesis (17), we first define the following hypothesis that tests whether $i\in\mathcal{N}_{j,h}^{e}$, i.e.,

Note that (31) is a test using the observation deviation $\tilde{y}_{t,h}^{i,\Delta}$ to judge whether node $i$ is an out-neighbor of node $i$ within $h$ steps. Although it cannot infer the $h$-hop neighbor directly, valuable information can still be extracted for the final inference. To begin with, we present the following result.

Note that Lemma 1 only illustrates how to reduce the misjudgement probability of $i\in\mathcal{N}_{j,h}^{e}$, and does not provide information about whether $i\in\mathcal{N}_{j,h}^{out}$. A key insight is that if $i$ is decided not in $\mathcal{N}_{j,h-1}^{e}$ but in $\mathcal{N}_{j,h}^{e}$, then it is very likely that $i\in\mathcal{N}_{j,h}^{out}$ is true. Starting from this point, we utilize a single-time excitation input and do $h$-rounds tests to achieve the inference goal. Two auxiliary functions are defined as

where $z\in[0,1]$. Based on $F_{0}(z)$ and $F_{1}(z)$, the inference probability of multi-hop out-neighbors is presented as follows.

Theorem 2 provides the lower probability bounds for $\Pr\{i\in\mathcal{N}_{j,h}^{out}\}$ given the maximum false alarm probability $\alpha$ of the test (31). Note that the test (31) is implemented multiple rounds to infer the neighbor within $h^{\prime}$-hop, $h^{\prime}=1,\cdots,h$, respectively. Therefore, a notable characteristic of the bounds by (35) is that they can be calculated recursively with just one-shot excitation input. The higher the hop number is, the lower the probability bound is. The practical application of this test is similar to (30) and omitted here.

Theorem 1 and 2 illustrate the conditions and performances of using just one-time excitation. However, there are also situations where a large excitation input is not allowed in the network dynamics, making the methods not directly available. To overcome this deficiency, multi-excitation is a promising alternative to achieve the inference goal. In this part, we will briefly show how to address the issue.

Suppose node $j$ is excited $m$ times with the same excitation input $e^{j}$, the inference center obtains the average observation deviation of $m$ rounds by $\tilde{y}^{i,\Delta}_{\bar{m}}=\frac{1}{m}\sum\limits_{l=1}^{m}y^{i,\Delta}{(l)}$.