盘点Neo4j中的15种不同图表算法及其功能

【IT168 技术】图表分析在企业决策中能够发挥极大的价值，而好的图形算法不仅易于使用，执行速度快，而且能够产生强大的结果。Neo4j包含一个不断增长的开放式高性能图形算法库，可以揭示连接数据中的隐藏模式和结构。

本文将为大家介绍Neo4j中提供的诸多图算法以及它们的功能。使用Neo4j图形算法，用户可以建模并预测复杂的动态特性，例如资源或信息的流动，传染或网络故障传播的途径，以及组的影响和弹性。

由于Neo4j是将原生图平台中的分析和事务操作结合在一起，用户不仅可以揭示真实世界系统的内在本质，还可以更快地开发和部署基于图形的解决方案，并具有易于使用、简化的工作流程。

遍历和寻路算法

1.广度优先算法(BFS)

做什么：遍历树数据结构，探索最近的邻居和他们的次级邻居。它用于定位连接，是许多其他图算法的前身。

当树较不平衡或目标更接近起点时，BFS是首选。它也可用于查找节点之间的最短路径或避免深度优先搜索的递归过程。

如何使用：广度优先搜索可用于定位像BitTorrent等对等网络中的邻居节点，GPS系统可精确定位附近的位置，社交网络服务可在特定距离内查找人员。

2.深度优先算法(DFS)

做什么：遍历树数据结构，通过在回溯之前尽可能探索每个分支。用于深层次的数据，是许多其他图算法的前身。当树较平衡或目标更接近端点时，深度优先搜索是首选。

如何使用：深度优先算法通常用于游戏模拟，其中每个选择或动作引发另一个操作，从而扩展成可能性的树形图。它将遍历选择树，直到找到最佳解决方案路径(即胜利)。

3.单源最短路径

做什么：计算节点与所有其他节点之间的路径，以及其与所有其他节点的总和值(成本，距离，时间或容量等关系的权重)并得出总和最小。

如何使用：单源最短路径通常用于自动获取物理位置之间的路线，例如通过Google地图获取驾车路线。在逻辑路由中也很重要，例如电话呼叫路由(最低成本路由)。

4.全源最短路径

做什么：计算包含图中节点之间所有最短路径的最短路径森林(组)。当最短路径被阻塞或变得次优时，切换到新的最短路径，通常用于备用路由。

如何使用：用于评估备用路由，例如高速公路备份或网络容量。它也是为逻辑路由提供多路径的关键，比如呼叫路由选择。

5.最小生成树(MWST)

做什么：计算与访问树中所有节点相关的最小值(如成本，时间或容量等关系的权重)的路径，用于逼近一些NP难题，如旅行商问题和随机或迭代舍入。

如何使用：最小生成树广泛用于网络设计：成本最低的逻辑或物理路由，如铺设电缆，最快的垃圾收集路线，供水系统容量，高效电路设计等等。它还可用于滚动优化的实时应用程序，如化学炼油厂的过程或行驶路线修正。

Centrality Algorithms

6. PageRank

做什么：估计当前节点对其相邻节点的重要性，然后再从其邻居那里获得节点的重要性。一个节点的排名来源于其传递链接的数量和质量。PageRank虽然被谷歌抛弃了，但它还是被广泛认为是检测任何网络中有影响力的节点的常用方式。

如何使用：PageRank用于评估重要性和影响力，经常的用法是推荐推特账户以及一般的情绪分析。

PageRank也用于机器学习，以确定最有影响的提取特征。在生物学中，它被用来识别食物网中哪些物种的灭绝会导致物种死亡的最大连锁反应。

7. Degree Centrality

做什么：测量节点(或整个图表)所具有的关系数量，被分为流入和流出两个方向，关系具有指向性。

如何使用：Degree Centrality着眼于用途的直接连通性，例如评估患者接近病毒或听取信息的近期风险。在社会研究中，可以用来预估人气或者其它情感。

8. Closeness Centrality

做什么：衡量一个节点对其集群内所有邻居的集中程度。假定到所有其他节点的路径都是最短的，那么该节点就能够以最快的速度到达整个组。

如何使用：Closeness Centrality适用于多种资源、交流和行为分析，尤其是当交互速度显着时。

在新公共服务中，被用于确定最大可访问性的位置。

在社交网络分析中，用于找到具有理想社交网络位置的人，以便更快地传播信息。

9. Betweenness Centrality

做什么：测量通过节点的最短路径的数量(首先通过广度优先算法找到)。出现在最短路径上次数最多的节点具有较高的介数中心性，并且是不同集群之间的桥梁。它通常与控制资源和信息的流动有关。

如何使用：Betweenness Centrality适用于网络科学中的各种问题，用于查明通信和交通网络中的瓶颈或可能的攻击目标。在基因组学中，被用于了解控制某些基因在蛋白质网络中的改进，例如更好的药物/疾病靶向。

Betweenness Centrality也被用来评估多人在线游戏玩家和共享医师专业知识的信息流。

社区发现算法

这个类别也被称为聚类算法或分区算法。

10. Label Propagation

做什么：基于邻域多数的标签作为推断集群的手段。这种极其快速的图形分割需要很少的先验信息，并且被广泛地应用于大规模的社区检测网络中。这是理解图组织的一个关键方法，通常是其他分析的主要步骤。

如何使用：Label Propagation具有不同的应用，例如了解社会团体中的共识形成、识别在生物网络的过程(功能模块)中所涉及的蛋白质集合等等。甚至还可以用于半监督和无监督的机器学习作为初始的预处理步骤。

11. Strongly Connected

做什么：定位节点组，其中每个节点可从同一组中的所有其他节点按照关系的方向到达，常被应用于深度优先算法。

如何使用：Strongly Connected通常用于在识别的集群上独立运行其他算法。作为有向图的预处理步骤，它有助于快速识别不连通的集群。

在零售推荐中，它有助于识别具有强亲和性的组，然后将向那些尚未购买商品的群体推荐首选商品。

12. Union-Find/Connected Components/Weakly Connected

做什么：查找节点组，其中每个节点可从同一组中的任何其他节点到达，而不考虑关系的方向。它提供几乎恒定的时间操作(独立于输入大小)来添加新的组，合并现有的组，并确定两个节点是否在同一组中。

如何使用：Union-find/connected 经常与其他算法结合使用，特别是对于高性能分组。作为无向图的预处理步骤，它有助于快速识别断开的组。

13. Louvain Modularity

做什么：通过比较它的关系密度与适当定义的随机网络来测量社团分组的质量(即假定的准确性)。它通常用于评估复杂网络的组织和社区层次结构。这对于无监督机器学习中的初始数据预处理也是有用的。

如何使用：Louvain用于评估Twitter，LinkedIn和YouTube上的社交结构;用于欺诈分析，以评估一个组织是只存在一些不良行为，还是背后一个连环欺诈。Louvain在比利时电信网络中揭示了一个六级客户层级。

14. Local Clustering Coefficient/Node Clustering Coefficient

做什么：对于一个特定的节点，量化了其到邻居节点的距离， (每个节点都直接连接到其他节点)。例如，如果您的所有朋友都直接了解对方，那么您的本地集群系数将是1。集群的小值表明尽管存在一个分组，但节点之间并没有紧密连接。

如何使用：Local cluster coefficient通过理解群体相关性或碎片化的可能性，对估计弹性具有重要意义。用这种方法对欧洲电网的分析发现，与稀疏连接的节点相比，集群更能抵御普遍的故障。

15. Triangle-Count and Average Clustering Coefficient

做什么：测量有多少节点具有三角形以及节点倾向于聚集在一起的程度。平均聚类系数为1时表明有一个分组，0时没有连接。为使聚类系数有意义，它应该明显高于网络中所有关系随机的版本。

如何使用：平均聚类系数通常用于估计网络是否可能展现基于紧密集群的“小世界”行为。这也是集群稳定性和弹性的一个因素。流行病学家使用平均聚类系数来帮助预测不同社区的各种感染率。

结论

世界是由关系驱动的，而Neo4j图形分析揭示了图形背后的意义，希望这些优化的图形算法能够帮助你以更加有意义、更有效的方式来理解所连接的数据。