关于图与矩阵的关系
邻接矩阵是用矩阵表示图的一种方法。 对于n个节点的图，邻接矩阵是n×n的方阵， 元素aᵢⱼ表示节点i和节点j之间是否存在边（以及边的权重）。
这种表示方法架起了图论与线性代数的桥梁， 使我们可以用矩阵运算来解决图论问题， 也可以将矩阵数据看作图来分析。
✦
18.1
无向图到邻接矩阵
对称矩阵表示无向连接
对于无向图，如果节点i和节点j之间存在边， 则邻接矩阵中aᵢⱼ = aⱼᵢ = 1（或边的权重）。 无向图的邻接矩阵是对称矩阵。
📊 基本定义
• 节点i到j有边：aᵢⱼ = 1
• 节点i到j无边：aᵢⱼ = 0
• 无向图：A = Aᵀ（对称）
• 有向图：A ≠ Aᵀ（非对称）
🎯 矩阵特性
• 列和：节点入度
• 行和：节点出度
• 主对角线：自环
• 元素值：边的权重
💻 图↔矩阵
nx.adjacency_matrix(G)
nx.to_numpy_matrix(G)
nx.Graph(A)
💡
重要性质
• 对称矩阵：无向图的邻接矩阵是对称矩阵， 这意味着可以进行特征值分解和谱分析
• 稀疏矩阵：真实网络的邻接矩阵通常很稀疏， 大部分元素为0
• 完全图：邻接矩阵可以写成 J - I（全1矩阵减单位矩阵）
✦
18.2
有向图到邻接矩阵
非对称矩阵表示有向连接
对于有向图，如果存在从节点i到节点j的有向边， 则aᵢⱼ = 1，但aⱼᵢ不一定等于1。 有向图的邻接矩阵通常不对称。
入度与出度
列和 = 入度
邻接矩阵第j列的和 = 节点j的入度
Σᵢ aᵢⱼ = deg⁻(j)
行和 = 出度
邻接矩阵第i行的和 = 节点i的出度
Σⱼ aᵢⱼ = deg⁺(i)
矩阵乘法
A @ Aᵀ
• 对角线元素 = 出度
• 非对角线 = 共同指向的节点数
Aᵀ @ A
• 对角线元素 = 入度
• 非对角线 = 共同来源的节点数
✦
18.3
传球问题
用邻接矩阵的幂解决组合问题
邻接矩阵的n次幂An可以告诉我们： 从节点i到节点j，经过n步路径的数量。 这个性质可以用来解决很多有趣的组合数学问题。
矩阵幂的含义
A²[i][j]
从节点i到节点j，
经过2步路径的数量
经过2步路径的数量
A³[i][j]
从节点i到节点j，
经过3步路径的数量
经过3步路径的数量
Aⁿ[i][j]
从节点i到节点j，
经过n步路径的数量
经过n步路径的数量
应用场景
• 传球问题
• 路径计数
• 随机游走
• 路径计数
• 随机游走
✦
本章小结
图与矩阵之间的对应关系为我们提供了分析网络的新视角。 通过邻接矩阵，图论问题可以转化为线性代数问题， 反过来，矩阵数据也可以看作图来进行网络分析。
📊 核心要点
1.
邻接矩阵
用n×n矩阵表示n个节点的图
2.
对称性
无向图→对称矩阵，有向图→非对称矩阵
3.
矩阵乘法
An表示n步路径的数量
4.
度数计算
通过行和/列和计算节点度数
🔗 后续章节预告
更多矩阵即图
• 距离矩阵
• 相似度矩阵
• 协方差矩阵
• 相关系数矩阵
• 相似度矩阵
• 协方差矩阵
• 相关系数矩阵
谱分析
利用特征值分解分析图的结构性质
💡 核心思想
图就是矩阵，矩阵就是图
有数据的地方，必有矩阵
有矩阵的地方，更有向量
有向量的地方，就有几何
有几何的地方，皆有空间
图与矩阵，殊途同归