Louvain

词汇表

有向

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

有向

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

有向

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

无向

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

无向

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

异构节点

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

异构节点

异构节点 允许。该算法对所有选定的节点进行类似的处理,而不管其标签如何。

异构关系

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

异构关系

异构关系 允许。该算法对所有选定的关系进行类似的处理,而不管其类型如何。

加权关系

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

加权关系

加权特征。该算法将每个关系视为同等重要,丢弃任何关系权重的值。

简介

Louvain 方法是一种用于检测大型网络中社区的算法。它最大化每个社区的模块度得分,其中模块度量化了节点分配到社区的质量。这意味着评估社区内节点的连接密度与在随机网络中连接密度的差异。

Louvain 算法是一种层次聚类算法,它递归地将社区合并成单个节点,并在压缩后的图上执行模块度聚类。

有关此算法的更多信息,请参阅

运行此算法需要足够的内存可用性。在运行此算法之前,我们建议您阅读内存估算

语法

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

每种模式下的 Louvain 语法
在命名图上以流模式运行 Louvain。
CALL gds.louvain.stream(
  graphName: String,
  configuration: Map
)
YIELD
  nodeId: Integer,
  communityId: Integer,
  intermediateCommunityIds: List of Integer
表 1. 参数
名称 类型 默认值 可选 描述

graphName

字符串

n/a

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

configuration

映射

{}

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

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

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4

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

jobId

字符串

内部生成

可以提供的 ID,以便更轻松地跟踪算法的进度。

logProgress

布尔值

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

relationshipWeightProperty

字符串

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

seedProperty

字符串

n/a

用于设置节点的初始社区。属性值需要是非负数。

maxLevels

整数

10

图聚类然后压缩的级别最大数量。

maxIterations

整数

10

模块度优化在每个级别运行的最大迭代次数。

tolerance

浮点数

0.0001

迭代之间模块度的最小变化。如果模块度的变化小于容差值,则结果被认为是稳定的,算法返回。

includeIntermediateCommunities

布尔值

指示是否写入中间社区。如果设置为 false,则仅持久化最终社区。

consecutiveIds

布尔值

标志,用于决定组件标识符是否映射到连续的 ID 空间(需要额外的内存)。不能与includeIntermediateCommunities标志一起使用。

minCommunitySize

整数

0

仅返回社区大小大于或等于给定值的社区内的节点。

表 3. 结果
名称 类型 描述

nodeId

整数

节点 ID。

communityId

整数

最终级别的社区 ID。

intermediateCommunityIds

整数列表

每个级别的社区 ID。如果includeIntermediateCommunities设置为 false,则为Null

在命名图上以统计模式运行 Louvain。
CALL gds.louvain.stats(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  communityCount: Integer,
  ranLevels: Integer,
  modularity: Float,
  modularities: List of Float,
  communityDistribution: Map,
  configuration: Map
表 4. 参数
名称 类型 默认值 可选 描述

graphName

字符串

n/a

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

configuration

映射

{}

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

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

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4

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

jobId

字符串

内部生成

可以提供的 ID,以便更轻松地跟踪算法的进度。

logProgress

布尔值

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

relationshipWeightProperty

字符串

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

seedProperty

字符串

n/a

用于设置节点的初始社区。属性值需要是非负数。

maxLevels

整数

10

图聚类然后压缩的级别最大数量。

maxIterations

整数

10

模块度优化在每个级别运行的最大迭代次数。

tolerance

浮点数

0.0001

迭代之间模块度的最小变化。如果模块度的变化小于容差值,则结果被认为是稳定的,算法返回。

includeIntermediateCommunities

布尔值

指示是否写入中间社区。如果设置为 false,则仅持久化最终社区。

consecutiveIds

布尔值

标志,用于决定组件标识符是否映射到连续的 ID 空间(需要额外的内存)。不能与includeIntermediateCommunities标志一起使用。

表 6. 结果
名称 类型 描述

preProcessingMillis

整数

预处理数据所用的毫秒数。

computeMillis

整数

运行算法所用的毫秒数。

postProcessingMillis

整数

计算百分位数和社区计数所用的毫秒数。

communityCount

整数

找到的社区数量。

ranLevels

整数

算法实际运行的超步数。

modularity

浮点数

最终模块度得分。

modularities

浮点数列表

每个级别的模块度得分。

communityDistribution

映射

包含最小值、最大值、平均值以及最后级别的社区大小的 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位数值的映射。

configuration

映射

用于运行算法的配置。

在命名图上以变异模式运行 Louvain。
CALL gds.louvain.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  mutateMillis: Integer,
  postProcessingMillis: Integer,
  communityCount: Integer,
  ranLevels: Integer,
  modularity: Float,
  modularities: List of Float,
  nodePropertiesWritten: Integer,
  communityDistribution: Map,
  configuration: Map
表 7. 参数
名称 类型 默认值 可选 描述

graphName

字符串

n/a

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

configuration

映射

{}

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

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

mutateProperty

字符串

n/a

GDS 图中将社区 ID 写入的节点属性。

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4

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

jobId

字符串

内部生成

可以提供的 ID,以便更轻松地跟踪算法的进度。

relationshipWeightProperty

字符串

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

seedProperty

字符串

n/a

用于设置节点的初始社区。属性值需要是非负数。

maxLevels

整数

10

图聚类然后压缩的级别最大数量。

maxIterations

整数

10

模块度优化在每个级别运行的最大迭代次数。

tolerance

浮点数

0.0001

迭代之间模块度的最小变化。如果模块度的变化小于容差值,则结果被认为是稳定的,算法返回。

includeIntermediateCommunities

布尔值

指示是否写入中间社区。如果设置为 false,则仅持久化最终社区。

consecutiveIds

布尔值

标志,用于决定组件标识符是否映射到连续的 ID 空间(需要额外的内存)。不能与includeIntermediateCommunities标志一起使用。

表 9. 结果
名称 类型 描述

preProcessingMillis

整数

预处理数据所用的毫秒数。

computeMillis

整数

运行算法所用的毫秒数。

mutateMillis

整数

向投影图添加属性所用的毫秒数。

postProcessingMillis

整数

计算百分位数和社区计数所用的毫秒数。

communityCount

整数

找到的社区数量。

ranLevels

整数

算法实际运行的超步数。

modularity

浮点数

最终模块度得分。

modularities

浮点数列表

每个级别的模块度得分。

nodePropertiesWritten

整数

添加到投影图的属性数量。

communityDistribution

映射

包含最小值、最大值、平均值以及最后级别的社区大小的 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位数值的映射。

configuration

映射

用于运行算法的配置。

在命名图上以写入模式运行 Louvain。
CALL gds.louvain.write(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  writeMillis: Integer,
  postProcessingMillis: Integer,
  nodePropertiesWritten: Integer,
  communityCount: Integer,
  ranLevels: Integer,
  modularity: Float,
  modularities: List of Float,
  communityDistribution: Map,
  configuration: Map
表 10. 参数
名称 类型 默认值 可选 描述

graphName

字符串

n/a

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

configuration

映射

{}

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

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

nodeLabels

字符串列表

['*']

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

relationshipTypes

字符串列表

['*']

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

concurrency

整数

4

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

jobId

字符串

内部生成

可以提供的 ID,以便更轻松地跟踪算法的进度。

logProgress

布尔值

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

writeConcurrency

整数

'concurrency'的值

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

writeProperty

字符串

n/a

Neo4j 数据库中将社区 ID 写入的节点属性。

relationshipWeightProperty

字符串

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

seedProperty

字符串

n/a

用于设置节点的初始社区。属性值需要是非负数。

maxLevels

整数

10

图聚类然后压缩的级别最大数量。

maxIterations

整数

10

模块度优化在每个级别运行的最大迭代次数。

tolerance

浮点数

0.0001

迭代之间模块度的最小变化。如果模块度的变化小于容差值,则结果被认为是稳定的,算法返回。

includeIntermediateCommunities

布尔值

指示是否写入中间社区。如果设置为 false,则仅持久化最终社区。

consecutiveIds

布尔值

标志,用于决定组件标识符是否映射到连续的 ID 空间(需要额外的内存)。不能与includeIntermediateCommunities标志一起使用。

minCommunitySize

整数

0

仅将大小大于或等于给定值的社区的社区 ID 写入 Neo4j。

表 12. 结果
名称 类型 描述

preProcessingMillis

整数

预处理数据所用的毫秒数。

computeMillis

整数

运行算法所用的毫秒数。

writeMillis

整数

写入结果数据所用的毫秒数。

postProcessingMillis

整数

计算百分位数和社区计数所用的毫秒数。

nodePropertiesWritten

整数

写入的节点属性数量。

communityCount

整数

找到的社区数量。

ranLevels

整数

算法实际运行的超步数。

modularity

浮点数

最终模块度得分。

modularities

浮点数列表

每个级别的模块度得分。

communityDistribution

映射

包含最小值、最大值、平均值以及最后级别的社区大小的 p1、p5、p10、p25、p50、p75、p90、p95、p99 和 p999 百分位数值的映射。

configuration

映射

用于运行算法的配置。

示例

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

这些示例使用Cypher 投影作为规范。本机投影将在将来的版本中弃用。

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

Visualization of the example graph
以下 Cypher 语句将在 Neo4j 数据库中创建示例图
CREATE
  (nAlice:User {name: 'Alice', seed: 42}),
  (nBridget:User {name: 'Bridget', seed: 42}),
  (nCharles:User {name: 'Charles', seed: 42}),
  (nDoug:User {name: 'Doug'}),
  (nMark:User {name: 'Mark'}),
  (nMichael:User {name: 'Michael'}),

  (nAlice)-[:LINK {weight: 1}]->(nBridget),
  (nAlice)-[:LINK {weight: 1}]->(nCharles),
  (nCharles)-[:LINK {weight: 1}]->(nBridget),

  (nAlice)-[:LINK {weight: 5}]->(nDoug),

  (nMark)-[:LINK {weight: 1}]->(nDoug),
  (nMark)-[:LINK {weight: 1}]->(nMichael),
  (nMichael)-[:LINK {weight: 1}]->(nMark);

此图有两个紧密连接的用户集群。在这些集群之间有一条边。连接每个组件中节点的关系具有属性weight,该属性确定关系的强度。

现在,我们可以投影图并将其存储在图目录中。我们将LINK关系的定向设置为UNDIRECTED,因为这最适合 Louvain 算法。

以下语句将投影图并将其存储在图目录中。
MATCH (source:User)
OPTIONAL MATCH (source)-[r:LINK]->(target:User)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  {
    sourceNodeProperties: source { .seed },
    targetNodeProperties: target { .seed },
    relationshipProperties: r { .weight }
  },
  { undirectedRelationshipTypes: ['*'] }
)

在以下示例中,我们将演示在此图上使用 Louvain 算法。

内存估算

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

有关estimate的一般详细信息,请参阅内存估算

以下将估算运行算法所需的内存:
CALL gds.louvain.write.estimate('myGraph', { writeProperty: 'community' })
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
表 13. 结果
nodeCount relationshipCount bytesMin bytesMax requiredMemory

6

14

5321

563216

"[5321 字节 ... 550 KiB]"

stream执行模式下,算法返回每个节点的社区 ID。这使我们能够直接检查结果或在 Cypher 中对其进行后处理,而不会产生任何副作用。

有关stream模式的一般详细信息,请参阅

以下将运行算法并流式传输结果
CALL gds.louvain.stream('myGraph')
YIELD nodeId, communityId, intermediateCommunityIds
RETURN gds.util.asNode(nodeId).name AS name, communityId
ORDER BY name ASC
表 14. 结果
name communityId

"Alice"

3

"Bridget"

3

"Charles"

3

"Doug"

5

"Mark"

5

"Michael"

5

我们对过程配置参数使用默认值。级别和innerIterations设置为 10,容差值为 0.0001。

统计

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

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

以下将运行算法并以统计和测量值的格式返回结果
CALL gds.louvain.stats('myGraph')
YIELD communityCount
表 15. 结果
communityCount

2

变异

mutate 执行模式扩展了 stats 模式,并增加了一个重要的副作用:使用一个新的节点属性更新命名图,该属性包含该节点的社区 ID。新属性的名称使用强制配置参数 mutateProperty 指定。结果是一行类似于 stats 的摘要行,但包含一些额外的指标。当多个算法结合使用时,mutate 模式尤其有用。

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

以下将运行算法并将结果存储在 myGraph
CALL gds.louvain.mutate('myGraph', { mutateProperty: 'communityId' })
YIELD communityCount, modularity, modularities
表 16. 结果
communityCount modularity modularities

2

0.3571428571428571

[0.3571428571428571]

mutate 模式下,过程只返回一行。结果包含元信息,例如识别出的社区数量和模块化值。与 write 模式不同,结果写入 GDS 内存图而不是 Neo4j 数据库。

写入

write 执行模式扩展了 stats 模式,并增加了一个重要的副作用:将每个节点的社区 ID 作为属性写入 Neo4j 数据库。新属性的名称使用强制配置参数 writeProperty 指定。结果是一行类似于 stats 的摘要行,但包含一些额外的指标。write 模式能够将结果直接持久化到数据库中。

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

以下运行算法,并将结果写回
CALL gds.louvain.write('myGraph', { writeProperty: 'community' })
YIELD communityCount, modularity, modularities
表 17. 结果
communityCount modularity modularities

2

0.3571428571428571

[0.3571428571428571]

写回结果时,过程只返回一行。结果包含元信息,例如识别出的社区数量和模块化值。

加权

Louvain 算法也可以在加权图上运行,在计算模块化时考虑给定的关系权重。

以下将在加权图上运行算法并流式传输结果
CALL gds.louvain.stream('myGraph', { relationshipWeightProperty: 'weight' })
YIELD nodeId, communityId, intermediateCommunityIds
RETURN gds.util.asNode(nodeId).name AS name, communityId
ORDER BY name ASC
表 18. 结果
name communityId

"Alice"

1

"Bridget"

3

"Charles"

3

"Doug"

1

"Mark"

5

"Michael"

5

使用加权关系,我们看到 AliceDoug 形成了自己的社区,因为他们的链接比所有其他链接都强得多。

带种子

Louvain 算法可以通过提供种子属性来增量运行。使用种子属性可以为加载节点的子集提供初始社区映射。算法将尝试保留种子社区 ID。

以下将运行算法并流式传输结果
CALL gds.louvain.stream('myGraph', { seedProperty: 'seed' })
YIELD nodeId, communityId, intermediateCommunityIds
RETURN gds.util.asNode(nodeId).name AS name, communityId
ORDER BY name ASC
表 19. 结果
name communityId

"Alice"

42

"Bridget"

42

"Charles"

42

"Doug"

47

"Mark"

47

"Michael"

47

使用种子图,我们看到围绕 Alice 的社区保留了其初始社区 ID 42。另一个社区被分配了一个新的社区 ID,该 ID 保证大于最大的种子社区 ID。请注意,为了保留种子值,不能将 consecutiveIds 配置选项与种子一起使用。

使用中间社区

如前所述,Louvain 是一种分层聚类算法。这意味着在每个聚类步骤之后,属于同一聚类的所有节点都将缩减为单个节点。同一聚类中节点之间的关系成为自关系,与其他聚类节点的关系连接到聚类的代表。然后使用此压缩图来运行下一级聚类。重复此过程,直到聚类稳定。

为了演示这种迭代行为,我们需要构建一个更复杂的图。

louvain multilevel graph
CREATE (a:Node {name: 'a'})
CREATE (b:Node {name: 'b'})
CREATE (c:Node {name: 'c'})
CREATE (d:Node {name: 'd'})
CREATE (e:Node {name: 'e'})
CREATE (f:Node {name: 'f'})
CREATE (g:Node {name: 'g'})
CREATE (h:Node {name: 'h'})
CREATE (i:Node {name: 'i'})
CREATE (j:Node {name: 'j'})
CREATE (k:Node {name: 'k'})
CREATE (l:Node {name: 'l'})
CREATE (m:Node {name: 'm'})
CREATE (n:Node {name: 'n'})
CREATE (x:Node {name: 'x'})

CREATE (a)-[:TYPE]->(b)
CREATE (a)-[:TYPE]->(d)
CREATE (a)-[:TYPE]->(f)
CREATE (b)-[:TYPE]->(d)
CREATE (b)-[:TYPE]->(x)
CREATE (b)-[:TYPE]->(g)
CREATE (b)-[:TYPE]->(e)
CREATE (c)-[:TYPE]->(x)
CREATE (c)-[:TYPE]->(f)
CREATE (d)-[:TYPE]->(k)
CREATE (e)-[:TYPE]->(x)
CREATE (e)-[:TYPE]->(f)
CREATE (e)-[:TYPE]->(h)
CREATE (f)-[:TYPE]->(g)
CREATE (g)-[:TYPE]->(h)
CREATE (h)-[:TYPE]->(i)
CREATE (h)-[:TYPE]->(j)
CREATE (i)-[:TYPE]->(k)
CREATE (j)-[:TYPE]->(k)
CREATE (j)-[:TYPE]->(m)
CREATE (j)-[:TYPE]->(n)
CREATE (k)-[:TYPE]->(m)
CREATE (k)-[:TYPE]->(l)
CREATE (l)-[:TYPE]->(n)
CREATE (m)-[:TYPE]->(n);
以下语句将投影图并将其存储在图目录中。
MATCH (source:Node)
OPTIONAL MATCH (source)-[r:TYPE]->(target:Node)
RETURN gds.graph.project(
  'myGraph2',
  source,
  target,
  {},
  { undirectedRelationshipTypes: ['*'] }
)

流式传输中间社区

以下运行算法并流式传输结果,包括中间社区
CALL gds.louvain.stream('myGraph2', { includeIntermediateCommunities: true })
YIELD nodeId, communityId, intermediateCommunityIds
RETURN gds.util.asNode(nodeId).name AS name, communityId, intermediateCommunityIds
ORDER BY name ASC
表 20. 结果
name communityId intermediateCommunityIds

"a"

6

[2, 6]

"b"

6

[2, 6]

"c"

6

[6, 6]

"d"

6

[2, 6]

"e"

6

[6, 6]

"f"

6

[6, 6]

"g"

11

[11, 11]

"h"

11

[11, 11]

"i"

11

[11, 11]

"j"

10

[10, 10]

"k"

10

[10, 10]

"l"

10

[10, 10]

"m"

10

[10, 10]

"n"

10

[10, 10]

"x"

6

[6, 6]

在此示例图中,在第一次迭代之后,我们看到 4 个聚类,在第二次迭代中,它们缩减为三个。

修改中间社区

以下运行算法并修改内存图
CALL gds.louvain.mutate('myGraph2', {
  mutateProperty: 'intermediateCommunities',
  includeIntermediateCommunities: true
})
YIELD communityCount, modularity, modularities
表 21. 结果
communityCount modularity modularities

3

0.3816

[0.37599999999999995, 0.3816]

以下从内存图流式传输修改后的属性
CALL gds.graph.nodeProperty.stream('myGraph2', 'intermediateCommunities')
YIELD nodeId, propertyValue
RETURN
  gds.util.asNode(nodeId).name AS name,
  toIntegerList(propertyValue) AS intermediateCommunities
ORDER BY name ASC
表 22. 结果
name intermediateCommunities

"a"

[2, 6]

"b"

[2, 6]

"c"

[6, 6]

"d"

[2, 6]

"e"

[6, 6]

"f"

[6, 6]

"g"

[11, 11]

"h"

[11, 11]

"i"

[11, 11]

"j"

[10, 10]

"k"

[10, 10]

"l"

[10, 10]

"m"

[10, 10]

"n"

[10, 10]

"x"

[6, 6]

写入中间社区

以下运行算法并写入 Neo4j 数据库
CALL gds.louvain.write('myGraph2', {
  writeProperty: 'intermediateCommunities',
  includeIntermediateCommunities: true
})
YIELD communityCount, modularity, modularities
表 23. 结果
communityCount modularity modularities

3

0.3816

[0.37599999999999995, 0.3816]

以下从 Neo4j 数据库流式传输写入的属性
MATCH (n:Node) RETURN n.name AS name, toIntegerList(n.intermediateCommunities) AS intermediateCommunities
ORDER BY name ASC
表 24. 结果
name intermediateCommunities

"a"

[2, 6]

"b"

[2, 6]

"c"

[6, 6]

"d"

[2, 6]

"e"

[6, 6]

"f"

[6, 6]

"g"

[11, 11]

"h"

[11, 11]

"i"

[11, 11]

"j"

[10, 10]

"k"

[10, 10]

"l"

[10, 10]

"m"

[10, 10]

"n"

[10, 10]

"x"

[6, 6]