Louvain

简介

Louvain 方法是一种在大规模网络中检测社区的算法。它最大化每个社区的模块度分数，模块度量化了节点到社区分配的质量。这意味着评估社区内节点的连接密度比在随机网络中高出多少。

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 作业的计算池选择器。
configuration	映射	`{}`	否	图项目、算法计算和结果回写的配置。

配置映射包含以下三个条目。

有关以下项目配置的更多详细信息，请参阅项目文档。

表 2. 项目配置
名称	类型
nodeTables	节点表列表。
relationshipTables	关系类型到关系表的映射。

表 3. 计算配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`'community'`	是	将回写到 Snowflake 数据库的节点属性。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性名称。如果未指定，算法将运行无权重计算。
seedProperty	字符串	`不适用`	是	用于设置节点的初始社区。属性值必须是非负数。
maxLevels	整数	`10`	是	图被聚类和浓缩的最大层数。
maxIterations	整数	`10`	是	模块度优化在每个级别上运行的最大迭代次数。
tolerance	浮点数	`0.0001`	是	迭代之间模块度的最小变化量。如果模块度变化小于容差值，则结果被视为稳定，算法将返回。
includeIntermediateCommunities	布尔值	`否`	是	指示是否写入中间社区。如果设置为 false，则仅保留最终社区。
consecutiveIds	布尔值	`否`	是	标志，用于决定组件标识符是否映射到连续的 ID 空间（需要额外内存）。不能与 `includeIntermediateCommunities` 标志结合使用。
minCommunitySize	整数	`0`	是	仅返回社区规模大于或等于给定值的节点。

有关以下写入配置的更多详细信息，请参阅写入文档。

表 4. 写入配置
名称	类型	默认值	可选	描述
nodeProperty	字符串	`'community'`	是	将回写到 Snowflake 数据库的节点属性。

示例

本节将展示在具体图上运行 Louvain 社区检测算法的示例。目的是说明结果的外观，并提供在实际设置中如何使用该算法的指南。我们将在一个由少数节点以特定模式连接的小型社交网络图上进行此操作。示例图如下所示

以下 SQL 语句将在 Snowflake 数据库中创建示例图表

CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.USERS (NODEID STRING);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.USERS VALUES
  ('Alice'), -- (nAlice:User {name: 'Alice', seed: 42}),
  ('Bridget'), -- (nBridget:User {name: 'Bridget', seed: 42}),
  ('Charles'), -- (nCharles:User {name: 'Charles', seed: 42}),
  ('Doug'), -- (nDoug:User {name: 'Doug'}),
  ('Mark'), -- (nMark:User {name: 'Mark'}),
  ('Michael'); -- (nMichael:User {name: 'Michael'}),

CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.LINKS (SOURCENODEID STRING, TARGETNODEID STRING, WEIGHT FLOAT);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.LINKS VALUES
  ('Alice',   'Bridget', 1), -- (nAlice)-[:LINK {weight: 1}]->(nBridget),
  ('Alice',   'Charles', 1), -- (nAlice)-[:LINK {weight: 1}]->(nCharles),
  ('Charles', 'Bridget', 1), -- (nCharles)-[:LINK {weight: 1}]->(nBridget),

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

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

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

我们加载方向设置为 UNDIRECTED 的 LINK 关系，因为这与 Louvain 算法配合最佳。

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

运行作业

运行 Louvain 作业涉及三个步骤：项目、计算和写入。

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

我们还假设应用程序名称是默认的 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': {
        'mutateProperty': 'community_id'
    },
    'write': [{
        'nodeLabel': 'USERS',
        'outputTable': 'USERS_COMMUNITY',
        'nodeProperty': 'community_id'
    }]
});

返回的结果包含作业执行和结果分布的信息。此外，每个节点的社区 ID 已回写到 Snowflake 数据库。我们可以这样查询它

SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.USERS_COMMUNITY;

表 5. 结果
节点 ID	社区 ID
Alice	1
Bridget	1
Charles	1
Doug	3
Mark	3
Michael	3

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