Louvain

简介

Louvain 方法是一种用于检测大型网络中社区的算法。它通过最大化每个社区的模块度（Modularity）分数来实现，其中模块度量化了将节点分配给社区的质量。这意味着评估社区内节点连接的密集程度，并将其与随机网络中的连接情况进行对比。

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

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

语法

本节涵盖了执行 Louvain 算法所使用的语法。

运行 Louvain。
CALL Neo4j_Graph_Analytics.graph.louvain(
  'CPU_X64_XS',                    (1)
  {
    ['defaultTablePrefix': '...',] (2)
    'project': {...},              (3)
    'compute': {...},              (4)
    'write':   {...}               (5)
  }
);
1 计算池选择器。
2 表引用的可选前缀。
3 项目配置。
4 计算配置。
5 写入配置。
表 1. 参数
名称 类型 默认 可选 描述

computePoolSelector

字符串

不适用

否

用于运行 Louvain 作业的计算池选择器。

配置

Map

{}

否

用于图项目、算法计算和结果回写的配置。

配置映射由以下三个条目组成。

有关以下项目配置的更多详细信息，请参阅 项目文档。
表 2. 项目配置
名称 类型

nodeTables

节点表列表。

relationshipTables

关系类型到关系表的映射。
表 3. 计算配置
名称 类型 默认 可选 描述

resultProperty

字符串

'community'

是

将回写到 Snowflake 数据库的节点属性。

relationshipWeightProperty

字符串

null

是

用作权重的关系属性名称。如果未指定，算法将作为无权重运行。

seedProperty

字符串

不适用

是

用于设置节点的初始社区。属性值必须为非负数。

maxLevels

整数

10

是

图进行聚类并随后压缩的最大层级数。

maxIterations

整数

10

是

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

tolerance

浮点数

0.0001

是

迭代之间模块度的最小变化值。如果模块度变化小于该容差值，则结果被视为稳定，算法终止。

includeIntermediateCommunities

布尔值

false

是

指示是否写入中间社区。如果设置为 false，则仅保留最终的社区。

consecutiveIds

布尔值

false

是

用于决定组件标识符是否映射到连续 ID 空间（需要额外内存）的标志。不能与 includeIntermediateCommunities 标志同时使用。
有关以下写入配置的更多详细信息，请参阅写入文档。
表 4. 写入配置
名称 类型 默认 可选 描述

nodeProperty

字符串

'community'

是

将回写到 Snowflake 数据库的节点属性。

示例

在本节中，我们将展示在具体图上运行 Louvain 社区检测算法的示例。目的是说明结果的样子，并提供如何在实际场景中使用该算法的指南。我们将在一个由少量节点按特定模式连接的小型社交网络图上进行演示。示例图如下所示

Visualization of the example graph
以下 SQL 语句将在 Snowflake 数据库中创建示例图表：
CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.USERS (NODEID VARCHAR, SEED NUMBER);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.USERS VALUES
  ('Alice', 42),
  ('Bridget', 42),
  ('Charles', 42),
  ('Doug', NULL),
  ('Mark', NULL),
  ('Michael', NULL);

CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.LINKS (SOURCENODEID VARCHAR, TARGETNODEID VARCHAR, WEIGHT FLOAT);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.LINKS VALUES
  ('Alice',   'Bridget', 1),
  ('Alice',   'Charles', 1),
  ('Charles', 'Bridget', 1),
  ('Alice',   'Doug',    5),
  ('Mark',    'Doug',    1),
  ('Mark',    'Michael', 1),
  ('Michael', 'Mark',    1);

该图有两个联系紧密的 Users（用户）集群。在这些集群之间有一条单一的边。连接每个组件中节点的这些关系具有一个 weight（权重）属性，该属性决定了关系的强度。

我们加载 LINK 关系并将方向设置为 UNDIRECTED（无向），因为这对于 Louvain 算法效果最好。

利用 Snowflake 中的节点和关系表，我们现在可以将其作为算法作业的一部分进行投影。在接下来的示例中，我们将演示如何在这些图上使用 Louvain 算法。

运行作业

运行 Louvain 作业包括三个步骤：投影（Project）、计算（Compute）和写入（Write）。

要运行查询，需要为应用程序、您的消费者角色和您的环境设置必要的权限。请参阅 入门 页面以了解更多信息。

我们还假设应用程序名称为默认的 Neo4j_Graph_Analytics。如果您在安装过程中选择了不同的应用程序名称，请将其替换为该名称。

以下代码将运行 Louvain 作业
CALL Neo4j_Graph_Analytics.graph.louvain('CPU_X64_XS', {
    'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
    'project': {
        'nodeTables': [ 'USERS' ],
        'relationshipTables': {
            'LINKS': {
                'sourceTable': 'USERS',
                'targetTable': 'USERS',
                'orientation': 'UNDIRECTED'
            }
        }
    },
    'compute': {
        'resultProperty': 'community_id'
    },
    'write': [{
        'nodeLabel': 'USERS',
        'outputTable': 'USERS_COMMUNITY',
        'nodeProperty': 'community_id'
    }]
});
表 5. 结果
JOB_ID JOB_STATUS JOB_START JOB_END JOB_RESULT

job_2735686e67ae49e7bf90e3f843652da7

SUCCESS

2025-06-27 09:51:10.964

2025-06-27 09:51:15.755

 
 {
  "louvain_1": {
    "communityCount": 2,
    "communityDistribution": {
    "max": 3,
    "mean": 3,
    "min": 3,
    "p1": 3,
    "p10": 3,
    "p25": 3,
    "p5": 3,
    "p50": 3,
    "p75": 3,
    "p90": 3,
    "p95": 3,
    "p99": 3,
    "p999": 3
    },
    "computeMillis": 92,
    "configuration": {
      "concurrency": 2,
      "consecutiveIds": false,
      "includeIntermediateCommunities": false,
      "maxIterations": 10,
      "maxLevels": 10,
      "nodeLabels": ["*"],
      "relationshipTypes": ["*"],
      "resultProperty": "community_id",
      "seedProperty": null,
      "tolerance": 1.000000000000000e-04
    },
    "modularities": [
      0.351428571428571
    ],
    "modularity": 0.3571428571428571,
    "ranLevels": 1
  },
  "project_1": {
    "graphName": "snowgraph",
    "nodeCount": 6,
    "nodeLabels": ...,
    "nodeMillis": 593,
    "relationshipCount": 14,
    "relationshipMillis": 712,
    "relationshipTypes": ...,
    "totalMillis": 1305
  },
  "write_node_property_1": {
    "copyIntoTableMillis": 1308,
    "nodeLabel": "USERS",
    "nodeProperty": "community_id",
    "outputTable": "EXAMPLE_DB.DATA_SCHEMA.USERS_COMMUNITY",
    "rowsWritten": 6,
    "stageUploadMillis": 1410,
    "writeMillis": 3098
  }
}

返回的结果包含有关作业执行和结果分布的信息。此外，每个节点的社区 ID 已写回 Snowflake 数据库。我们可以通过以下方式进行查询

SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.USERS_COMMUNITY;
表 6. 结果
NODEID COMMUNITY_ID

Alice

1

Bridget

1

Charles

1

Doug

3

Mark

3

Michael

3

我们为过程配置参数使用默认值。maxLevels 和 maxIterations 设置为 10，容差值（tolerance）为 0.0001。

加权

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

以下代码将在加权图上运行该算法
CALL Neo4j_Graph_Analytics.graph.louvain('CPU_X64_XS', {
    'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
    'project': {
        'nodeTables': [ 'USERS' ],
        'relationshipTables': {
            'LINKS': {
                'sourceTable': 'USERS',
                'targetTable': 'USERS',
                'orientation': 'UNDIRECTED'
            }
        }
    },
    'compute': {
        'resultProperty': 'community_id',
        'relationshipWeightProperty': 'WEIGHT'
    },
    'write': [{
        'nodeLabel': 'USERS',
        'outputTable': 'USERS_COMMUNITY_WEIGHTED',
        'nodeProperty': 'community_id'
    }]
});
表 7. 结果
JOB_ID JOB_STATUS JOB_START JOB_END JOB_RESULT

job_2735686e67ae49e7bf90e3f843652da7

SUCCESS

2025-06-27 09:51:10.964

2025-06-27 09:51:15.755

 
 {
  "louvain_1": {
    "communityCount": 3,
    "communityDistribution": {
      "max": 2,
      "mean": 2,
      "min": 2,
      "p1": 2,
      "p10": 2,
      "p25": 2,
      "p5": 2,
      "p50": 2,
      "p75": 2,
      "p90": 2,
      "p95": 2,
      "p99": 2,
      "p999": 2
    },
    "computeMillis": 271,
    "configuration": {
      "concurrency": 2,
      "consecutiveIds": false,
      "includeIntermediateCommunities": false,
      "maxIterations": 10,
      "maxLevels": 10,
      "nodeLabels": ["*"],
      "relationshipTypes": ["*"],
      "relationshipWeightProperty": "WEIGHT",
      "resultProperty": "community_id",
      "seedProperty": null,
      "tolerance": 1.000000000000000e-04
    },
    "modularities": [
      0.2933884297520661
    ],
    "modularity": 0.2933884297520661,
    "ranLevels": 1
  },
  "project_1": {
    "graphName": "snowgraph",
    "nodeCount": 6,
    "nodeLabels": ...,
    "nodeMillis": 251,
    "relationshipCount": 14,
    "relationshipMillis": 439,
    "relationshipTypes": ...,
    "totalMillis": 690
  },
  "write_node_property_1": {
    "copyIntoTableMillis": 1082,
    "nodeLabel": "USERS",
    "nodeProperty": "community_id",
    "outputTable": "EXAMPLE_DB.DATA_SCHEMA.USERS_COMMUNITY_WEIGHTED",
    "rowsWritten": 6,
    "stageUploadMillis": 1175,
    "writeMillis": 2549
  }
}
 
SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.USERS_COMMUNITY;
表 8. 结果
NODEID COMMUNITY_ID

Alice

3

Bridget

2

Charles

2

Doug

3

Mark

5

Michael

5

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

种子节点

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

以下代码将在加权图上运行该算法
CALL Neo4j_Graph_Analytics.graph.louvain('CPU_X64_XS', {
    'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
    'project': {
        'nodeTables': [ 'USERS' ],
        'relationshipTables': {
            'LINKS': {
                'sourceTable': 'USERS',
                'targetTable': 'USERS',
                'orientation': 'UNDIRECTED'
            }
        }
    },
    'compute': {
        'resultProperty': 'community_id',
        'seedProperty': 'SEED'
    },
    'write': [{
        'nodeLabel': 'USERS',
        'outputTable': 'USERS_COMMUNITY_SEEDED',
        'nodeProperty': 'community_id'
    }]
});
表 9. 结果
JOB_ID JOB_STATUS JOB_START JOB_END JOB_RESULT

job_605681ee04b84a1d87587ed411d85cee

SUCCESS

2025-07-17 12:35:41.478

2025-07-17 12:35:47.891

 
 {
  "louvain_1": {
    "communityCount": 2,
    "communityDistribution": {
      "max": 3,
      "mean": 3,
      "min": 3,
      "p1": 3,
      "p10": 3,
      "p25": 3,
      "p5": 3,
      "p50": 3,
      "p75": 3,
      "p90": 3,
      "p95": 3,
      "p99": 3,
      "p999": 3
    },
    "computeMillis": 233,
    "configuration": {
      "concurrency": 2,
      "consecutiveIds": false,
      "includeIntermediateCommunities": false,
      "maxIterations": 10,
      "maxLevels": 10,
      "nodeLabels": ["*"],
      "relationshipTypes": ["*"],
      "resultProperty": "community_id",
      "seedProperty": "SEED",
      "tolerance": 1.000000000000000e-04
    },
    "modularities": [
      0.3571428571428571
    ],
    "modularity": 0.3571428571428571,
    "ranLevels": 1
  },
  "project_1": {
    "graphName": "snowgraph",
    "nodeCount": 6,
    "nodeLabels": ...,
    "nodeMillis": 214,
    "relationshipCount": 14,
    "relationshipMillis": 385,
    "relationshipTypes": ...,
    "totalMillis": 599
  },
  "write_node_property_1": {
    "copyIntoTableMillis": 1492,
    "nodeLabel": "USERS",
    "nodeProperty": "community_id",
    "outputTable": "EXAMPLE_DB.DATA_SCHEMA.USERS_COMMUNITY_SEEDED",
    "rowsWritten": 6,
    "stageUploadMillis": 1727,
    "writeMillis": 3592
  }
}
 
SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.USERS_COMMUNITY;
表 10. 结果
NODEID COMMUNITY_ID

Alice

42

Bridget

42

Charles

42

Doug

47

Mark

47

Michael

47

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

使用中间社区

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

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

louvain multilevel graph
以下 SQL 语句将在 Snowflake 表中创建并编码一个多层图
CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.NODES (NODEID VARCHAR);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.NODES VALUES
  ('a'),
  ('b'),
  ('c'),
  ('d'),
  ('e'),
  ('f'),
  ('g'),
  ('h'),
  ('i'),
  ('j'),
  ('k'),
  ('l'),
  ('m'),
  ('n'),
  ('x');

CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.TYPES (SOURCENODEID VARCHAR, TARGETNODEID VARCHAR);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.TYPES VALUES
  ('a', 'b'),
  ('a', 'd'),
  ('a', 'f'),
  ('b', 'd'),
  ('b', 'x'),
  ('b', 'g'),
  ('b', 'e'),
  ('c', 'x'),
  ('c', 'f'),
  ('d', 'k'),
  ('e', 'x'),
  ('e', 'f'),
  ('e', 'h'),
  ('f', 'g'),
  ('g', 'h'),
  ('h', 'i'),
  ('h', 'j'),
  ('i', 'k'),
  ('j', 'k'),
  ('j', 'm'),
  ('j', 'n'),
  ('k', 'm'),
  ('k', 'l'),
  ('l', 'n'),
  ('m', 'n');

现在我们可以看到该算法的迭代流程

以下代码运行该算法并输出中间社区
CALL Neo4j_Graph_Analytics.graph.louvain('CPU_X64_XS', {
    'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
    'project': {
        'nodeTables': [ 'NODES' ],
        'relationshipTables': {
            'TYPES': {
                'sourceTable': 'NODES',
                'targetTable': 'NODES',
                'orientation': 'UNDIRECTED'
            }
        }
    },
    'compute': {
        'resultProperty': 'community_id',
        'includeIntermediateCommunities': true
    },
    'write': [{
        'nodeLabel': 'NODES',
        'outputTable': 'NODES_INTERMEDIATE_COMMUNITY',
        'nodeProperty': 'community_id'
    }]
});
表 11. 结果
JOB_ID JOB_STATUS JOB_START JOB_END JOB_RESULT

job_3369053998a44e73a651b4769f02ca6a

SUCCESS

2025-06-27 11:25:54.526

2025-06-27 11:25:59.379

 
 {
  "louvain_1": {
    "communityCount": 3,
    "communityDistribution": {
      "max": 7,
      "mean": 5,
      "min": 3,
      "p1": 3,
      "p10": 3,
      "p25": 3,
      "p5": 3,
      "p50": 5,
      "p75": 7,
      "p90": 7,
      "p95": 7,
      "p99": 7,
      "p999": 7
    },
    "computeMillis": 164,
    "configuration": {
      "concurrency": 2,
      "consecutiveIds": false,
      "includeIntermediateCommunities": true,
      "maxIterations": 10,
      "maxLevels": 10,
      "nodeLabels": ["*"],
      "relationshipTypes": ["*"],
      "resultProperty": "community_id",
      "seedProperty": null,
      "tolerance": 1.000000000000000e-04
    },
    "modularities": [
      0.37599999999999995,
      0.3816
    ],
    "modularity": 0.3816,
    "ranLevels": 2
  },
  "project_1": {
    "graphName": "snowgraph",
    "nodeCount": 15,
    "nodeLabels": ...,
    "nodeMillis": 472,
    "relationshipCount": 50,
    "relationshipMillis": 1011,
    "relationshipTypes": ...,
    "totalMillis": 1483
  },
  "write_node_property_1": {
    "copyIntoTableMillis": 1505,
    "nodeLabel": "NODES",
    "nodeProperty": "community_id",
    "outputTable": "EXAMPLE_DB.DATA_SCHEMA.NODES_INTERMEDIATE_COMMUNITY",
    "rowsWritten": 15,
    "stageUploadMillis": 1510,
    "writeMillis": 3297
  }
}
 
SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.NODES_INTERMEDIATE_COMMUNITY;
表 12. 结果
NODEID INTERMEDIATE_COMMUNITIES

a

[3, 14]

b

[3, 14]

c

[14, 14]

d

[3, 14]

e

[14, 14]

f

[14, 14]

g

[7, 7]

h

[7, 7]

i

[7, 7]

j

[12, 12]

k

[12, 12]

l

[12, 12]

m

[12, 12]

n

[12, 12]

x

[14, 14]

在此示例图中，在第一次迭代后我们看到 4 个集群，在第二次迭代中这些集群被合并为三个。