邻接矩阵

计算机里最常用的表示是邻接矩阵（adjacency matrix）$A$，一个 $N \times N$ 的矩阵：

$$A_{ij} = \begin{cases} 1, & \text{节点 } i \text{ 与 } j \text{ 之间有边} \\ 0, & \text{否则} \end{cases}$$

加权图中 $A_{ij}$ 取边权 $w_{ij}$；有向图中本站约定 $A_{ij}=1$ 表示存在 $i \to j$ 的边（行是起点，列是终点），这也是 NetworkX 的 to_numpy_array 等多数软件采用的约定。但 Barabási《Network Science》和 Newman《Networks》采用相反的约定：$A_{ij}=1$ 表示 $j\to i$。两种约定下入度、出度分别对应“行和”与“列和”的位置正好相反，读文献和换软件时要先确认。

例：4 个蛋白 a、b、c、d，相互作用为 a–b、a–c、b–c、c–d。

$$A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$

从这个矩阵可以直接读出几条性质：

• 无向图的邻接矩阵是对称的：$A = A^\top$；简单图的对角线全为 0；
• 节点 $i$ 的度（degree，连接的边数）是第 $i$ 行之和：$k_i = \sum_j A_{ij}$。上例中 $k_c = 3$；
• 所有节点的度之和等于边数的两倍：$\sum_i k_i = 2M$（每条边被两个端点各数一次）。上例 $2+2+3+1 = 8 = 2 \times 4$；
• 矩阵中非零元素的个数是 $2M$（无向）或 $M$（有向）。

度、平均度与密度的系统讨论见网络结构指标与随机图。

矩阵乘方与游走计数

游走（walk）是一串相继相邻的节点，允许重复经过节点和边；其长度是经过的边数。邻接矩阵最有用的代数性质是：

$$\big(A^r\big)_{ij} = \text{从 } i \text{ 到 } j \text{ 的长度为 } r \text{ 的游走条数}.$$

对上例，

$$A^2=\begin{pmatrix}2&1&1&1\\1&2&1&1\\1&1&3&0\\1&1&0&1\end{pmatrix},\qquad A^3=\begin{pmatrix}2&3&4&1\\3&2&4&1\\4&4&2&3\\1&1&3&0\end{pmatrix}.$$

• $A^2$ 的对角元等于度（从 $i$ 出发走两步回到 $i$，只能是“去一个邻居再回来”）；非对角元 $(A^2)_{ij}$ 是 $i$ 与 $j$ 的共同邻居数，例如 a 与 d 的共同邻居只有 c，所以 $(A^2)_{ad}=1$。共同邻居数是链路预测和“基因功能相似性”的最简单指标。
• $A^3$ 的对角元 $(A^3)_{ii}$ 是经过 $i$ 的三角形数的 2 倍（两个方向各走一次）。全图三角形数为 $\operatorname{tr}(A^3)/6=(2+2+2+0)/6=1$，正是 a–b–c 那个三角形。三角形计数是聚集系数的基础（见网络结构指标与随机图）。
• 两节点间的距离（最短路径长度）是使 $(A^r)_{ij}>0$ 的最小 $r$。这在理论上优雅，但对大网络应使用广度优先搜索（见网络结构指标与随机图）。

加权、自环与有向情形的约定

• 加权网络的 $(W^r)_{ij}$ 是所有长度为 $r$ 的游走上边权乘积之和，不再是计数；用它定义的指标（如通信性 communicability）对权重的尺度敏感。
• 无向图中一个自环在 Newman 的约定下记为 $A_{ii}=2$（因为它有两个端点都落在 $i$ 上），从而保持“度 = 行和”与握手定理；NetworkX 中自环在度中同样计 2，但邻接矩阵中存为 1。不同软件对自环的处理不同，是结果不一致的常见来源。
• 有向图中出度、入度分别是行和与列和（本站约定）；$(A^r)_{ij}$ 计数的是沿箭头方向的有向游走。

本专题页面的邻接矩阵演示可以点击添加或删除边，观察图、邻接矩阵与度序列的联动。