PageRank

词汇表

有向

有向特性。该算法在有向图上定义良好。

有向

有向特性。该算法忽略图的方向。

有向

有向特性。该算法不在有向图上运行。

无向

无向特性。该算法在无向图上定义良好。

无向

无向特性。该算法忽略图的无向性。

异构节点

异构节点完全支持。该算法能够区分不同类型的节点。

异构节点

异构节点允许。该算法对所有选定节点一视同仁,无论其标签如何。

异构关系

异构关系完全支持。该算法能够区分不同类型的关系。

异构关系

异构关系允许。该算法对所有选定关系一视同仁,无论其类型如何。

加权关系

加权特性。该算法支持使用关系属性作为权重,通过relationshipWeightProperty配置参数指定。

加权关系

加权特性。该算法将每个关系视为同等重要,忽略任何关系权重的值。

简介

PageRank 算法根据传入关系的数量和相应源节点的重要性来衡量图中每个节点的重要性。基本假设粗略地讲是,一个页面的重要性仅取决于链接到它的页面的重要性。

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

page rank formula

其中,

  • 我们假设页面 A 有指向它的页面 T1Tn

  • 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

String

不适用

存储在目录中的图的名称。

configuration

Map

{}

算法特定和/或图过滤的配置。

表 2. 配置
名称 类型 默认值 可选 描述

nodeLabels

List of String

['*']

使用给定节点标签过滤命名图。将包含具有任意给定标签的节点。

relationshipTypes

List of String

['*']

使用给定关系类型过滤命名图。将包含具有任意给定类型的关系。

concurrency

Integer

4 [1]

运行算法所使用的并发线程数。

jobId

String

内部生成

可用于更轻松地跟踪算法进度的 ID。

logProgress

Boolean

true

如果禁用,进度百分比将不会被记录。

dampingFactor

Float

0.85

PageRank 计算的阻尼因子。必须在 [0, 1) 之间。

maxIterations

Integer

20

PageRank 运行的最大迭代次数。

tolerance

Float

0.0000001

迭代之间分数的最小变化。如果所有分数变化小于容差值,则结果被认为是稳定的,算法返回。

relationshipWeightProperty

String

null

用作权重的关系属性名称。如果未指定,算法将以无权重方式运行。

sourceNodes

节点/数字或列表或列表对作为列表

[]

用于计算个性化 PageRank 的节点或节点 ID 或节点-偏置对。要对不同源节点使用不同偏置,请使用以下语法:[[nodeId1, bias1], [nodeId2, bias2], …​]

scaler

String 或 Map

应用于最终分数的缩放器名称。支持的值为 NoneMinMaxMaxMeanLogStdScore。要应用缩放器特定配置,请使用 Map 语法:{scaler: 'name', …​}

1. 在 GDS 会话中,默认值为可用处理器数量

表 3. 结果
名称 类型 描述

nodeId

Integer

节点 ID。

score

Float

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

String

不适用

存储在目录中的图的名称。

configuration

Map

{}

算法特定和/或图过滤的配置。

表 5. 配置
名称 类型 默认值 可选 描述

nodeLabels

List of String

['*']

使用给定节点标签过滤命名图。将包含具有任意给定标签的节点。

relationshipTypes

List of String

['*']

使用给定关系类型过滤命名图。将包含具有任意给定类型的关系。

concurrency

Integer

4 [2]

运行算法所使用的并发线程数。

jobId

String

内部生成

可用于更轻松地跟踪算法进度的 ID。

logProgress

Boolean

true

如果禁用,进度百分比将不会被记录。

dampingFactor

Float

0.85

PageRank 计算的阻尼因子。必须在 [0, 1) 之间。

maxIterations

Integer

20

PageRank 运行的最大迭代次数。

tolerance

Float

0.0000001

迭代之间分数的最小变化。如果所有分数变化小于容差值,则结果被认为是稳定的,算法返回。

relationshipWeightProperty

String

null

用作权重的关系属性名称。如果未指定,算法将以无权重方式运行。

sourceNodes

节点/数字或列表或列表对作为列表

[]

用于计算个性化 PageRank 的节点或节点 ID 或节点-偏置对。要对不同源节点使用不同偏置,请使用以下语法:[[nodeId1, bias1], [nodeId2, bias2], …​]

scaler

String 或 Map

应用于最终分数的缩放器名称。支持的值为 NoneMinMaxMaxMeanLogStdScore。要应用缩放器特定配置,请使用 Map 语法:{scaler: 'name', …​}

2. 在 GDS 会话中,默认值为可用处理器数量

表 6. 结果
名称 类型 描述

ranIterations

Integer

运行的迭代次数。

didConverge

Boolean

指示算法是否收敛。

preProcessingMillis

Integer

预处理图的毫秒数。

computeMillis

Integer

运行算法的毫秒数。

postProcessingMillis

Integer

计算 centralityDistribution 的毫秒数。

centralityDistribution

Map

包含中心性值的最小值、最大值、平均值以及 p50、p75、p90、p95、p99 和 p999 百分位值的 Map。

configuration

Map

用于运行算法的配置。

在命名图上以变异模式运行 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

String

不适用

存储在目录中的图的名称。

configuration

Map

{}

算法特定和/或图过滤的配置。

表 8. 配置
名称 类型 默认值 可选 描述

mutateProperty

String

不适用

GDS 图中要写入分数的节点属性。

nodeLabels

List of String

['*']

使用给定节点标签过滤命名图。

relationshipTypes

List of String

['*']

使用给定关系类型过滤命名图。

concurrency

Integer

4

运行算法所使用的并发线程数。

jobId

String

内部生成

可用于更轻松地跟踪算法进度的 ID。

dampingFactor

Float

0.85

PageRank 计算的阻尼因子。必须在 [0, 1) 之间。

maxIterations

Integer

20

PageRank 运行的最大迭代次数。

tolerance

Float

0.0000001

迭代之间分数的最小变化。如果所有分数变化小于容差值,则结果被认为是稳定的,算法返回。

relationshipWeightProperty

String

null

用作权重的关系属性名称。如果未指定,算法将以无权重方式运行。

sourceNodes

节点/数字或列表或列表对作为列表

[]

用于计算个性化 PageRank 的节点或节点 ID 或节点-偏置对。要对不同源节点使用不同偏置,请使用以下语法:[[nodeId1, bias1], [nodeId2, bias2], …​]

scaler

String 或 Map

应用于最终分数的缩放器名称。支持的值为 NoneMinMaxMaxMeanLogStdScore。要应用缩放器特定配置,请使用 Map 语法:{scaler: 'name', …​}

表 9. 结果
名称 类型 描述

ranIterations

Integer

运行的迭代次数。

didConverge

Boolean

指示算法是否收敛。

preProcessingMillis

Integer

预处理图的毫秒数。

computeMillis

Integer

运行算法的毫秒数。

postProcessingMillis

Integer

计算 centralityDistribution 的毫秒数。

mutateMillis

Integer

将属性添加到投影图的毫秒数。

nodePropertiesWritten

Integer

写入投影图的属性数量。

centralityDistribution

Map

包含中心性值的最小值、最大值、平均值以及 p50、p75、p90、p95、p99 和 p999 百分位值的 Map。

configuration

Map

用于运行算法的配置。

在命名图上以写入模式运行 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

String

不适用

存储在目录中的图的名称。

configuration

Map

{}

算法特定和/或图过滤的配置。

表 11. 配置
名称 类型 默认值 可选 描述

nodeLabels

List of String

['*']

使用给定节点标签过滤命名图。将包含具有任意给定标签的节点。

relationshipTypes

List of String

['*']

使用给定关系类型过滤命名图。将包含具有任意给定类型的关系。

concurrency

Integer

4 [3]

运行算法所使用的并发线程数。

jobId

String

内部生成

可用于更轻松地跟踪算法进度的 ID。

logProgress

Boolean

true

如果禁用,进度百分比将不会被记录。

writeConcurrency

Integer

'concurrency' 的值

用于将结果写入 Neo4j 的并发线程数。

writeProperty

String

不适用

Neo4j 数据库中要写入分数的节点属性。

dampingFactor

Float

0.85

PageRank 计算的阻尼因子。必须在 [0, 1) 之间。

maxIterations

Integer

20

PageRank 运行的最大迭代次数。

tolerance

Float

0.0000001

迭代之间分数的最小变化。如果所有分数变化小于容差值,则结果被认为是稳定的,算法返回。

relationshipWeightProperty

String

null

用作权重的关系属性名称。如果未指定,算法将以无权重方式运行。

sourceNodes

节点/数字或列表或列表对作为列表

[]

用于计算个性化 PageRank 的节点或节点 ID 或节点-偏置对。要对不同源节点使用不同偏置,请使用以下语法:[[nodeId1, bias1], [nodeId2, bias2], …​]

scaler

String 或 Map

应用于最终分数的缩放器名称。支持的值为 NoneMinMaxMaxMeanLogStdScore。要应用缩放器特定配置,请使用 Map 语法:{scaler: 'name', …​}

3. 在 GDS 会话中,默认值为可用处理器数量

表 12. 结果
名称 类型 描述

ranIterations

Integer

运行的迭代次数。

didConverge

Boolean

指示算法是否收敛。

preProcessingMillis

Integer

预处理图的毫秒数。

computeMillis

Integer

运行算法的毫秒数。

postProcessingMillis

Integer

计算 centralityDistribution 的毫秒数。

writeMillis

Integer

写回结果数据的毫秒数。

nodePropertiesWritten

Integer

写入 Neo4j 的属性数量。

centralityDistribution

Map

包含中心性值的最小值、最大值、平均值以及 p50、p75、p90、p95、p99 和 p999 百分位值的 Map。

configuration

Map

用于运行算法的配置。

示例

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

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

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

Visualization of the example graph
以下 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. 结果
名称 score

"主页"

3.215681999884452

"关于"

1.0542700552146722

"链接"

1.0542700552146722

"产品"

1.0542700552146722

"站点 A"

0.3278578964488539

"站点 B"

0.3278578964488539

"站点 C"

0.3278578964488539

"站点 D"

0.3278578964488539

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

虽然我们使用 stream 模式来说明算法作为 weightedunweighted 运行,但所有算法模式都支持此配置参数。

统计

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. 结果
名称 score

"主页"

3.53751028396339

"产品"

1.9357838291651097

"关于"

0.7452612763883698

"链接"

0.7452612763883698

"站点 A"

0.18152677135466103

"站点 B"

0.18152677135466103

"站点 C"

0.18152677135466103

"站点 D"

0.18152677135466103

我们使用 stream 模式来说明算法作为 加权无权重 运行,所有算法模式都支持此配置参数。

容忍度

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

以下将以 stream 模式运行算法,使用更大的 tolerance
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. 结果
名称 score

"主页"

1.5812450669583336

"关于"

0.5980194356381945

"链接"

0.5980194356381945

"产品"

0.5980194356381945

"站点 A"

0.23374955154166668

"站点 B"

0.23374955154166668

"站点 C"

0.23374955154166668

"站点 D"

0.23374955154166668

在这个例子中,我们使用 tolerance: 0.1,所以结果与流示例(它使用 tolerance 的默认值)相比略有不同。

阻尼因子

阻尼因子配置参数接受 0(包含)到 1(不包含)之间的值。如果其值过高,则可能出现陷阱和蜘蛛陷阱问题,并且值可能会振荡,导致算法不收敛。如果其值过低,则所有分数都将被推向 1,结果将无法充分反映图的结构。

以下将以 stream 模式运行算法,使用较小的 dampingFactor
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. 结果
名称 score

"主页"

1.2487309425844906

"关于"

0.9708121818724536

"链接"

0.9708121818724536

"产品"

0.9708121818724536

"站点 A"

0.9597081216238426

"站点 B"

0.9597081216238426

"站点 C"

0.9597081216238426

"站点 D"

0.9597081216238426

与使用 dampingFactor 默认值的流示例结果相比,当使用 dampingFactor: 0.05 时,分数会更接近。

个性化 PageRank

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

以下示例展示了如何围绕“站点 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. 结果
名称 score

"主页"

0.39902290442518784

"站点 A"

0.16890325301726694

"关于"

0.11220151747374331

"链接"

0.11220151747374331

"产品"

0.11220151747374331

"站点 B"

0.01890325301726691

"站点 C"

0.01890325301726691

"站点 D"

0.01890325301726691

将这些结果与流示例(未使用 sourceNodes 配置参数)的结果进行比较,显示我们用于 sourceNodes 列表的“站点 A”节点现在排名第二而不是第四。

偏置个性化 PageRank

在 GDS 中,个性化 PageRank 也可以在源节点之间以变化的偏置运行。与常规个性化 PageRank 一样,这模拟了一种在特定源节点集处重新启动的随机游走。在偏置情况下,重新启动的可能性 (1-dampingFactor) 保持不变,但重新启动的目标将根据设置进行偏置。

以下示例展示了如何围绕“站点 A”和“站点 B”运行 PageRank,其中“站点 B”的偏置是“站点 A”的两倍。偏置的源节点作为节点-值对(列表)列表输入。

以下将运行算法并流式传输结果
MATCH (siteA:Page {name: 'Site A'}), (siteB:Page {name: 'Site B'})
CALL gds.pageRank.stream('myGraph', {
  maxIterations: 20,
  dampingFactor: 0.85,
  sourceNodes: [[siteA, 1], [siteB, 2]]
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC
表 22. 结果
名称 score

"主页"

1.1970687132755635

"站点 B"

0.3567097590518008

"关于"

0.33660455242122994

"链接"

0.33660455242122994

"产品"

0.33660455242122994

"站点 A"

0.20670975905180075

"站点 C"

0.05670975905180073

"站点 D"

0.05670975905180073

缩放中心性分数

为了在算法执行过程中标准化最终分数,可以使用 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
表 23. 结果
名称 score

"主页"

0.780671346390832

"关于"

0.032214422681946

"链接"

0.032214422681946

"产品"

0.032214422681946

"站点 A"

-0.219328653609168

"站点 B"

-0.219328653609168

"站点 C"

-0.219328653609168

"站点 D"

-0.219328653609168

流示例的结果进行比较,我们可以看到分数的相对顺序是相同的。

© . All rights reserved.