INTRODUCTION
简介
- 图到处都是
- 举例
真实世界的图（具象化模型）
- Node classification: Predict the type of a given node 预测图的类型
- Link prediction: Predict the interaction (or existence of) between two nodes 预测链接类型
- Community detection: Identify linked clusters of nodes 识别链接集群
- Network similarity: Measure similarity among nodes/sub-graphs/whole networks 相似性的图（类比推理模型迁移）
社交网 social network
- 六人联系：我们可以根据最多六个人的关系就可以认识全世界的每一个人
传播类影响 Influence Propagation
- 网络预测，故障分析，薄弱点分析
- 病毒传播，感染力模型
知识图谱 Knowledge Graph
- 用图来表示信息
- 知识点上下位关系
- 知识点的串并联关系
- 知识点相关性力度
- 知识点联系长度
- 知识点的输入输出关系
推荐预测（信息茧房）Recommender System
- 也就是将相关的信息本体套上不同的维度，之后按照韦恩图一样进行叠加，在相应的用户进行阅读的时候，我们通过提取相关的信息来逐渐的找到用户所适合的维度，最后在用户所可能感兴趣的维度内进行相关的推荐和预测
- 举个例子：
- 电影推荐
- 演员维度
- 剧情维度
- 配乐维度
- 电影类型
- …
- 也可以看这个图
- 用户层（主观性内容）
- 知识层（客观性推荐内容）
- 通过确定二者的交杂点，就可以找到合适的推荐内容
- 电影推荐
生化流程应用 Biochemical Applications
- 药物的合成预测
- 产物路径预测
- 一般应用的是图卷积网络
Structure of a Graph
Network Properties
度的衡量
- 讲的也就是怎么样来进行度的描述和数学化
- 一般来说，会应用这样的模型
步长Path Length
这里讲的就是一些基本的定义基本的量，也就是最基本的一些表述元素
- path
- 拥有链接顺序
- 可以多次通过，自联系
- 遵循有向性
- distance
- 两个path之间的最短路径
- diameter
- 途中两个节点的最远距离
- average path length
- 仅限于联通的无方向的图
- 我们在这里也可以引入相互关联的强度，也可以类比卷积来思考和看
- 忽视那些没有联系的点，我们只对那些已经联系上的点来去步长
对于无向图的聚类计算Clustering Coefficient (for undirected graph)
-
Clustering Coefficient for a node i:节点的聚集关联度
- 表示了怎么和身边的信息进行关联
- 拥有聚集度k
- 要考虑边缘量
- 也就是类比的粒度关系，拥有0-1的相关联度
-
Average Clustering Coefficient平均聚合度计算
-
-
也就是从群体到个体的划分关系
关联复杂度 Connected Component
这里其实插入了一个BFS广度优先算法的内容，详细的解释来看超链接
这里讲的也就是图是否闭合的问题，如果全部都能走通，那就代表肯定是联系上的，那如果走通不了，那就代表是没有联系的。
随机图生成模型 Random Graph Generation Models
Erdos-Renyi Model
Application of Graphs
图的相关算法
- 图的搜索算法：图的搜索指的就是从图的某一节点开始，通过边到达不同的节点，最终找到目标节点的过程。根据搜索的顺序不同，图的搜索算法可分为“广度优先搜索”和“深度优先搜索”两种。
- 图的最短路径问题：最短路径问题就是要在两个节点的所有路径中，找到一条所经过的边的权重总和最小的路径。相关算法有“贝尔曼-福特算法”，“狄克斯特拉算法”和“A* 算法”三种。
图的搜索算法
广度优先搜索会根据离起点的距离，按照从近到远的顺序对各节点进行搜索。而深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条路径。
广度优先算法
广度优先搜索和深度优先搜索一样，都是对图进行搜索的算法，都是从起点开始顺着边搜索，此时并不知道图的整体结构，直到找到指定节点(即终点)。在此过程中每走到一个节点，就会判断一次它是否为终点。
广度优先搜索会根据离起点的距离，按照从近到远的顺序对各节点进行搜索。
在广度优先搜索中，有一个保存候补节点的队列，队列的性质就是先进先出，即先进入该队列的候补节点就先进行搜索。
下图中红色表示当前所在的节点（节点A），终点设为节点G，将与节点A直连的三个节点B, C, D放入存放候补节点的队列中（与节点A直连的三个节点放入时可以没有顺序，这里的放入顺序为B, C, D），用绿色表示。
1、上面左图：此时从队列中选出一个节点，优先选择最早放入队列的那个节点，这里选择最左边的节点B。将已经搜索过的节点变为橙色（节点A），搜索到节点B时，将与节点B直连的两个节点E和F放入队列中，此时队列为 [C, D, E, F]。
2、上面中图：对节点B搜索完毕，节点B不是要找的终点，再搜索节点C，将与节点C直连的节点H放入队列中，此时队列为 [D, E, F, H]。
3、然后对节点D进行同样的操作，此时队列为 [E, F, H, I, J]。
4、上面右图：对与节点A直连的节点搜索完毕，再对与节点B直连的节点进行搜索（因为剩下的点中它们最先放入队列），这里选择节点E，将与节点E直连的节点K放入队列中，此时队列为 [F, H, I, J, K]。
然后一直按照这个规则进行搜索，直到到达目标节点G为止，搜索结束
广度优先搜索为从起点开始，由近及远进行广泛的搜索。因此，目标节点离起点越近，搜索结束得就越快
深度优先算法
在深度优先搜索中，保存候补节点是栈，栈的性质就是先进后出，即最先进入该栈的候补节点就最后进行搜索。
还是将起点设为节点A，终点设为节点G，还是先将与节点A直连的三个节点B, C, D放入存放候补节点的栈中（这里的放入顺序为D, C, B）。到这里和广度优先搜索似乎没什么区别。
因为节点B是最后放入，则先从节点B开始搜索，将与节点B直连的两个节点E和F放入栈中，此时栈为 [D, C, F, E]。
1、上面左图：然后再对节点E进行搜索，将与节点E直连的节点K放入栈中，此时栈为 [D, C, F, K]。
2、此时节点K在栈的最后，所以先对节点K进行搜索，节点K不是终点，而且节点K没有其他直连的节点，所以此时栈为 [D, C, F]。
3、上面中图：然后再对节点F进行搜索，节点F也不是终点，而且节点F也没有其他直连的节点，所以此时栈为 [D, C]。
3、上面右图：接下来就对节点C进行搜索，将与节点C直连的节点H放入栈中，此时栈为 [D, H]。
然后一直按照这个规则进行搜索，直到到达目标节点G为止，搜索结束
深度优先搜索会沿着一条路径不断往下，搜索直到不能再继续为止，到了路径的尽头，再折返，再对另一条路径进行搜索。
总结
虽然广度优先搜索和深度优先搜索在搜索顺序上有很大的差异，但是在操作步骤上却只有一点不同，那就是选择哪一个候补节点作为下一个节点的基准不同。
广度优先搜索选择的是最早成为候补的节点，因为节点离起点越近就越早成为候补，所以会从离起点近的地方开始按顺序搜索；而深度优先搜索选择的则是最新成为候补的节点，所以会一路往下，沿着新发现的路径不断深入搜索。
上面介绍过连通图的定义，通过深度优先搜索可以判断图是否是连通图。具体实现为：在图中任意选择一个节点，从该节点开始进行深度优先搜索，如果在这个搜索过程中所有的节点都被搜索到，则该图为连通；反之，若存在没有被搜索到的节点，则说明该图是非连通的。
在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，所以不但可以判断两个节点之间是否有路径，还可以找出这两个节点的最短路径，即可以解决最短路径问题。
广度优先搜索可以用于找到两个节点的最短路径问题，这里的最短路径其实是针对于非加权图，寻找段数最少的路径。但是对于加权图，段数最少的路径并不代表路径中的权重总和也最小。
其实可以浅显的理解一下，广度搜索更像是横向发展，一点点的漫走整个树，直到找到理想的答案，而深度搜索更像是顺着一个方向不断地深究，然后再找那个理想的答案
Transclude of 深度优先搜索与广度优先搜索的本质区别！---知乎.mhtml
图的最短路径问题
贝尔曼-福特算法
狄克斯特拉算法
A* 算法
网络结构 Structure of the Web
- 其实可以思考成一个黑箱子，适当的减少一些路径，然后进行相应的处理和选择。
- 其实这里讲的很多很多都是相关的算法啥的，这个后续学python学习的时候再进行细化。
一些杂七杂八的知识
图的分类
1、如果给边加上一个值表示权重，这种图就是加权图，没有权重的图就是非加权图，没有权重的边只能表示两个节点的连接状态，而有权重的边就可以表示节点之间的“连接程度”。
2、如果给边加上表示方向的箭头，即表示节点之间的传递方向，这种图就是有向图，而边上没有箭头的图就是无向图。
3、如果图中任意两个节点都能找到路径可以将它们进行连接，则称该图为连通图，上面这个图就是连通图，反之则为非连通图。
加权图与有向图
连通图
非连通图
而图的存在目的是为了什么呢？当然是为了存储关系和信息呀，因此就有了下面的内容
参考资料
Transclude of 简单的图论入门---知乎.mhtmlhttps://blog.csdn.net/PolarisRisingWar/article/details/117287320 大佬写的笔记，可以直接拿来借鉴
https://zhuanlan.zhihu.com/p/272671494 https://zhuanlan.zhihu.com/p/543187296 知乎写的很好的总结，参考这个即可 # 图神经网络（GNN)的学习和GCN粗浅理解