点 击 蓝 字 关 注， 一 起 品 味 图 世 界 
图分析只有在您具有使用技巧并能够为您快速提供所需见解时才具有价值。因此，最佳的图算法一定：易于使用、快速执行以及产生强大的结果。Neo4j包含一个不断增长的开放式高性能图算法库，它可以揭示连接数据中的隐藏模式与结构。

使用Neo4j图算法，您将能够理解、建模和预测复杂的动态。例如：资源或信息的流动，传染病或网络故障蔓延的途径，以及对群组的影响和弹性。
Neo4j将原生图平台中的分析和事务操作结合在一起，不仅可以揭示真实世界系统的内在本质以形成新的发现，还可以更快地开发和部署基于图的解决方案，以及具有易用的、简化的工作流程。
以下是Neo4j在其图分析平台中使用的15种核心算法以及它们作用说明。
01
—
遍历与寻路算法
1. 并行广度优先搜索
描述：遍历树数据结构，通过扇出探索最近的邻居和他们的次级邻居。用于定位连接，是许多其他图算法的前身。当树较不平衡或目标更接近起点时，BFS是首选。它也可用于查找节点之间的最短路径，或避免深度优先搜索的递归过程。
应用：广度优先搜索可用于在像BitTorrent这样对等网络中定位邻居节点，在GPS系统中精确定位附近的位置，在社交网络服务中在特定距离内查找人员。
2. 并行深度优先搜索描述：通过在回溯之前尽可能探索每个分支来遍历树数据结构。它用于深层次的数据，是许多其他图算法的前身。当树较平衡或目标更接近端点时，深度优先搜索是首选。
应用：深度优先搜索通常用于游戏模拟中，其中每个选择或动作都会导致另一个选择或动作，并扩展为可能性的树状图。深度优先搜索将遍历选择树，直到发现最佳解决方案路径（比如获胜）。
3. 单源最短路径描述：计算一个节点和所有其他节点之间的路径，以使得连接两个节点之间的所有关系的权重总和最小。例如：成本、距离、时间或容量等。
应用：单源最短路径通常用于自动获取物理位置之间的路线，例如通过Google地图的查找行车路线。在逻辑路由中也很重要，例如：电话路由（最低成本路由）。
4. 全源最短路径描述：计算图中所有节点之间的最短路径，组成一个最短路径森林。当最短路径被阻塞或变为次优路径时，用于获取备用路由。
应用：全源最短路径用于评估备用路由，以解决诸如高速公路备用或网络容量之类的情况。这也是提供多种路径的逻辑路由的关键，例如：呼叫路由选择。
5. 最小权重生成树描述：计算遍历所有节点的树状结构路径，使路径中所有关系的权重之和为最小值。例如：成本、时间或容量。它也可以用来估计一些NP难题，例如：旅行商问题、随机或迭代舍入（Randomized or Iterative Rounding）。
应用：最小权重生成树广泛用于网络设计：成本最低的逻辑或物理路由，如铺设电缆；最快的垃圾收集路线；供水系统的容量；高效的电路设计等等。还可用于滚动优化实时应用，例如：化学精炼厂的流程或行驶路线校正。
02
—
中心性算法
6. 网页排名算法描述：从当前节点的邻居，和邻居的邻居评估当前节点的重要性。节点的等级是根据其传递链接的数量和质量来估算影响力的。虽然已被Google抛弃，但还是被广泛认为是检测任何网络中有影响力的节点的常用方式。
应用：PageRank在很多方面用于评估重要性和影响力，通常用于推荐Twitter账户以及一般情绪分析。还用于机器学习中，以识别和提取最具影响力的特征。在生物学中，它被用来识别食物网中哪些物种灭绝会导致物种死亡的最大连锁反应。
7. 度中心性算法描述：测量节点（或整个图）所具有的关系数量，当关系具有方向时，又被分为入度（流入）和出度（流出）。
应用：度中心性着眼于直接连通性，例如用于评估患者感染病毒或听力信息的近期风险。在社会研究中，朋友关系的入度可以用来评估人气（Popularity），而出度可以用来评估合群性（Gregariousness）。
8. 紧度中心性算法描述：衡量一个节点对其集群内所有邻居的中心程度。假定到所有其他节点的路径都是最短的，那么该节点就能够以最快的速度到达整个群组。
应用：紧密度中心性适用于多种资源、交流和行为分析，特别是在互动速度显着的情况下。它已被用来识别新公共服务的最佳位置，以实现最大的可访问性。在社交网络分析中，已被用于查找具有理想社交网络位置的人员，以便更快地传播信息。
9. 介数中心性算法描述：测量通过节点的最短路径的数量（首先通过广度优先算法找到）。出现在最短路径上次数最多的节点具有最高的介数中心性，是不同集群之间的桥梁。它通常控制着资源和信息的流动。
应用：介数中心性适用于网络科学中的各种问题，用于查明通信和交通网络中的瓶颈或可能的攻击目标。在基因组学中，被用于了解控制某些基因在蛋白质网络中的改进，例如更好的药物/疾病靶向。介数中心性也被用来评估多人在线游戏玩家以及医师专业知识共享社区的信息流。
03
—
社区发现算法
这个类别也被称为聚类算法或分区算法。10. 标签传播算法描述：基于邻域多数的标签传播，作为推断集群的手段。这种极其快速的图分割需要很少的先验信息，广泛应用于大规模网络的社区检测。这是理解图组织的一个关键方法，通常是其他分析的主要步骤。
应用：标签传播的应用范围很广，从了解社会社区的共识形成，到识别在生化网络过程（功能模块）中共同参与的蛋白质组。它还用于在半监督和无监督机器学习中作为一个初始的预处理步骤。
11. 强连通算法描述：根据关系的方向，找到一组节点，其中每个节点都可从组中的其他节点到达。通常是从深度优先搜索中应用。
应用：强连通常用于在已识别的集群上启用并独立运行其他算法。作为有向图的预处理步骤，它有助于快速识别不连通的集群。在零售推荐中，它有助于识别具有强亲和性的组，然后将向那些尚未购买商品的群体推荐首选商品。
12. 并查集/连通分量/弱连通描述：查找节点组，其中每个节点都可以从同一组中的任何其他节点到达，而不考虑关系的方向。它提供近乎恒定时间的操作（与输入大小无关）来添加新的组、合并现有组以及确定两个节点是否位于同一组中。
应用：并查集/联通分量通常与其他算法结合使用，特别是对于高性能分组。作为无向图的预处理步骤，它有助于快速识别断开的组。
13. Louvain 模块度描述：通过将社区关系密度与适当定义的随机网络进行比较来衡量社区分组的质量（即假定的准确性）。它通常用于评估复杂的网络和社区层次结构的组织。在无监督机器学习中对初始数据预处理也很有用。
应用：Louvain用于评估Twitter、LinkedIn和YouTube中的社交结构。在欺诈分析中，以评估一个组织是只存在一些不良行为，还是背后一个连环欺诈。Louvain在比利时电信网络中揭示了一个六级客户层级。
14. 局部集聚系数/节点聚类系数描述：对于特定节点，它量化其邻居与集团（每个节点都直接与其他每个节点相连）之间的距离。例如，如果您所有的朋友都直接认识，则您的局部聚类系数将为1。聚类的较小值表示尽管存在分组，但节点之间的连接并不紧密。
应用：局部聚类系数通过理解群体相关性或碎片化的可能性，对估计弹性具有重要意义。用这种方法对欧洲电网的分析发现，具有稀疏连通节点的集群对广泛的故障具有更强的适应性。
15. 三角计数和平均聚类系数描述：
测量多少个节点具有三角形以及节点趋于聚集在一起的程度。有集团时，平均聚类系数为1；没有任何连接时，则为0。为使聚类系数有意义，它应该明显高于网络中所有关系随机打乱的版本。
应用：平均聚类系数通常用于估计网络是否可能展现基于紧密集群的“小世界”行为。这也是集群稳定性和弹性的一个因素。流行病学家已经使用平均聚类系数来帮助预测不同社区的各种感染率。
小  结
世界是由关系驱动的。Neo4j 图分析使用实用、优化的图算法揭示了关系的含义。希望这些算法能够帮助您以更有意义和更有效的方式理解连接的数据。
本文由品图汇整理翻译。原文链接：
https://neo4j.com/blog/graph-algorithms-neo4j-15-different-graph-algorithms-and-what-they-do/
长 按 关 注 品 图 汇

我知道 你在看