Neo4j，图算法最强总结！

Neo4j图数据库中包含很多的图相关的算法，并且可以在Neo4j中执行图算法。 此外Neo4j可以与RAG（Retrieval-Augmented Generation）的结合，将数据以节点和关系的形式组织起来，增强检索信息的深度和上下文关联性。

https://neo4j.com/docs/graph-data-science/current/algorithms/syntax/

unsetunset中心性算法unsetunset

在图论和网络分析中，中心性（Centrality）算法用于确定网络中不同节点的重要性。Neo4j的图数据科学（GDS）库包含了多种中心性算法，这些算法根据其质量层级被分组。

Article Rank

https://neo4j.com/docs/graph-data-science/current/algorithms/article-rank/

ArticleRank是一种PageRank算法的变体，用于衡量节点之间的传递性影响。PageRank算法基于这样一个假设：来自低度节点（即连接数较少的节点）的关系比来自高度节点（即连接数较多的节点）的关系具有更高的影响力。而ArticleRank则通过在每次迭代中降低发送给低度节点邻居的分数来降低低度节点的影响力。

ArticleRank的计算公式如下：

其中：

• 表示节点 的入站邻居（指向 的节点）。
• 表示节点 的出站邻居（从 出发的节点）。
• 是一个阻尼因子，取值范围在 [0, 1] 之间。
• 是平均出站度，即所有节点的平均出站边数。

ArticleRank算法的核心思想是，一个节点的重要性不仅取决于它被多少其他节点指向，还取决于指向它的节点的重要性。通过降低低度节点的影响力，ArticleRank算法能够更好地识别出网络中的关键节点，这些节点通常是网络中的核心或权威节点。

Articulation Points

https://neo4j.com/docs/graph-data-science/current/algorithms/articulation-points/

关节点（Articulation Points）是指移除该节点后会增加图的连通分量数量的节点。

Betweenness Centrality

https://neo4j.com/docs/graph-data-science/current/algorithms/betweenness-centrality/

Betweenness Centrality（介数中心性）是一种检测节点在图中信息流中影响力的方法。它常用于发现作为图一部分到另一部分的桥梁的节点。

该算法计算图中所有节点对之间的最短路径。每个节点根据通过该节点的最短路径数量获得一个分数。那些更频繁地位于其他节点之间最短路径上的节点将具有更高的介数中心性分数。

介数中心性适用于无权重或具有正权重的图。GDS实现基于Brandes的近似算法，用于未加权图。对于加权图，使用多个并发Dijkstra算法。该实现需要O(n + m)空间，并在O(n * m)时间内运行，其中n是图中节点的数量，m是关系的数量。

Bridges

https://neo4j.com/docs/graph-data-science/current/algorithms/bridges/

在图论中，桥（Bridge）是指在图中移除某条边后会增加连通分量数量的关系。等价地说，一条关系成为桥的条件是它不被包含在任何环中。

CELF

https://neo4j.com/docs/graph-data-science/current/algorithms/celf/

CELF算法基于问题的贪心算法。它通过k步迭代工作来创建返回的种子集S，在每一步中，将产生最大预期传播增益的节点添加到S中。

CELF算法通过引入懒惰转发机制扩展了贪心算法，该机制从被检查的节点中剪枝，从而大幅减少了进行的模拟数量。这使得CELF在大型网络上比贪心算法快得多。

Closeness Centrality

https://neo4j.com/docs/graph-data-science/current/algorithms/closeness-centrality/

介数中心性（Closeness Centrality）是一种检测图中能够有效传播信息的节点的方法。

介数中心性衡量一个节点到所有其他节点的平均距离（距离的倒数）。具有高介数分数的节点到所有其他节点的距离最短。

对于每个节点u，介数中心性算法计算它到所有其他节点的距离之和，基于计算所有节点对之间的最短路径。然后，将得到的总和取倒数，以确定该节点的介数中心性分数。

Degree Centrality

https://neo4j.com/docs/graph-data-science/current/algorithms/degree-centrality/

度中心性（Degree Centrality）算法用于在图中识别受欢迎的节点。度中心性衡量一个节点的入站或出站（或两者）关系的数量，这取决于关系投影的方向。

Eigenvector Centrality

https://neo4j.com/docs/graph-data-science/current/algorithms/eigenvector-centrality/

介数中心性（Eigenvector Centrality）算法是一种衡量节点传递影响力的方法。来自高分节点的关系对节点分数的贡献大于来自低分节点的连接。高介数分数意味着一个节点连接到许多自身得分高的节点。

Page Rank

https://neo4j.com/docs/graph-data-science/current/algorithms/page-rank/

PageRank算法是由谷歌创始人拉里·佩奇和谢尔盖·布林在最初的谷歌论文中提出的，用于衡量图中每个节点的重要性，这个重要性基于指向该节点的关系数量以及相应源节点的重要性。PageRank的基本假设是：一个页面的重要性仅取决于链接到它的其他页面的重要性。

Harmonic Centrality

https://neo4j.com/docs/graph-data-science/current/algorithms/harmonic-centrality/

调和中心性（Harmonic Centrality），也称为值中心性，是介数中心性的一种变体，旨在解决原始介数中心性公式在处理不连通图时遇到的问题。与许多中心性算法一样，它起源于社会网络分析领域。

HITS

https://neo4j.com/docs/graph-data-science/current/algorithms/hits/

Hyperlink-Induced Topic Search（HITS）算法是一种链接分析算法，它根据两个分数对节点进行评级：枢纽分数（Hub Score）和权威分数（Authority Score）。权威分数估计节点在网络中的重要性，而枢纽分数估计其与其他节点关系的价值。

unsetunset社区检测算法unsetunset

社区检测（Community Detection）算法用于评估节点如何被聚集或分割成不同的群组，以及这些群组加强或分裂的倾向。

Conductance metric

https://neo4j.com/docs/graph-data-science/current/algorithms/conductance/

导电度（Conductance）是一个用于评估社区检测质量的度量指标。在社区C中，节点之间的关系可以指向社区内部或社区外部。导电度是指向社区外部的关系与社区C中总关系数的比率。导电度越低，表示社区越“紧密”。

K-Core Decomposition

https://neo4j.com/docs/graph-data-science/current/algorithms/k-core/

K-Core分解是一种基于图的度序列和拓扑结构将图中节点分组成不同群组的过程。i-Core是指原始图中的一个最大子图，该子图中每个节点的度至少为i。最大性确保不可能找到另一个度属性成立的更大子图。

K-1 Coloring

https://neo4j.com/docs/graph-data-science/current/algorithms/k1coloring/

K-1 Coloring算法，也称为图着色问题，旨在为图中的每个节点分配颜色，同时优化两个目标：确保给定节点的每个邻居都有与该节点本身不同的颜色；使用尽可能少的颜色。

K-Means Clustering

https://neo4j.com/docs/graph-data-science/current/algorithms/kmeans/

K-Means聚类是一种无监督学习算法，用于解决聚类问题。它通过一个简单的程序将给定的数据集分类到由参数k定义的多个簇中。

Label Propagation

https://neo4j.com/docs/graph-data-science/current/algorithms/label-propagation/

标签传播算法（LPA）是一种快速的图社区发现算法。它仅依赖于网络结构来检测社区，不需要预定义的目标函数或关于社区的先验信息。

Leiden

https://neo4j.com/docs/graph-data-science/current/algorithms/leiden/

Leiden算法是一种用于在大型网络中检测社区的算法。该算法将节点分离成不相交的社区，以最大化每个社区的模块度得分。模块度量化了节点分配到社区的质量，即社区内节点的连接密度与它们在随机网络中的连接密度相比如何。

Local Clustering Coefficient

https://neo4j.com/docs/graph-data-science/current/algorithms/local-clustering-coefficient/

本地聚类系数算法计算图中每个节点的本地聚类系数。节点n的本地聚类系数Cn描述了n的邻居之间也相互连接的可能性。计算Cn时，我们使用节点参与的三角形数量Tn和节点的度数dn。

Louvain

https://neo4j.com/docs/graph-data-science/current/algorithms/louvain/

Louvain方法是一种用于在大型网络中检测社区的算法。它为每个社区最大化一个模块度得分，其中模块度量化了节点分配到社区的质量。这意味着评估社区内节点的连接密度与它们在随机网络中的连接密度相比如何。

Modularity metric

https://neo4j.com/docs/graph-data-science/current/algorithms/modularity/

模块度（Modularity）是一个用于评估社区检测质量的度量指标。在社区C中，节点之间的关系可以指向社区内部或社区外部。具有高模块度的图在社区内部节点之间有密集的连接，但在不同社区的节点之间连接稀疏。

Modularity Optimization

https://neo4j.com/docs/graph-data-science/current/algorithms/modularity-optimization/

模块度优化算法旨在基于图的模块度来检测社区。模块度是衡量图结构的一个指标，它测量模块或社区内部的连接密度。具有高模块度得分的图将在社区内部有许多连接，但只有少数指向其他社区的连接。该算法将探索每个节点，如果它将其社区更改为其中一个邻近节点的社区，其模块度得分是否会增加。

Strongly Connected Components

https://neo4j.com/docs/graph-data-science/current/algorithms/strongly-connected-components/

强连通分量算法用于在有向图中找到最大连接节点集。一个集合被视为强连通分量，如果集合内每对节点之间都有一条有向路径。该算法通常在图分析过程中早期使用，以帮助我们了解图的结构。

Triangle Count

https://neo4j.com/docs/graph-data-science/current/algorithms/strongly-connected-components/

三角形计数算法计算图中每个节点的三角形数量。三角形是一组三个节点，其中每个节点都与其他两个节点有直接的关系。在图论术语中，这有时被称为3-团。

Weakly Connected Components

https://neo4j.com/docs/graph-data-science/current/algorithms/wcc/

弱连通分量算法用于在有向和无向图中找到相互连接的节点集。如果两个节点之间存在路径，则它们被认为是连接的。所有相互连接的节点集合构成了一个分量。与强连通分量（Strongly Connected Components, SCC）不同，弱连通分量不考虑两个节点之间路径上关系的方向。例如，在有向图中，即使没有直接的关系(b)→(a)，节点a和b也会处于同一个分量中，只要存在路径(a)→(b)。

Approximate Maximum k-cut

https://neo4j.com/docs/graph-data-science/current/algorithms/approx-max-k-cut/

近似最大k割算法是图分割问题的一种，其目标是将图中的节点分配到k个不相交的社区中，使得不同社区间的关系总权重最大化。换句话说，最大k割是寻找一种k分割，使得源节点和目标节点被分配到不同社区的关系的权重之和最大。

Speaker-Listener Label Propagation

https://neo4j.com/docs/graph-data-science/current/algorithms/sllpa/

演讲者-听众标签传播算法（SLLPA）是标签传播算法的一个变体，能够检测每个节点的多个社区归属。在每次迭代中，节点（演讲者）可以将其标签传播给邻居节点（听众），如果听众节点的标签尚未确定或演讲者节点的标签更有影响力。

unsetunset相似性算法unsetunset

相似性算法计算基于节点的邻域或属性的节点对之间的相似度。可以采用多种相似性度量标准来计算相似度得分。

Node Similarity

https://neo4j.com/docs/graph-data-science/current/algorithms/node-similarity/

节点相似性算法通过比较节点连接的节点集来比较一组节点。如果两个节点共享许多相同的邻居，则它们被认为是相似的。节点相似性计算基于以下相似性度量：

1. Jaccard相似性度量：也称为Jaccard相似性分数，用于计算两个节点集合的交集与并集的比例。
2. Overlap系数：也称为Szymkiewicz–Simpson系数，用于计算两个节点集合的交集与较小集合的大小的比例。
3. 余弦相似性度量：用于计算两个节点集合的向量表示的夹角的余弦值，通常与加权输入相关。

Filtered Node Similarity

https://neo4j.com/docs/graph-data-science/current/algorithms/filtered-node-similarity/

过滤节点相似性算法是节点相似性算法的扩展，它增加了对源节点、目标节点或两者的过滤支持。

节点过滤通过减少算法产生结果的节点空间来优化相似性计算：

1. 源节点过滤：如果指定了源节点过滤条件，只有匹配这些条件的节点才会被视为相似性计算的起点。
2. 目标节点过滤：如果指定了目标节点过滤条件，只有匹配这些条件的节点才会被视为相似性计算的终点。
3. 结果影响：考虑两个相似性结果：A = (alice)-[:SIMILAR_TO]→(bob) 和 B = (bob)-[:SIMILAR_TO]→(alice)。如果(alice)节点匹配源节点过滤条件，且(bob)节点匹配目标节点过滤条件，则会产生结果A。如果(alice)节点不匹配目标节点过滤条件，或(bob)节点不匹配源节点过滤条件，则不会生成结果B。

K-Nearest Neighbors

https://neo4j.com/docs/graph-data-science/current/algorithms/knn/

K-最近邻算法计算图中所有节点对之间的距离值，并为每个节点创建与其k个最近邻居之间的新关系。距离的计算基于节点属性。

Filtered K-Nearest Neighbors

https://neo4j.com/docs/graph-data-science/current/algorithms/knn/

过滤K-最近邻算法是K-最近邻算法的扩展，它增加了对源节点、目标节点或两者的过滤功能。

• 源节点过滤：限制可以作为源节点的节点集合或节点类型。这是源节点过滤。你想要从这些特定节点或特定类型的节点起源的最佳得分关系。
• 目标节点过滤：类似于源节点，有时你想要限制可以作为目标节点的节点集合或节点类型，即目标节点过滤。对于给定的源节点，目标节点来自一个集合或一个类型的最佳得分关系。

unsetunset路线查找算法unsetunset

路径查找算法用于发现两个或多个节点之间的路径，或者评估路径的可用性和质量。

Delta-Stepping Single-Source Shortest Path

https://neo4j.com/docs/graph-data-science/current/algorithms/delta-single-source/

增量步进最短路径算法计算源节点与图中所有可达节点之间的所有最短路径。该算法支持具有正关系权重的加权图。要计算源节点和单个目标节点之间的最短路径，可以使用Dijkstra源-目标算法。

A* Shortest Path

https://neo4j.com/docs/graph-data-science/current/algorithms/astar/

A（读作“A-Star”）最短路径算法用于计算两个节点之间的最短路径。A是一种启发式搜索算法，它使用启发式函数来指导图的遍历。该算法支持具有正关系权重的加权图。

与Dijkstra最短路径算法不同，A*算法选择下一个要搜索的节点不仅仅基于已经计算出的距离。相反，算法将已经计算出的距离与启发式函数的结果结合起来。该函数接受一个节点作为输入，并返回一个值，该值对应于从该节点到达目标节点的成本。在每次迭代中，图遍历从具有最低组合成本的节点继续。

Yen’s Shortest Path

https://neo4j.com/docs/graph-data-science/current/algorithms/yens/

Yen's Shortest Path算法用于计算两个节点之间的多条最短路径。该算法通常被称为Yen's k-Shortest Path算法，其中k是要计算的最短路径的数量。该算法支持具有正关系权重的加权图。在计算多条最短路径时，它还考虑了同一对节点之间的并行关系。

Bellman-Ford Single-Source Shortest Path

https://neo4j.com/docs/graph-data-science/current/algorithms/bellman-ford-single-source/

与仅适用于非负权重图的Dijkstra算法不同，Bellman-Ford算法也能处理包含负权重的图，前提是源节点不能到达任何涉及负权重循环的节点。图中的循环是一条起点和终点相同的路径。负权重循环是指关系权重之和为负的循环。当存在负权重循环时，最短路径不易被定义，因为我们可以多次遍历负权重循环，每次都能得到更小的成本。

unsetunset节点嵌入算法unsetunset

节点嵌入（Node Embedding）算法计算图中节点的低维向量表示。这些向量，也称为嵌入（embeddings）。

FastRP

https://neo4j.com/docs/graph-data-science/current/machine-learning/node-embeddings/fastrp/

快速随机投影（FastRP）是一种节点嵌入算法，属于随机投影算法家族。这些算法理论上由Johnson-Lindenstrauss引理支持，该引理指出，可以将任意维度的n个向量投影到O(log(n))维空间中，同时仍然近似保持点之间的成对距离。

GraphSAGE

https://neo4j.com/docs/graph-data-science/current/machine-learning/node-embeddings/graph-sage/

GraphSAGE（Graph Sample and Aggregation based on Eigenvector）是一种用于计算节点嵌入的归纳算法。GraphSAGE利用节点特征信息来为未见过的节点或图生成节点嵌入。与传统的为每个节点训练单独嵌入的方法不同，GraphSAGE算法学习一个函数，通过采样和聚合节点的局部邻域特征来生成嵌入。

Node2Vec

https://neo4j.com/docs/graph-data-science/current/machine-learning/node-embeddings/node2vec/

Node2Vec是一种节点嵌入算法，它基于图中的随机游走计算节点的向量表示。该算法通过随机游走采样节点的邻域，并利用这些样本训练一个单隐藏层的神经网络。神经网络的目标是预测在随机游走中一个节点出现的概率，基于另一个节点的出现情况。

HashGNN

https://neo4j.com/docs/graph-data-science/current/machine-learning/node-embeddings/hashgnn/

HashGNN是一种节点嵌入算法，它类似于图神经网络（Graph Neural Networks, GNNs），但不包括模型或需要训练。GNNs的神经网络被随机哈希函数所取代，这与min-hash局部敏感哈希的思想相似。因此，HashGNN结合了GNNs和快速随机算法的思想。

unsetunset拓扑链接预测算法unsetunset

拓扑链接预测算法（Topological link prediction ）通过使用图的拓扑结构来确定节点对之间的接近程度。计算出的分数随后可以用来预测它们之间的新关系。

Adamic Adar

https://neo4j.com/docs/graph-data-science/current/algorithms/linkprediction/

Adamic Adar算法是一种基于节点共享邻居来计算节点间亲密度的度量方法。这个算法在2003年由Lada Adamic和Eytan Adar提出，用于预测社交网络中的链接。

Common Neighbors

https://neo4j.com/docs/graph-data-science/current/alpha-algorithms/common-neighbors/

共同邻居算法是一种基于节点共享邻居来计算节点间亲密度的度量方法。这个概念捕捉了这样一个观点：有两个共同朋友的陌生人比没有共同朋友的陌生人更有可能被介绍认识。

Preferential Attachment

https://neo4j.com/docs/graph-data-science/current/alpha-algorithms/preferential-attachment/

优先连接算法是一种基于节点共享邻居来计算节点间亲密度的度量方法。这个概念意味着一个节点的连接数越多，它就越有可能接收到新的链接。这个算法由Albert-László Barabási和Réka Albert在他们的无标度网络研究中推广。

Resource Allocation

https://neo4j.com/docs/graph-data-science/current/alpha-algorithms/resource-allocation/

资源分配算法是一种基于节点共享邻居来计算节点间亲密度的度量方法。这个算法由Tao Zhou、Linyuan Lü和Yi-Cheng Zhang在2009年作为预测各种网络中链接的研究的一部分引入。

Same Community

https://neo4j.com/docs/graph-data-science/current/alpha-algorithms/same-community/

同社区算法是一种确定两个节点是否属于同一社区的方法。这些社区可以通过使用社区检测算法来计算。如果两个节点属于同一个社区，那么它们之间在未来更有可能存在关系，如果目前还没有的话。

转自：coggle数据科学