图论与网络基础

1. 图的表示

图$G=(V,E,A)$表示一个图三元组，其中V={v1,...,vn}V=\{v_1,...,v_n\}V={v1​,...,vn​}表示节点的集合，$E\subseteq V\times V$是有向边的集合，$A=(a_{ij}{)}_{n\times n}$ 是加权邻接矩阵，用来量化节点之间的关系。$a_{ij}>0$表示节点$v_j$接受到$v_i$的信息的大小，也就是有一个边从$v_i$出发链接到$v_j$（也有部分文献是反过来写的）。

2. 有向图和无向图

如果对于图中任意两个节点$v_i$和$v_j$ ，若存在连接关系就有$a_{ij}=a_{ji}>0$ ，否则$a_{ij}=a_{ji}=0$, ($i\ne j$；$i,j=1,2,\dots ,n$），这样的图就是无向图；若从节点$v_i$到$v_j$ 存在连接时$a_{ij}>0$ ，否则$a_{ij}=0$（$i\ne j$；$i,j=1,2,\dots ,n$），则是有向图。可以看出，无向图其实是有向图的一种特殊情况。

3. 连通性

在图论中，从节点$v_j$到$v_i$ 的有向（或无向）路径是有向（或无向）网络中由不同节点$v_{ik}$ （$k=1,2,\dots ,l$）组成的边序列$(v_i,v_{i1}),(v_{i1},v_{i2}),\dots ,(v_{il},v_j)$。如果一个有向（或无向）网络$G$中，任意两个不同节点$v_i$和$v_j$ 之间都存在从$v_i$到$v_j$ 的有向（或无向）路径，那么这个网络就是强连通（或连通）的。

4. 拉普拉斯矩阵

在图论和机器学习（尤其是图神经网络）的研究中，拉普拉斯矩阵（Laplacian Matrix）是连接图结构与代数运算的核心工具。对于矩阵$A$，其队形的拉普拉斯矩阵 L 是 $n\times n$的实矩阵，记为 $L=(l_{ij})\in {\mathbb{R}}^{n\times n}$，它的元素定义遵循两个规则：当 $i\ne j$（即非对角元素）时，$l_{ij}=-a_{ij}$，直接取邻接矩阵对应元素的负值；当 $i=j$（即对角元素）时，$l_{ii}={\sum }_{j=1,j\ne i}^n{a}_{ij}$，也就是邻接矩阵中第 i 行所有非对角元素的和，这个值其实就是节点 i 的 “度”（Degree）。从这个定义能直接推导出拉普拉斯矩阵的一个关键性质：它的每一行元素之和都为 0，即 ${\sum }_{j=1}^N{l}_{ij}=0$。
举个简单的例子帮助理解：假设一个包含 3 个节点的无向图，节点 1 与 2互相 相连、节点 1 与 3 互相相连，邻接矩阵 $$A=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 0\\ 1& 0& 0\end{array}\right)$$按照定义计算，拉普拉斯矩阵 $$L=\left(\begin{array}{ccc}2& -1& -1\\ -1& 1& 0\\ -1& 0& 1\end{array}\right)$$可以看到每一行元素相加都等于 0，完全符合定义要求。

5. 不可约矩阵

一个 $n\times n$ 的实矩阵 A（通常讨论非负矩阵），若不存在置换矩阵 P，使得 $P^{T}AP$ 化为如下分块上三角形式：$$P^{T}AP=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ 0& A_{22}\end{array}\right)$$其中 $A_{11}$、$A_{22}$ 是阶数非零的方阵，则称 A 为不可约矩阵；反之则为可约矩阵。

6.树

若一个有向网络忽略边的方向后，其底层结构是一棵树，则该网络称为有向树（directed tree）。有向根树（directed rooted tree） 是一种有向网络，它至少存在一个根节点r，且满足：对于除 $r$ 之外的任意节点 $v$，都存在从$r$到$v$的唯一有向路径。网络 $G$ 的有向生成树（directed spanning tree） 是一棵有向根树，它包 $G$ 中的所有节点和部分边。
不难看出，有向生成树是强链接图（强连通图）的 “必要非充分条件”，即强链接图一定包含有向生成树，但存在有向生成树的图不一定是强链接图。同时，若有向图 $G$ 是强连通图（强链接），则 $G$ 中必然存在以任意节点为根的有向生成树（出树或入树）。

图论代数

引理 1 一个矩阵A是不可约的，当且仅当其对应的图G是强链接的。

R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory. Cambridge, U.K.: Cambridge Univ. Press, 1991.

引理 2 矩阵A是不可约的，其对应的拉普拉斯矩阵$L$也是不可约的。
引理 3 若拉普拉斯矩阵$L$是不可约的，则有以下性质成立：

• $L\cdot 1_n=0$（其中$1_n$是元素全为 1 的N维列向量）；
• 存在正向量$\mathbf{\xi }=({\xi }_1,{\xi }_2,\dots ,{\xi }_n{)}^T$，使得${\mathbf{\xi }}^T\cdot L=0$；
• 存在正定对角矩阵$\Xi =\text{diag}({\xi }_1,{\xi }_2,\dots ,{\xi }_n)$，使得$\tilde{L}=\frac{1}{2}\left(\Xi L+L^T\Xi \right)$为对称矩阵，且对于所有$i=1,2,\dots ,N$，均满足：${\sum }_{j=1}^n{\tilde{L}}_{ij}={\sum }_{j=1}^n{\tilde{L}}_{ji}=0$

W. Yu, G. Chen, M. Cao, and J. Kurths, “Second-order consensus for multiagent systemsWith directed topologies and nonlinear dynamics,” IEEE Transactions on Systems Man & Cybernetics Part B: Cybernetics, vol. 40, no. 3, pp. 881-891, June 2010.

这里给个例子给大家直观体现引理3：
（1）邻接矩阵A（非对称）$$A=\left(\begin{array}{cccc}0& 2& 3& 0\\ 0& 0& 0& 1\\ 0& 4& 0& 0\\ 5& 0& 0& 0\end{array}\right)$$
（2）不可约拉普拉斯矩阵L对角元$l_{ii}={\sum }_{j\ne i}{a}_{ij}$（节点出度和）：$l_{11}=2+3=5$，$l_{22}=1$，$l_{33}=4$，$l_{44}=5$非对角元$l_{ij}=-a_{ij}$（$i\ne j$）$$L=\left(\begin{array}{cccc}5& -2& -3& 0\\ 0& 1& 0& -1\\ 0& -4& 4& 0\\ -5& 0& 0& 5\end{array}\right)$$
性质 1：验证不可约拉普拉斯矩阵的性质性质 1：$L\cdot 1_4=0$, $1_4=(1,1,1,1{)}^T$，计算：$$L\cdot 1_4=\left(\begin{array}{c}5-2-3+0\\ 0+1+0-1\\ 0-4+4+0\\ -5+0+0+5\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\\ 0\end{array}\right)=0$$成立。
性质 2：存在正向量$\mathbf{\xi }=({\xi }_1,{\xi }_2,{\xi }_3,{\xi }_4{)}^T$，使得${\mathbf{\xi }}^{T}L=0$解方程组${\mathbf{\xi }}^{T}L=(0,0,0,0)$：$$\{\begin{array}{l}5{\xi }_1-5{\xi }_4=0\\ -2{\xi }_1+{\xi }_2-4{\xi }_3=0\\ -3{\xi }_1+4{\xi }_3=0\\ -{\xi }_2+5{\xi }_4=0\end{array}$$
取${\xi }_1=4/31$（任意正数），解得：正向量$\mathbf{\xi }=(4/31,20/31,3/31,4/31{)}^T$，验证：$1/31\cdot (4,20,3,4)\cdot L=(0,0,0,0)$成立。
性质 3：正定对角矩阵$\Xi =1/31\cdot \text{diag}(4,20,3,4)$对角元均为正数，故正定。$\tilde{L}=\frac{1}{2}(\Xi L+L^T\Xi )$是对称矩阵，且行 / 列和为 0（1）计算$\Xi L$与$L^T\Xi$, $$\Xi L=\frac{1}{31}\cdot \left(\begin{array}{cccc}20& -8& -12& 0\\ 0& 20& 0& -20\\ 0& -12& 12& 0\\ -20& 0& 0& 20\end{array}\right),L^T\Xi =\frac{1}{31}\cdot \left(\begin{array}{cccc}20& 0& 0& -20\\ -8& 20& -12& 0\\ -12& 0& 12& 0\\ 0& -20& 0& 20\end{array}\right)$$
（2）对称矩阵$\tilde{L}$$$\tilde{L}=\frac{1}{2}(\Xi L+L^T\Xi )=\frac{1}{62}\left(\begin{array}{cccc}20& -4& -6& -10\\ -4& 20& -6& -10\\ -6& -6& 12& 0\\ -10& -10& 0& 20\end{array}\right)$$
对称成立且行 / 列和为 0。

未完待续