Symbolic network controllability based on a consistency protocol under distance division
-
摘要: 针对一般线性多智能体系统研究了符号网络的能控性。首先，聚焦2种不同的leader-follower模型，分析并描述了二者在表现形式上呈现出的差异。其次，基于上述模型，利用首次提出的距离划分这一工具，从网络拓扑的角度定量刻画了网络的能控子空间。进一步，受距离划分的启发，得到了系统K步可控的条件(K步可控是指控制信号在K步之内可达所有节点，K值等于系统的能控性指数)。特别地，针对密集网络(结构更为复杂)拓扑，给出了一种计算系统K值的算法，该算法从图论视角入手，通过遍历和删减边的操作，避免了传统方法中通过复杂的矩阵计算才得到K值的问题，并为领导者的选择提供了方法。最后，通过例子验证了算法的有效性。Abstract: The controllability of symbolic networks in general linear multiagent systems is explored in this study. First, two distinct leader-follower models are analyzed, highlighting and clarifying the differences in their expressions. Next, building on the above-mentioned models, the controllable subspace of the network is quantitatively described from the perspective of network topology, utilizing the distance division tool introduced here for the first time. Inspired by distance division, conditions for K-controllability were obtained (K-controllability means that the control signal can reach all nodes within K steps, where K corresponds to the system’s controllability index). For dense network topologies with complex structures, a novel algorithm is proposed for calculating the system’s K value. By adopting a graph theory approach, the algorithm leverages operations such as traversing and trimming edges of the topology graph. This approach circumvents the need for complex matrix calculations used in traditional methods while also providing a method for leader selection. Finally, the validity of the algorithm is demonstrated through practical examples.
-
近年来，多智能体系统在社会科学、大脑网络、传感器网络等领域被广泛应用[1-8]。通常使用拓扑图来表示智能体之间的交互关系，其中每个节点表示一个智能体，每个边的权重表示智能体之间的交互强度。作为现代控制理论的一个核心概念，多智能体系统能控性的意义在于，仅通过控制少数领导者节点，所有智能体就可以从初始状态被驱动到任意状态。最早的多智能体系统能控性概念由Tanner[9]提出，该文章利用系统矩阵的特征值和特征向量建立了跟随者节点对应的系统完全可控的充要条件。这项工作得到了系统能控的代数判据，但是代数判据的计算复杂度较大，不便于实际应用。因此，部分学者从图论角度研究多智能系统拓扑结构与能控性之间的关系，利用距离划分[10-12]、等价划分[13-14]以及几乎等价划分[15-16]等方法得到了能控性的图论判据。
具有正、负符号连接的网络被称为符号网络，智能体之间的合作(积极)作用和对抗(消极)作用分别用“+”和“−”表示。符号网络之所以在多智能体系统领域内受到广泛关注，其主要原因是符号网络比无符号网络具有更广泛的应用场景，例如社交网络分析、个性化推荐、社区或集群的划分以及生物领域中的神经元之间的关系表示等[17-22]。结构平衡是符号网络中的一个重要概念，该性质最早由Heider[18]提出。然而，目前大多数关于多智能体系统能控性的研究都聚焦于底层图拓扑(加权无符号图)，例如，Gambuzza等[23]考虑的多智能体系统通过加边减边实现的多一致性问题。相对较少的研究考虑了更有实践意义的符号网络的能控性[24-27]，例如Guan等[25]研究了固定拓扑和切换拓扑的符号多智能体网络的能控性，得到了能控性的图论条件。Sun等[26]利用图划分在原图和商图之间建立了等效的联系，揭示了不可控多智能体系统的稳定性不仅与领导者的选择有关，还与不可控模态有关。She等[27]研究了符号多智能体系统的可聚集性，利用图的划分得到了系统可聚集性的充分条件，揭示了商图可用来推断原图的可聚集性。
根据线性系统能控性理论可知，系统能控的充分必要条件是能控性判别矩阵满秩。Mortazavian[28]首次提出了系统k-controllability的概念，k-controllability是一个满足系统能控性判别矩阵的秩条件的指标。Chen等[29]在研究系统的控制能量时发现，当驱动节点距离目标节点的距离最短时控制能量最佳，这表明系统
$ K $ 值越小，网络的控制能量越佳。然而，稀疏网络的$ K $ 值常利用线性系统理论中能控性指数的定义来计算，但是在密集网络中，系统的$ K $ 值的计算复杂度较高。怎样从拓扑的角度获得密集网络的$ K $ 值是一个值得研究的问题。结合现有工作，本文的主要贡献如下：1)本文分析了2种分别聚焦于顶点和连边的多智能体leader-follower模型，这2种模型在表现形式上呈现出明显的差异，但是它们在本质上是相同的。2)基于上述模型，本文提出了一种新的距离划分定义，该定义是基于领导者集合得到的。在此定义的基础上，借助符号图的规范变换和路径符号的概念，得到了结构平衡符号图的特征描述。进一步，利用距离划分和几乎等价划分定量刻画了能控子空间的上界和下界。3)由于通过能控型矩阵计算密集网络的$ K $ 值(能控性指数)的计算复杂度较高，所以本文借助距离划分，提出一种图论视角下求得网络系统$ K $ 值的算法，该算法避免了大量的矩阵计算。本文剩余部分组织如下：第1章为预备知识，给出图论的初步概念和相关引理，并且比较了2种leader-follower模型。第2章总结了无向符号网络中系统能控性的主要结果。第3章在距离划分的基础上进一步研究系统的
$ K $ 步可控，针对密集网络提出一种领导者选取算法。最后，在第4部分总结结论。符号说明：
$ {{\bf{R}}^n} $ 和$ {{\bf{R}}^{n \times m}} $ 分别表示$ n $ 维欧氏空间和$ n \times m $ 阶矩阵的集合。$ {\mathrm{rank}}({\boldsymbol{A}}) $ 表示矩阵$ {\boldsymbol{A}} $ 的秩，$ {\mathrm{ker}}({\boldsymbol{A}}) $ 和$ {\mathrm{Im}}({\boldsymbol{A}}) $ 分别表示矩阵$ {\boldsymbol{A}} $ 的核空间和列空间。$ \boldsymbol{A}_{i,·} $ 表示矩阵$ {\boldsymbol{A}} $ 的第$ i $ 行，$ {{\boldsymbol{A}}_{i,j}} $ 表示矩阵$ {\boldsymbol{A}} $ 的第$ i $ 行第$ j $ 列元素。1. 预备知识
在多智能体系统中，用图来表示智能体之间的交互关系。令
$ G = (V,E,{\boldsymbol{A}}) $ 表示一个顶点集$ V $ 和边集$ E $ 分别为$ V = \{ {v_1},{v_2}, \cdots ,{v_n}\} $ ,$ E = \{ {E_{ij}} \} = \{ ({v_i},{v_j})| {v_i},{v_j} \in V,i \ne j\} $ 的无向符号图。邻接矩阵$ {\boldsymbol{A}} = [{a_{ij}}] \in {{\bf{R}}^n} $ ，当$ ({v_i},{v_j}) \notin E $ 时，$ {a_{ij}} = 0 $ ；当$ ({v_i},{v_j}) \in E $ 时，$ {a_{ij}} \ne 0 $ 。用$ {a_{ij + }} $ 和$ {a_{ij - }} $ 分别表示$ {a_{ij}} > 0 $ 和$ {a_{ij}} < 0 $ 。节点
$ {v_i} $ 的邻域集用$ {N_i} $ 表示，$ {N_{ij}} $ 表示节点$ {v_i} $ 的跟随者邻域集，$ {N_{il}} $ 表示节点$ {v_i} $ 的领导者邻域集，$ {N_i} = {N_{ij}} \cup {N_{il}} $ ，并且$ {N_{ij}} \cap {N_{il}} = \varnothing $ 。节点$ {v_i} $ 的度用$ {d_i} $ 表示，$ {d_i} = \displaystyle\sum_{j \in {N_i}} {{a_{ij}}} $ ，$ G $ 的拉普拉斯矩阵用$ {\boldsymbol{L}} = {\boldsymbol{D}} - {\boldsymbol{A}} $ 表示，其中，度矩阵$ {\boldsymbol{D}} \triangleq {\mathrm{diag}} ( {d_1},{d_2}, \cdots ,{d_n} ) $ 。$ {\boldsymbol{L}} $ 中的元素可以写成$$ {l_{ij}} = \left\{ {\begin{array}{*{20}{c}} {{d_i}{\text{ ,}}}&{i = j} \\ { - {a_{ij}}{\text{ ,}}}&{i \ne j} \end{array}} \right. $$ 状态向量用
$ {\boldsymbol{x}}(t) = {[{{\boldsymbol{x}}_1}(t){\text{ }}{{\boldsymbol{x}}_2}(t){\text{ }} \cdots {\text{ }}{{\boldsymbol{x}}_n}(t)]^{\rm T}} \in {{\bf{R}}^n} $ 表示，$ {{\boldsymbol{x}}_i}(t) \in {{\bf{R}}^n} $ 表示$ {v_i} $ 在t时刻的状态。令领导者集合为$ {V_{\rm l}} = \{ 1,2, \cdots ,m\} $ ，跟随者集合为$ {V_{\rm f}} = \{ m + 1, m + 2, \cdots ,n\} $ ，每个跟随者动态方程为$$ {\dot {\boldsymbol{x}}_i}(t) = - \sum\limits_{i \in {N_i}} {{a_{ij}}({{\boldsymbol{x}}_i}(t) - } {{\boldsymbol{x}}_j}(t)),i = {V_{\mathrm{f}}} $$ (1) 每个领导者的动态方程为
$$ {\dot {\boldsymbol{x}}_i}(t) = - \sum\limits_{i \in {N_i}} {{a_{ij}}({{\boldsymbol{x}}_i}(t) - } {{\boldsymbol{x}}_j}(t)) + {{\boldsymbol{u}}_i},i = {V_{\mathrm{l}}} $$ (2) 式(1)和(2)的紧凑形式为
${\boldsymbol{\dot x}} = - {\boldsymbol{Lx}} + {\boldsymbol{Bu}}$ ，其中${\boldsymbol{B}} = [0{\text{ }}{{\boldsymbol{E}}_{\rm l}}]$ 是输入矩阵，$ {\boldsymbol{u}} $ 是外部控制输入。定义1 (符号图)合作−竞争关系的多智能体系统用符号图表示，记为
$ G = (V,E,{\boldsymbol{A}}) $ 。如果邻接矩阵$ {\boldsymbol{A}} $ 的元素可以取负值，即存在权重值$ {a_{ij}} $ ，则图$ G $ 称为符号图。与$ G $ 对应的无符号图记为$ {G^{\rm U}} = (V,E,|{\boldsymbol{A}}|) $ ，其拉普拉斯矩阵用$ {{\boldsymbol{L}}^{\rm U}} $ 表示。定义2 (规范变换)如果存在正交矩阵
$ {\boldsymbol{D}} \in \{ {\mathrm{diag}} ( {\sigma _1},{\sigma _2}, \cdots ,{\sigma _n} ) \} $ ，$ {\sigma _i} \in \{ \pm 1\} $ ，在其作用下使得$ {{\boldsymbol{M}}_1} = {\boldsymbol{D}}{{\boldsymbol{M}}_2}{\boldsymbol{D}} $ ，$ {[{{\boldsymbol{M}}_1}]_{ij}} \geqslant 0 $ 成立，则将该过程称为规范变换。显然$ {\boldsymbol{D}} = {{\boldsymbol{D}}^{ - 1}} $ 。定义3 (结构平衡)给定符号图
$ G $ 。对于2个集合$ {V_1} $ 和$ {V_2} $ ，$ V = {V_1} \cup {V_2} $ 并且$ {V_1} \cap {V_2} = \varnothing $ ，使得对于任意$ {v_i} $ ，$ {v_j} $ $ \in {v_s}(s = 1,2) $ ，有$ {a_{ij}} \geqslant 0({a_{ij}} > 0) $ ，对于任意$ {v_i} \in {v_s} $ ，$ {v_j} \in {v_t} $ ，$ s,t \in \{ 1,2\} $ ，$ s \ne t $ ，有$ {a_{ij}} \leqslant 0{\text{ }}({a_{ij}} < 0) $ ，则说，$ G $ 是结构平衡的；否则，$ G $ 是结构不平衡的。例如图1(a)和(b)是结构平衡的，图1(c)和(d)是结构不平衡的。
图 1 结构平衡示例Fig. 1 Examples of structural balance
下载:
全尺寸图片
注1 对一个结构平衡的符号图，其中一个子集可以是空集。例如，一个无符号图是结构平衡的，但只有正的边，另外一个子集是空集。结构平衡的另外一个定义是利用正的圈(无向图)或正的弱圈(有向图不是强连通的，但去掉边的方向后形成的无向图是圈图)来给出；对于图
$ G $ ，当且仅当所有的弱圈是正时，$ G $ 是结构平衡的。引理1 PBH(Popov-Belevitch-Hautus)判据[14]，对于线性定常连续系统
$ {\boldsymbol{\dot x}}(t) = {\boldsymbol{Ax}}(t) + {\boldsymbol{Bu}}(t) $ ，其中$ {\boldsymbol{A}} \in {{\bf{R}}^n} $ ，$ {\boldsymbol{B}} \in {{\bf{R}}^{n \times m}} $ 分别表示系统的状态矩阵和控制输入矩阵。系统能控的充分必要条件是不存在满足下式的非零向量$ {\boldsymbol{v}} $ ：$$ \left\{ {\begin{array}{*{20}{c}} {{\boldsymbol{Av}} = \lambda {\boldsymbol{v}}} \\ {{{\boldsymbol{B}}^{\rm T}}{\boldsymbol{v}} = 0} \end{array}} \right. $$ 引理2 秩判据[14]，对于线性定常连续系统
$ {\boldsymbol{\dot x}}(t) = {\boldsymbol{Ax}}(t) + {\boldsymbol{Bu}}(t) $ ，系统能控当且仅当$$ {\mathrm{rank}}({\boldsymbol{C}}) = {\mathrm{rank}}[{\boldsymbol{B}}|{\boldsymbol{AB}}|{{\boldsymbol{A}}^2}{\boldsymbol{B}}| \cdots |{{\boldsymbol{A}}^{K - 1}}{\boldsymbol{B}}] = n $$ 2. 系统描述
在多智能体系统中，考虑到leader-follower结构，拉普拉斯矩阵
$ {\boldsymbol{L}} $ 可以被划分为$$ \left[ {\begin{array}{*{20}{c}} {{{\boldsymbol{L}}_{\mathrm{f}}}}&{{{\boldsymbol{L}}_{{\mathrm{fl}}}}} \\ {{\boldsymbol{L}}_{{\mathrm{fl}}}^{\rm T}}&{{{\boldsymbol{L}}_{\mathrm{l}}}} \end{array}} \right] $$ 式中：
$ {{\boldsymbol{L}}_{\rm f}} \in {{\bf{R}}^{(n - m)}} $ 和$ {{\boldsymbol{L}}_{\rm l}} \in {{\bf{R}}^m} $ 分别指跟随者和领导者对应的子矩阵，$ {{\boldsymbol{L}}_{\rm{fl}}} \in {{\bf{R}}^{(n - m) \times m}} $ 和$ {\boldsymbol{L}}_{\rm{fl}}^{\rm T} \in {{\bf{R}}^{m \times (n - m)}} $ 为领导者和跟随者之间的连接矩阵。假设跟随者仍然遵循式(1)，且领导者只接收外部输入信号而不受跟随者状态的影响，则有
$$ \left[ {\begin{array}{*{20}{c}} {{{{\boldsymbol{\dot x}}}_{\rm f}}(t)} \\ {{{{\boldsymbol{\dot x}}}_{\rm l}}(t)} \end{array}} \right] = - \left[ {\begin{array}{*{20}{c}} {{{\boldsymbol{L}}_{\rm f}}}&{{{\boldsymbol{L}}_{\rm{fl}}}} \\ 0&0 \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{{\boldsymbol{x}}_{\rm f}}(t)} \\ {{{\boldsymbol{x}}_{\rm l}}(t)} \end{array}} \right] + \left[ {\begin{array}{*{20}{c}} 0 \\ {{{\boldsymbol{E}}_{\rm l}}} \end{array}} \right]{\boldsymbol{\hat u}} $$ 式中：
$ {\boldsymbol{\hat u}} = - \left[ {{\boldsymbol{L}}_{\rm{fl}}^{\rm T}}\quad {{{\boldsymbol{L}}_{\rm l}}} \right]{\left[ {{{\boldsymbol{x}}_{\rm f}}(t)}\quad {{{\boldsymbol{x}}_{\rm l}}(t)} \right]^{\rm T}} + {\boldsymbol{u}}(t) $ ，$ {{\boldsymbol{E}}_{\rm l}} $ 为单位矩阵。将跟随者对应部分提取出来可以得到$$ {{\boldsymbol{\dot x}}_{\rm f}}(t) = - {{\boldsymbol{L}}_{\rm f}}{{\boldsymbol{x}}_{\rm f}}(t) - {{\boldsymbol{L}}_{\rm{fl}}}{{\boldsymbol{x}}_{\rm l}}(t) $$ (3) 按照智能体之间的连边关系将边分为领导者与跟随者之间的边以及跟随者与跟随者之间的边。式(1)可以推导出另一种表现形式的leader-follower模型：
$$ \begin{gathered}\boldsymbol{\dot{x}}_i(t)=-\sum\limits_{i\in N_i}^{ }a_{ij}(\boldsymbol{x}_i(t)-\boldsymbol{x}_i(t))= \\ -\sum\limits_{i\in N_{ij}}^{ }a_{ij}(\boldsymbol{x}_i(t)-\boldsymbol{x}_j(t))-\sum\limits_{i\in N_{il}}^{ }b_{ij}(\boldsymbol{x}_i(t)-\boldsymbol{x}\mathrm{_l}(t))= \\ \sum\limits_{i\in N_{ij}}^{ }a_{ij}(\boldsymbol{x}_j(t)-\boldsymbol{x}_i(t))+\sum\limits_{i\in N_{il}}^{ }b_{ij}(\boldsymbol{x}\mathrm{_l}(t)-\boldsymbol{x}_i(t))\end{gathered} $$ $$ {{\boldsymbol{\dot x}}_i}(t) = - ({\boldsymbol{\varLambda }} + {\mathrm{diag}}({b_i})){{\boldsymbol{x}}_{\text{f}}}(t) + {\boldsymbol B}{{\boldsymbol{x}}_{\text{l}}}(t) $$ (4) 式中：
$ {\boldsymbol{\varLambda }} $ 表示为网络中跟随者节点之间的拉普拉斯矩阵，$ {b_i} $ 表示接收领导者信息的跟随者$ {v_i} $ 的度。注2 式(3)、(4)的表现形式不同，其在能控性上，尤其是状态矩阵和输入矩阵的表示上是相同的。也就是说，从线性理论的角度来看，式(3)、(4)描述的是同一个动态过程，因此，在能控性的分析上是等价的。式(4)的系统矩阵不需要直接通过拉普拉斯矩阵分块得出，矩阵
$ {\boldsymbol{\varLambda }} $ 表示跟随者节点之间的拉普拉斯矩阵，$ {b_i} $ 表示接收领导者信息的跟随者$ {v_i} $ 的度，所以有$ {\boldsymbol{\varLambda }} + {\mathrm{diag}}({b_i}) = {{\boldsymbol{L}}_{\rm f}} $ 。此外，$ {{{\boldsymbol B}}} $ 与$ - {{\boldsymbol{L}}_{\rm{fl}}} $ 都表示跟随者节点与领导者节点之间的连边关系，即$ {{{\boldsymbol B}}} = - {{\boldsymbol{L}}_{\rm{fl}}} $ ，因此，式(3)、(4)能控性等价。表现形式的不同是由于模型推导的视角在连边还是在节点。在有领导者和跟随者的网络中，点可以划为2种：领导者和跟随者，而边可以划为3种：领导者与领导者的连边、跟随者与跟随者的连边、领导者与跟随者的连边。因此，式(4)会有与式(3)不同的表现形式。在实际应用中的主要差异体现在以下2个方面：1)式(4)的系统矩阵不需要直接通过拉普拉斯矩阵分块得出，在硬件上实现时，可以考虑通过是否需要使用拉普拉斯矩阵分块求解相关参数来选择模型表达式，以降低不同实验目标的实现难度；2)表现形式的不同为控制器的不同设计方法提供了思路。图2对2种模型在实际应用中的不同进行说明，该图形象地展示了距离划分与本文提到的2种模型之间的关系。根据图2可以分别写出式(3)、(4)的表达式。
图 2 模型关系示例Fig. 2 Example of model relationship下载:
全尺寸图片
式(3)的表达式：
$$ \begin{gathered}\boldsymbol{\dot{x}}_{\mathrm{f}}(t)=-\boldsymbol{L}_{\mathrm{f}}\boldsymbol{x}_{\mathrm{f}}(t)-\boldsymbol{L}_{\rm{fl}}\boldsymbol{x}\mathrm{_l}(t)= \\ \text{ }\left[\begin{array}{*{20}{r}}-1 & -1 & 2 & -1 \\ -1 & -3 & 2 & 2 \\ 2 & 2 & -4 & 0 \\ -1 & 2 & 0 & -1\end{array}\right]\left[ \begin{array}{*{20}{c}}\boldsymbol{x}_3 \\ \begin{array}{*{20}{c}}\boldsymbol{x}_4 \\ \begin{array}{*{20}{c}}\boldsymbol{x}_5 \\ \boldsymbol{x}_6\end{array}\end{array}\end{array} \right]+\left[ \begin{array}{*{20}{r}}2 & -1 \\ 0 & 0 \\ 0 & 0 \\ 0 & 0\end{array} \right]\left[ \begin{array}{*{20}{c}}\boldsymbol{x}_1 \\ \boldsymbol{x}_2\end{array} \right]\end{gathered} $$ 式(4)的表达式：
$$ \begin{gathered} {{{\boldsymbol{\dot x}}}_i}(t) = - ({\boldsymbol{\varLambda }} + {\mathrm{diag}}({b_i})){{\boldsymbol{x}}_{\text{f}}}(t) + {{{\boldsymbol B}}}{{\boldsymbol{x}}_{\text{l}}}(t) = \\ - \left\{ \left[ {\begin{array}{*{20}{r}} 0&1&{ - 2}&1 \\ 1&3&{ - 2}&{ - 2} \\ { - 2}&{ - 2}&4&0 \\ 1&{ - 2}&0&1 \end{array}} \right] +\right. \\ \left.\left. {\left[ {\begin{array}{*{20}{c}} 1&0&0&0 \\ 0&0&0&0 \\ 0&0&0&0 \\ 0&0&0&0 \end{array}} \right]} \right\} \right.\left[ {\begin{array}{*{20}{c}} {{{\boldsymbol{x}}_3}} \\ {{{\boldsymbol{x}}_4}} \\ {{{\boldsymbol{x}}_5}} \\ {{{\boldsymbol{x}}_6}} \end{array}} \right] + \left[ {\begin{array}{*{20}{r}} 2&{ - 1} \\ 0&0 \\ 0&0 \\ 0&0 \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{{\boldsymbol{x}}_1}} \\ {{{\boldsymbol{x}}_2}} \end{array}} \right] \\ \end{gathered} $$ 用
$ \mathcal{A} $ ,$ \mathcal{B} $ ,$ {\boldsymbol{x}}(t) $ ,$ {\boldsymbol{u}}(t) $ 分别表示$ {\boldsymbol{\varLambda }} + {\mathrm{diag}}({b_i}) $ ，$ {{{\boldsymbol B}}} $ ，$ {{\boldsymbol{x}}_{\rm f}}(t) $ ，$ {{\boldsymbol{x}}_{\rm l}}(t) $ ，可将式(4)写成$$ {\boldsymbol{\dot x}}(t) = \mathcal{A}{\boldsymbol{x}}(t) + \mathcal{B}{\boldsymbol{u}}(t) $$ (5) 3. 主要结论
3.1 距离划分下的符号网络能控性
给定图
$ G $ ，用$ {P_{v,w}} $ 表示从$ v \in {V_{\rm l}} $ 到$ w \in {V_{\rm f}} $ 的一条路径，路径的距离用$ |{P_{v,w}}| $ 表示。则路径的符号表示为$$ {\mathrm{sign}}({P_{v,w}}) = \prod\limits_{{E_{vw}} \in {P_{v,w}}} {{\mathrm{sign}}({E_{vw}})} $$ (6) 定义4 划分π是指将
$ G $ 的顶点集$ V $ 划分成$r$ 个胞腔$ C_1,C_2,\cdots,C_r $ ，使得$ {C_i} \subset V $ ，$ V = \bigcup\nolimits_{i = 1}^r {{C_i}} $ ，$ {C_i} \cap {C_j} = \varnothing $ ，$ i,j \in \{ 1,2, \cdots ,r\} $ ，$ i \ne j $ 且对于任意的$ s,t \in {C_i} $ 使得以下等式成立$$ {\mathrm{min}}|{P_{k,s}}| = {\mathrm{min}}|{P_{k,t}}|,k \in {V_{\rm l}} $$ 那么该划分称为图
$ {{\text{π}} _{\rm D}} $ 的一个距离划分，用$ {{\text{π}} _{\rm D}} $ 表示，$ |{{\text{π}} _{\rm D}}| $ 表示胞腔个数。注3 在给定领导者时，距离划分的结果是唯一的，并且领导者节点在同一个胞腔中。图3是距离划分的多部门参与决策的应用实例，根据示例可以得到对应拓扑。距离划分新定义是以领导者为中心，因此在划分胞腔中，第一步是将领导者划分在同一胞腔内，进而根据跟随者与领导者的最短距离划分成不同的胞腔，虚线代表胞腔，节点颜色对应示例部门。
图 3 距离划分示例及构造过程Fig. 3 Distance division example and construction process下载:
全尺寸图片
命题1 图
$ G $ 是结构平衡的，$ {\boldsymbol{H}} $ 表示图$ G $ 中具有非负元素$ {\boldsymbol{H}} = {\mathrm{min}}( {h_{ij + }},{h_{ij - }}) $ 的对角矩阵，$ {h_{ij + }} $ 和$ {h_{ij - }} $ 分别表示节点$ {v_i} $ 的正边权和以及负边权和，$ {h_{ij + }} = \displaystyle\sum\limits_{i \in {N_i}} {\left| {{a_{ij + }}} \right|} $ ，$ {h_{ij - }} = \displaystyle\sum\limits_{j \in {N_i}} {\left| {{a_{ij - }}} \right|} $ ，则有以下结论成立。(a)存在矩阵
$ {\boldsymbol{D}} \in \{ {\mathrm{diag}}( {\sigma _1},{\sigma _2}, \cdots ,{\sigma _n}\} ) , {\sigma _i} \in \{ \pm 1\} $ 使得$ {\boldsymbol{DAD}} $ 中所有元素都是非负的；(b)对于任意2个节点
$ v $ 和$ w $ ，每个路径$ {P_{v,w}} $ 符号相同；(c)对于矩阵
$ {\boldsymbol{L}} + 2{\boldsymbol{H}} $ 的第$ i $ 个特征值$ {\lambda _i} $ 和第$ i $ 个特征向量$ {{\boldsymbol{y}}_i} $ 以及矩阵$ {{\boldsymbol{L}}^{\rm U}} + 2{\boldsymbol{H}} $ 的第$ i $ 个特征值$ \lambda _i^{\rm U} $ 和第$ i $ 个特征向量$ {{\boldsymbol{x}}_i} $ ，有$ \lambda _i^{\rm U} = {\lambda _i} $ 且$ {{\boldsymbol{y}}_i} = {\boldsymbol{D}}{{\boldsymbol{x}}_i} $ 。证明 (a)假设
$ G $ 是结构平衡的，则$ V $ 可以被划分为2个不相交的分区子集$ {V_1} $ 和$ {V_2} $ 。在同一个分区子集中的2个节点$ i $ 和$ j $ 的邻接关系表示为$ {a_{ij}} \geqslant 0 $ ，不同分区子集中的2个节点$ i $ 和$ j $ 的邻接关系$ {a_{ij}} \leqslant 0 $ 。令$ {\boldsymbol{D}} \in \{ {\mathrm{diag}}( {\sigma _1},{\sigma _2}, \cdots ,{\sigma _n}) \} $ ，当节点在分区子集$ {V_1} $ 中时$ {\sigma _1} = 1 $ ，反之$ {\sigma _1} = - 1 $ ，则有$ {[{\boldsymbol{DAD}}]_{ij}} = {\sigma _i}{\sigma _j}{a_{ij}} $ 。所以，当2个节点属于同一个子集时，$ {a_{ij}} \geqslant 0 $ ，$ {\sigma _i}{\sigma _j} = 1 $ ，$ {[{\boldsymbol{DAD}}]_{ij}} \geqslant 0 $ ；当2个节点分别属于2个不同子集时，$ {a_{ij}} \leqslant 0 $ ，$ {\sigma _i}{\sigma _j} = - 1 $ ，$ {[{\boldsymbol{DAD}}]_{ij}} \geqslant 0 $ 。(b)根据定义3和式(6)，当任意2个节点属于同一个分区子集时，
$ {P_{v,w}} $ 中包含的边的符号都是正的，因此$ {\mathrm{sign}}({P_{v,w}}) > 0 $ ；当任意2个节点属于不同的分区子集时，$ {P_{v,w}} $ 中包含一条负边，即$ {\mathrm{sign}}({P_{v,w}}) < 0 $ 。(c)假设符号图
$ G $ 是结构平衡的，则有$ {{\boldsymbol{L}}^{\rm U}} + {\boldsymbol{D}}({\boldsymbol{L}} + 2{\boldsymbol{H}}){\boldsymbol{D}} $ 。已知矩阵特征值和特征向量的关系为$ {{\boldsymbol{L}}^{\rm U}}{{\boldsymbol{x}}_i} = \lambda _i^{\rm U}{{\boldsymbol{x}}_i} $ 。$ {\boldsymbol{D}} $ 是一个对角矩阵，并且$ {\boldsymbol{D}} = {{\boldsymbol{D}}^{ - 1}} $ ，可得$ {{\boldsymbol{L}}^{\rm U}} = {{\boldsymbol{D}}^{ - 1}}({\boldsymbol{L}} + 2{\boldsymbol{H}}){\boldsymbol{D}} $ ，将该式两边同时右乘$ {{\boldsymbol{L}}^{\rm U}} $ 的特征向量$ {{\boldsymbol{x}}_i} $ 可得$ {{\boldsymbol{L}}^{\rm U}}{{\boldsymbol{x}}_i} = {{\boldsymbol{D}}^{ - 1}}({\boldsymbol{L}} + 2{\boldsymbol{H}}){\boldsymbol{D}}{{\boldsymbol{x}}_i} = \lambda _i^{\rm U}{{\boldsymbol{x}}_i} $ ，在上式的基础上左乘$ {\boldsymbol{D}} $ 可得$ ({\boldsymbol{L}} + 2{\boldsymbol{H}}){\boldsymbol{D}}{{\boldsymbol{x}}_i} = {\boldsymbol{D}}\lambda _i^{\rm U} {{\boldsymbol{x}}_i} = \lambda _i^{\rm U}{\boldsymbol{D}}{{\boldsymbol{x}}_i} $ 。令$ {{\boldsymbol{y}}_i} = {\boldsymbol{D}}{{\boldsymbol{x}}_i} $ 则有$ ({\boldsymbol{L}} + 2{\boldsymbol{H}}){{\boldsymbol{y}}_i} = {\lambda _i}{{\boldsymbol{y}}_i} $ 。也就是说，$ {{\boldsymbol{L}}^{\rm U}} $ 和$ {\boldsymbol{L}} + 2{\boldsymbol{H}} $ 的特征值相同，特征向量关系为$ {{\boldsymbol{y}}_i} = {\boldsymbol{D}}{{\boldsymbol{x}}_i} $ ，证毕。例1 给出5个节点的符号图与其对应的无符号图，其中
$ {\boldsymbol{L}} $ 和$ {{\boldsymbol{L}}^{\rm U}} $ 分别表示图4的5个子图对应的拉普拉斯矩阵。接下来对命题1(c)的有效性进行验证。
图 4 结构平衡符号网络及其对应的无符号网络Fig. 4 Structural balance signed networks and its corresponding unsigned networks下载:
全尺寸图片
$$ \begin{gathered} \boldsymbol{H}=\left[\begin{array}{lllll} 1 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right], \\ \boldsymbol{L}+2 \boldsymbol{H}=\boldsymbol{L}^{\mathrm{U}}=\left[\begin{array}{rrrrr} 2 & 1 & -1 & 0 & 0 \\ 1 & 3 & -1 & -1 & 0 \\ -1 & -1 & 2 & 0 & 0 \\ 0 & -1 & 0 & 2 & -1 \\ 0 & 0 & 0 & -1 & 1 \end{array}\right] \end{gathered}$$ $ {{\boldsymbol{L}}^{\rm U}} $ 和$ {\boldsymbol{L}} + 2{\boldsymbol{H}} $ 的特征值分别为：0、0.518 8、2.3111 、3、4.170 1。$ {\boldsymbol{L}} + 2{\boldsymbol{H}} $ 的特征向量为$$ \left[ \begin{array}{rrrrr} -0.447\;2 & -0.419\;3 & 0.242\;2 & 0.707\;1 & -0.256\;0 \\ 0.447\;2 & 0.201\;8 & 0.317\;5 & 0\;\;\;\;\;\;\;\;\;\;\; & -0.811\;5 \\ -0.447\;2 & -0.419\;3 & 0.242\;2 & -0.707\;1 & -0.256\;0 \\ 0.447\;2 & -0.338\;0 & 0.703\;1 & 0\;\;\;\;\;\;\;\;\;\;\; & 0.437\;5 \\ 0.447\;2 & -0.702\;4 & -0.536\;2 & 0\;\;\;\;\;\;\;\;\;\;\; & -0.138\;0 \end{array} \right] $$ $ {{\boldsymbol{L}}^{\rm U}} $ 的特征向量为$$ \left[ \begin{array}{rrrrr} -0.447\;2 & 0.419\;3 & 0.242\;2 & 0.707\;1 & -0.256\;0 \\ -0.447\;2 & 0.201\;8 & -0.317\;5 & 0\;\;\;\;\;\;\;\;\;\;\; & 0.811\;5 \\ -0.447\;2 & 0.419\;3 & 0.242\;2 & -0.707\;1 & -0.256\;0 \\ -0.447\;2 & -0.338\;0 & -0.703\;1 & 0\;\;\;\;\;\;\;\;\;\;\; & -0.437\;5 \\ -0.447\;2 & -0.702\;4 & 0.536\;2 & 0\;\;\;\;\;\;\;\;\;\;\; & 0.138\;0 \end{array} \right] $$ 定义5 在结构平衡符号图中，称
$ {V_1} $ 和$ {V_2} $ 中有直接交互关系的节点称为边界节点。定理1 在结构平衡的符号网络中，选择边界节点作为领导者时，则有以下结论成立。
(a)结构平衡符号图
$ G $ 与其对应的无符号图$ {G^{\rm U}} $ 的能控性相同；(b)当分区子图
$ {G_1} = ({V_1},{E_1} \subseteq {V_1} \times {V_1},{{\boldsymbol{A}}_1}) $ 和分区子图$ {G_2} = ({V_2},{E_2} \subseteq {V_2} \times {V_2},{{\boldsymbol{A}}_2}) $ 都能控时，整个系统是能控的，其中，$ {{\boldsymbol{A}}_1} $ 和$ {{\boldsymbol{A}}_2} $ 分别表示两个分区子图的邻接矩阵。证明 (a)用
$ {\boldsymbol{L}}_1^{\rm U} $ 表示$ {G^{\rm U}} $ 中领导者之间的拉普拉斯矩阵，根据定义2有$$ {{\boldsymbol{L}}^{\rm U}} = \left[ {\begin{array}{*{20}{c}} {{{\boldsymbol{L}}_{\rm f}}}&{{{\boldsymbol{L}}_{\rm{fl}}}} \\ {{\boldsymbol{L}}_{\rm{fl}}^{\rm T}}&{{\boldsymbol{L}}_{\rm l}^{\rm U}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {{{\boldsymbol{L}}_{\rm f}}}&{{{\boldsymbol{L}}_{\rm{fl}}}} \\ {{\boldsymbol{L}}_{\rm{fl}}^{\rm T}}&{{\boldsymbol{D}}{{\boldsymbol{L}}_{\rm l}}{\boldsymbol{D}}} \end{array}} \right] 。 $$ 根据注2可知，式(3)、(4)能控性等价。因此，当边界节点被选为领导者时，
$ G $ 与$ {G^{\rm U}} $ 的能控性相同，即领导者之间的连边符号改变不影响系统的能控性。(b)
$ {{\boldsymbol{L}}_{1{\mathrm{f}}}} $ 表示$ {V_1} $ 中跟随者的拉普拉斯矩阵，$ {{\boldsymbol{v}}_1} $ 表示$ {{\boldsymbol{L}}_{1{\mathrm{f}}}} $ 的左特征向量，$ {{\boldsymbol{L}}_{2{\mathrm{f}}}} $ 表示$ {V_2} $ 中跟随者的拉普拉斯矩阵，$ {{\boldsymbol{v}}_2} $ 表示$ {{\boldsymbol{L}}_{2{\mathrm{f}}}} $ 的左特征向量。根据引理1可知，式(5)是不可控的，当且仅当存在一个$ \mathcal{A} $ 的左特征向量$ \boldsymbol{v}(\boldsymbol{v}^{\mathrm{T}}\mathcal{A}=\lambda\boldsymbol{v}^{\mathrm{T}}) $ 使得$ {{\boldsymbol{v}}^{\rm T}}\mathcal{B} = {{\bf{0}}_m} $ 成立，其中$ {{\bf 0}}_m $ 是一个全为零的$m$ 维向量。换句话说，当且仅当$ {\boldsymbol{v}} $ 是式(5)中状态矩阵$ \mathcal{A} $ 的左特征向量且$ {\boldsymbol{v}} \notin {\mathrm{ker}}({\mathcal{B}^{\rm T}}) $ ，式(5)是可控的。在选择边界节点作为领导者时，根据引理1可得$$ \begin{gathered} {\boldsymbol v}^{\rm T}\mathcal{A}=\left[ \begin{array}{cc}{\boldsymbol v}_{1}^{\rm T}& {\boldsymbol v}_{2}^{\rm T}\end{array} \right]\mathcal{A}=\left[ \begin{array}{cc}{\boldsymbol v}_{1}^{\rm T}& {\boldsymbol v}_{2}^{\rm T}\end{array} \right]\left[ \begin{array}{cc}{\mathcal{A}}_{1}& 0\\ 0& {\mathcal{A}}_{2}\end{array} \right]=\\ \left[ \begin{array}{cc}{\boldsymbol v}_{1}^{\rm T}{\mathcal{A}}_{1}& 0\\ 0& {\boldsymbol v}_{2}^{\rm T}{\mathcal{A}}_{2}\end{array} \right] \end{gathered}$$ 因此，当分区子图
$ {G_1} $ 和$ {G_2} $ 同时能控时，整个系统是能控的，证毕。定义6 (几乎等价划分)给定一个符号图
$ G $ ，图$ G $ 的划分$ {\text{π}} $ 是指将图的顶点集$ V $ 分成$r$ 个胞腔$ \{ {C_1},{C_2}, \cdots ,{C_r}\} $ ，使得$ {C_i} \subset V $ ，$ V = \bigcup\nolimits_{i = 1}^r {{C_i}} $ ，$ {C_i} \cap {C_j} = \varnothing $ ，$ i,j \in \{ 1,2, \cdots ,r\} $ ，$ i \ne j $ 。如果对于所有的$ s,t \in {C_i} $ ，$ i,j \in \{ 1,2, \cdots ,r\} $ 有等式成立$$ \sum\limits_{k \in {C_j}} {{l_{sk}}} = \sum\limits_{k \in {C_j}} {{l_{tk}}} $$ 则
$ {\text{π}} $ 被称为图$ G $ 的一个几乎等价划分，记为$ {{\text{π}} _{{\mathrm{AEP}}}} $ 。定义7 (领导者孤立的几乎等价划分)给定一个几乎等价划分
$ {{\text{π}} _{{\mathrm{AEP}}}} $ ，如果每个领导者都是单独一个胞腔，那么就称这个几乎等价划分为领导者孤立的几乎等价划分，记为$ {{\text{π}} _{{\mathrm{LAEP}}}} $ ,$ |{{\text{π}} _{{\mathrm{LAEP}}}}| $ 表示该划分的胞腔个数。定义8 (特征矩阵)一个划分
$ {\text{π}} $ 的特征矩阵为$ {\boldsymbol{P}} \in {{\bf{R}}^{(n - m) \times r}} $ ，其中$r$ 表示该划分的胞腔的个数。矩阵$ {\boldsymbol{P}} $ 的元素表示为$$ {\boldsymbol{P}}=\left\{\begin{array}{c}\text{ }1\text{ },\text{ }i\in {C}_{j}\\ 0\text{ },\text{ }其他\end{array}\right. $$ 定义9 (不变子空间)设
$ {\boldsymbol{M}} $ 为数域上线性空间$ \boldsymbol{X} $ 的映射，$ {\boldsymbol{W}} $ 是$ \boldsymbol{X} $ 的一个子空间。如果对于$ {\boldsymbol{W}} $ 中任意一个向量$ {\boldsymbol{x}} $ 有$ {\boldsymbol{Mx}} \in {\boldsymbol{W}} $ ，则称$ {\boldsymbol{W}} $ 是$ {\boldsymbol{M}} $ 不变子空间(如果映射$ {\boldsymbol{M}} $ 是平凡的，则$ {\boldsymbol{W}} $ 是平凡不变的)。引理3[17] 用
$ {\boldsymbol{P}} $ 表示$ {{\text{π}} _{{\mathrm{LAEP}}}} $ 的特征矩阵，当且仅当存在矩阵$ {\boldsymbol{Q}} = {{\boldsymbol{L}}_{\text{π}} } $ 使得$ {\boldsymbol{L}} $ 满足$ {\boldsymbol{LP}} = {\boldsymbol{P}}{{\boldsymbol{L}}_{\text{π}} } $ ，则$ {\mathrm{Im}}({\boldsymbol{P}}) $ 是$ {\boldsymbol{L}} $ 不变子空间。推论1 用
$ {{\boldsymbol{P}}^{\boldsymbol{*}}} $ 表示$ {{\text{π}} _{{\mathrm{LAEP}}}} $ 在$ {V_{\rm f}} $ 中的特征矩阵，即特征矩阵$ {\boldsymbol{P}} $ 中去掉领导者胞腔所在行和列之后的矩阵，用$ {\mathcal{A}_{\text{π}} } $ 表示$ - {{\boldsymbol{L}}_{\text{π}} } $ 中去掉领导者胞腔所在行和列之后的矩阵。根据引理3，当且仅当存在矩阵$ {\boldsymbol{Q}} = {\mathcal{A}_{\text{π}} } $ 使得$ \mathcal{A} $ 满足$ \mathcal{A}{P}^{*}={P}^{*}Q $ ，$ \mathrm{Im}(\boldsymbol{P}) $ 是$ \mathcal{A} $ 不变子空间。定理2 在符号图的距离划分和领导者孤立的几乎等价划分下，能控矩阵秩的取值范围是
$ |{{\text{π}} _{\mathrm{D}}}| - 1 \leqslant {\mathrm{rank}}({\boldsymbol{C}}) \leqslant |{\bar {\text{π}} _{{\mathrm{LAEP}}}}| - m $ ，其中$m$ 表示领导者的个数。证明 对于下界：一个给定领导者的符号网络
$ G $ ，$ |{{\text{π}} _{\mathrm{D}}}| $ 表示划分的胞腔个数。图$ G $ 的$ \mathcal{A} $ 和$ \mathcal{B} $ 表示为$$ \begin{gathered} \boldsymbol{\mathcal { A }}=\left[\begin{array}{ccccccc} \boldsymbol{L}_{22} & \boldsymbol{L}_{23} & 0 & \cdots & 0 & 0 & 0 \\ \boldsymbol{L}_{23}^{\mathrm{T}} & \boldsymbol{L}_{33} & \boldsymbol{L}_{34} & \cdots & 0 & 0 & 0 \\ 0 & \boldsymbol{L}_{34}^{\mathrm{T}} & \boldsymbol{L}_{44} & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & \boldsymbol{L}_{r-2, r-2} & \boldsymbol{L}_{r-2, r-1} & 0 \\ 0 & 0 & 0 & \cdots & \boldsymbol{L}_{r-2, r-1}^{\mathrm{T}} & \boldsymbol{L}_{r-1, r-1} & \boldsymbol{L}_{r-1, r} \\ 0 & 0 & 0 & \cdots & 0 & \boldsymbol{L}_{r-1, r}^{\mathrm{T}} & \boldsymbol{L}_{r, r} \end{array}\right] \\ \boldsymbol{\mathcal { B }}=[1,0, \cdots, 0]^{\mathrm{T}} \end{gathered} $$ 令
$ {\boldsymbol{M}} = \left[ {\mathcal{B}{\text{ }}\mathcal{A}\mathcal{B}{\text{ }} \cdots {\text{ }}{\mathcal{A}^{r - 2}}\mathcal{B}} \right] $ ，则有$$ \boldsymbol{M}=\left[\begin{array}{ccccccc} 1 & \boldsymbol{L}_{22} & * & \cdots & * & * & * \\ 0 & \boldsymbol{L}_{23}^{\mathrm{T}} & * & \cdots & * & * & * \\ 0 & 0 & \boldsymbol{L}_{34}^{\mathrm{T}} \boldsymbol{L}_{323}^{\mathrm{T}} & \cdots & * & * & * \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & \boldsymbol{L}_{r-3, r-2}^{\mathrm{T}} \cdots \boldsymbol{L}_{23}^{\mathrm{T}} & * & * \\ 0 & 0 & 0 & \cdots & 0 & \boldsymbol{L}_{r-2, r-1}^{\mathrm{T}} \cdots \boldsymbol{L}_{23}^{\mathrm{T}} & * \\ 0 & 0 & 0 & \cdots & 0 & 0 & \boldsymbol{L}_{r-1, r-1}^{\mathrm{T}} \cdots \boldsymbol{L}_{23}^{\mathrm{T}} \end{array}\right]$$ 易知
$ {\mathrm{rank}}({\boldsymbol{M}}) = |{{\text{π}} _{\rm D}}| - 1 $ 。其中“$ * $ ”表示不需要明确表示的矩阵。因为$$ \begin{array}{c}{\mathrm{rank}}({\boldsymbol{M}})={\mathrm{rank}}\left({\mathcal{B}},\mathcal{A}{\mathcal{B}},\cdots ,{\mathcal{A}}^{r-2}{\mathcal{B}}\right)\leqslant \\ {\mathrm{rank}}\left({\mathcal{B}},\mathcal{A}{\mathcal{B}},\cdots ,{\mathcal{A}}^{n-m-1}{\mathcal{B}}\right) ={\mathrm{rank}}({\boldsymbol{C}})\end{array} $$ 所以有
$ |{{\text{π}} _{\rm D}}| - 1 = {\mathrm{rank}}({\boldsymbol{M}}) \leqslant {\mathrm{rank}}({\boldsymbol{C}}) $ 。对于上界：令
$ {{\boldsymbol{P}}_{{{\text{π}} _{{\mathrm{LAEP}}}}}} $ 表示$ {{\boldsymbol{P}}_{{{\text{π}} _{{\mathrm{LAEP}}}}}} $ 的特征矩阵，那么有$ {\mathrm{Im}}(\mathcal{B}) \subseteq {\mathrm{Im}}({{\boldsymbol{P}}^*}) $ 。根据推论1可得$$ \begin{array}{c}{\rm{Im}}(C)={\rm{Im}}\left(\left[{\mathcal{B}},\mathcal{A}{\mathcal{B}},\cdots ,{\mathcal{A}}^{n-m-1}{\mathcal{B}}\right]\right)= \\ {\rm{Im}}({\mathcal{B}})+\mathcal{A}{\rm{Im}}({\mathcal{B}})+\cdots +{\mathcal{A}}^{n-m-1}{\rm{Im}}({\mathcal{B}})\subseteq \\ {\rm{Im}}({P}^{*})+\mathcal{A}{\rm{Im}}({P}^{*})+\cdots +{\mathcal{A}}^{n-m-1}{\rm{Im}}({P}^{*})= {\rm{Im}}({P}^{*})\end{array} $$ 式中+表示2个空间的和。因此有
$ {\mathrm{rank}}({\boldsymbol{C}}) \leqslant |{{\text{π}} _{{\mathrm{LAEP}}}}| - m $ 。此外，在符号图中领导者孤立的几乎等价划分并不唯一，用$ {\bar {\text{π}} _{{\mathrm{LAEP}}}} $ 表示不同的领导者孤立几乎等价划分中最细的划分，即$ {\bar {\text{π}} _{{\mathrm{LAEP}}}} = {\mathrm{min}}|{{\text{π}} _{{\mathrm{LAEP}}}}| $ ，用$ {{\bar{\boldsymbol P}}_{{{\text{π}} _{{\mathrm{LAEP}}}}}} $ 表示$ {{\text{π}} _{{\mathrm{LAEP}}}} $ 的特征矩阵。则有$ {\mathrm{Im}}({{\boldsymbol{P}}^*}) \subseteq {\mathrm{Im}}({{\bar{\boldsymbol P}}_{{{\text{π}} _{{\mathrm{LAEP}}}}}}) $ ，最后得证$ {\mathrm{rank}}({\boldsymbol{C}}) \leqslant |{\bar {\text{π}} _{{\mathrm{LAEP}}}}| - m $ 。综上所述，$ {\mathrm{rank}}({\boldsymbol{C}}) $ 的取值范围是$ |{{\text{π}} _{\rm D}}| - 1 \leqslant {\mathrm{rank}}({\boldsymbol{C}}) \leqslant |{\bar {\text{π}} _{{\mathrm{LAEP}}}}| - m $ ，证毕。例2 考虑图5中的多智能体系统，其中图5(a)中节点
$ {v_1} $ 为领导者，图5(b)中节点$ {v_1} $ 和$ {v_2} $ 为领导者，对定理2的有效性进行验证。
图 5 单领导者和多领导者符号网络Fig. 5 Single leader and multi-leader symbol networks下载:
全尺寸图片
图5(a)中几个领导者孤立的几乎等价划分分别为：
$ {{\text{π}} _{{\mathrm{LAEP1}}}} = \left\{ {\left\{ {{v_1}} \right\},\left\{ {{v_2}{,}{v_3}{,}{v_4}} \right\}{,}\left\{ {{v_5}{,}{v_6}{,}{v_7}} \right\}} \right\} $ ，$ {{\text{π}} _{{{\mathrm{LAEP}}}2}} = \left\{ \left\{ {{v_1}} \right\}{,} \left\{ {{v_2}{,}{v_3}} \right\}{,} \left\{ {{v_4}} \right\}{,}\left\{ {{v_5}{,}{v_6}} \right\}{,}\left\{ {{v_7}} \right\} \right\} $ ，$ {{\text{π}} _{{{\mathrm{LAEP}}}3}} = \left\{ \left\{ {{v_1}} \right\}{,}\left\{ {{v_2}} \right\}{,}\left\{ {{v_3}} \right\}{,}\left\{ {{v_4}} \right\}{,} \left\{ {{v_5}} \right\}{,} \left\{ {{v_6}} \right\}{,}\left\{ {{v_7}} \right\} \right\} $ 。$ {\bar {\text{π}} _{{{\mathrm{LAEP}}}}} $ 为所有领导者孤立几乎等价划分中最细的划分，则有$ {\bar {\text{π}} _{{{\mathrm{LAEP}}}}} = {{\text{π}} _{{{\mathrm{LAEP}}}3}} $ 。$ {{\text{π}} _{\rm D}} = \left\{ {\left\{ {{v_1}} \right\}{,}\left\{ {{v_2}{,}{v_3}{,}{v_4}} \right\}{,}\left\{ {{v_5},{v_6}{,}{v_7}} \right\}} \right\} $ ，根据定理2有$ |{{\text{π}} _{\rm D}}| - 1 = 2 < {{\mathrm{rank}}}({\boldsymbol{C}}) = 4 < 6 = |{\bar {\text{π}} _{{{\mathrm{LAEP}}}}}| - 1 $ 。图5(b)中几个领导者孤立的几乎等价划分分别为：
$ {{\text{π}} _{{{\mathrm{LAEP}}}1}} = \left\{ {\left\{ {{v_1}} \right\}{,}\left\{ {{v_2}{,}{v_3}} \right\}{,}\left\{ {{v_4}{,}{v_5}} \right\}{,}\left\{ {{v_6}} \right\}} \right\} $ ，$ {{\text{π}} _{{{\mathrm{LAEP}}}2}} = \left\{ \left\{ {{v_1}} \right\}{,} \left\{ {{v_2}{,}{v_3}} \right\}{,}\left\{ {{v_4}} \right\}{,}\left\{ {{v_5}} \right\}{,}\left\{ {{v_6}} \right\} \right\} $ ，$ {{\text{π}} _{{{\mathrm{LAEP}}}3}} = \left\{ \left\{ {{v_1}} \right\}{,}\left\{ {{v_2}} \right\}{,}\left\{ {{v_3}} \right\}{,}\left\{ {{v_4}} \right\}{,} \left\{ {{v_5}} \right\}{,} \left\{ {{v_6}} \right\} \right\} $ 。有$ {\bar {\text{π}} _{{{\mathrm{LAEP}}}}} = {{\text{π}} _{{{\mathrm{LAEP}}}3}} $ 。$ {{\text{π}} _{\rm D}} = \left\{ {\left\{ {{v_1}{,}{v_6}} \right\}{,}\left\{ {{v_2}{,}{v_3}{,}{v_4}{,}{v_5}} \right\}} \right\} $ ，根据定理2有$ |{{\text{π}} _{\rm D}}| - 1 = 1 < {{\mathrm{rank}}}({\boldsymbol{C}}) = 2 < 4 = |{\bar {\text{π}} _{{{\mathrm{LAEP}}}}}| - 2 $ 。注4 图5(a)是一个单领导者的符号图。
$ {{\text{π}} _{\rm D}} $ 与$ {{\text{π}} _{{{\mathrm{LAEP}}}}} $ 的划分有重合的情况，例如图3(a)中$ {{\text{π}} _{\rm D}} = {{\text{π}} _{{{\mathrm{LAEP}}}1}} $ 。根据注3，距离划分的结果是唯一的，仅利用同一个划分方法无法同时获得能控子空间维数的上界和下界。因此，通过限制$ {\bar {\text{π}} _{{{\mathrm{LAEP}}}}} $ 来处理这种划分结果重合的情况。图5(b)是一个多领导者的符号图。根据定义4和定义7中对于领导者集合的处理方式可知，在多个领导者的情况下$ {{\text{π}} _{\rm D}} \ne {{\text{π}} _{{{\mathrm{LAEP}}}}} $ 。因此，需要通过不同的划分来确定能控子空间维数的上界和下界。3.2 基于距离划分下的
$ K $ 步可控系统
$ K $ 步可控的物理意义是网络系统中施加各种控制器能够在$ K $ 步路径内直接或间接的控制网络中的所有状态节点，即控制作用能在$ K $ 步之内可达或者说覆盖所有节点。越小的能控性指数意味着大规模网络系统能够更快地达到稳定的状态。定义10 (能控性指数)对于完全可控的连续时间线性时不变系统
$ {\boldsymbol{\dot x}} = {\boldsymbol{Ax}} + {\boldsymbol{Bu}} $ ，系统的能控性指数等于使下列等式成立的最小正整数$ K(1 \leqslant K \leqslant n) $ ：$$ {{\mathrm{rank}}}({\boldsymbol{C}}) = {{\mathrm{rank}}}({\boldsymbol{B}}|{\boldsymbol{AB}}|{{\boldsymbol{A}}^{2}}{\boldsymbol{B}}| \cdots |{{\boldsymbol{A}}^{K - 1}}{\boldsymbol{B}}) = n $$ 引理4
$ K $ 步可控的充要条件[30]，系统$ {\boldsymbol{\dot x}} = {\boldsymbol{Ax}} + {\boldsymbol{Bu}} $ 是$ K $ 步可控的当且仅当正整数$ K $ 满足条件：$$ \left\{ {\begin{array}{*{20}{c}} {{{\mathrm{rank}}}({\boldsymbol{C}}) = {{\mathrm{rank}}}({\boldsymbol{B}}|{\boldsymbol{AB}}|{{\boldsymbol{A}}^{2}}{\boldsymbol{B}}| \cdots |{{\boldsymbol{A}}^{K - 1}}{\boldsymbol{B}}) = n} \\ {{{\mathrm{rank}}}({\boldsymbol{C}}) = {{\mathrm{rank}}}({\boldsymbol{B}}|{\boldsymbol{AB}}|{{\boldsymbol{A}}^{2}}{\boldsymbol{B}}| \cdots |{{\boldsymbol{A}}^{K - 2}}{\boldsymbol{B}}) < n} \end{array}} \right. $$ 注5 2个顶点
$ {v_i} $ 和$ {v_j} $ 之间的距离是从$ {v_i} $ 到$ {v_j} $ 最短路径的长度。对于无向路图，选择端点作为领导者时，有$ K = |{{\text{π}} _{\rm D}}| - 1 = n - 1 $ ，其中$ n $ 表示路图中节点的个数。定理3 若系统是
$ K $ 步可控的，则通过删除拓扑图的边可以将拓扑图分解成$s$ 个路图。选择每个路图的一个端点作为领导者时，系统的能控性指数$ K = {\mathrm{max}}{\text{ }}{K_i} $ ，其中$ {K_i}(1 \leqslant i \leqslant s) $ 为每个路图的能控性指数。证明
$ G $ 是由多个路图$ {G_1}{,}{G_2}{,} \cdots {,}{G_s} $ 组成，每个路图互不相连。其中一个端点作为领导者时，系统矩阵和输入矩阵表示为$$ \mathcal{A}=\left[\begin{array}{ccc} \mathcal{A}_1 & & 0 \\ & \ddots & \\ 0 & & \mathcal{A}_s \end{array}\right], \quad \mathcal{B}=\left[\begin{array}{ccc} \mathcal{B}_1 & & 0 \\ & \ddots & \\ 0 & & \mathcal{B}_s \end{array}\right] $$ 系统的能控矩阵为
$$ C = \left[ { {\begin{array}{*{20}{c}} {\cal B}\\ \vdots \\ 1 \end{array}} \left| {\begin{array}{*{20}{c}} {}\\ \cdots \\ {} \end{array}} \right| {\begin{array}{*{20}{c}} {{\cal A}_1^{K - 1}{{\cal B}_1}}\\ \vdots \\ 0 \end{array}} \left| {\begin{array}{*{20}{c}} {}\\ \cdots \\ {} \end{array}} \right| {\begin{array}{*{20}{c}} 0\\ \vdots \\ {{{\cal B}_s}} \end{array}} \left| {\begin{array}{*{20}{c}} {}\\ \cdots \\ {} \end{array}} \right| \begin{array}{*{20}{c}} 0\\ \vdots \\ {{\cal A}_1^{K - 1}{{\cal B}_s}} \end{array}} \right] $$ 所以，系统的
$ K $ 对应于子路图的$ K $ ，显然满足引理4。结合定义10可知最小正整数$ K = \max {K_i} $ ，证毕。下面给出一种从图论的角度得到系统
$ K $ 值的算法。定义节点$ {v_i} $ 的关联度为$ {c_i} = \displaystyle\sum_{i \in {N_i}} {|{a_{ij}}|} $ ，算法具体步骤如下。1) 初始化集合
$ {S_1} $ ，将关联度最大的节点记为$ {v_i} $ ，$ i \in V $ 存入集合$ {S_1} $ 中。2) 随机选取
$ {S_1} $ 中的一个节点，由该节点开始向任意一个关联度最小的节点$ w $ 进行遍历，遍历路径记为$ {P_{{v_i}{,}w}} $ ，路径长度记为$ |{P_{{v_i}{,}w}}| $ 。选取其中路径长度最短的一条路径记为$ P_{\min}^1 $ 。如果最短路径个数大于1，则随机选择一条最短遍历路径。3) 将
$ P_{\min}^1 $ 保留，将其他节点与该路径一步可达的边删除，新图记为图$ {G^{(1)}} $ 。4) 重复以上操作，直到图
$ {G^{(k)}} $ 中没有关联度大于2的节点为止。5) 选择
$ P_{\min}^v $ ,$ v = \{ 1{,}2{,} \cdots {,}k\} $ 的起始节点、剩余路径的任意一个端点以及孤立节点作为领导者，则系统能控性指数为$ K = {\max}{\text{ }}{K_s} $ ，其中$ {K_s} $ 表示$ {G^{(k)}} $ 中第$s$ 个路径在选定领导者时的能控性指数，$s$ 表示$ {G^{(k)}} $ 中独立路径的个数。注6 系统的
$ K $ 步可控与拓扑图的边权无关，因此定义节点$ {v_i} $ 的关联度$ {c_i} $ 中的$ |{a_{ij}}| = 1 $ 。以上算法提供了一种在图论视角下得到能控系统$ K $ 值和领导者选择的方法，可以在选取领导者保证系统能控的同时，通过更简单的计算就能得出系统的能控性指数$K$ 值，避免了按照传统方法[31]利用能控性判据对$K$ 值进行计算。该算法是基于距离划分新定义和定理3提出的，具有如下优势：1)该算法避免了求解$K$ 值的大量矩阵计算；2)图论的删减边方法减少了遍历次数，随着删减边的进行，遍历的节点数量也随之减少，从而减少了计算时间；3)该算法在计算$K$ 值的同时也为领导者的选择提供了方法。与大部分只讨论选择更少的领导者算法文献[32-33]相比，上述算法在讨论领导者选择方法的同时兼顾了$K$ 值的图论计算方法。该算法的时间复杂度为$O({n^2})$ ，空间复杂度为$O(n)$ ，其中$n$ 为拓扑网络的节点数，图6是算法流程。
图 6 算法流程Fig. 6 Algorithm flow下载:
全尺寸图片
例3 如图7所示，
$ G $ 是一个有10个节点、14条边的符号网络。接下来，对上述算法的有效性进行验证。
图 7 符号网络$ G $ Fig. 7 Symbolic network$ G $ 下载:
全尺寸图片
根据算法，先找到关联度最大的节点放入集合
$ {S_1} $ 中，$ {S_1} = \left\{ {{v_4}} \right\} $ 。由节点$ {v_4} $ 开始向关联度最小的节点$ {v_1}{、}{v_6}{、}{v_{10}} $ 遍历，在遍历的所有路径中选择最短路径$ P_{\min}^1 = {v_4} \to {v_6} $ ，保留$ P_{\min}^1 $ ，删除与该路径相连的边得到图8(a)的$ {G^{(1)}} $ 。
图 8$ {G^{(1)}} $ 和$ {G^{(2)}} $ Fig. 8$ {G^{(1)}} $ and$ {G^{(2)}} $ 下载:
全尺寸图片
寻找
$ {G^{(1)}} $ 中关联度最大的节点放入集合$ {S_2} $ 中，$ {S_2} = \left\{ {{v_3}{,}{v_7}{,}{v_9}} \right\} $ ，随机选择节点$ {v_9} $ 开始向关联度最小的节点$ {v_5} $ 遍历，在所有路径中选择最短遍历路径$ P_{\min}^2 = {v_9} \to {v_7} \to {v_5} $ ，保留$ P_{\min}^2 $ ，删除与该路径相连的边得到图8(b)的$ {G^{(2)}} $ 。寻找
$ {G^{(2)}} $ 中关联度最大的节点放入集合$ {S_3} $ 中，$ {S_3} = \left\{ {{v_3}} \right\} $ ，选择节点$ {v_3} $ 开始向关联度最小的节点$ {v_8} $ 遍历，在所有路径中选择最短遍历路径$ P_{\min}^3 = {v_3} \to {v_8} $ ，保留$ P_{\min}^3 $ ，删除与该路径相连的边得到图9(a)的$ {G^{(3)}} $ 。
图 9$ {G^{(3)}} $ 和$ G_{\mathrm{l}}^{(3)} $ Fig. 9$ {G^{(3)}} $ and$ G_{\mathrm{l}}^{(3)} $ 下载:
全尺寸图片
在
$ {G^{(3)}} $ 中，选择最短路径的初始节点$ {v_3}{,}{v_4}{,}{v_9} $ 、剩余路径中端点$ {v_2} $ 和孤立节点$ {v_{10}} $ 为领导者，即$ {V_{\rm l}} = \left\{ {{v_2}{,}{v_3}{,}{v_4}{,}{v_9}{,}{v_{10}}} \right\} $ ，如图9(b)的$ G_{\mathrm{l}}^{(3)} $ 。$ G_{\rm l}^{(3)} $ 中4条路径在该领导者选择下是能控的且$ {K_1} = 1{,}{K_2} = 2{,}{K_3} = 1{,}{K_4} = 1 $ 。按照该算法选择领导者在原图中表示为图10。根据定理3，系统的能控性指数为$ K=\max\left(K_1,K_2,K_3,K_4\right)=2 $ 。通过计算对上述结果进行验证：
图 10$ G' $ Fig. 10$ G' $ 下载:
全尺寸图片
$$ \mathcal{A}=\left[ \begin{array}{rrrrr} -2 & 0 & 0 & 0 & 0 \\ 0 & -1 & 1 & -1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & -3 \end{array} \right], \mathcal{B}=\left[ \begin{array}{rrrrr} 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \end{array} \right] $$ $$ \begin{aligned} \operatorname{rank}(\boldsymbol{C}) =\operatorname{rank}\left(\left[\begin{array}{rrrrr} 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 \end{array}\right] \right. \\ \left. \left| \left[\begin{array}{rrrrr} -2 & -2 & 0 & 0 & 0 \\ 0 & 0 & -2 & -1 & -1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & -1 & -1 & -1 \\ 0 & -3 & -3 & -3 & 0 \end{array}\right]\right| \cdots\right) =5, K=2 \end{aligned} $$ 该算法是基于定理3得到的。在结构更复杂的系统中，定理3给出的
$K$ 值计算方法相比于定义10，是图中节点距离与矩阵数值计算的差别。从例3可以直观看出，根据算法求解系统$K$ 值仅需要比较处理后的拓扑图中最大路径的步数，即$ K = \max {K_i} $ ，其中$ {K_i}(1 \leqslant i \leqslant s) $ ，而这一步在算法的步骤2中就已经得出，系统的$K$ 值直接通过$ G_{\mathrm{l}}^{(3)} $ 中的路径距离进行比较即可，相比于满足能控型矩阵满秩的最小正整数的求解过程来说，节省了大量矩阵计算。4. 结束语
本文主要讨论了符号网络下的多智能体系统能控性问题。首先，在2种leader-follower模型的基础上，利用新定义的距离划分和规范变换对结构平衡符号图进行特征描述。特别地，该划分方法是以领导者节点为中心定义的。其次，利用距离划分和几乎等价划分得到了符号多智能体网络能控子空间的上界和下界。最后，在距离划分定义的基础上进行拓展，结合路图
$ K $ 步可控的特殊性，给出了一种在图论视角下计算密集网络$ K $ 值的算法。未来考虑将研究结果扩展到有向图。此外，目前对多智能体网络可控性的研究几乎都是针对线性系统的，事实上，非线性普遍存在于许多实际的复杂网络中。对于单节点非线性系统，目前还没有通用的方法来直接分析系统的可控性，这也是今后工作的一个重要方向。 -
图 1 结构平衡示例
Fig. 1 Examples of structural balance
下载:
全尺寸图片
图 2 模型关系示例
Fig. 2 Example of model relationship
下载:
全尺寸图片
图 3 距离划分示例及构造过程
Fig. 3 Distance division example and construction process
下载:
全尺寸图片
图 4 结构平衡符号网络及其对应的无符号网络
Fig. 4 Structural balance signed networks and its corresponding unsigned networks
下载:
全尺寸图片
图 5 单领导者和多领导者符号网络
Fig. 5 Single leader and multi-leader symbol networks
下载:
全尺寸图片
图 6 算法流程
Fig. 6 Algorithm flow
下载:
全尺寸图片
图 7 符号网络
$ G $ Fig. 7 Symbolic network
$ G $ 下载:
全尺寸图片
图 8
$ {G^{(1)}} $ 和$ {G^{(2)}} $ Fig. 8
$ {G^{(1)}} $ and$ {G^{(2)}} $ 下载:
全尺寸图片
图 9
$ {G^{(3)}} $ 和$ G_{\mathrm{l}}^{(3)} $ Fig. 9
$ {G^{(3)}} $ and$ G_{\mathrm{l}}^{(3)} $ 下载:
全尺寸图片
图 10
$ G' $ Fig. 10
$ G' $ 下载:
全尺寸图片
-
[1] GUO Junhao, JI Zhijian, LIU Yungang, et al. Unified understanding and new results of controllability model of multi-agent systems[J]. International journal of robust and nonlinear control, 2022, 32(11): 6330−6345. doi: 10.1002/rnc.6140 [2] LIU Bo, AN Qing, GAO Yanping, et al. Leader–follower controllability of signed networks[J]. ISA transactions, 2022, 128: 115−122. doi: 10.1016/j.isatra.2021.10.007 [3] LOU Yanhong, JI Zhijian, QU Jijun. New results of multi-agent controllability under equitable partitions[J]. IEEE access, 2020, 8: 73523−73535. doi: 10.1109/ACCESS.2020.2988141 [4] 关永强, 纪志坚, 张霖, 等. 多智能体系统能控性研究进展[J]. 控制理论与应用, 2015, 32(4): 421−431. doi: 10.7641/CTA.2014.40419 GUAN Yongqiang, JI Zhijian, ZHANG Lin, et al. Recent developments on controllability of multi-agent systems[J]. Control theory & applications, 2015, 32(4): 421−431. doi: 10.7641/CTA.2014.40419 [5] 王龙, 杜金铭. 多智能体协调控制的演化博弈方法[J]. 系统科学与数学, 2016, 36(3): 302−318. doi: 10.12341/jssms12735 WANG Long, DU Jinming. Evolutionary game theoretic approach to coordinated control of multi-agent systems[J]. Journal of systems science and mathematical sciences, 2016, 36(3): 302−318. doi: 10.12341/jssms12735 [6] 赵兰浩, 纪志坚. 符号网络条件下扩散耦合多智能体系统的可控性分析[J]. 系统科学与数学, 2021, 41(6): 1455−1466. ZHAO Lanhao, JI Zhijian. Controllability analysis of diffusion coupled multi-agent system under signed networks[J]. Journal of systems science and mathematical sciences, 2021, 41(6): 1455−1466. [7] 陈万金, 纪志坚. 基于拓扑结构和个体动态层面的多智能体系统可控性分析[J]. 智能系统学报, 2020, 15(2): 264−270. doi: 10.11992/tis.201901006 CHEN Wanjin, JI Zhijian. Controllability analysis of multi-agent systems based on topological structure and individual dynamic level[J]. CAAI transactions on intelligent systems, 2020, 15(2): 264−270. doi: 10.11992/tis.201901006 [8] JI Zhijian, YU Haisheng. A new perspective to graphical characterization of multiagent controllability[J]. IEEE transactions on cybernetics, 2017, 47(6): 1471−1483. doi: 10.1109/TCYB.2016.2549034 [9] TANNER H G. On the controllability of nearest neighbor interconnections[C]//2004 43rd IEEE Conference on Decision and Control. Nassau: IEEE, 2004: 2467−2472. [10] SUN Chao, HU Guoqiang, XIE Lihua. Controllability of multiagent networks with antagonistic interactions[J]. IEEE transactions on automatic control, 2017, 62(10): 5457−5462. doi: 10.1109/TAC.2017.2697202 [11] AGUILAR C O, GHARESIFARD B. Graph controllability classes for the Laplacian leader-follower dynamics[J]. IEEE transactions on automatic control, 2015, 60(6): 1611−1623. doi: 10.1109/TAC.2014.2381435 [12] YAZıCıOĞLU A Y, ABBAS W, EGERSTEDT M. Graph distances and controllability of networks[J]. IEEE transactions on automatic control, 2016, 61(12): 4125−4130. doi: 10.1109/TAC.2016.2546180 [13] 纪志坚. 等价划分下多智能体系统能控性的一种判定方法[J]. 聊城大学学报(自然科学版), 2023, 36(6): 1−8. JI Zhijian. A method for determining the controllability of multi-agent systems under equitable partition[J]. Journal of Liaocheng University (natural science edition), 2023, 36(6): 1−8. [14] SU Mengmeng, JI Zhijian, LIU Yungang, et al. Improved multi-agent controllability processing technique based on equitable partition[J]. ISA transactions, 2023, 138: 301−310. doi: 10.1016/j.isatra.2023.03.004 [15] ZHANG Xiufeng, SUN Jian. Almost equitable partitions and controllability of leader-follower multi-agent systems[J]. Automatica, 2021, 131: 109740. doi: 10.1016/j.automatica.2021.109740 [16] AGUILAR C O, GHARESIFARD B. Almost equitable partitions and new necessary conditions for network controllability[J]. Automatica, 2017, 80: 25−31. doi: 10.1016/j.automatica.2017.01.018 [17] GAO Hua, JI Zhijian, HOU Ting. Equitable partitions in the controllability of undirected signed graphs[C]//2018 IEEE 14th International Conference on Control and Automation. Anchorage: IEEE, 2018: 532−537. [18] HEIDER F. Attitudes and cognitive organization[J]. The journal of psychology, 1946, 21: 107−112. doi: 10.1080/00223980.1946.9917275 [19] GUBANOV D A, CHKHARTISHVILI A G. A conceptual approach to online social networks analysis[J]. Automation and remote control, 2015, 76(8): 1455−1462. doi: 10.1134/S000511791508010X [20] FACCHETTI G, IACONO G, ALTAFINI C. Computing global structural balance in large-scale signed social networks[J]. Proceedings of the national academy of sciences of the United States of America, 2011, 108(52): 20953−20958. [21] LI Guilu, REN Change, PHILIP CHEN C L. Preview-based leader-following consensus control of distributed multi-agent systems[J]. Information sciences, 2021, 559: 251−269. doi: 10.1016/j.ins.2020.12.081 [22] GAO Yanping, KOU Kaixuan, ZHANG Weijing, et al. Consensus in networks of agents with cooperative and antagonistic interactions[J]. Mathematics, 2023, 11(4): 921. doi: 10.3390/math11040921 [23] GAMBUZZA L V, FRASCA M. Distributed control of multiconsensus[J]. IEEE transactions on automatic control, 2021, 66(5): 2032−2044. doi: 10.1109/TAC.2020.3006820 [24] 王晓宇, 刘开恩, 纪志坚, 等. 异质多智能体系统二分一致性的充要条件[J]. 智能系统学报, 2020, 15(4): 679−686. doi: 10.11992/tis.201901008 WANG Xiaoyu, LIU Kaien, JI Zhijian, et al. Necessary and sufficient conditions for bipartite consensus of heterogeneous multi-agent systems[J]. CAAI transactions on intelligent systems, 2020, 15(4): 679−686. doi: 10.11992/tis.201901008 [25] GUAN Yongqiang, WANG Long. Controllability of multi-agent systems with directed and weighted signed networks[J]. Systems & control letters, 2018, 116: 47−55. [26] SUN Yinshuang, JI Zhijian, LIU Yungang, et al. On stabilizability of multi-agent systems[J]. Automatica, 2022, 144: 110491. doi: 10.1016/j.automatica.2022.110491 [27] SHE Baike, KAN Zhen. Characterizing controllable subspace and herdability of signed weighted networks via graph partition[J]. Automatica, 2020, 115: 108900. doi: 10.1016/j.automatica.2020.108900 [28] MORTAZAVIAN H. On k-Controllability and k-Observability of linear systems[M]//Analysis and Optimization of Systems. Berlin/Heidelberg: Springer-Verlag, 2006: 600−612. [29] CHEN Hong, YONG E H. Optimizing target nodes selection for the control energy of directed complex networks[J]. Scientific reports, 2020, 10(1): 18112. doi: 10.1038/s41598-020-75101-w [30] PÓSFAI M, LIU Yangyu, SLOTINE J J, et al. Effect of correlations on network controllability[J]. Scientific reports, 2013, 3: 1067. doi: 10.1038/srep01067 [31] 郑大钟. 线性系统理论[M]. 第2版. 北京: 清华大学出版社, 2002. [32] 魏静, 关永强, 谌煜, 等. 基于领导者选择的聚类平衡网络的可牧性[J]. 控制与决策, 2025, 40(4): 1386−1394. WEI Jing, GUAN Yongqiang, SHEN Yu. et al. Herdability of clustering balanced networks based on leader selection[J]. Control and decision, 2025, 40(4): 1386−1394. [33] WANG Wenxu, NI Xuan, LAI Yingcheng, et al. Optimizing controllability of complex networks by minimum structural perturbations[J]. Physical review E, Statistical, nonlinear, and soft matter physics, 2012, 85(2 Pt 2): 026115.
