1. 图分析
1.1. 图分析和机器学习（ML）是进一步探索图时要探索的两个最常见领域
1.2. 寻路
1.2.1. 每一个特定的寻路算法的工作原理都略有不同，并且各有优缺点
-
1.2.2. 测向
- 1.2.2.1. 地理制图工具使用寻路算法的一些变体来提供方向
-
1.2.3. 优化问题
- 1.2.3.1. 寻路算法可以优化处理大量相互依赖的实体的各种问题，从管理供应链到优化金融交易，再到确定计算机网络中的瓶颈和故障点
-
1.2.4. 欺诈检测
- 1.2.4.1. 许多欺诈算法使用循环检测，发现与自身相连的实体组，以寻找紧密相连的子图，作为潜在欺诈账户的衡量标准
-
1.2.5. 最常见的寻路算法是最短路径算法，它计算两个顶点之间的最短路径
-
1.2.5.1. 无加权方法将所有路径视为相等的，根据所遍历的边数计算最短路径
1.2.5.1.1. 社交网络就是说明无加权最短路径算法有用的一个好例子
-
1.2.5.2. 加权方法为所有路径分配相对权重，然后在计算中使用这些权重
1.2.5.2.1. 当遍历边的相对成本不相等时，加权最短路径算法是一个很好的选择
1.2.5.2.2. 供应链优化
1.2.5.2.2.1. 移动货物的相对成本（距离/时间）是不相等的
1.2.5.2.3. 网络路由问题
1.2.5.2.3.1. 硬件或其他方面的原因（如地理邻近），连接之间传输网络数据包所需的时间也不同
-
1.2.6. 最常见的是Djkstra算法和A*搜索算法，它们都可用于加权图和无加权图
1.3. 中心性
1.3.1. 重要性一词来描述一个特定顶点在图整体结构中起的作用
1.3.2. 顶点重要性的具体含义根据特定算法所计算的内容而异
1.3.3. 每个方法都是定义重要性的完美有效方法，但计算每个方法都可能会产生不同的结果
-
1.3.4. 度数
1.3.4.1. 度数（degree）中心性是最容易理解的
1.3.4.2. 度数是指与一个顶点相关联的边的数量，因此度数中心性是基于边数对顶点进行排序的
1.3.4.3. 度数中心性可以通过分别测量内度和外度来进一步细分
1.3.4.4. 度数中心性通常用于确定图连接程度的基线，尤其是在计算平均值、最小值和最大值时
-
1.3.5. 间隙
1.3.5.1. 间隙（betweenness）中心性是指一个顶点在图中所有节点对之间的最短路径中被使用的次数
1.3.5.2. 间隙中心性在寻找连接不同顶点组的临界点方面很有效
1.3.5.3. 使用该算法时，返回的数越大，表示该顶点越重要。如果在
1.3.5.4. 如果在我们的社交网络中运行间隙中心性，就能发现谁与不同的社会群体有最多的联系
-
1.3.6. 亲密度
1.3.6.1. 亲密度（closeness）中心性是对从一个顶点到所有其他顶点的最短路径平均长度的度量，表示相对于所有其他顶点，哪些顶点位于最中心的位置
1.3.6.2. 使用亲密度数中心性时，返回值越小，说明该顶点越重要
1.3.6.3. 在我们的社交网络中运行亲密度中心性，就能识别出哪些人是社交网络的“核心”
-
1.3.7. 特征向量
1.3.7.1. 特征向量（eigenvector）中心性是一种复杂的中心性测量，使用相邻顶点的相对重要性作为输入来计算给定顶点的重要性
1.3.7.2. 仅凭一个顶点与许多其他顶点相连，并不一定能说明它很重要
1.3.7.3. 应该使用相邻顶点的重要性来计算该顶点的总体重要性
1.3.7.4. 在我们的社交网络中运行特征向量中心性，可以找到社交网络中最有影响力的人，他们不仅拥有最多的联系，而且这些联系很紧密
-
1.3.8. PageRank
1.3.8.1. PageRank是因为被Google的拉里·佩奇和谢尔盖·布林用于对搜索结果进行加权而出名的一种算法
1.3.8.2. 使用相邻顶点的相对重要性来帮助确定顶点的总体重要性
1.3.8.3. 包括一个衰减值（通常设置为0.85），以指示随着网络的遍历，影响会逐步衰减
1.3.8.4. 顶点的PageRank返回值越高，该顶点就越重要
1.3.8.5. 与特征向量中心性一样，如果在我们的社交网络中运行PageRank，结果将代表在社交网络中最有影响力的人
1.4. 群体检测
1.4.1. 群体检测（community detection）算法来发现相互紧密连接但与图中其他顶点松散连接的顶点组或群体
1.4.2. 群体检测算法不仅仅局限于社交网络，还被用于许多行业和用例
1.4.3. 与中心性算法一样，有大量潜在的群体检测算法，每个算法都以稍微不同的方式找到群体
-
1.4.4. 三角形计数
1.4.4.1. 计算图中三角形的数量称为三角形计数
1.4.4.2. 三角形计数在捕捉图中顶点网络的内聚性或紧密性方面很有用
1.4.4.3. 含紧密关联网络或社区的图具有较高的三角形计数
1.4.4.4. 包含松散连接网络的图具有较低的三角形计数
-
1.4.5. 连通分量
1.4.5.1. 在图论中，将每个顶点都有一条到所有其他顶点路径的子图称为分量
1.4.5.2. 连通分量在全局图中发现相关数据的集群，这有助于在社交图中查找家庭、查找有联系的组织或在电商网站中查找可能重复的账户
-
1.4.5.3. 弱连通分量算法
1.4.5.3.1. 算法没有考虑顶点之间边的方向
-
1.4.5.4. 强连通分量算法
1.4.5.4.1. 在本质上和弱连通分量是一样的，只是考虑了边的方向
1.4.5.4.2. 在强连通分量中，子图中任意两个顶点之间存在一对边，每个方向上都有一条边
1.4.5.4.3. 强连通分量算法来检测图中有方向性的高度连接群体
1.4.5.4.4. 经常用于在金融风控领域查找欺诈活动的中心
1.4.5.4.5. 经常用于在产品推荐中寻找相似的用户群体
1.5. 图和机器学习
1.5.1. 有讽刺意味的是，尽管许多ML技术严重依赖图来完成其学习，但这些技术既不允许将图作为输入，也不允许将图作为输出
-
1.5.2. 大多数标准的ML算法还是将固定向量或数据矩阵作为输入
1.5.2.1. 向量操作比在图上的类似操作更简单、更快
1.5.2.2. 可用的许多算法和工具都针对向量操作进行了优化
1.5.2.3. 很少有人将图作为输入数据来构建
-
1.5.3. 特征提取
1.5.3.1. 在ML中使用图的最简单方法是提取图的特征，以深入了解图中的数据
-
1.5.3.2. 最短路径
1.5.3.2.1. 取一个人和已知的不良行为者之间的最短路径，作为欺诈ML模型的预测度量
-
1.5.3.3. 三角形计数
1.5.3.3.1. 在社交网络中使用三角形计数来确定特定用户的社交性或反社交性
-
1.5.3.4. 度数
1.5.3.4.1. 使用顶点的连接度来确定传感器在传感器网络中的重要性
-
1.5.4. 图嵌入
-
1.5.4.1. 图嵌入是一种将图的稀疏多维结构表示为向量或矩阵的机制
1.5.4.1.1. 将稀疏数据转化为更紧凑的向量表示
1.5.4.2. 大部分研究是由自然语言处理（NLP）方面的工作推动的，但它现在被更普遍地应用于图中，为预测新的友谊和发现欺诈活动等任务提供输入
-
1.5.4.3. 顶点嵌入
1.5.4.3.1. 将每个顶点表示为一个向量/矩阵，用于比较顶点级别的项
-
1.5.4.4. 图嵌入
1.5.4.4.1. 将整张图/子图表示为一个向量/矩阵，用于对整张图进行相互比较
1.5.4.5. 挑战是确保我们包含的任何特征都能充分表示拓扑、连通性和其他图属性，同时最大限度地减小向量的大小
1.5.4.6. 更大的嵌入需要更多的处理时间和存储空间，但也保持了原始图数据的高保真度
-
1.5.5. 特征工程本身就是一门完整的学科
2. 其他资源
2.1. 图论
2.1.1. Sarada Herke的“Graph Theory Channel”
2.1.2. Richard J. Trudeau的Introduction to Graph Theory
2.1.3. Douglas B. West的《图论导引（第2版）》
2.2. 图数据库
2.2.1. Ian Robinson等人的《图数据库》
2.2.2. Denise Gosnell和Matthias Broecheler的The Practitioner's Guide to Graph Data
2.2.3. Kelvin R. Lawrence的PRACTICAL GREMLIN: An Apache TinkerPop Tutorial
2.2.4. Corey L. Lanum的Visualizing Graph Data
2.3. 图数据集
2.3.1. Stanford Network Analysis Project（SNAP）
2.3.2. Kaggle
2.3.3. Google Datasets
2.3.4. LDBC（Linked Data Bench Council）的The Social Network Benchmark（SNB)
2.4. 图算法
2.4.1. Tushar Roy的“Coding Made Simple, Graph Algorithms Playlist”
2.4.2. Algorithms Course的“Graph Theory Tutorial from a Google Engineer”
2.4.3. Alessandro Negro的Graph-Powered Machine Learning
2.4.4. Mark Needham和Amy E. Hodler的《数据分析之图算法：基于Spark和Neo4j》
