1、图 (graph) 概念
图（Graph）是由节点（Node）和边（Edge）组成的一种数据结构，用于描述事物之间的关系。在图中，节点表示事物，边表示事物之间的关系。图可以用来描述各种复杂的关系网络，例如社交网络、交通网络、生物网络等。
在图中，节点可以表示各种实体，例如人、物、地点、基因等。边可以表示各种关系，例如人与人之间的社交关系、物品之间的相似性关系、地点之间的距离关系、基因之间的相互作用关系等。图可以用来描述各种不同类型的关系网络，从而帮助我们更好地理解事物之间的联系和相互作用。图可以分为有向图和无向图两种类型。在有向图中，边有方向，表示从一个节点到另一个节点的单向关系；在无向图中，边没有方向，表示两个节点之间的双向关系。此外，图还可以包含权重，用于表示边的强度或者权重。
图是计算机科学中的重要概念，被广泛应用于各种领域，例如社交网络分析、生物信息学、交通网络规划等。
2、图的基本表示
图的基本构成 ： 节点(nodes, vertices,$N$)， 连接(links,edges,$E$)，从而图可以被系统描述 $G(N,E)$ .
图的本体（Ontology）: 图的本体是对知识图谱的正式描述，用以描述一个领域内的一组概念以及它们之间的关系。要构建一个图，需要清楚图的本体，哪些信息可以被描述为节点对象，哪些关系用以描述对象连接。
2.2 图的分类:
根据连接关系的指向性有无分成 无向图，有向图
如果一张图里存在不同类型的节点或连接，则形成 异质图(heterogeneous graph) ，$G(V,E,R,T)$
这种图结构复杂性较高，是目前大部分图神经网络论文的主要关注对象。Nodes with node types $v_i \in V$
Edges with relation types $(v_i,r,v_j) \in E$
Node type $T(v_i)$
Relation type $r \in R$
基于边的连接是否带权重，可以分为连接带权重的图
2.3 节点度(degree)
在一个网络中，如果一个节点与其它节点广泛连接（连接的边很多），意味着它在该图所表示的关系中起着非常重要的作用，所以 node degree 可以简单的反映出一个节点的重要度(中心度，枢纽度)。类比社交网络中，当一个人认识的人越多，那么他就是社交中枢。
3、图的矩阵表示--邻接矩阵
描述图结构的矩阵称为 邻接矩阵($Adjacency \ Matrix$)，用以描述图中任意两个节点的邻接关系。
- 对于无向图，节点的间的连接是互为指向的关系，所以图矩阵为对称阵，如果节点不存在指向自己的连接，则矩阵的对角线为0；图的总连接数为$L = \frac {1}{2}{sum(X)}$
- 对于有向图，矩阵的行方向为 source，列方向为 target 的格式，非对称阵；对有向图矩阵，对某列求和可得节点$k_j$ 总入度($k_j^{(in)}$)，对某行求和可得节点$k_i$ 总出度($k_i^{(out)}$)，图的总连接数为$L = \sum_{i=1}^N{k_i^{(in)}} = \sum_{j=1}^N{k_j^{(out)}} = sum(X)$
3.2 图的连接列表和邻接列表
由于现实中大部分关系图都是稀疏的($k << N-1 $)，每个节点邻接的其它节点不会太多，所以邻接矩阵也是个非常稀疏的矩阵，直接用稠密矩阵表示图关系将非常耗费计算资源。 所以扩展出来图的 连接列表 和邻接列表 表示方式。
- 连接列表(list of edges) 相比起邻接矩阵，只记录存在连接的节点对，一个三元组表("source,target,weight,label,...")；
- 邻接列表(Adjacency list) 相比起 连接列表 进一步压缩了信息，图中有$N$个节点，只需要创建$N$个$elements$来表示 。
Graphs in Python - Theory and Implementation - Representing Graphs in Code (stackabuse.com)
2、图的应用
- 最短路径搜索(地图导航)
- 节点重要度分析，搜索重要节点(度中心性评价)
- 社群检测(community detection)，如 Louvain 社群检测算法（节点聚类）
- 连接预测(Link Prediction)
- 节点相似性分析，分析图即使连接遥远，但是在属性特征等方面相似的节点
- Embeddings，将一个节点映射成 d维向量，该嵌入向量表征了节点在图中的语义和连接关系，以用作下游分析。
...
