PageRank
词汇表
- 有向
-
有向特性。该算法在有向图上定义良好。
- 有向
-
有向特性。该算法忽略图的方向。
- 有向
-
有向特性。该算法不在有向图上运行。
- 无向
-
无向特性。该算法在无向图上定义良好。
- 无向
-
无向特性。该算法忽略图的无向性。
- 异构节点
-
异构节点完全支持。该算法能够区分不同类型的节点。
- 异构节点
-
异构节点允许。该算法对所有选定节点一视同仁,无论其标签如何。
- 异构关系
-
异构关系完全支持。该算法能够区分不同类型的关系。
- 异构关系
-
异构关系允许。该算法对所有选定关系一视同仁,无论其类型如何。
- 加权关系
-
加权特性。该算法支持使用关系属性作为权重,通过relationshipWeightProperty配置参数指定。
- 加权关系
-
加权特性。该算法将每个关系视为同等重要,忽略任何关系权重的值。
简介
PageRank 算法根据传入关系的数量和相应源节点的重要性来衡量图中每个节点的重要性。基本假设粗略地讲是,一个页面的重要性仅取决于链接到它的页面的重要性。
PageRank 在最初的 Google 论文中被引入为一个解决以下方程的函数
其中,
-
我们假设页面 A 有指向它的页面 T1 到 Tn。
-
d 是一个阻尼因子,可以在 0(包含)到 1(不包含)之间设置。它通常设置为 0.85。
-
C(A) 定义为从页面 A 出去的链接数量。
该方程用于迭代更新候选解并得到同一方程的近似解。
有关此算法的更多信息,请参阅
运行此算法需要足够的内存可用性。在运行此算法之前,我们建议您阅读内存估算。 |
注意事项
使用 PageRank 算法时需要注意以下几点
-
如果页面组内没有关系指向组外,则该组被认为是蜘蛛陷阱。
-
当页面网络形成无限循环时,可能发生排名下沉。
-
当页面没有传出关系时,会发生死胡同。
改变阻尼因子有助于解决上述所有问题。它可以被解释为网络冲浪者有时会随机跳转到某个页面,因此不会陷入下沉的概率。
语法
本节介绍在每种执行模式下执行 PageRank 算法所使用的语法。我们描述的是命名图变体的语法。要了解更多关于通用语法变体的信息,请参阅语法概述。
CALL gds.pageRank.stream(
graphName: String,
configuration: Map
)
YIELD
nodeId: Integer,
score: Float
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
graphName |
String |
|
否 |
存储在目录中的图的名称。 |
configuration |
Map |
|
是 |
算法特定和/或图过滤的配置。 |
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
List of String |
|
是 |
使用给定节点标签过滤命名图。将包含具有任意给定标签的节点。 |
|
List of String |
|
是 |
使用给定关系类型过滤命名图。将包含具有任意给定类型的关系。 |
|
Integer |
|
是 |
运行算法所使用的并发线程数。 |
|
String |
|
是 |
可用于更轻松地跟踪算法进度的 ID。 |
|
Boolean |
|
是 |
如果禁用,进度百分比将不会被记录。 |
|
dampingFactor |
Float |
|
是 |
PageRank 计算的阻尼因子。必须在 [0, 1) 之间。 |
Integer |
|
是 |
PageRank 运行的最大迭代次数。 |
|
Float |
|
是 |
迭代之间分数的最小变化。如果所有分数变化小于容差值,则结果被认为是稳定的,算法返回。 |
|
String |
|
是 |
用作权重的关系属性名称。如果未指定,算法将以无权重方式运行。 |
|
sourceNodes |
节点/数字或列表或列表对作为列表 |
|
是 |
用于计算个性化 PageRank 的节点或节点 ID 或节点-偏置对。要对不同源节点使用不同偏置,请使用以下语法: |
scaler |
String 或 Map |
|
是 |
应用于最终分数的缩放器名称。支持的值为 |
名称 | 类型 | 描述 |
---|---|---|
nodeId |
Integer |
节点 ID。 |
score |
Float |
PageRank 分数。 |
CALL gds.pageRank.stats(
graphName: String,
configuration: Map
)
YIELD
ranIterations: Integer,
didConverge: Boolean,
preProcessingMillis: Integer,
computeMillis: Integer,
postProcessingMillis: Integer,
centralityDistribution: Map,
configuration: Map
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
graphName |
String |
|
否 |
存储在目录中的图的名称。 |
configuration |
Map |
|
是 |
算法特定和/或图过滤的配置。 |
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
List of String |
|
是 |
使用给定节点标签过滤命名图。将包含具有任意给定标签的节点。 |
|
List of String |
|
是 |
使用给定关系类型过滤命名图。将包含具有任意给定类型的关系。 |
|
Integer |
|
是 |
运行算法所使用的并发线程数。 |
|
String |
|
是 |
可用于更轻松地跟踪算法进度的 ID。 |
|
Boolean |
|
是 |
如果禁用,进度百分比将不会被记录。 |
|
dampingFactor |
Float |
|
是 |
PageRank 计算的阻尼因子。必须在 [0, 1) 之间。 |
Integer |
|
是 |
PageRank 运行的最大迭代次数。 |
|
Float |
|
是 |
迭代之间分数的最小变化。如果所有分数变化小于容差值,则结果被认为是稳定的,算法返回。 |
|
String |
|
是 |
用作权重的关系属性名称。如果未指定,算法将以无权重方式运行。 |
|
sourceNodes |
节点/数字或列表或列表对作为列表 |
|
是 |
用于计算个性化 PageRank 的节点或节点 ID 或节点-偏置对。要对不同源节点使用不同偏置,请使用以下语法: |
scaler |
String 或 Map |
|
是 |
应用于最终分数的缩放器名称。支持的值为 |
名称 | 类型 | 描述 |
---|---|---|
ranIterations |
Integer |
运行的迭代次数。 |
didConverge |
Boolean |
指示算法是否收敛。 |
preProcessingMillis |
Integer |
预处理图的毫秒数。 |
computeMillis |
Integer |
运行算法的毫秒数。 |
postProcessingMillis |
Integer |
计算 |
centralityDistribution |
Map |
包含中心性值的最小值、最大值、平均值以及 p50、p75、p90、p95、p99 和 p999 百分位值的 Map。 |
configuration |
Map |
用于运行算法的配置。 |
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
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
graphName |
String |
|
否 |
存储在目录中的图的名称。 |
configuration |
Map |
|
是 |
算法特定和/或图过滤的配置。 |
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
mutateProperty |
String |
|
否 |
GDS 图中要写入分数的节点属性。 |
List of String |
|
是 |
使用给定节点标签过滤命名图。 |
|
List of String |
|
是 |
使用给定关系类型过滤命名图。 |
|
Integer |
|
是 |
运行算法所使用的并发线程数。 |
|
String |
|
是 |
可用于更轻松地跟踪算法进度的 ID。 |
|
dampingFactor |
Float |
|
是 |
PageRank 计算的阻尼因子。必须在 [0, 1) 之间。 |
Integer |
|
是 |
PageRank 运行的最大迭代次数。 |
|
Float |
|
是 |
迭代之间分数的最小变化。如果所有分数变化小于容差值,则结果被认为是稳定的,算法返回。 |
|
String |
|
是 |
用作权重的关系属性名称。如果未指定,算法将以无权重方式运行。 |
|
sourceNodes |
节点/数字或列表或列表对作为列表 |
|
是 |
用于计算个性化 PageRank 的节点或节点 ID 或节点-偏置对。要对不同源节点使用不同偏置,请使用以下语法: |
scaler |
String 或 Map |
|
是 |
应用于最终分数的缩放器名称。支持的值为 |
名称 | 类型 | 描述 |
---|---|---|
ranIterations |
Integer |
运行的迭代次数。 |
didConverge |
Boolean |
指示算法是否收敛。 |
preProcessingMillis |
Integer |
预处理图的毫秒数。 |
computeMillis |
Integer |
运行算法的毫秒数。 |
postProcessingMillis |
Integer |
计算 |
mutateMillis |
Integer |
将属性添加到投影图的毫秒数。 |
nodePropertiesWritten |
Integer |
写入投影图的属性数量。 |
centralityDistribution |
Map |
包含中心性值的最小值、最大值、平均值以及 p50、p75、p90、p95、p99 和 p999 百分位值的 Map。 |
configuration |
Map |
用于运行算法的配置。 |
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
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
graphName |
String |
|
否 |
存储在目录中的图的名称。 |
configuration |
Map |
|
是 |
算法特定和/或图过滤的配置。 |
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
List of String |
|
是 |
使用给定节点标签过滤命名图。将包含具有任意给定标签的节点。 |
|
List of String |
|
是 |
使用给定关系类型过滤命名图。将包含具有任意给定类型的关系。 |
|
Integer |
|
是 |
运行算法所使用的并发线程数。 |
|
String |
|
是 |
可用于更轻松地跟踪算法进度的 ID。 |
|
Boolean |
|
是 |
如果禁用,进度百分比将不会被记录。 |
|
Integer |
|
是 |
用于将结果写入 Neo4j 的并发线程数。 |
|
String |
|
否 |
Neo4j 数据库中要写入分数的节点属性。 |
|
dampingFactor |
Float |
|
是 |
PageRank 计算的阻尼因子。必须在 [0, 1) 之间。 |
Integer |
|
是 |
PageRank 运行的最大迭代次数。 |
|
Float |
|
是 |
迭代之间分数的最小变化。如果所有分数变化小于容差值,则结果被认为是稳定的,算法返回。 |
|
String |
|
是 |
用作权重的关系属性名称。如果未指定,算法将以无权重方式运行。 |
|
sourceNodes |
节点/数字或列表或列表对作为列表 |
|
是 |
用于计算个性化 PageRank 的节点或节点 ID 或节点-偏置对。要对不同源节点使用不同偏置,请使用以下语法: |
scaler |
String 或 Map |
|
是 |
应用于最终分数的缩放器名称。支持的值为 |
名称 | 类型 | 描述 |
---|---|---|
ranIterations |
Integer |
运行的迭代次数。 |
didConverge |
Boolean |
指示算法是否收敛。 |
preProcessingMillis |
Integer |
预处理图的毫秒数。 |
computeMillis |
Integer |
运行算法的毫秒数。 |
postProcessingMillis |
Integer |
计算 |
writeMillis |
Integer |
写回结果数据的毫秒数。 |
nodePropertiesWritten |
Integer |
写入 Neo4j 的属性数量。 |
centralityDistribution |
Map |
包含中心性值的最小值、最大值、平均值以及 p50、p75、p90、p95、p99 和 p999 百分位值的 Map。 |
configuration |
Map |
用于运行算法的配置。 |
示例
以下所有示例都应在空数据库中运行。 示例使用Cypher 投影作为规范。原生投影将在未来版本中弃用。 |
在本节中,我们将展示在具体图上运行 PageRank 算法的示例。目的是说明结果的样子,并提供如何在实际设置中使用算法的指南。我们将在一个由少数节点以特定模式连接的小型 Web 网络图上进行操作。示例图如下所示
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
的属性,描述了关系的重要性。
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
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
名称 | score |
---|---|
"主页" |
3.215681999884452 |
"关于" |
1.0542700552146722 |
"链接" |
1.0542700552146722 |
"产品" |
1.0542700552146722 |
"站点 A" |
0.3278578964488539 |
"站点 B" |
0.3278578964488539 |
"站点 C" |
0.3278578964488539 |
"站点 D" |
0.3278578964488539 |
虽然我们使用 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
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
nodePropertiesWritten | ranIterations |
---|---|
|
|
写入
write
执行模式扩展了 stats
模式,并具有一个重要的副作用:将每个节点的分数作为属性写入 Neo4j 数据库。新属性的名称由强制配置参数 writeProperty
指定。结果是单个摘要行,类似于 stats
,但带有一些额外的指标。write
模式能够将结果直接持久化到数据库中。
有关 write
模式的更多详细信息,请参阅写入。
write
模式运行算法CALL gds.pageRank.write('myGraph', {
maxIterations: 20,
dampingFactor: 0.85,
writeProperty: 'pagerank'
})
YIELD nodePropertiesWritten, ranIterations
nodePropertiesWritten | ranIterations |
---|---|
|
|
加权
默认情况下,该算法将图中的关系视为 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
名称 | 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
名称 | 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
名称 | 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
名称 | 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
名称 | 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
名称 | score |
---|---|
"主页" |
0.780671346390832 |
"关于" |
0.032214422681946 |
"链接" |
0.032214422681946 |
"产品" |
0.032214422681946 |
"站点 A" |
-0.219328653609168 |
"站点 B" |
-0.219328653609168 |
"站点 C" |
-0.219328653609168 |
"站点 D" |
-0.219328653609168 |
与流示例的结果进行比较,我们可以看到分数的相对顺序是相同的。