一、图论速概览
- 研究图的性质和图之间的关系
- 节点和边组成，节点表示对象，边表示对象之间的关系
- 无向图：边没有方向，节点之间的连接是双向的。常用于描述简单的关系，如社交网络中的朋友关系。根据边有无权重分为无权重无向图和有权重无向图。无权重无向图中，通常使用 0和 1表示边的存在或不存在；有权重无向图的边有关联的数值（欧氏距离、相似度、相关性系数等）
- 有向图：边有方向，从一个节点指向另一个节点。常用于描述有向关系，例如网页之间的链接、任务执行的顺序、陆地生物链的能量流动模式等
- 图就是矩阵，矩阵就是图！例如有向图与邻接矩阵的关系（无向图也有对应的）：
再例如（成对）欧式距离矩阵也可抽象为一幅无向图如下。类比，（成对）亲近度矩阵、成对余弦距离、协方差矩阵、相关性系数矩阵等都可以表示为图。
更进阶地，关联矩阵、度矩阵、拉普拉斯矩阵等都能反映图论与矩阵之间奇妙的关系！
- 图可以用来分类/聚类，树是图的特殊形态——如k-NN中的kd树、决策树、层次聚类等
- 图神经网络（GNNs）：图论的一种拓展，专门处理图结构数据。GNNs 能够在图上进行节点和边的信息传递，使得模型能够理解节点之间的复杂关系
- 大语言模型（LLM）：自然语言处理的应用主要体现在语言结构的建模上。语言结构可以被视为一个图，其中单词或子词是节点，语法和语义关系则是边
- NetworkX工具 ： Python 编写的图论和复杂网络分析的开源软件包。提供了创建、操作和研究复杂网络结构的工具。—— 编程时需要导入的库
二、无向图
1、关键概念
- 节点集：所有节点的集合（对象的集合）。
- 边集：所有边的集合。
- 阶（order）：节点的数量。
- 大小（size）：边的数量。
- 度（degree）：无向图中，一个节点的度是与它相连的边的数量——针对一个节点来说
- 邻居（neighbors）：无向图中，一个节点的邻居是通过一条边直接相连的其他节点——针对一个节点来说
- 端点（end vertex, end node）：度数为1的节点。
- 孤立点（isolated node, isolated vertex）：度数为0的节点。
2、特殊结构
- 自环：一个节点与它自己连接的边叫做自环（圈）
- 同构：节点名称、边名称、外观等都不同，但本质是的连接关系一致，即等价图
- 多图：连接两个节点的边不止一条。对于某些应用很有用，如网络建模、流量分析等。
- 子图：原始图的一部分
- 有权图：一种图论中的数据结构，在无向图每条边上附加了一个权重或值，表示了连接两个节点之间的某种度量，例如距离、成本、时间等
三、有向图
除了节点集、边集、阶、大小、邻居等概念，有向图由于其边的方向性，度分为出度和入度：
- 入度：指向该节点的边的数量——针对一个节点来说
- 出度：从该节点出发的边的数量——针对一个节点来说
- 其实，对应入度和出度，邻居也可分为入度邻居（上家）、出度邻居（下家）
特殊结构可类比无向图，除此之外，再介绍一个概念三元组：
- 三元组类型是指在社交网络或其他网络中，根据节点之间的连接关系，将节点组合成不同类型的三元组。三元组由 三个节点组成 ，它们之间存在 特定的连接模式。如下是三元组的16种模式：
非三元组的有向图里可能包含三元组，可拆分观察！！
四、图的可视化
可视化关键点：
- 节点：位置、标签、颜色、大小、记号、选择性绘制
- 边：标签、颜色、线宽、线型、选择性绘制
- 图的布局
1、节点位置
- 绘制有向图和无向图用networkx.draw_networkx() 函数，参数pos可指定节点位置布局
- networkx.spring_layout() 产生节点位置布局——使用弹簧模型算法将图的节点布局在平面上，模拟节点间的弹簧力和斥力关系：
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np# 创建无向图
G = nx.random_geometric_graph(200, 0.2, seed=888)# 使用弹簧模型算法布局节点
pos = nx.spring_layout(G, seed = 888)# 可视化
plt.figure(figsize = (6,6))
nx.draw_networkx(G, pos = pos, node_color = '#3388FF',alpha = 0.5,with_labels = False, node_size = 68)
plt.savefig('节点布局，弹簧算法布局.svg')
- 直接输入节点位置坐标的字典。
例如：字典里的位置坐标由随机数发生器生成：
# 自定义节点位置
data_loc = np.random.rand(200,2)
# 随机数发生器生成节点平面坐标# 创建节点位置坐标字典
pos_loc = {i: (data_loc[i, 0], data_loc[i, 1]) for i in range(len(data_loc))}# 可视化
plt.figure(figsize = (6,6))
nx.draw_networkx(G, pos = pos_loc, node_color = '#3388FF',alpha = 0.5, with_labels = False, node_size = 68)
plt.savefig('节点布局，随机数.svg')
也可以调节字典里的“节点-坐标”元素，实现完全二分图、圆周布局、螺旋布局等图。
2、节点装饰：大小、透明度、颜色
3、边装饰
颜色、线宽、选择性绘制边（比如仅仅保留欧式距离小于0.5的边）
4、节点标签
networkx.draw_networkx_labels() #标签即a、b、c、d对象名5、常见图的绘制
networkx.balanced_tree() 创建平衡树图
networkx.barbell_graph() 创建哑铃型图
networkx.binomial_tree() 创建二叉图
networkx.bipartite.gnmk_random_graph() 创建随机二分图
networkx.bipartite_layout() 二分图布局
networkx.circular_layout() 圆周布局
networkx.complete_bipartite_graph() 创建完全二分图
networkx.complete_graph() 创建完全图
networkx.complete_multipartite_graph() 创建完全多向图
networkx.cycle_graph() 创建循环图
networkx.ladder_graph() 创建梯子图
networkx.lollipop_graph() 创建棒棒糖型图
networkx.multipartite_layout() 多向图布局
networkx.path_graph() 创建路径图
networkx.star_graph() 创建星型图
networkx.wheel_graph() 创建轮型图五、路径问题
重要概念，注意包含关系：
- 通道：沿图的边依次经过一系列节点的序列，可包含重复边或经过相同节点。
- 迹：无重复边的通道，可以包含重复节点。
- 路径：无重复边、无重复节点的通道。
- 回路：闭合的迹。
- 环：闭合的路径。
几种常见路径问题对比：
networkx常用代码：
networkx.algorithms.approximation.christofides() 使用 Christofides 算法为加权图找到一个近似最短
哈密顿回路的
networkx.all_simple_edge_paths() 查找图中两个节点之间所有简单路径，以边的形式返回
networkx.all_simple_paths() 查找图中两个节点之间所有简单路径
networkx.complete_graph() 生成一个完全图，图中每对不同的节点之间都有一条边
networkx.DiGraph() 创建一个有向图
networkx.find_cycle() 在图中查找一个环
networkx.get_node_attributes() 获取图中所有节点的指定属性
networkx.has_path() 检查图中是否存在从一个节点到另一个节点的路径
networkx.shortest_path() 计算图中两个节点之间的最短路径
networkx.shortest_path_length() 计算图中两个节点之间最短路径的长度
networkx.simple_cycles() 查找有向图中所有简单环
networkx.utils.pairwise() 生成一个节点对的迭代器，用于遍历图中相邻的节点对
