模块度优化 (Modularity Optimization)

术语表

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

简介

模块度优化算法旨在基于模块度（Modularity）检测图中的社群。模块度是衡量图结构的一种指标，用于测量模块或社群内部连接的密度。高模块度得分的图在社群内部拥有许多连接，而指向其他社群的连接则较少。该算法会为每个节点进行探索，判断如果将其移动到邻近节点的社群中，其模块度得分是否会提高。

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

运行此算法需要足够的可用内存。在运行之前，建议您阅读内存估计 (Memory Estimation)。

语法

各模式下的模块度优化语法

在命名图上以流（stream）模式运行模块度优化。

CALL gds.modularityOptimization.stream(graphName: String, configuration: Map)
YIELD
  nodeId: Integer,
  communityId: Integer

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

表 2. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
maxIterations	整数	`10`	是	运行的最大迭代次数。
tolerance	浮点数	`0.0001`	是	迭代之间模块度的最小变化值。如果模块度变化小于该容差值，则结果被视为稳定，算法终止。
seedProperty	字符串	`不适用`	是	用于定义初始标签集（必须为非负数）。
consecutiveIds	布尔值	`false`	是	用于决定组件标识符是否映射到连续 ID 空间的标志（需要额外的内存）。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
minCommunitySize	整数	`0`	是	仅将大小大于或等于给定值的社区的社区 ID 写入 Neo4j。
1. 在 GDS 会话中，默认值为可用处理器的数量。

表 3. 结果
名称	类型	描述
nodeId	整数	节点 ID
communityId	整数	社群 ID

在命名图上以统计（stats）模式运行模块度优化。

CALL gds.modularityOptimization.stats(graphName: String, configuration: Map)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  communityCount: Integer,
  communityDistribution: Map,
  modularity: Float,
  ranIterations: Integer,
  didConverge: Boolean,
  nodes: Integer,
  configuration: Map

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

表 5. 常规配置
名称	类型	默认	可选	描述
concurrency	整数	`4 ^[2]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
communityProperty	字符串	`不适用`	否	节点属性，用于存储每个节点的社群 ID（整数）。请注意，只有非负社群 ID 才被视为有效，并会据此计算模块度得分。
2. 在 GDS 会话中，默认值为可用处理器的数量。

表 6. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	['*']	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	['*']	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	4 ^[3]	是	用于运行算法的并发线程数。
jobId	字符串	内部生成	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	true	是	如果禁用，进度百分比将不会被记录。
maxIterations	整数	10	是	运行的最大迭代次数。
tolerance	浮点数	0.0001	是	迭代之间模块度的最小变化值。如果模块度变化小于该容差值，则结果被视为稳定，算法终止。
seedProperty	字符串	不适用	是	用于定义初始标签集（必须为非负数）。
consecutiveIds	布尔值	false	是	用于决定组件标识符是否映射到连续 ID 空间的标志（需要额外的内存）。
relationshipWeightProperty	字符串	null	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
3. 在 GDS 会话中，默认值为可用处理器的数量。

表 7. 结果
名称	类型	描述
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
postProcessingMillis	整数	计算百分位数和社区数量所需的毫秒数。
节点	整数	所考虑的节点数量。
didConverge	布尔值	如果算法在给定的最大迭代次数内收敛到稳定的模块度得分，则为 True。
ranIterations	整数	运行的迭代次数。
modularity	浮点数	最终的模块度得分。
communityCount	整数	发现的社区数量。
communityDistribution	Map	包含社群大小的最小值、最大值、平均值，以及 50、75、90、95、99 和 999 百分位数。
配置	Map	用于运行算法的配置。

在命名图上以变异（mutate）模式运行模块度优化。

CALL gds.modularityOptimization.mutate(graphName: String, configuration: Map})
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  mutateMillis: Integer,
  communityCount: Integer,
  communityDistribution: Map,
  modularity: Float,
  ranIterations: Integer,
  didConverge: Boolean,
  nodes: Integer,
  configuration: Map

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

表 9. 配置
名称	类型	默认	可选	描述
mutateProperty	字符串	`不适用`	否	GDS 图中用于写入社群信息的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
seedProperty	字符串	`不适用`	是	用于为节点设置初始社群。属性值必须为数字。
maxIterations	整数	`10`	是	模块度优化在每个层级运行的最大迭代次数。
tolerance	浮点数	`0.0001`	是	迭代之间模块度的最小变化值。如果模块度变化小于该容差值，则结果被视为稳定，算法终止。
consecutiveIds	布尔值	`false`	是	用于决定组件标识符是否映射到连续 ID 空间的标志（需要额外的内存）。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。

表 10. 结果
名称	类型	描述
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
mutateMillis	整数	向投影图添加属性的毫秒数。
postProcessingMillis	整数	计算百分位数和社区数量所需的毫秒数。
节点	整数	所考虑的节点数量。
didConverge	布尔值	如果算法在给定的最大迭代次数内收敛到稳定的模块度得分，则为 True。
ranIterations	整数	运行的迭代次数。
modularity	浮点数	最终的模块度得分。
communityCount	整数	发现的社区数量。
communityDistribution	Map	包含社群大小的最小值、最大值、平均值，以及 50、75、90、95、99 和 999 百分位数。
配置	Map	用于运行算法的配置。

在命名图上以写入（write）模式运行模块度优化。

CALL gds.modularityOptimization.write(graphName: String, configuration: Map})
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  postProcessingMillis: Integer,
  writeMillis: Integer,
  communityCount: Integer,
  communityDistribution: Map,
  modularity: Float,
  ranIterations: Integer,
  didConverge: Boolean,
  nodes: Integer,
  configuration: Map

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

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

表 13. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[5]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeProperty	字符串	`不适用`	否	Neo4j 数据库中用于写入社群信息的节点属性。
seedProperty	字符串	`不适用`	是	用于为节点设置初始社群。属性值必须为数字。
maxIterations	整数	`10`	是	模块度优化在每个层级运行的最大迭代次数。
tolerance	浮点数	`0.0001`	是	迭代之间模块度的最小变化值。如果模块度变化小于该容差值，则结果被视为稳定，算法终止。
consecutiveIds	布尔值	`false`	是	用于决定组件标识符是否映射到连续 ID 空间的标志（需要额外的内存）。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
minCommunitySize	整数	`0`	是	仅将大小大于或等于给定值的社区的社区 ID 写入 Neo4j。
5. 在 GDS 会话中，默认值为可用处理器数量。

表 14. 结果
名称	类型	描述
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
writeMillis	整数	将结果数据写回的毫秒数。
postProcessingMillis	整数	计算百分位数和社区数量所需的毫秒数。
节点	整数	所考虑的节点数量。
didConverge	布尔值	如果算法在给定的最大迭代次数内收敛到稳定的模块度得分，则为 True。
ranIterations	整数	运行的迭代次数。
modularity	浮点数	最终的模块度得分。
communityCount	整数	发现的社区数量。
communityDistribution	Map	包含社群大小的最小值、最大值、平均值，以及 50、75、90、95、99 和 999 百分位数。
配置	Map	用于运行算法的配置。

示例

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

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

考虑由以下 Cypher 语句创建的图

CREATE
  (a:Person {name:'Alice'})
, (b:Person {name:'Bridget'})
, (c:Person {name:'Charles'})
, (d:Person {name:'Doug'})
, (e:Person {name:'Elton'})
, (f:Person {name:'Frank'})
, (a)-[:KNOWS {weight: 0.01}]->(b)
, (a)-[:KNOWS {weight: 5.0}]->(e)
, (a)-[:KNOWS {weight: 5.0}]->(f)
, (b)-[:KNOWS {weight: 5.0}]->(c)
, (b)-[:KNOWS {weight: 5.0}]->(d)
, (c)-[:KNOWS {weight: 0.01}]->(e)
, (f)-[:KNOWS {weight: 0.01}]->(d)

该图由两个中心节点“Alice”和“Bridget”组成，每个中心节点有两个邻居。此外，“Alice”的每个邻居都与“Bridget”的一个邻居相连。观察关系的权重，可以看出从两个中心节点到其邻居的连接非常强，而这些组之间的连接较弱。因此，模块度优化算法应检测到两个社群：“Alice”及其邻居组成的社群，以及“Bob”及其邻居组成的社群。

以下语句将投影图并将其存储在图目录中。

MATCH (source:Person)-[r:KNOWS]->(target:Person)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  { relationshipProperties: r { .weight } },
  { undirectedRelationshipTypes: ['*'] }
)

内存估算

首先，我们将使用 estimate 过程估算运行算法的成本。这可以在任何执行模式下完成。在这个例子中我们将使用 write 模式。估算算法有助于了解在您的图上运行该算法将产生的内存影响。当您随后在其中一种执行模式下真正运行算法时，系统将执行一次估算。如果估算显示执行超出其内存限制的可能性非常高，则禁止执行。要阅读更多关于此的内容，请参阅自动估算和执行阻塞。

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

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

CALL gds.modularityOptimization.write.estimate('myGraph', { relationshipWeightProperty: 'weight', writeProperty: 'community' })
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 15. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
6	14	5160	5248	"[5160 字节 ... 5248 字节]"

流 (Stream)

在 stream 执行模式下，算法返回每个节点的社群信息。这允许我们直接检查结果或在 Cypher 中对其进行后处理，而不会产生任何副作用。

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

在流模式下运行模块度优化算法

CALL gds.modularityOptimization.stream('myGraph', { relationshipWeightProperty: 'weight' })
YIELD nodeId, communityId
RETURN gds.util.asNode(nodeId).name AS name, communityId
ORDER BY name

表 16. 结果
名称 (name)	communityId
"Alice"	3
“Bridget”	1
“Charles”	1
“Doug”	1
"Elton"	3
"Frank"	3

统计 (Stats)

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

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

在统计模式下运行模块度优化算法

CALL gds.modularityOptimization.stats('myGraph', { relationshipWeightProperty: 'weight' })
YIELD nodes, communityCount, ranIterations, didConverge

表 17. 结果
节点	communityCount	ranIterations	didConverge
6	2	2	true

写入 (Write)

write 执行模式扩展了 stats 模式并增加了一个重要的副作用：将每个节点的社群信息作为属性写入 Neo4j 数据库。新属性的名称通过强制配置参数 writeProperty 指定。结果是单行摘要，类似于 stats，但包含一些额外的指标。write 模式可以直接将结果持久化到数据库中。

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

在写入模式下运行模块度优化算法

CALL gds.modularityOptimization.write('myGraph', { relationshipWeightProperty: 'weight', writeProperty: 'community' })
YIELD nodes, communityCount, ranIterations, didConverge

表 18. 结果
节点	communityCount	ranIterations	didConverge
6	2	2	true

当使用 write 模式时，该过程将返回有关算法执行的信息。在此示例中，我们返回已处理节点的数量、图中分配给节点的社群数量、迭代次数以及算法是否收敛的信息。

如果不指定 relationshipWeightProperty，算法运行将默认所有关系权重为 1.0。

变异 (Mutate)

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

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

在变异模式下运行模块度优化算法

CALL gds.modularityOptimization.mutate('myGraph', { relationshipWeightProperty: 'weight', mutateProperty: 'community' })
YIELD nodes, communityCount, ranIterations, didConverge

表 19. 结果
节点	communityCount	ranIterations	didConverge
6	2	2	true

当使用 mutate 模式时，该过程将像 write 模式一样返回有关算法执行的信息。