K-Core 分解

有向

无向

异构节点

异构关系

加权关系

词汇表

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

简介

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

术语i-core指的是原始图的一个最大子图，使得该子图中的每个节点的度数至少为i。最大性确保不可能找到另一个具有更多节点的子图，其中此度数属性成立。

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

K-Core分解的标准算法迭代地删除度数最低的节点，直到图变为空。当节点从图中删除时，其所有关系都会被删除，并且其邻居的度数会减少一。使用这种方法，可以逐一发现不同的核心组。

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

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

ParK：一种在多核处理器上进行k-core分解的有效算法

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

语法

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

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

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

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

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

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

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

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

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

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

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

表6. 结果
名称	类型	描述
degeneracy	整数	图中的最大核心值。
preProcessingMillis	整数	预处理图的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算统计信息的毫秒数。
configuration	映射	用于运行算法的配置。

在命名图上以变异模式运行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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定和/或图形过滤的配置。

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

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

在命名图上以写入模式运行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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定和/或图形过滤的配置。

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

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

例子

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

这些示例使用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执行模式下，算法返回每个节点的核心值。这使我们能够直接检查结果或在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. 结果
名称	coreValue
"詹姆斯"	1
"伊恩"	1
"布里奇特"	1
"爱丽丝"	1
"哈利"	2
"查尔斯"	2
"格雷格"	3
"菲利普"	3
"伊莱"	3
"道格"	3

该算法已将图中的节点分成三个不同的组。第一组中所有节点的核心值都等于1，包括詹姆斯、伊恩、布里奇特和爱丽丝。第二组包括哈利和查尔斯。在这里，所有节点的核心值都等于2。第三组包括格雷格、菲利普、伊莱和道格，所有节点的核心值都等于3。

正如在简介中解释的那样，核心值为i的节点在仅包含核心值至少为i的节点的子图中具有至少i的度数。例如，虽然查尔斯的度数为3，但他不能成为3-core子图的一部分，因为他的一个邻居是来自第一组核心值1的布里奇特。一旦排除布里奇特，查尔斯的度数就剩下2，这充当其核心值的上限。他剩下的两个邻居之一是道格，他属于3-core。

请注意，如结果所示，不同连通分量中的节点可能是同一核心组的一部分（例如伊恩和爱丽丝）。

统计数据

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

有关stats模式的一般详细信息，请参阅统计数据。

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

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

表15. 结果
degeneracy
3

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

变异

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 执行模式扩展了 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，其中包含该节点的核心值。