Visualize-ML

关于有向图

在图论中，图可以分为无向图和有向图两种基本类型。无向图中的边没有方向，即连接两个节点的边不区分起点和终点。有向图中的边有方向，即连接两个节点的边有明确的起点和终点。

有向图在现实世界中有广泛应用：网页之间的链接、社交网络中的关注关系、任务之间的依赖关系、交通网络中的单行道等。本章将系统介绍有向图的核心概念，并对比无向图学习。

✦

12.1

有向图：边有方向

节点集、有向边集、阶、大小

有向图记做 G_D = (V, A)，其中 V 是节点集，A 是有向边集（arc/arrows）。与无向图不同，有向图的边是节点的有序对，(a,b) ≠ (b,a)。在有向边 (a,b) 中，a 叫做头（head），b 叫做尾（tail）。

🔄 有向 vs 无向

• 节点集：相同，都用 V 表示

• 边集：无向图用 E（edge），有向图用 A（arc）

• 方向性：无向边 (a,b) = (b,a)，有向边 (a,b) ≠ (b,a)

• NetworkX：Graph() vs DiGraph()

🎯 应用场景

• 网页链接：A链接到B，但B不一定链接A

• 社交关注：我关注你，不代表你关注我

• 任务依赖：任务A必须在任务B之前完成

• 单行道：交通网络中的方向限制

✦

12.2

出度、入度

度数的分解：入度 + 出度

有向图中，节点的入度（indegree）是指向该节点的边的数量，出度（outdegree）是从该节点出发的边的数量。节点的度数等于入度和出度之和：deg(v) = indeg(v) + outdeg(v)。对于整个有向图，所有节点的入度之和等于出度之和，都等于边数。

📐 度数定理

• 节点度数：deg(v) = indeg(v) + outdeg(v)

• 全局性质：∑ indeg(v) = ∑ outdeg(v) = |A|

• 特殊节点：入度=0为源节点（source），出度=0为汇节点（sink）

✦

12.3

邻居：上家、下家

Predecessor 和 Successor

在有向图中，邻居的定义需要考虑边的方向。入度邻居（predecessor/上家）是指向该节点的节点，出度邻居（successor/下家）是该节点指向的节点。这种不对称的邻居关系在社交网络、引用网络等场景中有重要应用。

💻 NetworkX 方法

list(nx.all_neighbors(G, 'a'))

list(G.predecessors('a'))

list(G.successors('a'))

🔍 对比无向图

• 无向图：邻居关系是对称的

• 有向图：需区分上家和下家

• 术语：Predecessor（前驱）、Successor（后继）

✦

12.4

有向多图：平行边

MultiDiGraph 允许平行有向边

与无向多图类似，有向多图（MultiDiGraph）允许在同一对节点之间存在多条有向边。注意 a→b 和 b→a 是两条不同的边，同时 a→b 可以有多条平行边。这在表示多条交通路线、多次交互等场景中很有用。

💻 NetworkX 代码

G = nx.MultiDiGraph()

G.add_edges_from([('a','b'), ('a','b')])

# 添加两条平行的有向边 a→b

✦

12.5

三元组：三个节点的16种关系

社交网络分析的基本单元

三元组（triad）由三个节点组成，根据节点之间的连接关系，共有16种可能的类型。三元组的编码规则：前三位数字分别表示相互、非对称、空值二元组的数量；字母表示方向，分别是向上（U）、向下（D）、循环（C）或传递（T）。三元组分析在社交网络研究中有重要应用。

🔺 典型三元组

• 003：三个孤立节点

• 102：一对互相关注

• 030C：循环（A→B→C→A）

• 030T：传递（A→B→C, A→C）

• 300：完全图

💻 NetworkX 函数

nx.triad_graph('030C')

nx.is_triad(G)

nx.all_triads(G)

nx.triad_type(T)

🎯 应用价值

• 社交网络分析

• 群体结构识别

• 信息传播研究

• 推荐系统

✦

12.6

NetworkX 创建图

列表、数据帧、NumPy数组三种方式

NetworkX 提供了多种创建图的方法：列表（最简单）、数据帧（可附加属性）、邻接矩阵（数学表示）。这三种方法都支持创建有向图和无向图。邻接矩阵揭示了图论的核心思想：图就是矩阵，矩阵就是图。

📋 列表方法

• 最简单直观

• 直接列出所有边

• 适合小规模图

nx.from_edgelist()

📊 数据帧方法

• 可附加边属性

• 支持权重、标签

• 适合数据分析

nx.from_pandas_edgelist()

🔢 邻接矩阵方法

• 数学表示

• 矩阵运算

• 线性代数分析

nx.from_numpy_array()

✦

本章小结

本章系统介绍了有向图的核心概念，并与无向图进行了对比。通过交互式组件，深入理解了有向边、入度出度、邻居关系、三元组等重要概念。

🎯 核心概念

• 有向边：(a,b) ≠ (b,a)

• 入度出度：deg = indeg + outdeg

• 上家下家：Predecessor & Successor

• 有向多图：允许平行有向边

• 三元组：16种基本类型

• 创建方法：列表、数据帧、矩阵

🚀 实际应用

• 网页排名：PageRank算法

• 社交网络：影响力分析

• 任务调度：拓扑排序

• 推荐系统：基于三元组

• 交通规划：单行道网络

• 知识图谱：实体关系

💡

学习建议

• 动手操作每个交互组件，理解方向性的重要性

• 对比有向图和无向图的异同

• 尝试用三种方法创建同一个有向图

• 思考实际问题如何用有向图建模

• 探索三元组在社交网络分析中的应用