关联矩阵、度矩阵与拉普拉斯矩阵

邻接矩阵描述“节点–节点”关系。另外几个矩阵在网络动力学、谱方法和社团发现中同样基础。

关联矩阵

关联矩阵与二分图、超图的关系是：把每条边看成一个“边节点”，$B$ 就是“节点–边”二分图的双邻接矩阵；超图的关联矩阵是允许一列有两个以上非零元的推广。对上例（边按 a–b、a–c、b–c、c–d 排列）：

$$B=\begin{pmatrix}1&1&0&0\\1&0&1&0\\0&1&1&1\\0&0&0&1\end{pmatrix},\qquad BB^\top=\begin{pmatrix}2&1&1&0\\1&2&1&0\\1&1&3&1\\0&0&1&1\end{pmatrix}=D+A.$$

度矩阵与拉普拉斯矩阵

上例的拉普拉斯矩阵为

$$L=\begin{pmatrix}2&-1&-1&0\\-1&2&-1&0\\-1&-1&3&-1\\0&0&-1&1\end{pmatrix}.$$

拉普拉斯矩阵的基本性质（证明见数学推导与算法）：

1. 每行之和为 0，所以全 1 向量 $\mathbf 1$ 是特征值 0 的特征向量；
2. $L=\nabla\nabla^\top$（与边方向的选取无关），于是对任意向量 $\mathbf x$， $$\mathbf x^\top L\mathbf x=\sum_{\{i,j\}\in E}(x_i-x_j)^2\ \ge 0,$$ $L$ 是半正定矩阵，特征值 $0=\mu_1\le\mu_2\le\cdots\le\mu_N$；
3. 特征值 0 的重数等于连通分支数。因此 $\mu_2>0$ 当且仅当图连通；$\mu_2$ 称为代数连通度（Fiedler 值），越大越“难以切开”；
4. $\sum_i\mu_i=\operatorname{tr}L=\sum_i k_i=2M$。

手算算例。上例的特征值是 $0,1,3,4$。可以逐个验证：

• $\mu=0$：$L\mathbf 1=\mathbf 0$；
• $\mu=3$：取 $\mathbf x=(1,-1,0,0)^\top$（a 与 b 反相，c、d 为 0），$L\mathbf x=(3,-3,0,0)^\top=3\mathbf x$；
• 迹检验：$0+1+3+4=8=2M$。

$\mu_2=1>0$，说明图连通；对应的 Fiedler 向量把 d 与其他节点分在符号相反的两侧——切断 c–d 这一条边就能把图分开，这正是谱划分的思想（见社团结构与社区发现）。

为什么拉普拉斯矩阵重要

二次型 $\mathbf x^\top L\mathbf x$ 衡量信号 $\mathbf x$ 在网络上的“不平滑程度”：相邻节点的值越接近，它越小。由此引出几类核心模型：

• 扩散：节点上的量沿边从高处流向低处，$\dot{\mathbf x}=-\beta L\mathbf x$；解为 $\mathbf x(t)=e^{-\beta Lt}\mathbf x(0)$。Raj 等（2012，Neuron）用结构连接组的拉普拉斯扩散模型描述痴呆中病理沿白质网络的扩散，模型预测的萎缩空间分布与患者影像有显著对应。
• 共识与同步：$L$ 的谱决定共识速度和相同振荡器的可同步性（见同步与协同动力学）。
• 网络传播（network propagation）：在互作组上从已知疾病基因出发做扩散或带重启随机游走，用于候选基因排序，Cowen 等（2017）的综述称之为遗传关联的“放大器”。

归一化拉普拉斯与转移矩阵

度高度异质时，常用两种归一化形式：

$$\mathcal L = I - D^{-1/2}AD^{-1/2},\qquad P = D^{-1}A .$$

$P$ 是简单随机游走的转移矩阵：$P_{ij}=A_{ij}/k_i$ 是从 $i$ 一步走到邻居 $j$ 的概率，每行和为 1。$\mathcal L$ 的特征值落在 $[0,2]$ 区间内，便于比较不同规模的网络；上例中为 $0,\ 0.771,\ 1.5,\ 1.729$。度为 0 的孤立节点会使 $D^{-1}$ 无定义，计算前要先移除或单独处理。

有向图的拉普拉斯矩阵有多种不对称的定义（按出度或入度），性质也不再像无向情形那样整齐；使用前要确认软件采用的是哪一种。

关联矩阵、拉普拉斯矩阵及上述恒等式与特征值的数值核对见代码示例“关联矩阵、度矩阵与拉普拉斯矩阵”。