图是什么
图的定义
图表示物件与物件之间的关系的数学对象，是图论的基本研究对象。
如下图：
图可用于表示:
社交网络
网页
生物网络
图的基本表示方法
图 G=(V, E) 由下列要素构成：
一组节点（也称为 verticle）V=1,…,n
一组边 E⊆V×V
边 (i,j) ∈ E 连接了节点 i 和 j
i 和 j 被称为相邻节点（neighbor）
节点的度（degree）是指相邻节点的数量
如果一个图的所有节点都有 n-1 个相邻节点，则该图是完备的（complete）。也就是说所有节点都具备所有可能的连接方式。
从 i 到 j 的路径（path）是指从 i 到达 j 的边的序列。该路径的长度（length）等于所经过的边的数量。
图的直径（diameter）是指连接任意两个节点的所有最短路径中最长路径的长度。
测地路径（geodesic path）是指两个节点之间的最短路径。
如果所有节点都可通过某个路径连接到彼此，则它们构成一个连通分支（connected component）。如果一个图仅有一个连通分支，则该图是连通的（connected）
如果一个图的边是有顺序的配对，则该图是有向的（directed）。i 的入度（in-degree）是指向 i 的边的数量，出度（out-degree）是远离 i 的边的数量
如果可以回到一个给定节点，则该图是有环的（cyclic）。相对地，如果至少有一个节点无法回到，则该图就是无环的（acyclic）。
图可以被加权（weighted），即在节点或关系上施加权重。
如果一个图的边数量相比于节点数量较小，则该图是稀疏的（sparse）。相对地，如果节点之间的边非常多，则该图是密集的（dense）
Neo4J 的关于图算法的书给出了清晰明了的总结：
e.g
空手道俱乐部图
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JzubWPbN-1639659392854)(https://i.loli.net/2021/12/02/EM4nSPIU83NfW1A.png)]
这个「空手道」图表示什么？Wayne W. Zachary 在 1970 到 1972 年这三年中研究的一个空手道俱乐部的社交网络。该网络包含了这个空手道俱乐部的 34 个成员，成员对之间的连接表示他们在俱乐部之外也有联系。在研究期间，管理员 JohnA 与教练 Mr.Hi（化名）之间出现了冲突，导致俱乐部一分为二。一半成员围绕 Mr.Hi 形成了一个新的俱乐部，另一半则找了一个新教练或放弃了空手道。基于收集到的数据，除了其中一个成员，Zachary 正确分配了所有成员在分裂之后所进入的分组。
图的存储
存储图的方式有三种，取决于你想用它做什么：
存储为边列表：
我们存储有边连接的每一对节点的 ID，例如：
G_karate.edges()
使用邻接矩阵，这通常是在内存中加载的方式：
对于图中的每一个可能的配对，如果两个节点有边相连，则设为 1。如果该图是无向图，则 A 是对称的。
使用邻接列表：
1 ：[2, 3, 4]
2 ：[1,3]
3 ：[2, 4]
图的类型和性质
有很多分类方式，参考集合论与图论（下）_中国大学MOOC(慕课) (icourse163.org)
应用中常见的一种分类方法，同构图与异构图：
同构图与异构图
两个图G和H是同构图（isomorphic graphs），能够通过重新标记图G的顶点而产生图H。
如果G和H同构，那么它们的阶是相同的，它们大小是相同的，它们个顶点的度数也对应相同。
异构图是一个与同构图相对应的新概念。
传统同构图（Homogeneous Graph）数据中只存在一种节点和边，因此在构建图神经网络时所有节点共享同样的模型参数并且拥有同样维度的特征空间。
而异构图（Heterogeneous Graph）中可以存在不只一种节点和边，因此允许不同类型的节点拥有不同维度的特征或属性。
图算法
目前传统框架（比如 Python 的 networkx 或 Neo4J）支持的图算法类别主要有三个：
Pathfinding（寻路）：根据可用性和质量等条件确定最优路径。搜索算法也包含在这一类别中。这可用于确定最快路由或流量路由。
Centrality（中心性）：确定网络中节点的重要性。这可用于识别社交网络中有影响力的人或识别网络中潜在的攻击目标。
Community detection（社群检测）：评估群体聚类的方式。这可用于划分客户或检测欺诈等。
networkx 中的所有算法都可在这里找到：https://networkx.github.io/documentation/stable/reference/algorithms/index.html
1. 寻路和图搜索算法
寻路算法是通过最小化跳（hop）的数量来寻找两个节点之间的最短路径。
搜索算法不是给出最短路径，而是根据图的相邻情况或深度来探索图。这可用于信息检索。
1). 搜索算法
图搜索算法主要有两种：
宽度优先搜索（BFS）：首先探索每个节点的相邻节点，然后探索相邻节点的相邻节点；
深度优先搜索（DFS）：会尝试尽可能地深入一条路径，如有可能便访问新的相邻节点。
2). 寻路算法
a. 最短路径
最短路径计算的是一对节点之间的最短的加权（如果图有加权的话）路径。
这可用于确定最优的驾驶方向或社交网络上两个人之间的分离程度。
计算图中的最短路径的方法有很多，包括 Dijkstra 算法，这是 networkx 中的默认算法。
b. 单源最短路径
单源最短路径（Single Source Shortest Path/SSSP）是找到给定节点与图中其它所有节点之间的最短路径。
这常用于 IP 网络的路由协议。
c. 所有配对最短路径
所有配对最短路径（All Pairs Shortest Path / APSP）算法是找到所有节点对之间的最短路径。
尽管能够提供相近的结果，但这比为每个节点对调用单源最短路径算法更快。该算法通常可用于确定交通网格的不同分区的流量负载。
d. 最小权重生成树
最小权重生成树（minimum spanning tree）是图（一个树）的一个子图，其用权重和最小的边连接了图中的所有节点。
注意，最小生成树应该用于无向图。
2. 社群检测
社群检测是根据给定的质量指标将节点划分为多个分组。
这通常可用于识别社交社群、客户行为或网页主题。
**社区是指一组相连节点的集合。**但是，目前关于社群还没有广泛公认的定义，只是社群内的节点应该要密集地相连。
Girvan Newman 算法是一个用于发现社群的常用算法。其通过逐步移除网络内的边来定义社区。我们将居间性称为「边居间性（edge betweenness）」。这是一个正比于穿过该边的节点对之间最短路径的数量的值。
该算法的步骤如下：
计算网络中所有已有边的居间性。
移除居间性最高的边。
移除该边后，重新计算所有边的居间性。
重复步骤 2 和 3，直到不再剩余边。
3. 分层聚类
在分层聚类（hierarchical clustering）中，我们构建聚类的层次结构。我们用树状图的形式表示聚类。
其思想是以不同的规模分析社群结构。我们通常自下而上构建树状图。我们从每个节点一个聚类开始，然后合并两个「最近」的节点。
但我们如何衡量聚类是否相近呢？我们使用相似度距离。令 d(i,j) 为 i 和 j 之间的最短路径的长度。
要得到最大连接，在每个步骤，被最短距离分开的两个聚类被组合到一起。相似度距离可用以下示意图阐释
