IV. 网络动态
根据协议(A1)，一组连续时间积分器代理的网络状态按照以下线性系统演化：
\[\dot{x}(t)=-L x(t)\qquad(8) \]其中，L 被称为由信息流 G 引发的图拉普拉斯矩阵，其定义为
\[l_{i j}=\left\{\begin{array}{ll}\sum_{k=1, k\neq i}^n a_{i k},& j=i\\ -a_{i j},& j\neq i\end{array}.\right. \]显然，系统(8)的稳定性取决于图拉普拉斯矩阵 L 的特征值位置。图的谱特性是代数图论的主要研究主题之一[30],[31]。这里使用的图拉普拉斯矩阵的基本属性将在第V节中讨论。
在具有切换拓扑的网络中，协议(A1)的收敛性分析等价于混合系统的稳定性分析：
\[\dot{x}(t)=-L_k x(t)\quad k=s(t) \]其中 \(L_{k}=\mathcal{L}\left(G_{k}\right)\) 是属于集合 \(\Gamma\) 的图 \(G_{k}\) 的拉普拉斯矩阵。集合 \(\Gamma\) 是一个有限的有向图集，包含 n 阶图，索引集 \(\mathcal{I}_{\Gamma}\subset Z\)。映射 \(s(t): R\rightarrow\mathcal{I}_{\Gamma}\) 是一个切换信号，用于确定网络拓扑。
在第IX节中，我们将看到对于 \(n\gg 1\)，集合 \(\Gamma\) 是相对较大的。对(10)中的混合系统进行稳定性分析的任务颇具挑战性。原因之一是两个拉普拉斯矩阵的乘积通常不交换。
对于离散时间模型的代理，应用协议(A1)会得到以下离散时间网络动态：
\[x(k+1)=P_\epsilon x(k)\qquad(11) \]其中
\[P_\epsilon=I-\epsilon L.(12) \]令 \(d_{\max}=\max_{i} l_{i i}\) 表示有向图 G 的最大节点出度，则对于所有 \(\epsilon\in\left(0,1/ d_{\max}\right)\)，\(P_{\epsilon}\) 是一个非负且随机的矩阵。我们称 \(P_{\epsilon}\) 为由 G 引导的 Perron 矩阵。
对于离散时间代理的协议(A1)的收敛性分析主要依赖于非负矩阵理论[32],[35]，并将在另一篇论文中讨论。我们的方法提出了基于 Lyapunov 的收敛性分析，用于分析具有离散时间模型的网络中的一致性。这与 Jadbabaie 等人的工作中所采用的方法不同，后者主要依赖于矩阵理论性质和随机矩阵的无限右收敛乘积(RCP)[36]。
V. 代数图论和矩阵理论
在本节中，我们介绍了图论中一些基本概念和符号，这些概念将贯穿本文使用。更多信息可参见[31]和[37]。关于无向图拉普拉斯矩阵性质的全面综述可参见[38]。然而，我们需要使用一些有向图拉普拉斯矩阵的基本性质，这些性质在图论文献中找不到，将在此处陈述。
设 \(G=(\mathcal{V},\mathcal{E},\mathcal{A})\) 为一个具有 n 个节点的加权有向图(或有向图)。节点 \(v_{i}\) 的入度和出度分别定义如下：
\[\operatorname{deg}_{\text{in}}\left(v_i\right)=\sum_{j=1}^n a_{j i}\quad\operatorname{deg}_{\text{out}}\left(v_i\right)=\sum_{j=1}^n a_{i j}.\qquad(13) \]对于具有 0-1 邻接元素的图，\(\operatorname{deg}_{\text{out}}\left(v_i\right)=\left|N_i\right|\)。有向图 G 的度矩阵是对角矩阵 \(\Delta=\) \(\left[\Delta_{i j}\right]\) ，其中 \(\Delta_{i j}=0\) 适用于所有 \(i\neq j\)，\(\Delta_{i i}=\operatorname{deg}_{\text{out}}\left(v_i\right)\)。与有向图 G 关联的图拉普拉斯矩阵定义为
\[\mathcal{L}(\mathcal{G})=L=\Delta-\mathcal{A}.\qquad(14) \]该定义与(9)中的 L 定义一致。
Remark 3: 图拉普拉斯矩阵 L 不依赖于 G 的邻接矩阵的对角元素 \(a_{i i}\)。这些对角元素对应于图中自环 \(\left(v_{i}, v_{i}\right)\) (即长度为一的环路)的权重。我们假设 \(a_{i i}=0\) 适用于所有 i，除非另有说明。
对于无向图，(5)中定义的拉普拉斯势可以表示为具有核 L 的二次型，或
\[\Phi_G(x)=x^T L x=\frac{1}{2}\sum_{i, j} a_{i j}\left(x_j-x_i\right)^2.\qquad(15) \]这表明无向图的拉普拉斯矩阵是正半定的。这种 L 的正定性并不一定适用于有向图。
对于有向图，拉普拉斯矩阵的正定性并不一定成立。举一个例子，考虑一个有两个节点的有向图 \(G_{2}\)，其邻接矩阵和图拉普拉斯矩阵分别为：
\[\mathcal{A}=\left[\begin{array}{ll}0& 1\\ 0& 0\end{array}\right]\quad L=\left[\begin{array}{cc}1&-1\\ 0& 0\end{array}\right]. \]我们有 \(\Phi_{G_{2}}(x)=x^{T} L x=x_{1}^{2}-x_{1} x_{2}\)，这是一个不定符号的二次型。
根据定义，拉普拉斯矩阵的每一行和为零。因此，拉普拉斯矩阵总是具有零特征值，并对应一个右特征向量
\[w_r=1=(1,1,\ldots, 1)^T \]该向量的所有元素都相同且非零。这意味着 \(\operatorname{rank}(L)\leq n-1\)。
如果一个有向图是强连通的 \((S C)\)，则当且仅当该图中的任意两个不同的节点可以通过遵循有向图边的路径连接时，该图被称为强连通图。以下定理建立了有向图的 SC 属性与其拉普拉斯矩阵秩之间的直接关系。根据下述定理，强连通有向图的拉普拉斯矩阵在零处有一个孤立特征值。
定理 1：设 \(G=(\mathcal{V},\mathcal{E},\mathcal{A})\) 为一个带有拉普拉斯矩阵 L 的加权有向图。如果 G 是强连通的，则 \(\operatorname{rank}(L)=n-1\)。
证明：见附录。
备注 4：对于无向图 G，定理 1 可以表述为：G 是连通的，当且仅当 \(\operatorname{rank}(L)=n-1\)。
无向图情况的证明在文献中有所记载[30],[31]。定理 1 的逆命题不成立。例如(16)中指定的有向图 \(G_{2}\) 明显不是强连通的，因为没有路径能够连接节点 \(v_{2}\) 和节点 \(v_{1}\)。然而，\(\operatorname{rank}(L)=1=n-1\)。
对于连通的无向图 G，以下众所周知的性质成立[31]：
\[\min_{1^{T} x=0}\frac{x^T L x}{\|x\|^2}=\lambda_2(L).\quad(17) \]证明可以参考 Courant-Fischer 定理的一个特殊情况[32]。稍后我们将建立 \(\lambda_{2}(\hat{L})\) 与 \(\hat{L}=\left(L+L^{T}\right)/ 2\) (即 \(\hat{L}\) 的 Fiedler 特征值[39])之间的联系，以及协议(A1)在有向图上执行时的性能(即最坏情况下的收敛速度)。
备注 5：图的代数连通性(或 \(\lambda_{2}\))的概念最早由 Fiedler 为无向图定义[39]。我们通过定义对有向图的镜像操作(见定义 2)生成一个无向图 \(\hat{G}\)，从而将该概念扩展为有向图的代数连通性。
(8) 的稳定性分析关键在于图拉普拉斯矩阵的谱特性。以下结果对于无向图是众所周知的(例如，参见[38])。在这里，我们对有向图陈述该结果并通过 Gergorin 圆盘定理[32]证明它。
定理 2 (谱定位)：设 \(G=(\mathcal{V},\mathcal{E},\mathcal{A})\) 为一个带有拉普拉斯矩阵 L 的有向图。记该有向图 G 的最大节点出度为 \(d_{\max}(G)=\max_{i}\operatorname{deg}_{\text{out}}\left(v_{i}\right)\)。那么，\(L=\mathcal{L}(G)\) 的所有特征值都位于以下圆盘内：
\[D(G)=\left\{z\in C:\left|z-d_{\max}(G)\right|\leq d_{\max}(G)\right\} \]该圆盘以 \(z=d_{\max}(G)+0 j\) 为圆心位于复*面内(见图1)。
证明：根据 Gergorin 圆盘定理，\(L=\left[l_{i j}\right]\) 的所有特征值都位于以下 n 个圆盘的并集中：
\[D_i=\left\{z\in C:\left|z-l_{i i}\right|\leq\sum_{j\in\mathcal{I}, j\neq i}\left|l_{i j}\right|\right\}. \]然而，对于有向图 \(G, l_{i i}=\Delta_{i i}\) 并且
\[\sum_{j\in\mathcal{I}, j\neq i}\left|l_{i j}\right|=\operatorname{deg}_{\text{out}}\left(v_i\right)=\Delta_{i i}. \]因此，\(D_{i}=\left\{z\in C:\left|z-\Delta_{i i}\right|\leq\Delta_{i i}\right\}\)。另一方面，这 n 个圆盘都包含在半径为 \(d_{\max}(G)\) 的最大圆盘 \(D(G)\) 内。显然，\(-L\) 的所有特征值都位于圆盘 \(D^{\prime}(G)=\left\{z\in C:\left|z+d_{\max}(G)\right|\leq d_{\max}(G)\right\}\) 中，该圆盘是 \(D(G)\) 相对于虚轴的镜像。\(\square\)
这里有一个直接推论，它是针对具有固定拓扑 G 的有向网络的协议(A1)的第一个收敛性证明。
推论 1：考虑一个积分器网络 \(\dot{x}_{i}=u_{i}\)，其中每个节点应用协议(A1)。假设 G 是一个强连通的有向图。那么，协议(A1)全局渐*地解决了共识问题。
推论 1 的证明：由于 G 是强连通的，\(\operatorname{rank}(L)=n-1\)，并且 L 在零处有一个简单的特征值。根据定理 2，\(-L\) 的其余特征值具有负实部，因此系统(8)是稳定的。另一方面，(8)中的任何*衡点 \(x^{*}\) 都是与 \(\lambda=0\) 对应的 L 的右特征向量。由于与零特征值相关的特征空间是一维的，存在 \(\alpha\in R\)，使得 \(x^{*}=\alpha 1\)，即 \(x_{i}^{*}=\alpha\) 对所有 i 都成立。
需要注意的是，推论 1 并不能保证群体决策值 \(\alpha\) 是否等于 \(\operatorname{Ave}(x(0))\)。换句话说，推论 1 不一定解决*均一致性问题。
我们需要为指数矩阵 \(\exp(-L t)\) 提供一个极限定理。考虑到具有固定拓扑的系统(8)的解为
\[x(t)=\exp(-L t) x(0)\qquad(20) \]通过显式计算 \(\exp(-L t)\)，可以获得一般有向图的群体决策值。下述定理与非负矩阵理论中的 Perron-Frobenius 定理[32]密切相关。我们将利用此定理来描述使用协议(A1)解决*均一致性问题的有向图类。
符号：根据[32]中的符号约定，我们用 \(M_{m, n}\) 表示 \(m\times n\) 实矩阵的集合，用 \(M_{n}\) 表示 \(n\times n\) 方阵的集合。此外，在本文中，L 的与 \(\lambda_{1}=0\) 对应的右、左特征向量分别表示为 \(w_{r}\) 和 \(w_{l}\)。
定理 3：假设 G 是一个具有拉普拉斯矩阵 L 的强连通有向图，满足 \(L w_{r}=0, w_{l}^{T} L=0\)，并且 \(w_{l}^{T} w_{r}=1\)。那么
\[R=\lim_{t\rightarrow+\infty}\exp(-L t)=w_r w_l^T\in M_n.\qquad(21) \]证明：设 \(A=-L\) 并令 J 为 A 的约当标准形 (Jordan form)，即 \(A=S J S^{-1}\)。我们有 \(\exp(A t)=S\exp(J t) S^{-1}\)，且随着 \(t\rightarrow+\infty\)，\(\exp(J t)\) 收敛到矩阵 \(Q=\left[q_{i j}\right]\)，其中只有一个非零元素 \(q_{11}=1\)。在对角线上其他块消失是由于 \(A\) 的所有非零特征值 \(\lambda_{k}(A)\) 满足 \(\operatorname{Re}\left(\lambda_{k}(A)\right)<0\) 对于所有 \(k\geq 2\)。注意到 \(R=S Q S^{-1}\)。由于 \(A S=S J\)，S 的第一列是 \(w_{r}\)。类似地，\(S^{-1} A=J S^{-1}\)，这意味着 \(S^{-1}\) 的第一行是 \(w_{l}^{T}\)。由于 \(S^{-1} S=I\)，\(w_{l}\) 满足 \(w_{l}^{T} w_{r}=1\) 的条件。通过直接计算，可以得到 \(R=w_{r} w_{l}^{T}\in M_{n}\)。\(\square\)
VI. *均一致性的反例
在推论 1 的证明中，每个节点的决策值 \(\alpha\) 等于 \(\operatorname{Ave}(x(0))\) 的充分条件是 \(\sum_{i=1}^{n} u_{i}\equiv 0\)。如果 G 是无向的(即 \(a_{i j}=a_{j i}>0,\forall i, j\))，则条件 \(\sum_{i=1}^{n} u_{i}=0,\forall x\) 自动成立，并且 \(\operatorname{Ave}(x(t))\) 是一个不变量[29]。然而，对于一般的有向图，此性质不成立。
一个简单的反例是一个阶为 \(n=3\) 的有向图，其顶点集和边集为：
\[\mathcal{V}=\left\{v_{1}, v_{2}, v_{3}\right\}\quad\mathcal{E}=\left\{e_{12}, e_{23}, e_{31}, e_{13}\right\} \]如图2所示。假设该图的权重为0-1。注意，G 是一个强连通的有向图。给定 \(G=(\mathcal{V},\mathcal{E})\)，我们有 \(\sum_{i=1}^{3} u_{i}=x_{3}-x_{1}\)。因此，如果节点 \(v_{1}\) 和 \(v_{3}\) 之间存在分歧，则对于所有 x，性质 \(\sum_{i=1}^{3} u_{i}=0\) 不成立。另一方面，读者可以验证，对于该例子
\[L=\left[\begin{array}{ccc} 2&-1&-1\\ 0& 1&-1\\ -1& 0& 1\end{array}\right]. \]使用定理 3，可以得到极限 \(x_{i}^{*}=\left[x_{1}(0)+x_{2}(0)+2 x_{3}(0)\right]/ 4\) 对于 \(i=1,2,3\)。当且仅当 \(x_{1}(0)+x_{2}(0)\neq 2 x_{3}(0)\) 时，该群体决策值不同于 \(\operatorname{Ave}(x(0))\)。因此，对于所有满足 \(x_{1}(0)+x_{2}(0)\neq 2 x_{3}(0)\) 的初始条件，协议(A1)不解决*均一致性问题，但所有节点最终会渐*达到一致。这促使我们去描述解决*均一致性问题的所有有向图的类别。
VII. 具有固定拓扑和*衡图的网络
以下有向图类对于解决具有固定和切换拓扑的网络的*均一致性问题非常重要。
定义 1 (*衡图)：我们说有向图 \(G=(\mathcal{V},\mathcal{E},\mathcal{A})\) 的节点 \(v_{i}\) 是*衡的，当且仅当它的入度和出度相等，即 \(\operatorname{deg}_{\text{out}}\left(v_{i}\right)=\operatorname{deg}_{\text{in}}\left(v_{i}\right)\)。如果所有节点都是*衡的，则称图 \(G=(\mathcal{V},\mathcal{E},\mathcal{A})\) 为*衡图，或
\[\sum_{j} a_{i j}=\sum_{j} a_{j i}\quad\forall i.\qquad(22) \]定理 4：考虑一个具有固定拓扑的积分器网络 \(G=(\mathcal{V},\mathcal{E},\mathcal{A})\)，它是一个强连通的有向图。协议(A1)如果且仅如果 G 是*衡的，则全局渐*解决*均一致性问题。
证明：证明由下述定理 5 和 6 得出。□
备注 6：根据定理 4，如果一个图不是*衡的，那么协议(A1)不会全局解决所有初始条件下的*均一致性问题。这一论断与图 2 中给出的反例是一致的。
定理 5：考虑一个具有固定拓扑的积分器网络 \(G=(\mathcal{V},\mathcal{E},\mathcal{A})\)，它是一个强连通有向图。协议(A1)如果且仅如果 \(1^{T} L=0\)，则全局渐*解决*均一致性问题。
证明：根据定理 3，令 \(w_{r}=(1/\sqrt{n}) 1\)，我们得到
\[x^{*}=\lim_{t\rightarrow+\infty} x(t)=R x_{0}=w_{r}\left(w_{l}^{T} x_{0}\right)=\frac{1}{\sqrt{n}}\left(w_{l}^{T} x_{0}\right) 1. \]这意味着协议 1 以指数速度全局解决一致性问题，决策值为 \(\left(1/\sqrt{n}\right)\left(w_{l}^{T} x_{0}\right)\)。如果该决策值等于 \(\operatorname{Ave}\left(x_{0}\right),\forall x_{0}\in R^{n}\)，则必须满足 \((1/\sqrt{n}) w_{l}=1/\sqrt{n}\)，即 \(w_{l}=w_{r}=(1/\sqrt{n}) 1\)。这意味着 \(1\) 是 L 的左特征向量。为了证明反之，假设 \(1^{T} L=0\)。取 \(w_{r}=(1/\sqrt{n}) 1\)，\(w_{l}=\beta 1\)，其中 \(\beta\in R,\beta\neq 0\)。根据条件 \(w_{l}^{T} w_{r}=1\)，我们得到 \(\beta=(1/\sqrt{n})\)，因此 \(w_l=(1/\sqrt{n}) 1\)。这意味着对于每个节点的决策值为 \(1/\sqrt{n}\left(w_{l}^{T} x_{0}\right)=(1/ n) 1^{T} x_{0}\)。□
推论 2：假设定理 5 中的所有条件成立。假设 L 具有与 \(\lambda=0\) 对应的非负左特征向量 \(\gamma=\left(\gamma_{1},\ldots,\gamma_{n}\right)^{T}\)，且满足 \(\sum_{i}\gamma_{i}>0\)。那么，在达到一致后，群体决策值为
\[\alpha=\frac{\sum_i\gamma_i x_i(0)}{\sum_i\gamma_i}(23) \]即，决策值属于初始值的凸包。
证明：由于 \(\gamma^{T} L=0\)，我们有 \(\gamma^{T} u\equiv 0\) (因为 \(u=-L x)\)。因此，\(\beta=\gamma^{T} x\) 是不变量。假设图 G 不是*衡的，则会渐*达到一致。设 \(\alpha\) 为所有节点在达到一致后的决策值。由于 \(\gamma^{T} x^{*}=\gamma^{T} x(0)\) 的不变性，且 \(x^{*}=\alpha 1\)，因此我们得到
\[\left(\sum_i\gamma_i\right)\alpha=\gamma^T x(0) \]结果得证。
以下结果表明，如果一个代理使用了相对较小的更新速率(或步长)，则群体决策值将相对接* \(x_{i}^{*}\)。换句话说，代理 \(v_{i^{*}}\) 在领导-跟随架构中充当了领导者的角色。
推论 3（多速率积分器）：考虑一个具有节点动态的多速率积分器网络
\[\gamma_i\dot{x}_i=u_i\quad\gamma_i>0\quad\forall i\in\mathcal{I}。\qquad(24) \]假设网络具有固定拓扑 \(G=(\mathcal{V},\mathcal{E},\mathcal{A})\)，并且每个节点都应用协议(A1)。那么，将会全局渐*地达成一致，并且群体决策值为
\[\alpha=\frac{\sum_i\gamma_i x_i(0)}{\sum_i\gamma_i}.\qquad(25) \]证明：网络的动态遵循
\[D\dot{x}=-L x \]其中 \(D=\operatorname{diag}(\gamma)\) 是一个对角矩阵，其第 i 个对角元素为 \(\gamma_{i}>0\)。该方程可以重写为
\[\dot{x}=-\tilde{L} x \]其中 \(\tilde{L}=D^{-1} L=\operatorname{diag}\left(1/\gamma_{1},\ldots, 1/\gamma_{n}\right) L\)。注意，\(\tilde{L}\) 是有向图 \(\tilde{G}\) 的有效拉普拉斯矩阵，其邻接矩阵为 \(\tilde{A}=D^{-1}\mathcal{A}\)。要从 G 获取 \(\tilde{G}\)，需要将离开节点 \(v_{i}\) 的边权重除以 \(\gamma_{i}\)。显然，\(\gamma\) 是 \(\tilde{L}\) 的具有正元素的左特征向量。根据推论 2，决策值是初始值的加权*均，权重由 \(\gamma\) 指定。
备注 7：在文献[28]中讨论的离散时间模型和姿态对齐协议对应于方程(24)的协议(A1)的欧拉一阶*似，且在推论 3 中选择 \(\gamma_{i}=\operatorname{deg}_{\text{out}}\left(v_{i}\right)+1\)。在文献[1]中，拉普拉斯矩阵定义为 \(I-D^{-1}\mathcal{A}\)，在本文的背景下，相当于一个具有 \(\gamma_{i}=\operatorname{deg}_{\text{out}}(v_{i})\geq 0\) 的多速率积分器网络。文献[28]通过适当地为 \(\operatorname{deg}_{\text{out}}(v_{i})\) 增加一个正数，避免了 D 的奇异性。
任何无向图都是*衡的。此外，图 3 中显示的有向图都是*衡的。
定理 6：设 \(G=(\mathcal{V},\mathcal{E},\mathcal{A})\) 为一个具有邻接矩阵 \(\mathcal{A}=\left[a_{i j}\right]\) 的有向图。那么，以下所有陈述是等价的：
i) G 是*衡的。
ii) \(w_{l}=1\) 是与零特征值相关的 G 的拉普拉斯矩阵的左特征向量，即 \(1^{T} L=0\)。
iii) 对所有 \(x\in R^{n}\)，有 \(\sum_{i=1}^{n} u_{i}=0\)，其中 \(u_{i}=\sum_{v_{j}\in N_{i}} a_{i j}(x_{j}-x_{i})\)。
证明：我们证明 i) \(\Longleftrightarrow\) ii) 和 ii) \(\Longleftrightarrow\) iii)。
证明 i) \(\Longleftrightarrow\) ii)：我们有 \(\Delta_{i i}=\operatorname{deg}_{\text{out}}\left(v_i\right)\)，并且 \(\operatorname{deg}_{\text{in}}\left(v_{i}\right)=\sum_{j, j\neq i} a_{j i}\)，因此 L 的第 i 列和为零，或者
\[\sum_i l_{j i}=\sum_{i, j\neq i} l_{j i}+l_{i i}=-\operatorname{deg}_{\text{in}}\left(v_i\right)+\operatorname{deg}_{\text{out}}\left(v_i\right)=0 \]当且仅当 G 的节点 \(v_{i}\) 是*衡的。注意 L 的 i 列和等于行向量 \(1^{T} L\) 的 i 元素，因此 \(1^{T} L=0\) 当且仅当 G 的所有节点是*衡的，即 G 是*衡的。
证明 ii) \(\Longleftrightarrow\) iii)：由于 \(u=-L x\)，有 \(\left(\sum_{i} u_{i}=0,\forall x\right)\Leftrightarrow \left(1^{T} u=-\left(1^{T} L\right) x=0,\forall x\right)\Longleftrightarrow 1^{T} L=0\)。
注意在定理 6 中，图 G 不需要是连通的。
VIII. 协议性能与镜像图
在本节中，我们讨论具有*衡图的协议(A1)的性能问题。定理 6 的一个重要结果是，对于信息流*衡的网络，\(\alpha=\operatorname{Ave}(x)\) 是一个不变量。这对于任意有向图并不总是成立。\(\operatorname{Ave}(x)\) 的不变性允许根据以下方程分解 x：
\[x=\alpha 1+\delta \]其中 \(\alpha=\operatorname{Ave}(x)\)，\(\delta\in R^{n}\) 满足 \(\sum_{i}\delta_{i}=0\)。我们将 \(\delta\) 称为(群体)分歧向量。如果 G 是强连通的，则向量 \(\delta\) 与 \(1\) 正交，且属于一个 \((n-1)\) 维的子空间，该子空间称为 L 的分歧特征空间。此外，\(\delta\) 按照(群体)分歧动态演化：
\[\dot{\delta}=-L\delta。 \]定义有向图 G 的拉普拉斯分歧函数为
\[\Phi_G(x)=x^T L x \]其中 \(L=\mathcal{L}(G)\)。有向图的拉普拉斯分歧不一定是非负的。(16)中给出了一个具有不定符号拉普拉斯分歧的有向图的例子。
接下来我们证明，对于任何*衡的有向图 G，存在一个无向图 \(\hat{G}\)，其拉普拉斯分歧函数与 G 的拉普拉斯分歧函数相同。这证明了*衡图的拉普拉斯矩阵是正半定的。以下是该无向图的定义。
定义 2 (镜像图/操作)：设 \(G=(\mathcal{V},\mathcal{E},\mathcal{A})\) 为一个加权有向图。令 \(\tilde{\mathcal{E}}\) 为 G 的反向边集，通过反转 \(\mathcal{E}\) 中所有节点对的顺序得到。G 的镜像图记为 \(\hat{G}=\mathcal{M}(G)\)，其形式为 \(\hat{G}=(\mathcal{V},\hat{\mathcal{E}},\hat{\mathcal{A}})\)，具有与 G 相同的节点集，边集 \(\hat{\mathcal{E}}=\mathcal{E}\cup\tilde{\mathcal{E}}\)，对称的邻接矩阵 \(\hat{\mathcal{A}}=\left[\hat{a}_{i j}\right]\) 的元素为
\[\hat{a}_{i j}=\hat{a}_{j i}=\frac{a_{i j}+a_{j i}}{2}\geq 0.\qquad(29) \]以下结果表明，\(\mathcal{L}\) 和 Sym 在加权邻接矩阵上的操作是可交换的。
定理 7：设 G 为一个邻接矩阵 \(\mathcal{A}\) 的有向图，其拉普拉斯矩阵为 \(L=\mathcal{L}(G)\)。那么 \(L_{s}=\operatorname{Sym}(L)=\left(L+L^{T}\right)/ 2\) 是无向图 \(\hat{G}=\mathcal{M}(G)\) 的有效拉普拉斯矩阵，当且仅当 G 是*衡的，或者等价地，以下图示中的操作可交换：
\[\begin{array}{l}G\xrightarrow{\text{ adj}}\mathcal{A}\xrightarrow{\mathcal{L}} L\\ \mathcal{M}\downarrow\quad\operatorname{Sym}\downarrow\quad\operatorname{Sym}\downarrow。\\ \hat{G}\underset{\text{ adj}}{\longrightarrow}\hat{\mathcal{A}}\underset{\mathcal{L}}{\longrightarrow}\hat{L}\\ \end{array} \]此外，如果 G 是*衡的，则 G 和 \(\hat{G}\) 的拉普拉斯分歧函数相等。
证明：我们知道，G 是*衡的当且仅当 \(1^{T} L=0\)。由于 \(L 1=0\)，所以我们有 \(1^{T} L=0 \Longleftrightarrow 1/2\left(L+L^{T}\right) 1=0\)。因此，G 是*衡的当且仅当 \(L_{s}\) 具有一个与 \(\lambda=0\) 对应的右特征向量 1，即 \(L_{s}\) 是一个有效的拉普拉斯矩阵。现在，我们证明 \(L_{s}=\mathcal{L}(\hat{G})\)。为此，我们逐元素计算 \(\hat{\Delta}\)，得到
\[\hat{\Delta}_{i i}=\sum_j\frac{a_{i j}+a_{j i}}{2}=\frac{1}{2}\left(\operatorname{deg}_{\text{out}}\left(v_i\right)+\operatorname{deg}_{\text{in}}\left(v_i\right)\right)=\operatorname{deg}_{\text{out}}\left(v_i\right)=\Delta_{i i}。 \]因此，\(\hat{\Delta}=\Delta\)。另一方面，我们有
\[L_s=\frac{1}{2}\left(L+L^T\right)=\Delta-\frac{A+A^T}{2}=\hat{\Delta}-\hat{A}=\hat{L}=\mathcal{L}(\hat{G})。 \]最后一部分简单地归因于 \(\hat{L}\) 等于 L 的对称部分，且 \(x^{T}\left(L-L^{T}\right) x\equiv 0\)。\(\square\)
符号：为了简化符号，在代数图论的上下文中，\(\lambda_{k}(G)\) 用来表示 \(\lambda_{k}(\mathcal{L}(G))\)。
现在我们已经准备好提出关于协议(A1)性能的主要结果，该结果基于到达一致的最坏情况下的速度。
定理 8 (一致性的性能)：考虑一个具有固定拓扑的积分器网络 G，它是一个强连通的有向图。给定协议(A1)，以下结论成立：
i) 作为(27)中分歧动态解的群体分歧向量 \(\delta\) 全局渐*消失，其速度等于 \(\kappa=\lambda_{2}(\check{G})\)，即由 G 诱导的镜像图的 Fiedler 特征值。
ii) 以下*滑的、正定的、适当的函数
\[V(\delta)=\frac{1}{2}\|\delta\|^2 \]是分歧动态的有效 Lyapunov 函数。
证明：我们有
\[\dot{V}=\delta^T L\delta=-\delta^T L_s\delta=-\delta^T\hat{L}\delta\leq-\lambda_2(\hat{G})\|\delta\|^2=-2\kappa V(\delta)<0\quad\forall\delta\neq 0。 \]这证明了 \(V(\delta)\) 是群体分歧动态的有效 Lyapunov 函数。此外，\(\delta(t)\) 以速度 \(\kappa=\lambda_{2}(\hat{G})\) 全局渐*消失，随着 \(t\rightarrow+\infty\)，\(\delta(t)\) 消失的速度为 \(\kappa\)。最后，\(L_s=\hat{L}\) 是无向图 \(\hat{G}\) 的有效拉普拉斯矩阵(即 G 的镜像图)，这是基于定理 7 的事实。此外，不等式
\[\delta^T\hat{L}\delta\geq\lambda_2(\hat{G})\|\delta\|^2\quad\forall\delta: 1^T\delta=0 \]由(17)得出。
众所周知，无向图的 Fiedler 特征值的一个观察是，对于密集图，\(\lambda_{2}\) 相对较大，而对于稀疏图，\(\lambda_{2}\) 相对较小[31]。因此，\(\lambda_{2}\) 被称为图的代数连通性。根据这一观察结果，从定理 8 可以得出，具有密集互连的网络比连接但稀疏的网络更快地解决一致性问题。作为一个特例，长度为 n 的循环图在 n 个节点上形成了一个*衡的有向图，并解决了一致性问题。然而，这种解决一致性问题的方法相对较慢。
IX. 切换拓扑的网络
考虑一个移动代理的网络，它们相互通信，需要就某个感兴趣的目标达成一致或实现同步。由于网络中的节点是移动的，因此可以很容易地想象，一些现有的通信链路可能由于两个代理之间存在障碍而失效。反过来，当代理在彼此之间的有效探测范围内时，可能会形成新的链路。这意味着，在网络的拓扑 G 中，某些边被添加或移除。在这里，我们希望研究在具有切换拓扑的网络中是否仍然能够达成一致。
考虑一个具有连续状态 \(x\in R^{n}\) 和离散状态 G 的混合系统，该离散状态属于有限的有向图集合 \(\Gamma\)，其中 G 是一个 n 阶强连通和*衡的有向图。这个集合可以通过以下公式进行分析表达：
\[\Gamma_n=\left\{G=(\mathcal{V},\mathcal{E},\mathcal{A}):\operatorname{rank}(\mathcal{L}(G))=n-1, 1^T\mathcal{L}(G)=0\right\}。 \]给定协议(A1)，系统的连续状态按照以下动态演化：
\[\|\delta(t)\|\leq\|\delta(0)\|\exp(-\kappa t).\qquad(31) \]\[\dot{x}(t)=-\mathcal{L}\left(G_k\right) x(t)\quad k=s(t), G_k\in\Gamma_n\quad(35) \]其中，\(s(t): R_{\geq 0}\rightarrow\mathcal{I}_{\Gamma_{n}}\) 是一个切换信号，\(\mathcal{I}_{\Gamma_{n}}\subset N\) 是与 \(\Gamma_{n}\) 元素相关联的索引集。由于在 n 阶图中最多有 \(n(n-1)\) 条有向边，集合 \(\Gamma_{n}\) 是有限的。
我们分析的关键是移动网络中的*均一致性，它取决于(32)中分歧函数的基本性质。该分歧函数与网络拓扑 G 无关。此外，对于所有 \(k\in\mathcal{I}_{\Gamma_{n}}\)，有向图 \(G_k\) 的拉普拉斯矩阵是正半定的，因为 \(G_k\) 是*衡的。因此，\(V(\delta)\) 沿着切换系统的解单调递减。由于 \(V(\delta)\) 的这种性质，它成为了切换系统(35)的稳定性分析中的一个公共 Lyapunov 函数。
定理 9：对于任意切换信号 \(s(\cdot)\)，切换系统(35)的解全局渐*收敛到 \(\operatorname{Ave}(x(0))\) (即，达成*均一致性)。此外，以下*滑的、正定的、适当的函数：
\[V(\delta)=\frac{1}{2}\|\delta\|^{2} \]是由
\[\dot{\delta}(t)=-\mathcal{L}\left(G_k\right)\delta(t)\quad k=s(t), G_k\in\Gamma_n。\qquad(37) \]给出的分歧动态的有效公共 Lyapunov 函数。此外，\(\|\delta(t)\|\leq\|\delta(0)\|\exp\left(-\kappa^* t\right)\)，即分歧向量 \(\delta\) 以最小速率
\[\kappa^*=\min_{G\in\Gamma_n}\lambda_2(\mathcal{L}(\hat{G}))。\qquad(38) \]消失。
证明：由于对于所有 k，\(G_k\) 是*衡的，并且 \(u=-\mathcal{L}\left(G_{k}\right) x\)，我们有 \(1^{T} u=-\left(1^{T}\mathcal{L}\left(G_{k}\right)\right) x\equiv 0\)。因此，\(\alpha=\operatorname{Ave}(x)\) 是一个不变量。这允许我们将 x 分解为 \(x=\alpha 1+\delta\)。因此，由(35)诱导的切换系统的分歧动态变为(37)的形式。计算 \(\dot{V}\)，我们得到
\[\dot{V}=-\delta^{T}\mathcal{L}\left(G_{k}\right)\delta=-\delta^{T}\mathcal{L}\left(\hat{G}_{k}\right)\delta\leq-\lambda_{2}\left(\mathcal{L}\left(\hat{G}_{k}\right)\right)\|\delta\|^{2}\leq-2\kappa^{*} V(\delta)<0\quad\forall\delta\neq 0。 \]这保证了 \(V(\delta)\) 是切换系统(37)的有效公共 Lyapunov 函数。此外，我们有
\[V(\delta(t))\leq V(\delta(0))\exp\left(-2\kappa^{*} t\right)\Rightarrow\|\delta(t)\|\leq\|\delta(0)\|\exp\left(-\kappa^{*} t\right) \]并且分歧向量 \(\delta(t)\) 以速率 \(\kappa^{*}>0\) 全局渐*消失，随着 \(t\rightarrow+\infty\)。由于 \(\Gamma_{n}\) 是有限集，(38) 中的最小值总是存在并且可以达到。\(\square\)
X. 具有通信时延的网络
考虑一个具有稳定拓扑 \(G=(\mathcal{V},\mathcal{E},\mathcal{A})\) 的连续时间积分器网络，其中节点 \(v_{i}\) 的状态通过一个带有时延 \(\tau_{i j}>0\) 的通信信道 \(e_{i j}\) 传递到节点 \(v_{j}\)。与边 \(e_{i j}\) 相关的传递函数可以用拉普拉斯域表示为：
\[h_{i j}(s)=e^{-\tau_{i j} s} \]给定协议(A2)，网络的动态可以表示为：
\[\dot{x}_{i}(t)=\sum_{v_{j}\in N_{i}} a_{i j}\left[x_{j}\left(t-\tau_{i j}\right)-x_{i}\left(t-\tau_{i j}\right)\right]。\quad(40) \]在对(40)的两边进行拉普拉斯变换后，我们得到
\[s X_i(s)-x_i(0)=\sum_{j\in N_i} a_{i j} h_{i j}(s)\left(X_j(s)-X_i(s)\right)\quad(41) \]其中 \(X_{i}(s)\) 表示 \(x_{i}(t)\) 的拉普拉斯变换。
该方程可以简化为以下紧凑形式：
\[X(s)=(s I + L(s))^{-1} x(0)\qquad(42) \]其中，\(L(s)\) 是一个图的拉普拉斯矩阵，其邻接矩阵为 \(\mathcal{A}(s)=\left[a_{i j} h_{i j}(s)\right]\)。链路 \(e_{i j}\) 的任何线性滤波效应都可以整合到该链路的传递函数 \(h_{i j}(s)\) 中。对于带有通信时延的积分器网络，协议(A2)的收敛性分析简化为多输入多输出(MIMO)系统的稳定性分析，其传递函数为：
\[G(s) = (s I + L(s))^{-1} \qquad(43) \]为了分析具有通信时延的积分器网络的拉普拉斯矩阵和协议(A2)的收敛特性，我们首先考虑所有链路的时延都相等的最简单情形，并且网络拓扑是固定且无向的。立刻可以得出 \(\sum_{i} u_{i} \equiv 0\)，因此 \(\alpha = \operatorname{Ave}(x(t))\) 是一个不变量。此外，我们有：
\[L(s) = e^{-\tau s} L \]其中 \(L = \mathcal{L}(G)\)。接下来，我们提出在具有通信时延和固定拓扑的网络中解决*均一致性问题的主要结果[29]：
定理 10：考虑一个具有相同通信时延 \(\tau > 0\) 的积分器网络，假设网络拓扑 G 是固定的、无向的、连通的。如果协议(A2)中的时延 \(\tau_{i j} = \tau\)，则协议(A2)全局渐*地解决了*均一致性问题，当且仅当以下等价条件之一成立：
-
\(\tau \in \left(0, \tau^*\right)\)，其中 \(\tau^* = \frac{\pi}{2\lambda_n}\)，\(\lambda_n = \lambda_{\max}(L)\)。
-
\(\Gamma(s) = \frac{e^{-\tau s}}{s}\) 的奈奎斯特图(Nyquist plot)在 \(-\frac{1}{\lambda_k}\) (对所有 \(k > 1\))附*无绕行。
此外，当 \(\tau = \tau^{*}\) 时，系统具有频率为 \(\omega = \lambda_n\) 的全局渐*同步解。
证明：见附录。
A. 性能与鲁棒性的权衡
根据定理 10 的部分结论可以得出，网络中可接受的时延上限与最大拉普拉斯特征值 \(\lambda_n\) 反比，即信息流的最大特征值 \(\lambda_n\)。根据 Gergorin 定理，我们知道 \(\lambda_n \leq 2 d_{\max}(G)\)，其中 \(d_{\max}(G)\) 是图 G 的最大节点出度。因此，协议(A2)收敛的充分条件是：
\[\tau \leq \frac{\pi}{4 d_{\max}(G)} \qquad(44) \]这意味着节点出度相对较高的网络不能容忍相对较长的通信时延。另一方面，令 \(\tilde{\mathcal{A}} = k\mathcal{A}\)，其中 \(k > 0\)，为 \(\tilde{G}\) 的邻接矩阵。记 \(\tilde{G}\) 的拉普拉斯矩阵为 \(\tilde{L}\)，并注意 \(\lambda_n(\tilde{L}) = k\lambda_n(L)\)。因此，对于任意时延 \(\tau > 0\)，总是存在一个足够小的 \(k > 0\) 使得 \(\tau < \frac{\pi}{2k\lambda_n}\)。结果表明，通过缩小有向图的权重，可以容忍任意大的时延 \(\tau > 0\)。然而，权衡在于协议的收敛速度(即 \(\lambda_2\))以 \(1/k > 0\) 的因子下降。换句话说，在协议的鲁棒性和性能之间存在权衡。
B. 高性能与低通信成本之间的权衡
对于具有 0-1 权重的无向图，通信成本相对较高的图通常具有较高的代数连通性 \(\lambda_2\) (例如，完全图)。相反，通信成本较低的图通常具有较低的 \(\lambda_2\) (例如，循环图)。这意味着在实现高性能和保持低通信成本之间存在另一种权衡。第二种权衡是如何在高性能和低通信成本之间取得*衡。
上述两种权衡的存在表明，可以提出并解决一个网络设计问题，该问题试图找到一个具有受限通信成本 \(C\) 的邻接矩阵 \(\mathcal{A}\)，并在性能和鲁棒性之间实现*衡的协同作用(见备注 2)。
XI. 仿真结果
图4显示了四种不同的网络，每个网络都有 \(n=10\) 个节点。该图中的所有有向图的权重都是 0-1，并且它们都是强连通和*衡的。在图5(a)中，展示了一个有限自动机，其状态集为 \(\left\{G_{a}, G_{b}, G_{c}, G_{d}\right\}\)，代表一个具有切换拓扑的网络的离散状态。
该混合系统从离散状态 \(G_{b}\) 开始，并且每隔 \(T=1\) 秒根据图 5(a) 中的状态机切换到下一个状态。图 5(b) 显示了系统的连续时间状态轨迹和群体分歧向量的二范数 \(||\delta||_2\)。显然，群体分歧是单调递减的，可以观察到系统最终渐*地达成*均一致性。此外，群体分歧以指数速度消失。
对于满足 \(\operatorname{Ave}(x(0))=0\) 的随机初始状态，图 6 显示了系统的状态轨迹和分歧函数 \(||\delta||_2\) 随时间的变化。很明显，随着图的边数增加，代数连通性(或 \(\lambda_2\)) 增加，状态轨迹的收敛时间减少。
长度为 10 的有向循环图 \(G_a\) 的超调现象最为明显。在所有四种情况下，系统都渐*地达成一致性，并且性能随着 \(\lambda_2(\hat{G}_k)\) 的增加而提高。
接下来，我们展示了具有通信时延的网络在*均一致性问题上的仿真结果，网络的拓扑如图 3(d) 所示。图 7 展示了具有通信时延 \(\tau\) 的网络的状态轨迹，分别对应 \(\tau=0, 0.5\tau_{\max}, 0.7\tau_{\max}, \tau_{\max}\)，其中 \(\tau_{\max}=\frac{\pi}{2\lambda_{\max}(G_e)}=0.269\)。在该仿真中，初始状态是均值为零的一组随机数。显然，对于 \(\tau < \tau_{\max}\) 的情况(即图 7(a)、(b) 和 (c))，系统达成一致性。而在 \(\tau = \tau_{\max}\) 的情况下，系统表现出同步振荡，如图 7(d) 所示。为了模拟时延，我们使用了二阶 Pade *似。
XII. 结论
本文提供了具有固定或切换拓扑的有向信息流积分器网络的一致性协议的收敛性分析。我们的分析依赖于代数图论、矩阵理论和控制理论的多种工具。我们建立了线性一致性协议的性能与拉普拉斯矩阵 Fiedler 特征值(即镜像图的代数连通性)之间的联系，这扩展了无向图代数连通性的概念，适用于*衡的有向图。
我们引入了一个简单的分歧函数作为群体分歧动态的 Lyapunov 函数。该函数随后用于为切换拓扑的网络中的一致性协议提供公共 Lyapunov 函数，以进行收敛性分析。我们还展示了一个交换图，表明在*衡图的邻接矩阵上，拉普拉斯矩阵与对称操作的可交换性。*衡图在解决*均一致性问题上起到了至关重要的作用。
对于具有固定拓扑的无向网络，我们提供了在存在通信时延的情况下达成*均一致性问题的充分必要条件。结果表明，线性一致性协议的鲁棒性与时延的容忍度之间存在权衡。此外，保持低通信成本与实现高性能之间也存在第二种权衡。本文通过广泛的仿真结果展示了理论结果和分析工具的有效性。
附录：部分定理的证明
定理 1 的证明：为了证明该结果，我们展示了如果一个 n 阶有向图是强连通的，则其拉普拉斯矩阵的零空间是 \(R^n\) 的一维子空间。
定义 \(\phi_{i j}(z)=a_{i j} z\) 对所有 \(e_{i j} \in \mathcal{E}\)。显然，如果对所有 \(e_{i j} \in \mathcal{E}\) 满足 \(x_i = x_j\)，则 \(u=0\)。现在我们证明反过来：如果 \(u=0\)，则所有节点达成一致。如果所有节点的值相等，结论成立。假设存在一个节点 \(v_{i^*}\)，称之为最大领导者，使得 \(x_{i^*} \geq x_j\) 对所有 \(j \neq i^*\) 成立，即 \(i^*\) 是
标签：有向图,共识,right,delta,mathcal,operatorname,left From： https://www.cnblogs.com/zhangxianrong/p/18402276