文章排名
词汇表
- 有向
-
有向特征。该算法在有向图上定义良好。
- 有向
-
有向特征。该算法忽略图的方向。
- 有向
-
有向特征。该算法不在有向图上运行。
- 无向
-
无向特征。该算法在无向图上定义良好。
- 无向
-
无向特征。该算法忽略图的无向性。
- 异构节点
-
异构节点 完整支持。该算法能够区分不同类型的节点。
- 异构节点
-
异构节点 允许。该算法将所有选定的节点视为相同,无论其标签如何。
- 异构关系
-
异构关系 完整支持。该算法能够区分不同类型的关系。
- 异构关系
-
异构关系 允许。该算法将所有选定的关系视为相同,无论其类型如何。
- 加权关系
-
加权特征。该算法支持使用关系属性作为权重,通过 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) 内。 |
整数 |
|
是 |
运行文章排名的最大迭代次数。 |
|
浮点数 |
|
是 |
迭代之间分数的最小变化。如果所有分数的变化都小于容差值,则结果被认为是稳定的,并且算法返回。 |
|
字符串 |
|
是 |
用作权重的关系属性的名称。如果未指定,则算法运行不加权。 |
|
sourceNodes |
节点或数字列表 |
|
是 |
用于计算个性化 Page 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) 内。 |
整数 |
|
是 |
运行文章排名的最大迭代次数。 |
|
浮点数 |
|
是 |
迭代之间分数的最小变化。如果所有分数的变化都小于容差值,则结果被认为是稳定的,并且算法返回。 |
|
字符串 |
|
是 |
用作权重的关系属性的名称。如果未指定,则算法运行不加权。 |
|
sourceNodes |
节点或数字列表 |
|
是 |
用于计算个性化 Page Rank 的节点或节点 ID。 |
scaler |
字符串或映射 |
|
是 |
应用于最终分数的缩放器的名称。支持的值为 |
名称 | 类型 | 描述 |
---|---|---|
ranIterations |
整数 |
运行的迭代次数。 |
didConverge |
布尔值 |
指示算法是否收敛。 |
preProcessingMillis |
整数 |
预处理图的毫秒数。 |
computeMillis |
整数 |
运行算法的毫秒数。 |
postProcessingMillis |
整数 |
计算 |
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
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
graphName |
字符串 |
|
否 |
存储在目录中的图的名称。 |
configuration |
映射 |
|
是 |
算法特定和/或图过滤的配置。 |
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
mutateProperty |
字符串 |
|
否 |
GDS 图中写入分数的节点属性。 |
字符串列表 |
|
是 |
使用给定的节点标签过滤命名图。 |
|
字符串列表 |
|
是 |
使用给定的关系类型过滤命名图。 |
|
整数 |
|
是 |
用于运行算法的并发线程数。 |
|
字符串 |
|
是 |
一个 ID,可以提供以更轻松地跟踪算法的进度。 |
|
dampingFactor |
浮点数 |
|
是 |
Page Rank 计算的阻尼因子。必须在 [0, 1) 内。 |
整数 |
|
是 |
运行文章排名的最大迭代次数。 |
|
浮点数 |
|
是 |
迭代之间分数的最小变化。如果所有分数的变化都小于容差值,则结果被认为是稳定的,并且算法返回。 |
|
字符串 |
|
是 |
用作权重的关系属性的名称。如果未指定,则算法运行不加权。 |
|
sourceNodes |
节点或数字列表 |
|
是 |
用于计算个性化 Page Rank 的节点或节点 ID。 |
scaler |
字符串或映射 |
|
是 |
应用于最终分数的缩放器的名称。支持的值为 |
名称 | 类型 | 描述 |
---|---|---|
ranIterations |
整数 |
运行的迭代次数。 |
didConverge |
布尔值 |
指示算法是否收敛。 |
preProcessingMillis |
整数 |
预处理图的毫秒数。 |
computeMillis |
整数 |
运行算法的毫秒数。 |
postProcessingMillis |
整数 |
计算 |
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
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
graphName |
字符串 |
|
否 |
存储在目录中的图的名称。 |
configuration |
映射 |
|
是 |
算法特定和/或图过滤的配置。 |
名称 | 类型 | 默认值 | 可选 | 描述 |
---|---|---|---|---|
字符串列表 |
|
是 |
使用给定的节点标签过滤命名图。具有任何给定标签的节点将被包含。 |
|
字符串列表 |
|
是 |
使用给定的关系类型过滤命名图。具有任何给定类型的关系将被包含。 |
|
整数 |
|
是 |
用于运行算法的并发线程数。 |
|
字符串 |
|
是 |
一个 ID,可以提供以更轻松地跟踪算法的进度。 |
|
布尔值 |
|
是 |
如果禁用,进度百分比将不会被记录。 |
|
整数 |
|
是 |
用于将结果写入 Neo4j 的并发线程数。 |
|
字符串 |
|
否 |
Neo4j 数据库中写入分数的节点属性。 |
|
dampingFactor |
浮点数 |
|
是 |
Page Rank 计算的阻尼因子。必须在 [0, 1) 内。 |
整数 |
|
是 |
运行文章排名的最大迭代次数。 |
|
浮点数 |
|
是 |
迭代之间分数的最小变化。如果所有分数的变化都小于容差值,则结果被认为是稳定的,并且算法返回。 |
|
字符串 |
|
是 |
用作权重的关系属性的名称。如果未指定,则算法运行不加权。 |
|
sourceNodes |
节点或数字列表 |
|
是 |
用于计算个性化 Page Rank 的节点或节点 ID。 |
scaler |
字符串或映射 |
|
是 |
应用于最终分数的缩放器的名称。支持的值为 |
名称 | 类型 | 描述 |
---|---|---|
ranIterations |
整数 |
运行的迭代次数。 |
didConverge |
布尔值 |
指示算法是否收敛。 |
preProcessingMillis |
整数 |
预处理图的毫秒数。 |
computeMillis |
整数 |
运行算法的毫秒数。 |
postProcessingMillis |
整数 |
计算 |
writeMillis |
整数 |
将结果数据写回的毫秒数。 |
nodePropertiesWritten |
整数 |
写入 Neo4j 的属性数。 |
centralityDistribution |
映射 |
包含最小值、最大值、平均值以及中心度值的第 50、75、90、95、99 和 999 百分位数的映射。 |
configuration |
映射 |
用于运行算法的配置。 |
示例
以下所有示例都应在空数据库中运行。 这些示例使用 Cypher 投影 作为规范。原生投影将在未来的版本中被弃用。 |
在本节中,我们将展示在具体图上运行文章排名算法的示例。目的是说明结果是什么样的,并提供如何在真实环境中使用该算法的指南。我们将在一个小型网页网络图上进行此操作,该图由少量节点以特定模式连接。示例图如下所示
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
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
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
配置参数。如果设置了该参数,则关联的属性值将用作关系权重。在 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
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
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
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
name | score |
---|---|
"首页" |
2.550761988515413 |
"关于" |
-0.036593974039468 |
"链接" |
-0.036593974039468 |
"产品" |
-0.036593974039468 |
"站点 A" |
-0.610245016599252 |
"站点 B" |
-0.610245016599252 |
"站点 C" |
-0.610245016599252 |
"站点 D" |
-0.610245016599252 |
将结果与流示例进行比较,我们可以看到得分的相对顺序是相同的。