文章排名

词汇表

有向

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

有向

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

有向

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

无向

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

无向

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

异构节点

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

异构节点

异构节点 允许。该算法将所有选定的节点视为相同,无论其标签如何。

异构关系

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

异构关系

异构关系 允许。该算法将所有选定的关系视为相同,无论其类型如何。

加权关系

加权特征。该算法支持使用关系属性作为权重,通过 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 算法时使用的语法。我们正在描述命名图变体的语法。要了解有关通用语法变体的更多信息,请参阅 语法概述

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

graphName

字符串

n/a

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

configuration

映射

{}

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

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

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4

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

jobId

字符串

内部生成

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

logProgress

布尔值

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

dampingFactor

浮点数

0.85

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

maxIterations

整数

20

运行文章排名的最大迭代次数。

tolerance

浮点数

0.0000001

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

relationshipWeightProperty

字符串

用作权重的关系属性的名称。如果未指定,则算法运行不加权。

sourceNodes

节点或数字列表

[]

用于计算个性化 Page Rank 的节点或节点 ID。

scaler

字符串或映射

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

表 3. 结果
名称 类型 描述

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
表 4. 参数
名称 类型 默认值 可选 描述

graphName

字符串

n/a

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

configuration

映射

{}

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

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

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4

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

jobId

字符串

内部生成

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

logProgress

布尔值

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

dampingFactor

浮点数

0.85

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

maxIterations

整数

20

运行文章排名的最大迭代次数。

tolerance

浮点数

0.0000001

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

relationshipWeightProperty

字符串

用作权重的关系属性的名称。如果未指定,则算法运行不加权。

sourceNodes

节点或数字列表

[]

用于计算个性化 Page Rank 的节点或节点 ID。

scaler

字符串或映射

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

表 6. 结果
名称 类型 描述

ranIterations

整数

运行的迭代次数。

didConverge

布尔值

指示算法是否收敛。

preProcessingMillis

整数

预处理图的毫秒数。

computeMillis

整数

运行算法的毫秒数。

postProcessingMillis

整数

计算 centralityDistribution 的毫秒数。

centralityDistribution

映射

包含最小值、最大值、平均值以及中心度值的第 50、75、90、95、99 和 999 百分位数的映射。

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
表 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

运行文章排名的最大迭代次数。

tolerance

浮点数

0.0000001

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

relationshipWeightProperty

字符串

用作权重的关系属性的名称。如果未指定,则算法运行不加权。

sourceNodes

节点或数字列表

[]

用于计算个性化 Page Rank 的节点或节点 ID。

scaler

字符串或映射

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

表 9. 结果
名称 类型 描述

ranIterations

整数

运行的迭代次数。

didConverge

布尔值

指示算法是否收敛。

preProcessingMillis

整数

预处理图的毫秒数。

computeMillis

整数

运行算法的毫秒数。

postProcessingMillis

整数

计算 centralityDistribution 的毫秒数。

mutateMillis

整数

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

nodePropertiesWritten

整数

写入投影图的属性数。

centralityDistribution

映射

包含最小值、最大值、平均值以及中心度值的第 50、75、90、95、99 和 999 百分位数的映射。

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
表 10. 参数
名称 类型 默认值 可选 描述

graphName

字符串

n/a

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

configuration

映射

{}

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

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

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4

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

jobId

字符串

内部生成

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

logProgress

布尔值

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

writeConcurrency

整数

'concurrency' 的值

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

writeProperty

字符串

n/a

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

dampingFactor

浮点数

0.85

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

maxIterations

整数

20

运行文章排名的最大迭代次数。

tolerance

浮点数

0.0000001

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

relationshipWeightProperty

字符串

用作权重的关系属性的名称。如果未指定,则算法运行不加权。

sourceNodes

节点或数字列表

[]

用于计算个性化 Page Rank 的节点或节点 ID。

scaler

字符串或映射

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

表 12. 结果
名称 类型 描述

ranIterations

整数

运行的迭代次数。

didConverge

布尔值

指示算法是否收敛。

preProcessingMillis

整数

预处理图的毫秒数。

computeMillis

整数

运行算法的毫秒数。

postProcessingMillis

整数

计算 centralityDistribution 的毫秒数。

writeMillis

整数

将结果数据写回的毫秒数。

nodePropertiesWritten

整数

写入 Neo4j 的属性数。

centralityDistribution

映射

包含最小值、最大值、平均值以及中心度值的第 50、75、90、95、99 和 999 百分位数的映射。

configuration

映射

用于运行算法的配置。

示例

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

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

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

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

"首页"

0.5607071761939444

"关于"

0.250337073634706

"链接"

0.250337073634706

"产品"

0.250337073634706

"站点 A"

0.18152391630760797

"站点 B"

0.18152391630760797

"站点 C"

0.18152391630760797

"站点 D"

0.18152391630760797

上面的查询以 stream 模式作为 unweighted 运行算法。下面,可以找到 加权图 的示例。

统计

stats 执行模式下,算法返回包含算法结果摘要的单行。例如特征向量统计返回中心度直方图,可用于监控所有计算节点的中心度分数的分布。这种执行模式没有任何副作用。它可以通过检查 computeMillis 返回项来评估算法性能。在下面的示例中,我们将省略返回计时。该过程的完整签名可以在 语法部分 中找到。

有关 stats 模式的更多详细信息,请参阅 统计

以下将运行算法并返回有关中心度分数的统计信息。
CALL gds.articleRank.stats('myGraph')
YIELD centralityDistribution
RETURN centralityDistribution.max AS max
表 15. 结果
max

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 配置参数。如果设置了该参数,则关联的属性值将用作关系权重。在 weighted 情况下,发送到其邻居的节点的先前分数将乘以归一化的关系权重。请注意,负关系权重在计算过程中会被忽略。

在以下示例中,我们使用输入图的 weight 属性作为关系权重属性。

以下将在 stream 模式下使用关系权重运行算法。
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. 结果
name score

"首页"

0.5160810726222141

"产品"

0.24570958074084706

"关于"

0.1819031935802824

"链接"

0.1819031935802824

"站点 A"

0.15281123078335393

"站点 B"

0.15281123078335393

"站点 C"

0.15281123078335393

"站点 D"

0.15281123078335393

与不加权示例一样,“首页”节点具有最高分数。相反,“产品”现在具有第二高分数,而不是第四高分数。

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

容差

tolerance 配置参数表示迭代之间分数的最小变化。如果所有分数的变化都小于配置的容差,则迭代将中止并被认为已收敛。请注意,设置更高的容差会导致更早的收敛,但也导致更不准确的中心度分数。

以下将在 stream 模式下使用高 tolerance 值运行算法。
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. 结果
name score

"首页"

0.4470707071

"关于"

0.2300021265

"链接"

0.2300021265

"产品"

0.2300021265

"站点 A"

0.1688888889

"站点 B"

0.1688888889

"站点 C"

0.1688888889

"站点 D"

0.1688888889

我们使用 tolerance: 0.1,这导致与 流示例 相比略有不同的结果。但是,计算在四次迭代后收敛,我们已经可以观察到结果分数的趋势。

个性化文章排名

个性化文章排名是文章排名的变体,它偏向于一组sourceNodes。默认情况下,幂迭代从所有节点的相同值开始:1 / |V|。对于给定的源节点集S,每个源节点的初始值设置为1 / |S|,对于所有剩余节点设置为0

以下示例展示了如何以“站点 A”和“站点 B”为中心运行特征向量中心性。

以下将运行算法并流式传输结果
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. 结果
name score

"站点 A"

0.15249052775314756

"站点 B"

0.15249052775314756

"首页"

0.1105231342997017

"关于"

0.019777824032578193

"链接"

0.019777824032578193

"产品"

0.019777824032578193

"站点 C"

0.002490527753147571

"站点 D"

0.002490527753147571

将这些结果与来自流示例的结果(它没有使用sourceNodes配置参数)进行比较,可以看出我们用在sourceNodes列表中的“站点 A”和站点 B节点现在排名第二和第三,而不是第四和第五。

缩放中心性得分

为了在算法执行期间将最终得分标准化,可以使用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
表 21. 结果
name score

"首页"

2.550761988515413

"关于"

-0.036593974039468

"链接"

-0.036593974039468

"产品"

-0.036593974039468

"站点 A"

-0.610245016599252

"站点 B"

-0.610245016599252

"站点 C"

-0.610245016599252

"站点 D"

-0.610245016599252

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