特征向量中心性

词汇表

有向

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

有向

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

有向

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

无向

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

无向

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

异构节点

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

异构节点

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

异构关系

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

异构关系

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

加权关系

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

加权关系

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

简介

特征向量中心性是一种衡量节点传递性影响的算法。源自高分节点的关系对节点得分的贡献大于来自低分节点的连接。较高的特征向量得分意味着一个节点连接到许多自身也具有高分数的节点。

该算法计算与最大绝对特征值相关的特征向量。为了计算该特征值,算法应用幂迭代方法。在每次迭代中,每个节点的中心性得分都从其入站邻居的得分中得出。在幂迭代方法中,特征向量在每次迭代后进行 L2 归一化,默认情况下导致归一化结果。

PageRank 算法是特征向量中心性的一种变体,具有额外的跳转概率。

注意事项

使用特征向量中心性算法时需要注意一些事项

  • 没有入站关系的节点的中心性得分将收敛到 0

  • 由于缺少度归一化,高阶节点对其邻居的得分有非常强的影响。

语法

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

每种模式的特征向量中心性语法
在命名图上以流模式运行特征向量中心性。
CALL gds.eigenvector.stream(
  graphName: String,
  configuration: Map
)
YIELD
  nodeId: Integer,
  score: Float
表 1. 参数
名称 类型 默认 可选 描述

graphName

String

不适用

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

configuration

Map

{}

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

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

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4 [1]

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

jobId

String

内部生成

可提供用于更轻松地跟踪算法进度的 ID。

logProgress

布尔

true

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

maxIterations

整数

20

特征向量中心性算法运行的最大迭代次数。

tolerance

浮点数

0.0000001

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

relationshipWeightProperty

String

null

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

sourceNodes

列表或节点或数字

[]

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

scaler

字符串或映射

None

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

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

表 3. 结果
名称 类型 描述

nodeId

整数

节点 ID。

score

浮点数

特征向量得分。

在命名图上以统计模式运行特征向量中心性。
CALL gds.eigenvector.stats(
  graphName: String,
  configuration: Map
)
YIELD
  ranIterations: Integer,
  didConverge: Boolean,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  centralityDistribution: Map,
  configuration: Map
表 4. 参数
名称 类型 默认 可选 描述

graphName

String

不适用

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

configuration

Map

{}

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

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

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4 [2]

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

jobId

String

内部生成

可提供用于更轻松地跟踪算法进度的 ID。

logProgress

布尔

true

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

maxIterations

整数

20

特征向量中心性算法运行的最大迭代次数。

tolerance

浮点数

0.0000001

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

relationshipWeightProperty

String

null

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

sourceNodes

列表或节点或数字

[]

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

scaler

字符串或映射

None

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

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

表 6. 结果
名称 类型 描述

ranIterations

整数

运行的迭代次数。

didConverge

布尔

指示算法是否收敛。

preProcessingMillis

整数

预处理图的毫秒数。

computeMillis

整数

运行算法的毫秒数。

postProcessingMillis

整数

计算 centralityDistribution 的毫秒数。

centralityDistribution

Map

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

configuration

Map

用于运行算法的配置。

在命名图上以变异模式运行特征向量中心性。
CALL gds.eigenvector.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

String

不适用

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

configuration

Map

{}

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

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

mutateProperty

String

不适用

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

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4

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

jobId

String

内部生成

可提供用于更轻松地跟踪算法进度的 ID。

maxIterations

整数

20

特征向量中心性算法运行的最大迭代次数。

tolerance

浮点数

0.0000001

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

relationshipWeightProperty

String

null

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

sourceNodes

列表或节点或数字

[]

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

scaler

字符串或映射

None

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

表 9. 结果
名称 类型 描述

ranIterations

整数

运行的迭代次数。

didConverge

布尔

指示算法是否收敛。

preProcessingMillis

整数

预处理图的毫秒数。

computeMillis

整数

运行算法的毫秒数。

postProcessingMillis

整数

计算 centralityDistribution 的毫秒数。

mutateMillis

整数

将属性添加到内存图的毫秒数。

nodePropertiesWritten

整数

写入内存图的属性数量。

centralityDistribution

Map

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

configuration

Map

用于运行算法的配置。

在命名图上以写入模式运行特征向量中心性。
CALL gds.eigenvector.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

String

不适用

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

configuration

Map

{}

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

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

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4 [3]

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

jobId

String

内部生成

可提供用于更轻松地跟踪算法进度的 ID。

logProgress

布尔

true

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

writeConcurrency

整数

'concurrency' 的值

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

writeProperty

String

不适用

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

maxIterations

整数

20

特征向量中心性算法运行的最大迭代次数。

tolerance

浮点数

0.0000001

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

relationshipWeightProperty

String

null

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

sourceNodes

列表或节点或数字

[]

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

scaler

字符串或映射

None

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

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

表 12. 结果
名称 类型 描述

ranIterations

整数

运行的迭代次数。

didConverge

布尔

指示算法是否收敛。

preProcessingMillis

整数

预处理图的毫秒数。

computeMillis

整数

运行算法的毫秒数。

postProcessingMillis

整数

计算 centralityDistribution 的毫秒数。

writeMillis

整数

写回结果数据的毫秒数。

nodePropertiesWritten

整数

写入 Neo4j 的属性数量。

centralityDistribution

Map

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

configuration

Map

用于运行算法的配置。

示例

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

这些示例通常使用Cypher 投影。原生投影将在未来版本中弃用。

在本节中,我们将展示在具体图上运行特征向量中心性算法的示例。目的是说明结果是什么样子,并提供如何在实际设置中使用该算法的指南。我们将在一个小型 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.eigenvector.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.eigenvector.stream('myGraph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC
表 14. 结果
名称 score

"主页"

0.7465574981728249

"关于"

0.33997520529777137

"链接"

0.33997520529777137

"产品"

0.33997520529777137

"站点 A"

0.15484062876886298

"站点 B"

0.15484062876886298

"站点 C"

0.15484062876886298

"站点 D"

0.15484062876886298

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

统计

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

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

以下将运行算法并返回有关中心性得分的统计信息。
CALL gds.eigenvector.stats('myGraph', {
  maxIterations: 20
})
YIELD centralityDistribution
RETURN centralityDistribution.max AS max
表 15. 结果
max

0.7465591431

变异

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

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

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

8

20

写入

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

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

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

8

20

加权

默认情况下,算法将图中的关系视为无权重。要更改此行为,我们可以使用 relationshipWeightProperty 配置参数。如果设置了该参数,则关联的属性值将用作关系权重。在加权情况下,发送到其邻居的节点的先前分数乘以归一化的关系权重。请注意,负关系权重在计算过程中会被忽略。

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

以下将在 stream 模式下使用关系权重运行算法
CALL gds.eigenvector.stream('myGraph', {
  maxIterations: 20,
  relationshipWeightProperty: 'weight'
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC
表 18. 结果
名称 score

"主页"

0.8328163407319487

"产品"

0.5004775834976313

"关于"

0.1668258611658771

"链接"

0.1668258611658771

"站点 A"

0.008327591469710233

"站点 B"

0.008327591469710233

"站点 C"

0.008327591469710233

"站点 D"

0.008327591469710233

与无加权示例一样,“主页”节点的得分最高。相比之下,“产品”现在是第二高得分,而不是第四高。

我们使用 stream 模式来演示以 weighted 方式运行算法,但是,所有算法模式都支持 relationshipWeightProperty 配置参数。

容差

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

以下将在 stream 模式下使用高 tolerance 值运行算法
CALL gds.eigenvector.stream('myGraph', {
  maxIterations: 20,
  tolerance: 0.1
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC
表 19. 结果
名称 score

"主页"

0.7108273818583551

"关于"

0.3719400001993262

"链接"

0.3719400001993262

"产品"

0.3719400001993262

"站点 A"

0.14116155811301126

"站点 B"

0.14116155811301126

"站点 C"

0.14116155811301126

"站点 D"

0.14116155811301126

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

个性化特征向量中心性

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

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

以下将运行算法并流式传输结果
MATCH (siteA:Page {name: 'Site A'}), (siteB:Page {name: 'Site B'})
CALL gds.eigenvector.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

"主页"

0.7465645391567868

"关于"

0.33997203172449453

"链接"

0.33997203172449453

"产品"

0.33997203172449453

"站点 A"

0.15483736775159632

"站点 B"

0.15483736775159632

"站点 C"

0.15483736775159632

"站点 D"

0.15483736775159632

缩放中心性得分

在内部,中心性得分在每次迭代后使用 L2 归一化进行缩放。因此,最终值已经归一化。此行为无法更改,因为它属于幂迭代方法的一部分。

但是,为了将最终分数作为算法执行的一部分进行归一化,可以使用 scaler 配置参数。所有可用缩放器的描述可以在 scaleProperties 过程的文档中找到。

以下将在 stream 模式下运行算法并返回归一化结果
CALL gds.eigenvector.stream('myGraph', {
  scaler: "MINMAX"
})
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC
表 21. 结果
名称 score

"主页"

1.0

"关于"

0.312876962110942

"链接"

0.312876962110942

"产品"

0.312876962110942

"站点 A"

0.0

"站点 B"

0.0

"站点 C"

0.0

"站点 D"

0.0

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

© . All rights reserved.