K-核分解 (K-Core Decomposition)

术语表

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

简介

K-Core 分解是一个根据图的度序列和拓扑结构将图中节点进行分组的过程。

术语 i-core 指的是原始图的一个最大子图，其中该子图中的每个节点的度至少为 i。这种最大性确保了无法找到另一个包含更多节点且满足此度属性的子图。

对于任何 j<i，由 i-core 表示的子图中的节点也属于由 j-core 表示的子图。反之则不然。每个节点 u 都关联一个核心值（core value），该值表示 u 所属的 i-core 的最大 i 值。最大的核心值被称为该图的退化度（degeneracy）。

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

Neo4j GDS 库提供了一种基于近期两种解决该问题方法的并行实现：

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

ParK：一种用于多核处理器的高效 k-core 分解算法

K-Core 分解可应用于从社交网络分析到生物信息学的多个领域。此处列出了一些可能的用例。

语法

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

各模式下的 K-Core 分解语法

在命名图上以流（stream）模式运行 K-Core 分解。

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. 结果
名称	类型	描述
nodeId	整数	节点 ID。
coreValue	浮点数	核心值。

在命名图上以统计（stats）模式运行 K-Core 分解。

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. 结果
名称	类型	描述
degeneracy	整数	图中的最大核心值。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算统计数据的毫秒数。
配置	Map	运行算法所使用的配置。

在命名图上以变异（mutate）模式运行 K-Core 分解。

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`	是	用于运行算法的并发线程数。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。

表 9. 结果
名称	类型	描述
degeneracy	整数	图中的最大核心值。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算统计数据的毫秒数。
mutateMillis	整数	向投影图添加属性的毫秒数。
nodePropertiesWritten	整数	添加到投影图中的属性数量。
配置	Map	运行算法所使用的配置。

在命名图上以写入（write）模式运行 K-Core 分解。

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`	是	如果禁用，进度百分比将不会被记录。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`不适用`	否	Neo4j 数据库中用于写入核心值的节点属性。
3. 在 GDS 会话中，默认值为可用处理器的数量。

表 12. 结果
名称	类型	描述
degeneracy	整数	图中的最大核心值。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算统计数据的毫秒数。
writeMillis	整数	将结果数据写回的毫秒数。
nodePropertiesWritten	整数	写入 Neo4j 的属性数量。
配置	Map	用于运行算法的配置。

示例

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

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

在本节中，我们将展示在具体图上运行 K-Core 分解算法的示例。目的是说明结果的样子，并为如何在实际环境中使用该算法提供指导。我们将使用一个小型的社交网络图，其中包含以特定模式连接的少量节点。示例图如下所示：

以下 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. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
10	24	1456	1456	"1456 字节"

流（Stream）模式

在 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. 结果
名称 (name)	coreValue
"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。第二组（核心值为 2）包括 Harry 和 Charles。第三组（核心值为 3）包括 Greg、Filip、Eli 和 Doug。

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

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

统计（Stats）模式

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

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

以下语句将以 stats 模式运行该算法：

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

表 15. 结果
degeneracy
3

正如流模式示例的结果所证实的那样，退化度（即最大核心值）等于 3。

变异（Mutate）模式

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

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

以下语句将以 mutate 模式运行该算法：

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

表 16. 结果
degeneracy	nodePropertiesWritten
3	10

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

写入（Write）模式

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

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

以下语句将以 write 模式运行该算法：

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

表 17. 结果
degeneracy	nodePropertiesWritten
3	10

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