🌏 GIStudio

图论基础

6 min read

推荐阅读

图论基础：学习节点、边、邻接矩阵等概念，可参考GeeksforGeeks Graph Theory 机器学习基础：了解监督学习、非监督学习和半监督学习，可参考Scikit-learn Documentation.

图论与图学习基础教程

引言

图（Graph）是一种表示实体及其关系的强大数据结构，广泛应用于社交网络、分子结构分析、推荐系统等领域。本教程将介绍图论基础知识、图的表示方法、常见类型及图学习任务，帮助读者构建对图数据的系统性理解。

一、预习资料

  1. 图论基础

    • 核心概念：节点（Node/Vertex）、边（Edge）、邻接矩阵（Adjacency Matrix）。
    • 推荐阅读：GeeksforGeeks Graph Theory（重点阅读图的定义与基本操作）。
    • 目标：理解“节点表示实体，边表示关系”的核心思想。

  2. 机器学习基础

    • 关键知识点：监督学习（带标签训练）、非监督学习（无标签聚类）、半监督学习（部分标签）。
    • 推荐工具：Scikit-learn Documentation（熟悉分类与聚类算法）。
    • 目标：掌握如何将机器学习方法应用于结构化数据。

二、图的表示方法

1. 邻接矩阵（Adjacency Matrix）

  • 定义：用方阵 ( A ) 表示节点间的连接关系。若节点 ( i ) 与 ( j ) 之间有边，则 ( A[i][j] = 1 )（无权图）或边的权重（加权图）。
  • 示例： 
    # 3个节点的无向图（节点0-1、1-2相连）
Adjacency Matrix = [
  [0, 1, 0],
  [1, 0, 1],
  [0, 1, 0]
]
  • 特点：
    • 优点：快速判断两节点是否相连（时间复杂度 ( O(1) )）。
    • 缺点：空间复杂度 ( O(N^2) )，不适用于稀疏图（边数远小于 ( N^2 ) 的图）。

2. 邻接列表（Adjacency List）

  • 定义：用列表存储每个节点的邻居。例如，节点 ( i ) 的邻居存储为列表 ( [j, k, …] )。
  • 示例： 
    # 同上3个节点图的邻接列表
Adjacency List = {
  0: [1],
  1: [0, 2],
  2: [1]
}
  • 特点：
    • 优点：空间复杂度 ( O(N + E) )，适合稀疏图。
    • 缺点：查询两节点是否相连需遍历列表（时间复杂度 ( O(d) )，( d ) 为节点度数）。

三、图的类型

1. 有向图 vs 无向图

类型边的方向示例场景
无向图边无方向（双向）社交网络中的好友关系
有向图边有方向（单向）网页超链接、微博关注关系
  • 邻接矩阵区别：无向图的邻接矩阵是对称的，有向图不一定对称。

2. 加权图 vs 非加权图

类型边是否带权重示例场景
非加权图边权重相同（通常为1）论文合作网络（合作关系存在与否）
加权图边有权重（如距离、概率）交通网络（道路长度）、推荐系统（用户相似度）

四、常见图学习任务

1. 节点分类（Node Classification）

  • 目标：预测图中节点的类别标签。
  • 示例：
    • 社交网络中预测用户的兴趣领域（标签：科技、体育等）。
    • 引用网络中预测论文的研究主题。
  • 方法：利用图神经网络（GNN）聚合邻居信息（如GCN、GraphSAGE）。
  • 目标：预测节点间是否存在缺失的边。
  • 示例：
    • 推荐系统中预测用户可能购买的商品（用户-商品边）。
    • 社交平台推荐“可能认识的人”。
  • 方法：计算节点对的相似度（如DeepWalk、Node2Vec）。

3. 图分类（Graph Classification）

  • 目标：预测整个图的类别。
  • 示例：
    • 化学分子图中判断分子是否具有毒性。
    • 代码流程图分类（如检测恶意软件）。
  • 方法：全局池化（Global Pooling）后接全连接层（如Graph Kernels、GIN）。

五、结语

掌握图论基础与图的表示方法是进行图学习的前提。后续可结合具体算法（如PageRank、GNN）深入实践。建议使用工具如NetworkX（图操作）和PyTorch Geometric（图神经网络）进行代码实战。

下一步学习建议：

  • 实践邻接矩阵与邻接列表的相互转换（如用Python字典实现邻接列表）。
  • 在Kaggle上尝试图分类任务（如TUDatasets）。

Graph View