K-核分解

有向

无向

异构节点

异构关系

加权关系

词汇表

有向: 有向特性。该算法在有向图上定义良好。
有向: 有向特性。该算法忽略图的方向。
有向: 有向特性。该算法不能在有向图上运行。
无向: 无向特性。该算法在无向图上定义良好。
无向: 无向特性。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法能够区分不同类型的节点。
异构节点: 异构节点允许。该算法对所有选定的节点一视同仁，无论其标签如何。
异构关系: 异构关系完全支持。该算法能够区分不同类型的关系。
异构关系: 异构关系允许。该算法对所有选定的关系一视同仁，无论其类型如何。
加权关系: 加权特性。该算法支持将关系属性用作权重，通过 relationshipWeightProperty 配置参数指定。
加权关系: 加权特性。该算法将每个关系视为同等重要，忽略任何关系权重的值。

简介

K-核分解是一种根据图的度序列和拓扑结构将图中的节点分成组的过程。

术语 i-核 指的是原始图的一个最大子图，其中该子图中的每个节点都至少具有 i 度。最大性确保不可能找到另一个具有更多节点且满足此度属性的子图。

由 i-核 表示的子图中的节点也属于由 j-核 表示的子图，对于任何 j<i 都成立。然而反之则不然。每个节点 u 都关联着一个核心值，该值表示最大的 *i* 值，使得 *u* 属于 i-核。最大的核心值称为图的 *退化度*。

K-核分解的标准算法迭代地移除度数最低的节点，直到图变空。当一个节点从图中移除时，其所有关系都将被移除，其邻居的度数也会减一。通过这种方法，不同的核心组会逐一被发现。

Neo4j GDS 库提供了基于两种最新方法的问题并行实现

多核平台上的并行 k-核分解

ParK：多核处理器上高效的 k-核分解算法

K-核分解可在从社交网络分析到生物信息学等多个领域中应用。一些可能的用例此处呈现。

语法

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

每种模式下的 K-核分解语法

在命名图上以流模式运行 K-核分解。

CALL gds.kcore.stream(
  graphName: String,
  configuration: Map
) YIELD
  nodeId: Integer,
  coreValue: Float

表 1. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`不适用`	否	目录中存储的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
1. 在 GDS 会话中，默认值为可用处理器数量

表 3. 结果
名称	类型	描述
节点ID	整数	节点 ID。
核心值	浮点数	核心值。

在命名图上以统计模式运行 K-核分解。

CALL gds.kcore.stats(
  graphName: String,
  configuration: Map
) YIELD
  degeneracy: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  configuration: Map

表 4. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`不适用`	否	目录中存储的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 5. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[2]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
2. 在 GDS 会话中，默认值为可用处理器数量

表 6. 结果
名称	类型	描述
退化度	整数	图中的最大核心值。
预处理毫秒数	整数	预处理图所需毫秒数。
计算毫秒数	整数	运行算法所需毫秒数。
后处理毫秒数	整数	计算统计数据所需毫秒数。
配置	Map	用于运行算法的配置。

在命名图上以变异模式运行 K-核分解。

CALL gds.kcore.mutate(
  graphName: String,
  configuration: Map
) YIELD
  degeneracy: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  mutateMillis: Integer,
  nodePropertiesWritten: Integer,
  configuration: Map

表 7. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`不适用`	否	目录中存储的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 8. 配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`不适用`	否	GDS 图中用于写入核心值的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松跟踪算法进度的 ID。

表 9. 结果
名称	类型	描述
退化度	整数	图中的最大核心值。
预处理毫秒数	整数	预处理图所需毫秒数。
计算毫秒数	整数	运行算法所需毫秒数。
后处理毫秒数	整数	计算统计数据所需毫秒数。
变异毫秒数	整数	向投影图添加属性所需毫秒数。
写入的节点属性数	整数	添加到投影图的属性数量。
配置	Map	用于运行算法的配置。

在命名图上以写入模式运行 K-核分解。

CALL gds.kcore.write(
  graphName: String,
  configuration: Map
) YIELD
  degeneracy: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  writeMillis: Integer,
  nodePropertiesWritten: Integer,
  configuration: Map

表 10. 参数
名称	类型	默认值	可选	描述
graphName	字符串	`不适用`	否	目录中存储的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 11. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[3]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
写入并发数	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`不适用`	否	Neo4j 数据库中用于写入核心值的节点属性。
3. 在 GDS 会话中，默认值为可用处理器数量

表 12. 结果
名称	类型	描述
退化度	整数	图中的最大核心值。
预处理毫秒数	整数	预处理图所需毫秒数。
计算毫秒数	整数	运行算法所需毫秒数。
后处理毫秒数	整数	计算统计数据所需毫秒数。
写入毫秒数	整数	写回结果数据所需毫秒数。
写入的节点属性数	整数	写入 Neo4j 的属性数量。
配置	Map	用于运行算法的配置。

示例

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

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

在本节中，我们将展示在具体图上运行 K-核分解算法的示例。目的是说明结果是什么样子，并提供在实际环境中如何使用该算法的指南。我们将在一个由少数节点以特定模式连接的小型社交网络图上进行此操作。示例图如下所示

以下 Cypher 语句将在 Neo4j 数据库中创建示例图

CREATE
  (alice:User {name: 'Alice'}),
  (bridget:User {name: 'Bridget'}),
  (charles:User {name: 'Charles'}),
  (doug:User {name: 'Doug'}),
  (eli:User {name: 'Eli'}),
  (filip:User {name: 'Filip'}),
  (greg:User {name: 'Greg'}),
  (harry:User {name: 'Harry'}),
  (ian:User {name: 'Ian'}),
  (james:User {name: 'James'}),

  (alice)-[:FRIEND]->(bridget),
  (bridget)-[:FRIEND]->(charles),
  (charles)-[:FRIEND]->(doug),
  (charles)-[:FRIEND]->(harry),
  (doug)-[:FRIEND]->(eli),
  (doug)-[:FRIEND]->(filip),
  (doug)-[:FRIEND]->(greg),
  (eli)-[:FRIEND]->(filip),
  (eli)-[:FRIEND]->(greg),
  (filip)-[:FRIEND]->(greg),
  (greg)-[:FRIEND]->(harry),
  (ian)-[:FRIEND]->(james)

有了 Neo4j 中的图，我们现在可以将其投影到图目录中，为算法执行做准备。我们使用针对 User 节点和 FRIEND 关系的 Cypher 投影来完成此操作。

以下语句将使用无向投影投影一个图，并将其以名称“graph”存储在图目录中。

MATCH (source:User)-[r:FRIEND]->(target:User)
RETURN gds.graph.project(
  'graph',
  source,
  target,
  {},
  { undirectedRelationshipTypes: ['*'] }
)

该图以 UNDIRECTED 方向投影，因为友情关系是关联的。

内存估算

首先，我们将使用 estimate 过程估算运行算法的成本。这可以在任何执行模式下完成。在此示例中，我们将使用 write 模式。估算算法有助于了解在图上运行算法对内存的影响。当您稍后实际在某种执行模式下运行算法时，系统将执行估算。如果估算显示执行极有可能超出其内存限制，则将禁止执行。要了解更多信息，请参阅自动估算和执行阻止。

有关 estimate 的更多详细信息，请参阅内存估算。

以下将估算运行算法所需的内存

CALL gds.kcore.write.estimate('graph', { writeProperty: 'coreValue' })
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
节点数	关系数	最小字节数	最大字节数	所需内存
10	24	1456	1456	"1456 字节"

流

在 stream 执行模式下，算法返回每个节点的核心值。这使我们能够直接检查结果，或在 Cypher 中对其进行后处理，而没有任何副作用。例如，我们可以对结果进行排序，以找到具有最高核心值的节点。

有关 stream 模式的更多详细信息，请参阅流。

以下将在 stream 模式下运行算法

CALL gds.kcore.stream('graph')
YIELD nodeId, coreValue
RETURN gds.util.asNode(nodeId).name AS name, coreValue
ORDER BY coreValue ASC, name DESC

表 14. 结果
名称	核心值
"James"	1
"Ian"	1
"Bridget"	1
"Alice"	1
"Harry"	2
"Charles"	2
"Greg"	3
"Filip"	3
"Eli"	3
"Doug"	3

算法将图中的节点分为三个不同的组。第一个组中所有节点的核心值都等于 1，包括 James、Ian、Bridget 和 Alice。第二个组包括 Harry 和 Charles，其中所有节点的核心值都等于 2。第三个组包括 Greg、Filip、Eli 和 Doug，所有节点的核心值都等于 3。

正如简介中所解释的，核心值为 i 的节点在仅包含核心值至少为 i 的节点的子图中，其度数至少为 *i*。例如，尽管 Charles 的度数为 3，但他不能成为 3-核子图的一部分，因为其邻居之一是来自核心值为 1 的第一组的 Bridget。一旦 Bridget 被排除，Charles 的度数就剩下 2，这作为其核心值的上限。其剩余的两个邻居之一是属于 3-核的 Doug。

请注意，结果显示，不同连通分量中的节点可能属于同一个核心组（例如 Ian 和 Alice）。

统计

在 stats 执行模式下，算法返回一行包含算法结果摘要的数据。此执行模式没有任何副作用。通过检查 computeMillis 返回项来评估算法性能非常有用。在下面的示例中，我们将省略返回时间。该过程的完整签名可以在语法部分找到。

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

以下将在 stats 模式下运行算法

CALL gds.kcore.stats('graph')
YIELD degeneracy
RETURN degeneracy

表 15. 结果
退化度
3

正如流示例的结果也证实，退化度，即最大核心值，等于三。

变异

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

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

以下将在 mutate 模式下运行算法

CALL gds.kcore.mutate('graph', { mutateProperty: 'coreValue' })
YIELD degeneracy, nodePropertiesWritten
RETURN degeneracy , nodePropertiesWritten

表 16. 结果
退化度	写入的节点属性数
3	10

返回的结果与 stats 示例相同。此外，内存中的图现在具有一个节点属性 coreValue，它存储每个节点的核心值。要了解如何检查内存中图的新模式，请参阅列出目录中的图。

写入

write 执行模式扩展了 stats 模式，并带有一个重要的副作用：将每个节点的核心值作为属性写入 Neo4j 数据库。新属性的名称使用强制配置参数 writeProperty 指定。结果是一行摘要，类似于 stats，但带有一些额外的指标。write 模式使得可以直接将结果持久化到数据库。

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

以下将在 write 模式下运行算法

CALL gds.kcore.write('graph', { writeProperty: 'coreValue' })
YIELD degeneracy, nodePropertiesWritten
RETURN degeneracy , nodePropertiesWritten

表 17. 结果
退化度	写入的节点属性数
3	10

返回的结果与 stats 示例相同。此外，七个节点中的每个节点现在在 Neo4j 数据库中都有一个新的属性 coreValue，其中包含该节点的核心值。