Article Rank
词汇表
- 有向
-
有向特性。该算法在有向图上定义良好。
- 有向
-
有向特性。该算法忽略图的方向性。
- 有向
-
有向特性。该算法不在有向图上运行。
- 无向
-
无向特性。该算法在无向图上定义良好。
- 无向
-
无向特性。该算法忽略图的无向性。
- 异构节点
-
异构节点完全支持。该算法能够区分不同类型的节点。
- 异构节点
-
异构节点允许。该算法对所有选定节点一视同仁,无论其标签如何。
- 异构关系
-
异构关系完全支持。该算法能够区分不同类型的关系。
- 异构关系
-
异构关系允许。该算法对所有选定关系一视同仁,无论其类型如何。
- 加权关系
-
加权特性。该算法支持将关系属性用作权重,通过relationshipWeightProperty配置参数指定。
- 加权关系
-
加权特性。该算法将每个关系视为同等重要,忽略任何关系权重的数值。
简介
ArticleRank 是 Page Rank 算法的一种变体,用于衡量节点的传递影响力。
Page Rank 遵循的假设是,源自低度节点的关系统计影响力高于源自高度节点的关系。Article Rank 通过在每次迭代中降低发送给邻居的分数来降低低度节点的影响力。
节点 v 在第 i 次迭代中的 Article Rank 定义为
其中,
-
Nin(v) 表示节点 v 的入站邻居,Nout(v) 表示节点 v 的出站邻居。
-
d 是一个在 [0, 1] 范围内的阻尼因子。
-
Nout 是平均出度
注意事项
使用 Article Rank 算法时需要注意以下几点
-
如果一组页面内部没有关系指向组外,则该组被视为蜘蛛陷阱。
-
当页面网络形成无限循环时,可能发生排名陷阱。
-
当页面没有出站关系时,会发生死胡同。
改变阻尼因子有助于解决上述所有问题。这可以解释为网页冲浪者有时会跳转到随机页面的概率,从而避免陷入陷阱。
语法
本节介绍在每种执行模式下执行 Article Rank 算法所使用的语法。我们将描述命名图变体的语法。要了解有关通用语法变体的更多信息,请参阅语法概述。
CALL gds.articleRank.stream(
graphName: String,
configuration: Map
)
YIELD
nodeId: Integer,
score: Float
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
graphName |
字符串 |
|
否 |
存储在目录中的图的名称。 |
configuration |
映射 |
|
是 |
用于算法特定和/或图过滤的配置。 |
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
字符串列表 |
|
是 |
使用给定节点标签过滤命名图。将包含具有任何给定标签的节点。 |
|
字符串列表 |
|
是 |
使用给定关系类型过滤命名图。将包含具有任何给定类型的关系。 |
|
整数 |
|
是 |
用于运行算法的并发线程数。 |
|
字符串 |
|
是 |
可以提供一个 ID 以更轻松地跟踪算法的进度。 |
|
布尔值 |
|
是 |
如果禁用,将不会记录进度百分比。 |
|
dampingFactor |
浮点数 |
|
是 |
Page Rank 计算的阻尼因子。必须在 [0, 1) 范围内。 |
整数 |
|
是 |
Article Rank 的最大迭代次数。 |
|
浮点数 |
|
是 |
迭代之间分数的最小变化量。如果所有分数的变化都小于容差值,则结果被视为稳定,算法返回。 |
|
字符串 |
|
是 |
用作权重的关系属性名称。如果未指定,算法将运行无权重模式。 |
|
sourceNodes |
节点/数字或列表或成对列表 |
|
是 |
用于计算个性化 Article Rank 的节点或节点 ID 或节点-偏置对。要对不同源节点使用不同的偏置,请使用以下语法: |
scaler |
字符串或映射 |
|
是 |
应用于最终分数的缩放器名称。支持的值有 |
名称 | 类型 | 描述 |
---|---|---|
nodeId |
整数 |
节点 ID。 |
score |
浮点数 |
特征向量分数。 |
CALL gds.articleRank.stats(
graphName: String,
configuration: Map
)
YIELD
ranIterations: Integer,
didConverge: Boolean,
preProcessingMillis: Integer,
computeMillis: Integer,
postProcessingMillis: Integer,
centralityDistribution: Map,
configuration: Map
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
graphName |
字符串 |
|
否 |
存储在目录中的图的名称。 |
configuration |
映射 |
|
是 |
用于算法特定和/或图过滤的配置。 |
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
字符串列表 |
|
是 |
使用给定节点标签过滤命名图。将包含具有任何给定标签的节点。 |
|
字符串列表 |
|
是 |
使用给定关系类型过滤命名图。将包含具有任何给定类型的关系。 |
|
整数 |
|
是 |
用于运行算法的并发线程数。 |
|
字符串 |
|
是 |
可以提供一个 ID 以更轻松地跟踪算法的进度。 |
|
布尔值 |
|
是 |
如果禁用,将不会记录进度百分比。 |
|
dampingFactor |
浮点数 |
|
是 |
Page Rank 计算的阻尼因子。必须在 [0, 1) 范围内。 |
整数 |
|
是 |
Article Rank 的最大迭代次数。 |
|
浮点数 |
|
是 |
迭代之间分数的最小变化量。如果所有分数的变化都小于容差值,则结果被视为稳定,算法返回。 |
|
字符串 |
|
是 |
用作权重的关系属性名称。如果未指定,算法将运行无权重模式。 |
|
sourceNodes |
节点/数字或列表或成对列表 |
|
是 |
用于计算个性化 Article Rank 的节点或节点 ID 或节点-偏置对。要对不同源节点使用不同的偏置,请使用以下语法: |
scaler |
字符串或映射 |
|
是 |
应用于最终分数的缩放器名称。支持的值有 |
名称 | 类型 | 描述 |
---|---|---|
ranIterations |
整数 |
运行的迭代次数。 |
didConverge |
布尔值 |
指示算法是否收敛。 |
preProcessingMillis |
整数 |
预处理图的毫秒数。 |
computeMillis |
整数 |
运行算法的毫秒数。 |
postProcessingMillis |
整数 |
计算 |
centralityDistribution |
映射 |
包含中心性值(最小值、最大值、平均值以及 p50、p75、p90、p95、p99 和 p999 百分位数)的映射。 |
configuration |
映射 |
用于运行算法的配置。 |
CALL gds.articleRank.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 |
字符串 |
|
否 |
存储在目录中的图的名称。 |
configuration |
映射 |
|
是 |
用于算法特定和/或图过滤的配置。 |
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
mutateProperty |
字符串 |
|
否 |
要将分数写入的 GDS 图中的节点属性。 |
字符串列表 |
|
是 |
使用给定节点标签过滤命名图。 |
|
字符串列表 |
|
是 |
使用给定关系类型过滤命名图。 |
|
整数 |
|
是 |
用于运行算法的并发线程数。 |
|
字符串 |
|
是 |
可以提供一个 ID 以更轻松地跟踪算法的进度。 |
|
dampingFactor |
浮点数 |
|
是 |
Page Rank 计算的阻尼因子。必须在 [0, 1) 范围内。 |
整数 |
|
是 |
Article Rank 的最大迭代次数。 |
|
浮点数 |
|
是 |
迭代之间分数的最小变化量。如果所有分数的变化都小于容差值,则结果被视为稳定,算法返回。 |
|
字符串 |
|
是 |
用作权重的关系属性名称。如果未指定,算法将运行无权重模式。 |
|
sourceNodes |
节点/数字或列表或成对列表 |
|
是 |
用于计算个性化 Article Rank 的节点或节点 ID 或节点-偏置对。要对不同源节点使用不同的偏置,请使用以下语法: |
scaler |
字符串或映射 |
|
是 |
应用于最终分数的缩放器名称。支持的值有 |
名称 | 类型 | 描述 |
---|---|---|
ranIterations |
整数 |
运行的迭代次数。 |
didConverge |
布尔值 |
指示算法是否收敛。 |
preProcessingMillis |
整数 |
预处理图的毫秒数。 |
computeMillis |
整数 |
运行算法的毫秒数。 |
postProcessingMillis |
整数 |
计算 |
mutateMillis |
整数 |
向投影图添加属性的毫秒数。 |
nodePropertiesWritten |
整数 |
写入投影图的属性数量。 |
centralityDistribution |
映射 |
包含中心性值(最小值、最大值、平均值以及 p50、p75、p90、p95、p99 和 p999 百分位数)的映射。 |
configuration |
映射 |
用于运行算法的配置。 |
CALL gds.articleRank.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 |
字符串 |
|
否 |
存储在目录中的图的名称。 |
configuration |
映射 |
|
是 |
用于算法特定和/或图过滤的配置。 |
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
字符串列表 |
|
是 |
使用给定节点标签过滤命名图。将包含具有任何给定标签的节点。 |
|
字符串列表 |
|
是 |
使用给定关系类型过滤命名图。将包含具有任何给定类型的关系。 |
|
整数 |
|
是 |
用于运行算法的并发线程数。 |
|
字符串 |
|
是 |
可以提供一个 ID 以更轻松地跟踪算法的进度。 |
|
布尔值 |
|
是 |
如果禁用,将不会记录进度百分比。 |
|
整数 |
|
是 |
用于将结果写入 Neo4j 的并发线程数。 |
|
字符串 |
|
否 |
要将分数写入的 Neo4j 数据库中的节点属性。 |
|
dampingFactor |
浮点数 |
|
是 |
Page Rank 计算的阻尼因子。必须在 [0, 1) 范围内。 |
整数 |
|
是 |
Article Rank 的最大迭代次数。 |
|
浮点数 |
|
是 |
迭代之间分数的最小变化量。如果所有分数的变化都小于容差值,则结果被视为稳定,算法返回。 |
|
字符串 |
|
是 |
用作权重的关系属性名称。如果未指定,算法将运行无权重模式。 |
|
sourceNodes |
节点/数字或列表或成对列表 |
|
是 |
用于计算个性化 Article Rank 的节点或节点 ID 或节点-偏置对。要对不同源节点使用不同的偏置,请使用以下语法: |
scaler |
字符串或映射 |
|
是 |
应用于最终分数的缩放器名称。支持的值有 |
名称 | 类型 | 描述 |
---|---|---|
ranIterations |
整数 |
运行的迭代次数。 |
didConverge |
布尔值 |
指示算法是否收敛。 |
preProcessingMillis |
整数 |
预处理图的毫秒数。 |
computeMillis |
整数 |
运行算法的毫秒数。 |
postProcessingMillis |
整数 |
计算 |
writeMillis |
整数 |
回写结果数据的毫秒数。 |
nodePropertiesWritten |
整数 |
写入 Neo4j 的属性数量。 |
centralityDistribution |
映射 |
包含中心性值(最小值、最大值、平均值以及 p50、p75、p90、p95、p99 和 p999 百分位数)的映射。 |
configuration |
映射 |
用于运行算法的配置。 |
示例
以下所有示例都应在一个空数据库中运行。 这些示例以 Cypher 投影为标准。原生投影将在未来版本中弃用。 |
本节将展示在具体图上运行 Article Rank 算法的示例。目的是说明结果是什么样子,并提供如何在实际设置中使用该算法的指南。我们将在一个由少量节点以特定模式连接的小型 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.articleRank.write.estimate('myGraph', {
writeProperty: 'centrality',
maxIterations: 20
})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
nodeCount | relationshipCount | bytesMin | bytesMax | requiredMemory |
---|---|---|---|---|
8 |
14 |
696 |
696 |
"696 字节" |
流模式
在 stream
执行模式下,算法返回每个节点的分数。这使我们能够直接检查结果或在 Cypher 中对其进行后处理,而不会产生任何副作用。例如,我们可以对结果进行排序,以找到具有最高特征向量分数的节点。
有关 stream
模式的更多详细信息,请参阅流模式。
stream
模式下运行算法CALL gds.articleRank.stream('myGraph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC
名称 | score |
---|---|
"Home" |
0.5607071761939444 |
"About" |
0.250337073634706 |
"Links" |
0.250337073634706 |
"Product" |
0.250337073634706 |
"Site A" |
0.18152391630760797 |
"Site B" |
0.18152391630760797 |
"Site C" |
0.18152391630760797 |
"Site D" |
0.18152391630760797 |
上述查询以无权重模式在 stream
模式下运行算法。下面,可以找到加权图的示例。
统计模式
在 stats
执行模式下,算法返回一行,其中包含算法结果的摘要。例如,特征向量统计返回中心性直方图,可用于监控所有计算节点的中心性分数分布。此执行模式没有任何副作用。通过检查 computeMillis
返回项来评估算法性能会很有用。在下面的示例中,我们将省略返回时间。该过程的完整签名可在语法部分找到。
有关 stats
模式的更多详细信息,请参阅统计模式。
CALL gds.articleRank.stats('myGraph')
YIELD centralityDistribution
RETURN centralityDistribution.max AS max
最大值 |
---|
0.560710907 |
变异模式
mutate
执行模式扩展了 stats
模式,具有一个重要的副作用:使用包含该节点分数的新节点属性更新命名图。新属性的名称使用强制配置参数 mutateProperty
指定。结果是一行摘要,类似于 stats
,但包含一些附加指标。当多个算法结合使用时,mutate
模式特别有用。
有关 mutate
模式的更多详细信息,请参阅变异模式。
mutate
模式下运行算法CALL gds.articleRank.mutate('myGraph', {
mutateProperty: 'centrality'
})
YIELD nodePropertiesWritten, ranIterations
nodePropertiesWritten | ranIterations |
---|---|
|
|
写入模式
write
执行模式扩展了 stats
模式,具有一个重要的副作用:将每个节点的分数作为属性写入 Neo4j 数据库。新属性的名称使用强制配置参数 writeProperty
指定。结果是一行摘要,类似于 stats
,但包含一些附加指标。write
模式支持将结果直接持久化到数据库。
有关 write
模式的更多详细信息,请参阅写入模式。
write
模式下运行算法CALL gds.articleRank.write('myGraph', {
writeProperty: 'centrality'
})
YIELD nodePropertiesWritten, ranIterations
nodePropertiesWritten | ranIterations |
---|---|
|
|
加权
默认情况下,算法认为图中的关系是无权重的。要更改此行为,我们可以使用 relationshipWeightProperty
配置参数。如果设置了该参数,则关联的属性值将用作关系权重。在加权情况下,发送给其邻居的节点的先前分数将乘以归一化的关系权重。请注意,在计算过程中,负关系权重将被忽略。
在以下示例中,我们使用输入图的 weight
属性作为关系权重属性。
CALL gds.articleRank.stream('myGraph', {
relationshipWeightProperty: 'weight'
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC
名称 | score |
---|---|
"Home" |
0.5160810726222141 |
"Product" |
0.24570958074084706 |
"About" |
0.1819031935802824 |
"Links" |
0.1819031935802824 |
"Site A" |
0.15281123078335393 |
"Site B" |
0.15281123078335393 |
"Site C" |
0.15281123078335393 |
"Site D" |
0.15281123078335393 |
与无权重示例一样,"Home" 节点具有最高分数。相比之下,"Product" 现在具有第二高分数,而不是第四高分数。
我们使用 stream 模式来演示加权算法的运行,但是,所有算法模式都支持 relationshipWeightProperty 配置参数。 |
容差
tolerance
配置参数表示迭代之间分数的最小变化量。如果所有分数的变化都小于配置的容差,则迭代将中止并被视为收敛。请注意,设置更高的容差会导致更早收敛,但也会导致中心性分数不太准确。
stream
模式使用高容差值运行算法CALL gds.articleRank.stream('myGraph', {
tolerance: 0.1
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC
名称 | score |
---|---|
"Home" |
0.4470707071 |
"About" |
0.2300021265 |
"Links" |
0.2300021265 |
"Product" |
0.2300021265 |
"Site A" |
0.1688888889 |
"Site B" |
0.1688888889 |
"Site C" |
0.1688888889 |
"Site D" |
0.1688888889 |
我们使用 tolerance: 0.1
,这导致与流模式示例相比略有不同的结果。然而,计算在四次迭代后收敛,我们已经可以观察到结果分数的趋势。
个性化 Article Rank
个性化 Article Rank 是 Article Rank 的一种变体,它偏向于一组 sourceNodes
。默认情况下,随机游走以相同的概率传送到图中的任何节点。与 PageRank 一样,这可以改为仅传送到一组 sourceNodes
。
以下示例展示了如何围绕 'Site A' 和 'Site B' 运行 Article Rank。
MATCH (siteA:Page {name: 'Site A'}), (siteB:Page {name: 'Site B'})
CALL gds.articleRank.stream('myGraph', {
maxIterations: 20,
sourceNodes: [siteA, siteB]
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC
名称 | score |
---|---|
"Site A" |
0.15249052775314756 |
"Site B" |
0.15249052775314756 |
"Home" |
0.1105231342997017 |
"About" |
0.019777824032578193 |
"Links" |
0.019777824032578193 |
"Product" |
0.019777824032578193 |
"Site C" |
0.002490527753147571 |
"Site D" |
0.002490527753147571 |
将这些结果与流模式示例(未使用 sourceNodes
配置参数)中的结果进行比较,结果显示我们用于 sourceNodes
列表中的 'Site A' 和 'Site B' 节点现在得分分别为第二和第三,而不是第四和第五。
偏置个性化 Article Rank
与个性化 PageRank 类似,GDS 允许对 sourceNodes
进行不同的加权,从而增加传送到某些节点的可能性。
以下示例展示了如何围绕 'Site A' 和 'Site B' 运行 Article Rank,其中 'Site B' 的偏置是 'Site A' 的两倍。偏置源节点以节点-值对(列表)的形式输入。
MATCH (siteA:Page {name: 'Site A'}), (siteB:Page {name: 'Site B'})
CALL gds.articleRank.stream('myGraph', {
maxIterations: 100,
tolerance: 0,
sourceNodes: [[siteA, 1], [siteB, 2]]
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC
名称 | score |
---|---|
"Site B" |
0.303735818640820054 |
"Home" |
0.165785031378950204 |
"Site A" |
0.153735818640819949 |
"About" |
0.029666795088864776 |
"Links" |
0.029666795088864776 |
"Product" |
0.029666795088864776 |
"Site C" |
0.003735818640820008 |
"Site D" |
0.003735818640820008 |
缩放中心性分数
为了将最终分数作为算法执行的一部分进行归一化,可以使用 scaler
配置参数。所有可用缩放器的说明可在 scaleProperties
过程的文档中找到。
stream
模式下运行算法并返回归一化结果CALL gds.articleRank.stream('myGraph', {
scaler: "StdScore"
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC
名称 | score |
---|---|
"Home" |
2.550761988515413 |
"About" |
-0.036593974039468 |
"Links" |
-0.036593974039468 |
"Product" |
-0.036593974039468 |
"Site A" |
-0.610245016599252 |
"Site B" |
-0.610245016599252 |
"Site C" |
-0.610245016599252 |
"Site D" |
-0.610245016599252 |
将结果与流模式示例进行比较,我们可以看到分数的相对顺序是相同的。