图论及概念

术语

性质可以包含多种数据，如数值、字符串以及空间数据和时态数据。例如上图中，Person节点的性质name取值为Dan，MARRIED_TO关系的性质on则取值为Jan 1, 2013。路径由一组节点及其连接关系构成。例如：一条简单的路径可以包含节点Dan、Ann和Car以及关系DRIVES和OWNS。

图的类型和结构

图的种类

连通与不连通：图中任意两个节点是否存在一条路径，不考虑距离因素，节点“孤岛”可能会导致意外表现，例如无法处理不连通分量。

加权与不加权：关系或节点是否有值，许多算法涉及权重，如果忽略权重，就会发现算法在性能和结果上都存在显著差异

有向与无向：关系是否明确定义了起始节点和终止节点，这为推断额外含义增加了丰富的上下文信息。在某些算法中，可以明确设定使用单向、双向还是无向。

有环与无环：路径的起点和终点是否为同一节点，有环图很常见，但是在算法处理中必须小心，否则循环可能无法终止。

稀疏与稠密：关系数与节点数的比值。极为稀疏和极为稠密的连通图都会导致异常结果，假如稀疏性或稠密性并非该领域的固有特征，则可以借助数据建模。

单部、二部与k部：节点只与一种其他类型的节点连接（例如用户喜欢某些电影），或者与其他多种节点连接（用户喜欢爱好某些电影的用户），有助于创建关系来分析和投影更有用的图。

连通图与非连通图

无权图与加权图

无向图与有向图

无环图与有环图

稀疏图与稠密图

单部图，二部图和k部图

图算法的类型

路径查找

查找最短路径是图算法中使用的比较频繁的任务。最短路径是跳数最少或权重最小的遍历路径。如果图是有向的，它就是指两个节点之间关系方向所允许的最短路径。

中心性

人们创建了不同类型的中心性算法来度量不同的事物，例如快速传播信息的能力和桥接不同群体的能力。

社团发现

连通性是图论的核心概念之一，它支持复杂网络分析，比如社团发现。现实世界中的大多数网络或多或少呈现出独立子图这样的子结构（通常是准分形）。
连通度用于发现社团并且量化分组的质量。评估图中不同类型的社团有助于揭示图的结构，比如中心结构和层级结构，也有助于了解某个群组吸引或排斥其他群组的倾向。这些方法用于研究一些突发现象，例如那些导致回音壁效应和过滤气泡效应的现象。