PageRank

定向

无向

异构节点

异构关系

加权关系

词汇表

定向: 定向特征。该算法在有向图上定义良好。
定向: 定向特征。该算法忽略图的方向。
定向: 定向特征。该算法不在有向图上运行。
无向: 无向特征。该算法在无向图上定义良好。
无向: 无向特征。该算法忽略图的无向性。
异构节点: 异构节点全面支持。该算法能够区分不同类型的节点。
异构节点: 异构节点允许。该算法将所有选定的节点视为相似，而不考虑其标签。
异构关系: 异构关系全面支持。该算法能够区分不同类型的关系。
异构关系: 异构关系允许。该算法将所有选定的关系视为相似，而不考虑其类型。
加权关系: 加权特征。该算法支持将关系属性用作权重，通过 relationshipWeightProperty 配置参数指定。
加权关系: 加权特征。该算法将每个关系视为同等重要，丢弃任何关系权重的值。

简介

PageRank 算法根据传入关系的数量和相应源节点的重要性，衡量图中每个节点的重要性。基本假设大致来说是，一个页面只有在其链接到它的页面的重要性才能获得重要性。

PageRank 在最初的谷歌论文中被引入，作为一个解决以下方程的函数

其中，

我们假设页面 A 有页面 T₁ 到 T_n 指向它。
d 是一个阻尼因子，可以设置在 0（包含）和 1（不包含）之间。通常设置为 0.85。
C(A) 定义为从页面 A 出去的链接数量。

此方程用于迭代更新候选解并得出与该方程相同近似解。

有关此算法的更多信息，请参阅

运行此算法需要足够的内存可用性。在运行此算法之前，我们建议您阅读内存估计。

注意事项

在使用 PageRank 算法时，有一些事项需要注意。

如果一组页面内部没有到该组外部的关系，则该组被视为蜘蛛陷阱。
当一组页面形成无限循环时，可能会出现排名汇集。
死胡同出现在页面没有外向关系时。

更改阻尼因子可以帮助解决上述所有注意事项。它可以解释为网络冲浪者有时跳到随机页面的概率，因此不会陷入汇集。

语法

本节介绍在每种执行模式下执行 PageRank 算法所使用的语法。我们正在描述命名的图变体语法。要了解有关一般语法变体的更多信息，请参阅语法概述。

每种模式的 PageRank 语法

在命名图上以流模式运行 PageRank。

CALL gds.pageRank.stream(
  graphName: String,
  configuration: Map
)
YIELD
  nodeId: Integer,
  score: Float

表 1. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	用于算法特定和/或图过滤的配置。

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。包含具有给定标签的任何节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。包含具有给定类型的任何关系。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
dampingFactor	浮点数	`0.85`	是	Page Rank 计算的阻尼因子。必须在 [0, 1) 内。
maxIterations	整数	`20`	是	要运行的 Page Rank 迭代的最大次数。
tolerance	浮点数	`0.0000001`	是	迭代之间分数的最小变化。如果所有分数的变化都小于容差值，则结果被认为是稳定的，并且算法返回。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性的名称。如果未指定，算法将不加权运行。
sourceNodes	节点或数字列表	`[]`	是	用于计算个性化 Page Rank 的节点或节点 ID。
scaler	字符串或映射	`None`	是	应用于最终分数的缩放器的名称。支持的值为 `None`、`MinMax`、`Max`、`Mean`、`Log` 和 `StdScore`。要应用特定于缩放器的配置，请使用映射语法：`{scaler: 'name', …}`。

表 3. 结果
名称	类型	描述
nodeId	整数	节点 ID。
score	浮点数	PageRank 分数。

在命名图上以统计模式运行 PageRank。

CALL gds.pageRank.stats(
  graphName: String,
  configuration: Map
)
YIELD
  ranIterations: Integer,
  didConverge: Boolean,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  centralityDistribution: Map,
  configuration: Map

表 4. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	用于算法特定和/或图过滤的配置。

表 5. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。包含具有给定标签的任何节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。包含具有给定类型的任何关系。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
dampingFactor	浮点数	`0.85`	是	Page Rank 计算的阻尼因子。必须在 [0, 1) 内。
maxIterations	整数	`20`	是	要运行的 Page Rank 迭代的最大次数。
tolerance	浮点数	`0.0000001`	是	迭代之间分数的最小变化。如果所有分数的变化都小于容差值，则结果被认为是稳定的，并且算法返回。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性的名称。如果未指定，算法将不加权运行。
sourceNodes	节点或数字列表	`[]`	是	用于计算个性化 Page Rank 的节点或节点 ID。
scaler	字符串或映射	`None`	是	应用于最终分数的缩放器的名称。支持的值为 `None`、`MinMax`、`Max`、`Mean`、`Log` 和 `StdScore`。要应用特定于缩放器的配置，请使用映射语法：`{scaler: 'name', …}`。

表 6. 结果
名称	类型	描述
ranIterations	整数	运行的迭代次数。
didConverge	布尔值	指示算法是否收敛。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算 `centralityDistribution` 的毫秒数。
centralityDistribution	映射	包含最小值、最大值、平均值以及中心值 p50、p75、p90、p95、p99 和 p999 百分位的映射。
configuration	映射	用于运行算法的配置。

在命名图上以变异模式运行 PageRank。

CALL gds.pageRank.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  nodePropertiesWritten: Integer,
  ranIterations: Integer,
  didConverge: Boolean,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  mutateMillis: Integer,
  centralityDistribution: Map,
  configuration: Map

表 7. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	用于算法特定和/或图过滤的配置。

表 8. 配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`n/a`	否	GDS 图中将分数写入其中的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松地跟踪算法进度的 ID。
dampingFactor	浮点数	`0.85`	是	Page Rank 计算的阻尼因子。必须在 [0, 1) 内。
maxIterations	整数	`20`	是	要运行的 Page Rank 迭代的最大次数。
tolerance	浮点数	`0.0000001`	是	迭代之间分数的最小变化。如果所有分数的变化都小于容差值，则结果被认为是稳定的，并且算法返回。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性的名称。如果未指定，算法将不加权运行。
sourceNodes	节点或数字列表	`[]`	是	用于计算个性化 Page Rank 的节点或节点 ID。
scaler	字符串或映射	`None`	是	应用于最终分数的缩放器的名称。支持的值为 `None`、`MinMax`、`Max`、`Mean`、`Log` 和 `StdScore`。要应用特定于缩放器的配置，请使用映射语法：`{scaler: 'name', …}`。

表 9. 结果
名称	类型	描述
ranIterations	整数	运行的迭代次数。
didConverge	布尔值	指示算法是否收敛。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算 `centralityDistribution` 的毫秒数。
mutateMillis	整数	向投影图添加属性的毫秒数。
nodePropertiesWritten	整数	写入投影图的属性数量。
centralityDistribution	映射	包含最小值、最大值、平均值以及中心值 p50、p75、p90、p95、p99 和 p999 百分位的映射。
configuration	映射	用于运行算法的配置。

在命名图上以写入模式运行 PageRank。

CALL gds.pageRank.write(
  graphName: String,
  configuration: Map
)
YIELD
  nodePropertiesWritten: Integer,
  ranIterations: Integer,
  didConverge: Boolean,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  writeMillis: Integer,
  centralityDistribution: Map,
  configuration: Map

表 10. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	用于算法特定和/或图过滤的配置。

表 11. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。包含具有给定标签的任何节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。包含具有给定类型的任何关系。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`n/a`	否	Neo4j 数据库中将分数写入其中的节点属性。
dampingFactor	浮点数	`0.85`	是	Page Rank 计算的阻尼因子。必须在 [0, 1) 内。
maxIterations	整数	`20`	是	要运行的 Page Rank 迭代的最大次数。
tolerance	浮点数	`0.0000001`	是	迭代之间分数的最小变化。如果所有分数的变化都小于容差值，则结果被认为是稳定的，并且算法返回。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性的名称。如果未指定，算法将不加权运行。
sourceNodes	节点或数字列表	`[]`	是	用于计算个性化 Page Rank 的节点或节点 ID。
scaler	字符串或映射	`None`	是	应用于最终分数的缩放器的名称。支持的值为 `None`、`MinMax`、`Max`、`Mean`、`Log` 和 `StdScore`。要应用特定于缩放器的配置，请使用映射语法：`{scaler: 'name', …}`。

表 12. 结果
名称	类型	描述
ranIterations	整数	运行的迭代次数。
didConverge	布尔值	指示算法是否收敛。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算 `centralityDistribution` 的毫秒数。
writeMillis	整数	将结果数据写回的毫秒数。
nodePropertiesWritten	整数	写入 Neo4j 的属性数量。
centralityDistribution	映射	包含最小值、最大值、平均值以及中心值 p50、p75、p90、p95、p99 和 p999 百分位的映射。
configuration	映射	用于运行算法的配置。

示例

以下所有示例都应在空数据库中运行。

这些示例使用 Cypher 投影作为规范。原生投影将在未来版本中被弃用。

在本节中，我们将展示在具体图上运行 PageRank 算法的示例。目的是说明结果是什么样子，并提供如何在实际环境中使用该算法的指南。我们将在一个小型网页网络图上执行此操作，该图由少数节点以特定模式连接。示例图如下所示

以下 Cypher 语句将在 Neo4j 数据库中创建示例图

CREATE
  (home:Page {name:'Home'}),
  (about:Page {name:'About'}),
  (product:Page {name:'Product'}),
  (links:Page {name:'Links'}),
  (a:Page {name:'Site A'}),
  (b:Page {name:'Site B'}),
  (c:Page {name:'Site C'}),
  (d:Page {name:'Site D'}),

  (home)-[:LINKS {weight: 0.2}]->(about),
  (home)-[:LINKS {weight: 0.2}]->(links),
  (home)-[:LINKS {weight: 0.6}]->(product),
  (about)-[:LINKS {weight: 1.0}]->(home),
  (product)-[:LINKS {weight: 1.0}]->(home),
  (a)-[:LINKS {weight: 1.0}]->(home),
  (b)-[:LINKS {weight: 1.0}]->(home),
  (c)-[:LINKS {weight: 1.0}]->(home),
  (d)-[:LINKS {weight: 1.0}]->(home),
  (links)-[:LINKS {weight: 0.8}]->(home),
  (links)-[:LINKS {weight: 0.05}]->(a),
  (links)-[:LINKS {weight: 0.05}]->(b),
  (links)-[:LINKS {weight: 0.05}]->(c),
  (links)-[:LINKS {weight: 0.05}]->(d);

此图表示八个页面，彼此链接。每个关系都有一个名为 weight 的属性，它描述了关系的重要性。

以下语句将使用 Cypher 投影投影图，并将其存储在名为 'myGraph' 的图目录中。

MATCH (source:Page)-[r:LINKS]->(target:Page)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  { relationshipProperties: r { .weight } }
)

内存估计

首先，我们将使用 estimate 过程估计运行算法的成本。这可以使用任何执行模式完成。在本例中，我们将使用 write 模式。估计算法有助于了解在图上运行算法的内存影响。当您稍后实际上在其中一种执行模式下运行算法时，系统将执行估计。如果估计表明执行很有可能超过其内存限制，则会禁止执行。要详细了解这一点，请参阅自动估计和执行阻塞。

有关 estimate 的更多详细信息，请参阅内存估计。

以下将估计运行算法所需的内存量

CALL gds.pageRank.write.estimate('myGraph', {
  writeProperty: 'pageRank',
  maxIterations: 20,
  dampingFactor: 0.85
})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
8	14	696	696	"696 字节"

流

在 stream 执行模式下，算法返回每个节点的分数。这使我们能够直接检查结果，或在 Cypher 中对其进行后处理，而没有任何副作用。例如，我们可以对结果进行排序以找到 PageRank 分数最高的节点。

有关 stream 模式的更多详细信息，请参阅流。

以下将在 stream 模式下运行算法

CALL gds.pageRank.stream('myGraph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC

表 14. 结果
name	score
"Home"	3.215681999884452
"About"	1.0542700552146722
"Links"	1.0542700552146722
"Product"	1.0542700552146722
"Site A"	0.3278578964488539
"Site B"	0.3278578964488539
"Site C"	0.3278578964488539
"Site D"	0.3278578964488539

上面的查询以 stream 模式运行算法为 unweighted，返回的分数未进行归一化。在下面，您可以找到加权图的示例。另一个示例显示了将缩放器应用于归一化最终分数。

虽然我们使用 stream 模式来说明以 weighted 或 unweighted 方式运行算法，但所有算法模式都支持此配置参数。

统计数据

在 stats 执行模式下，算法返回一行包含算法结果摘要的行。例如，PageRank 统计数据返回中心性直方图，可用于监视所有计算节点的 PageRank 分数值分布。此执行模式没有任何副作用。它可以通过检查 computeMillis 返回项来评估算法性能。在以下示例中，我们将省略返回计时信息。可以在语法部分中找到该过程的完整签名。

有关 stats 模式的更多详细信息，请参阅统计数据。

以下将运行算法并以统计数据和测量值的形式返回结果

CALL gds.pageRank.stats('myGraph', {
  maxIterations: 20,
  dampingFactor: 0.85
})
YIELD centralityDistribution
RETURN centralityDistribution.max AS max

表 15. 结果
max
3.2156829834

中心性直方图可用于检查计算的分数或执行归一化。

变异

mutate 执行模式通过一个重要的副作用扩展了 stats 模式：使用名为 mutateProperty 的强制配置参数指定的新节点属性更新命名图。结果是一行与 stats 类似的摘要行，但包含一些额外的指标。mutate 模式在将多个算法结合使用时特别有用。

有关 mutate 模式的更多详细信息，请参阅变异。

以下将在 mutate 模式下运行算法

CALL gds.pageRank.mutate('myGraph', {
  maxIterations: 20,
  dampingFactor: 0.85,
  mutateProperty: 'pagerank'
})
YIELD nodePropertiesWritten, ranIterations

表 16. 结果
nodePropertiesWritten	ranIterations
`8`	`20`

写入

write 执行模式通过一个重要的副作用扩展了 stats 模式：将每个节点的分数作为属性写入 Neo4j 数据库。使用名为 writeProperty 的强制配置参数指定新属性的名称。结果是一行与 stats 类似的摘要行，但包含一些额外的指标。write 模式能够将结果直接持久化到数据库中。

有关 write 模式的更多详细信息，请参阅写入。

以下将在 write 模式下运行算法

CALL gds.pageRank.write('myGraph', {
  maxIterations: 20,
  dampingFactor: 0.85,
  writeProperty: 'pagerank'
})
YIELD nodePropertiesWritten, ranIterations

表 17. 结果
nodePropertiesWritten	ranIterations
`8`	`20`

加权

默认情况下，算法认为图的关系是 unweighted 的，要更改此行为，我们可以使用名为 relationshipWeightProperty 的配置参数。在 weighted 案例中，发送到其邻居的节点的先前分数将乘以关系权重，然后除以其外出关系的权重之和。如果关系属性的值为负数，则在计算过程中将忽略它。以下是如何使用关系属性运行算法的示例。

以下将在 stream 模式下运行算法，使用关系权重

CALL gds.pageRank.stream('myGraph', {
  maxIterations: 20,
  dampingFactor: 0.85,
  relationshipWeightProperty: 'weight'
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC

表 18. 结果
name	score
"Home"	3.53751028396339
"Product"	1.9357838291651097
"About"	0.7452612763883698
"Links"	0.7452612763883698
"Site A"	0.18152677135466103
"Site B"	0.18152677135466103
"Site C"	0.18152677135466103
"Site D"	0.18152677135466103

我们使用 stream 模式来说明以 weighted 或 unweighted 方式运行算法，但所有算法模式都支持此配置参数。

容差

tolerance 配置参数表示迭代之间分数的最小变化。如果所有分数的变化都小于配置的 tolerance 值，则结果将稳定，算法将返回。

以下操作将使用更大的 tolerance 值在 stream 模式下运行算法。

CALL gds.pageRank.stream('myGraph', {
  maxIterations: 20,
  dampingFactor: 0.85,
  tolerance: 0.1
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC

表 19. 结果
name	score
"Home"	1.5812450669583336
"About"	0.5980194356381945
"Links"	0.5980194356381945
"Product"	0.5980194356381945
"Site A"	0.23374955154166668
"Site B"	0.23374955154166668
"Site C"	0.23374955154166668
"Site D"	0.23374955154166668

在本例中，我们使用 tolerance: 0.1，因此结果与流示例中使用 tolerance 的默认值的结果略有不同。请注意，节点 'About'、'Link' 和 'Product' 现在具有相同的分数，而使用 tolerance 的默认值时，节点 'Product' 的分数高于另外两个。

阻尼因子

阻尼因子配置参数接受 0（包含）到 1（不包含）之间的值。如果其值过高，则可能会出现汇点和蜘蛛陷阱问题，并且值可能会振荡，从而导致算法无法收敛。如果其值过低，则所有分数将趋近于 1，并且结果将不足以反映图的结构。

以下操作将使用较小的 dampingFactor 值在 stream 模式下运行算法。

CALL gds.pageRank.stream('myGraph', {
  maxIterations: 20,
  dampingFactor: 0.05
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC

表 20. 结果
name	score
"Home"	1.2487309425844906
"About"	0.9708121818724536
"Links"	0.9708121818724536
"Product"	0.9708121818724536
"Site A"	0.9597081216238426
"Site B"	0.9597081216238426
"Site C"	0.9597081216238426
"Site D"	0.9597081216238426

与使用 dampingFactor 默认值的流示例中的结果相比，使用 dampingFactor: 0.05 时，分数值彼此更接近。此外，请注意，节点 'About'、'Link' 和 'Product' 现在具有相同的分数，而使用 dampingFactor 的默认值时，节点 'Product' 的分数高于另外两个。

个性化 PageRank

个性化 PageRank 是 PageRank 的一种变体，它偏向于一组 sourceNodes。PageRank 的这种变体通常用作推荐系统的一部分。

以下示例显示了如何运行以 'Site A' 为中心的 PageRank。

以下操作将运行算法并流式传输结果。

MATCH (siteA:Page {name: 'Site A'})
CALL gds.pageRank.stream('myGraph', {
  maxIterations: 20,
  dampingFactor: 0.85,
  sourceNodes: [siteA]
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC

表 21. 结果
name	score
"Home"	0.39902290442518784
"Site A"	0.16890325301726694
"About"	0.11220151747374331
"Links"	0.11220151747374331
"Product"	0.11220151747374331
"Site B"	0.01890325301726691
"Site C"	0.01890325301726691
"Site D"	0.01890325301726691

将这些结果与流示例（不使用 sourceNodes 配置参数）中的结果进行比较，可以看出，我们用于 sourceNodes 列表中的 'Site A' 节点现在排名第二，而不是第四。

缩放中心性分数

为了在算法执行过程中对最终分数进行归一化，可以使用 scaler 配置参数。有关所有可用缩放器的描述，请参阅 scaleProperties 过程的文档。

以下操作将以 stream 模式运行算法并返回归一化结果。

CALL gds.pageRank.stream('myGraph', {
  scaler: "MEAN"
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC

表 22. 结果
name	score
"Home"	0.780671346390832
"About"	0.032214422681946
"Links"	0.032214422681946
"Product"	0.032214422681946
"Site A"	-0.219328653609168
"Site B"	-0.219328653609168
"Site C"	-0.219328653609168
"Site D"	-0.219328653609168

将结果与流示例进行比较，可以看出分数的相对顺序是相同的。