Article Rank

词汇表

有向

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

有向

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

有向

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

无向

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

无向

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

异构节点

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

异构节点

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

异构关系

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

异构关系

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

加权关系

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

加权关系

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

简介

ArticleRank 是 Page Rank 算法的一种变体,用于衡量节点的传递影响力。

Page Rank 遵循的假设是,源自低度节点的关系统计影响力高于源自高度节点的关系。Article Rank 通过在每次迭代中降低发送给邻居的分数来降低低度节点的影响力。

节点 v 在第 i 次迭代中的 Article Rank 定义为

articleRank

其中,

  • Nin(v) 表示节点 v 的入站邻居,Nout(v) 表示节点 v 的出站邻居。

  • d 是一个在 [0, 1] 范围内的阻尼因子。

  • Nout 是平均出度

注意事项

使用 Article Rank 算法时需要注意以下几点

  • 如果一组页面内部没有关系指向组外,则该组被视为蜘蛛陷阱。

  • 当页面网络形成无限循环时,可能发生排名陷阱。

  • 当页面没有出站关系时,会发生死胡同。

改变阻尼因子有助于解决上述所有问题。这可以解释为网页冲浪者有时会跳转到随机页面的概率,从而避免陷入陷阱。

语法

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

每种模式下的 Article Rank 语法
在命名图上以流模式运行 Article Rank。
CALL gds.articleRank.stream(
  graphName: String,
  configuration: Map
)
YIELD
  nodeId: Integer,
  score: Float
表 1. 参数
名称 类型 默认值 可选 描述

graphName

字符串

不适用

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

configuration

映射

{}

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

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

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4 [1]

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

jobId

字符串

内部生成

可以提供一个 ID 以更轻松地跟踪算法的进度。

logProgress

布尔值

true

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

dampingFactor

浮点数

0.85

Page Rank 计算的阻尼因子。必须在 [0, 1) 范围内。

maxIterations

整数

20

Article Rank 的最大迭代次数。

tolerance

浮点数

0.0000001

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

relationshipWeightProperty

字符串

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

sourceNodes

节点/数字或列表或成对列表

[]

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

scaler

字符串或映射

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

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

表 3. 结果
名称 类型 描述

nodeId

整数

节点 ID。

score

浮点数

特征向量分数。

在命名图上以统计模式运行 Article Rank。
CALL gds.articleRank.stats(
  graphName: String,
  configuration: Map
)
YIELD
  ranIterations: Integer,
  didConverge: Boolean,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  centralityDistribution: Map,
  configuration: Map
表 4. 参数
名称 类型 默认值 可选 描述

graphName

字符串

不适用

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

configuration

映射

{}

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

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

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4 [2]

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

jobId

字符串

内部生成

可以提供一个 ID 以更轻松地跟踪算法的进度。

logProgress

布尔值

true

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

dampingFactor

浮点数

0.85

Page Rank 计算的阻尼因子。必须在 [0, 1) 范围内。

maxIterations

整数

20

Article Rank 的最大迭代次数。

tolerance

浮点数

0.0000001

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

relationshipWeightProperty

字符串

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

sourceNodes

节点/数字或列表或成对列表

[]

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

scaler

字符串或映射

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

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

表 6. 结果
名称 类型 描述

ranIterations

整数

运行的迭代次数。

didConverge

布尔值

指示算法是否收敛。

preProcessingMillis

整数

预处理图的毫秒数。

computeMillis

整数

运行算法的毫秒数。

postProcessingMillis

整数

计算 centralityDistribution 的毫秒数。

centralityDistribution

映射

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

configuration

映射

用于运行算法的配置。

在命名图上以变异模式运行 Article Rank。
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
表 7. 参数
名称 类型 默认值 可选 描述

graphName

字符串

不适用

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

configuration

映射

{}

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

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

mutateProperty

字符串

不适用

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

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4

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

jobId

字符串

内部生成

可以提供一个 ID 以更轻松地跟踪算法的进度。

dampingFactor

浮点数

0.85

Page Rank 计算的阻尼因子。必须在 [0, 1) 范围内。

maxIterations

整数

20

Article Rank 的最大迭代次数。

tolerance

浮点数

0.0000001

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

relationshipWeightProperty

字符串

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

sourceNodes

节点/数字或列表或成对列表

[]

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

scaler

字符串或映射

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

表 9. 结果
名称 类型 描述

ranIterations

整数

运行的迭代次数。

didConverge

布尔值

指示算法是否收敛。

preProcessingMillis

整数

预处理图的毫秒数。

computeMillis

整数

运行算法的毫秒数。

postProcessingMillis

整数

计算 centralityDistribution 的毫秒数。

mutateMillis

整数

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

nodePropertiesWritten

整数

写入投影图的属性数量。

centralityDistribution

映射

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

configuration

映射

用于运行算法的配置。

在命名图上以写入模式运行 Article Rank。
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
表 10. 参数
名称 类型 默认值 可选 描述

graphName

字符串

不适用

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

configuration

映射

{}

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

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

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4 [3]

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

jobId

字符串

内部生成

可以提供一个 ID 以更轻松地跟踪算法的进度。

logProgress

布尔值

true

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

writeConcurrency

整数

'concurrency' 的值

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

writeProperty

字符串

不适用

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

dampingFactor

浮点数

0.85

Page Rank 计算的阻尼因子。必须在 [0, 1) 范围内。

maxIterations

整数

20

Article Rank 的最大迭代次数。

tolerance

浮点数

0.0000001

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

relationshipWeightProperty

字符串

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

sourceNodes

节点/数字或列表或成对列表

[]

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

scaler

字符串或映射

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

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

表 12. 结果
名称 类型 描述

ranIterations

整数

运行的迭代次数。

didConverge

布尔值

指示算法是否收敛。

preProcessingMillis

整数

预处理图的毫秒数。

computeMillis

整数

运行算法的毫秒数。

postProcessingMillis

整数

计算 centralityDistribution 的毫秒数。

writeMillis

整数

回写结果数据的毫秒数。

nodePropertiesWritten

整数

写入 Neo4j 的属性数量。

centralityDistribution

映射

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

configuration

映射

用于运行算法的配置。

示例

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

这些示例以 Cypher 投影为标准。原生投影将在未来版本中弃用。

本节将展示在具体图上运行 Article Rank 算法的示例。目的是说明结果是什么样子,并提供如何在实际设置中使用该算法的指南。我们将在一个由少量节点以特定模式连接的小型 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.articleRank.write.estimate('myGraph', {
  writeProperty: 'centrality',
  maxIterations: 20
})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
表 13. 结果
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
表 14. 结果
名称 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
表 15. 结果
最大值

0.560710907

变异模式

mutate 执行模式扩展了 stats 模式,具有一个重要的副作用:使用包含该节点分数的新节点属性更新命名图。新属性的名称使用强制配置参数 mutateProperty 指定。结果是一行摘要,类似于 stats,但包含一些附加指标。当多个算法结合使用时,mutate 模式特别有用。

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

以下将在 mutate 模式下运行算法
CALL gds.articleRank.mutate('myGraph', {
  mutateProperty: 'centrality'
})
YIELD nodePropertiesWritten, ranIterations
表 16. 结果
nodePropertiesWritten ranIterations

8

19

写入模式

write 执行模式扩展了 stats 模式,具有一个重要的副作用:将每个节点的分数作为属性写入 Neo4j 数据库。新属性的名称使用强制配置参数 writeProperty 指定。结果是一行摘要,类似于 stats,但包含一些附加指标。write 模式支持将结果直接持久化到数据库。

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

以下将在 write 模式下运行算法
CALL gds.articleRank.write('myGraph', {
  writeProperty: 'centrality'
})
YIELD nodePropertiesWritten, ranIterations
表 17. 结果
nodePropertiesWritten ranIterations

8

19

加权

默认情况下,算法认为图中的关系是无权重的。要更改此行为,我们可以使用 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
表 18. 结果
名称 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
表 19. 结果
名称 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
表 20. 结果
名称 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
表 21. 结果
名称 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
表 22. 结果
名称 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

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

© . All rights reserved.