Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/louvain/
Documentation version: v5.3.2
# Louvain 社区发现
本文介绍 Louvain 算法，并演示如何使用 GQL 实现该算法。
## 算法介绍
Louvain 是一种面向加权图的社区发现算法，目标是通过最大化模块度（modularity）将图划分为若干内部连接紧密、外部连接稀疏的社区。算法从“每个点单独属于一个社区”开始，反复尝试把点移动到相邻社区；只要这样的移动能够提升当前划分质量，就继续执行。当当前层的划分稳定后，再将每个社区压缩成一个超级点，在粗化后的图上继续同样的过程。最终得到的结果是一组分层优化后的社区划分，以及每个原始点所属的最终社区。
### 整体流程
1. 初始化当前层图的统计量：
1. 遍历所有边，计算当前层图的总边权`m`。
2. 统计每个点的加权度，即与该点相连的边权之和。
3. 将每个点初始化为一个独立社区，此时点 ID 同时作为初始社区 ID。
2. 在当前层图上执行局部移动：
1. 对每个点，累计它连向各个相邻社区的边权和。
2. 以当前社区为基线，分别计算该点迁移到每个候选相邻社区后的模块度增益 \(\Delta Q\)。
3. 从所有候选社区中选出收益最大的迁移；只有当 \(\Delta Q > 0\) 时才真正执行迁移。
4. 在后续迭代中，点迁移后同步更新旧社区和新社区的总权重。第一次迭代时每个社区仅含一个点（singleton），社区权重等于点自身权重，因此使用简化公式计算，迭代结束后统一构建社区权重。
5. 当一轮迭代结束后，如果仍有点发生迁移，则继续下一轮；否则认为当前层已经收敛。
3. 在当前层收敛后构造粗化图（将一个社区里的多个点形成一个“超级点”）：
1. 将同一社区中的点压缩为一个新的社区点。
2. 将社区之间的边权累加，形成下一层图中的加权边。
3. 同时保留“原始点 -> 当前社区”的映射，用于最终结果回溯。
4. 对粗化图重复执行“局部移动 -> 粗化”的过程：
1. 如果尚未达到`max_layer`，则在粗化后的图上继续下一层优化。
2. 如果已经达到`max_layer`，或者后续层不再发生有效变化，则停止外层迭代。
5. 输出最终社区划分：
1. 根据多层迭代过程中维护的映射关系，输出每个原始点所属的最终社区。
### 计算公式
本文实现中的模块度计算公式为：
\[ Q(\gamma) = \sum_{c}\left(\frac{e_c}{m} - \gamma \left(\frac{a_c}{2m}\right)^2\right) \]
其中：
- \(m\) 表示当前无向图的总边权。
- \(e_c\) 表示社区 \(c\) 的内部边权总和，每条无向边按一次计数。
- \(a_c\) 表示社区 \(c\) 中所有点加权度之和。
- \(\gamma\) 表示分辨率参数。当 \(\gamma\) 较大时，算法更倾向于得到较小的社区；当 \(\gamma\) 较小时，更倾向于得到较大的社区。
局部移动时使用的模块度增益：
\[ \Delta Q = k_{i \to C_{\text{target}}} - k_{i \to C_{\text{current}}} + \frac{\gamma}{m} \cdot k_i \left( \Sigma_{\text{current}} - \Sigma_{\text{target}} \right) \]
其中：
- \(k_{i \to C_{\text{target}}}\) 表示点 \(i\) 到目标社区的边权和。
- \(k_{i \to C_{\text{current}}}\) 表示点 \(i\) 到当前社区的边权和。
- \(k_i\) 表示点 \(i\) 的加权度。
- \(\Sigma_{\text{current}}\) 和 \(\Sigma_{\text{target}}\) 分别表示当前社区和目标社区的总权重。
- 在公式记号中，\(\gamma\) 表示分辨率参数，\(m\) 表示总边权。
如果某个候选社区对应的 \(\Delta Q\) 为正，则说明把该点移动到该社区可以提升当前层的模块度；实现中会选择正收益最大的那个候选社区作为本轮迁移目标。
更多信息，请参见论文 [Fast unfolding of communities in large networks](https://arxiv.org/abs/0803.0476)。
## 数据模型
为了演示使用 GQL 中实现 Louvain，这里使用以下数据模型：
- 人员实体使用`Person`类型点表示。
- 人员之间的加权关系使用`KNOWS`类型边表示，边属性为`weight`。
`Person`点包含`id`和`cid`两个属性。导入原始图时，使用同一个 CSV 字段`id`同时初始化这两个属性，即`id = cid`。其中，`cid`用于保证统一的内层过程在原始图和粗化工作图上都能访问社区映射属性；算法运行后，最终社区归属通过过程返回值输出，不会回写原始图中的`cid`。
为了支持外层粗化迭代，实现中还会创建一个内部工作图：
- 社区使用`community`类型点表示。
- 社区之间聚合后的边使用`edge`类型边表示，边属性为`weight`。
这里需要注意，内部工作图中的点语义和输入图中的点语义并不相同。输入图里的`Person`点表示业务实体，而内部工作图里的`community`点表示算法内部构造出来的社区图点。因此，内部工作图实际上是在“借用点”来表示社区图中的点。
更具体地说，工作图中`community`点的两个字段承担了两种不同的语义：
- `id`表示当前工作图中的超级点 ID，也就是某一轮粗化之后得到的社区图点。
- `cid`表示初始点到最终社区的映射链路中，当前记录对应的社区 ID；在多层迭代时，它用于把原始点的归属继续向上层社区传递。
因此，`edge (community)~[:edge]~(community)`不是业务层面的实体关系边，而是超级点之间的聚合边；它的两个端点对应的是粗化后社区图中的点，而不是原始业务点。
完整的图类型定义见[准备图数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/louvain/#prepare_data)。
## 过程实现[]()
为了在加权无向图上执行社区发现，我们定义了一个对外入口过程和两个辅助过程：
- `louvain_detect_communities`：对外入口，负责协调外层迭代。
- `louvain_inner_phase`：统一的内层过程，通过布尔参数`is_init`区分第一层和后续层，在原始图和粗化图上执行相同的局部移动逻辑。
- `louvain_load_work_graph`：将上一层输出的粗化图加载到工作图中。
它们的执行关系如下：
````
%%{init: {"flowchart": {"nodeSpacing": 30, "rankSpacing": 40}}}%%
graph LR
Start([开始]) --> Entry{总指挥:
detect_communities}
Entry -->|is_init=true| Inner(统一内层:
inner_phase)
Inner -->|输出| Tables[(临时表)]
Tables -->|下一层| Load(构建粗化图:
load_work_graph)
Load -->|is_init=false| Inner
Inner -->|收敛/结束| End([输出结果])
````
完整的过程定义见[创建过程](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/louvain/#create_procedures)。下面先说明这些过程的核心组成部分。
对外入口过程接受以下输入参数：
- `max_layer`：外层粗化迭代的最大层数。
- `max_iter`：每一层内部局部移动的最大迭代次数。
- `resolution`：模块度目标中的分辨率参数。
`louvain_inner_phase`过程通过布尔参数`is_init`区分行为：
- `is_init = true`（第一层）：所有点在局部移动后都有`community_primary_id`，点到社区的映射是直接的。
- `is_init = false`（后续层）：只有 active_set 中的点（社区代表）有`community_primary_id`；非代表点通过`node2_community_id`回溯。
辅助过程通过以下表变量在层与层之间传递结果：
- `nodes`：记录原始点到当前层社区的映射。
- `edges`：记录下一层粗化图的加权边。
辅助过程中还会用到如下关键变量：
| 变量 | 类型 | 说明
| `total_weight` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 当前无向图的总边权，初始值为`0`。
| `community_weight` | 全局 [MapAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/map_agg/) | 当前每个社区的加权度总和，以`community_primary_id`为键。
| `node_weight` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每个点的加权度，初始值为`0`。
| `node_community_weight` | 点绑定 [MapAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/map_agg/) | 点连向各相邻社区的边权累计值。
| `community_id` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 点当前所属社区的 ID（存储为`element_id`），初始值为`0`。
| `community_primary_id` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 社区的代表（主）节点 ID，作为`community_weight`的键。初始值为`0`。
| `best_move` | 点绑定 [TopKAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/topk_agg/) | 按`delta_q`排序保存最优迁移候选，包含`community_id`和`community_primary_id`。
| `new_active` | 全局 [OrAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/or_agg/) | 当前迭代是否仍有点发生迁移，初始值为`true`。
| `active_set` | [活动集变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/active-set-variable/) | 活跃点集合。在粗化图（`is_init = false`）中仅包含社区代表点，因为只有它们有边。
| `node2_community_id` | 全局 [MapAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/map_agg/) | 将原始节点 ID（`s.id`）映射为其当前`community_primary_id`。仅在`is_init = false`时填充。
| `community_edge_weight` | 点绑定 [MapAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/map_agg/) | 保存收敛后社区之间的聚合边权，以`community_primary_id`为键。
| `modularity_q` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 当前分区的模块度，初始值为`0`。
| `community_cnt` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 当前层得到的社区数量，初始值为`0`。
| `g` | [图变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/graph-variable/) | 外层迭代中使用的临时工作图。
| `nodes` | [表变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/table-variable/) | 保存原始点到当前社区的映射。
| `edges` | [表变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/table-variable/) | 保存下一层粗化图的加权边。
`louvain_inner_phase`过程的执行逻辑如下：
1. 初始化图统计量：计算`total_weight`和每个点的`node_weight`，并构建`active_set`。
2. 初始化社区划分：让每个点先独立成社区（`community_id = element_id(s)`，`community_primary_id = s.id`）。此时不预建`community_weight`，因为初始状态下每个社区仅含一个点（singleton），社区权重等于点自身权重。
3. 在单层内部执行局部移动迭代（分两阶段）：
1. 第一次迭代（singleton 优化，即每个社区仅含一个点）：利用社区权重等于点自身权重的特性，使用简化公式计算 \(\Delta Q\)，其中分辨率项使用`s.@community_primary_id`和`t.@community_primary_id`（在 singleton 情况下均等于节点权重）。迁移时不更新`community_weight`。迭代结束后统一以`community_primary_id`为键构建`community_weight`。
2. 后续迭代（WHILE 循环）：使用标准公式计算 \(\Delta Q\)，以`@community_weight.get(community_primary_id)`获取社区权重。迁移时同步更新`community_weight`（从旧社区减去，向新社区增加）。当无点迁移或达到`max_iter`时停止。
4. 当本层收敛后，聚合社区级边权（Section 4）。由于`community_id`直接存储`element_id(s)`，可直接通过`NODE(s_comm)`寻址，无需`primaryid_2_nodeid`映射。
5. 当`is_init = false`时，构建`node2_community_id`映射（Section 5），从节点 ID 到`community_primary_id`。
6. 使用`@community_weight.get(s.id)`和`s.@community_edge_weight.get(s.id)`计算当前层模块度（Section 6）。
7. 导出两张中间表（Section 7）：
1. `nodes`：当`is_init = true`时直接导出`cid = s.@community_primary_id`；当`is_init = false`时通过`@node2_community_id.get(s.cid)`解析，对孤立点回退到`s.cid`。
2. `edges`：下一层粗化图所需的聚合边。
8. 在粗化图上重复相同流程，直到达到`max_layer`。
9. 返回最终的点到社区映射。
## 操作步骤
在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。
### 1. 准备图数据[]() []()
1.
创建输入图对应的图类型。
````
'''
CREATE GRAPH TYPE IF NOT EXISTS louvain_demo_gt AS {
NODE TYPE Person (
LABEL Person {
id INT PRIMARY KEY,
cid INT
}
),
EDGE TYPE KNOWS (
Person
)~[LABEL KNOWS {
weight DOUBLE, MULTIEDGE KEY ()
} ]~(
Person
)
}
'''
````
2.
下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/louvain/`：
- [louvain_node.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/louvain/louvain_node.csv)：点数据。
- [louvain_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/louvain/louvain_edge.csv)：边数据。
`cid`无需作为单独的 CSV 列提供。导入时会使用`id`列同时初始化`Person.id`和`Person.cid`。
查看 CSV 内容
louvain_node.csv
````
id
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
````
louvain_edge.csv
````
src,dst,weight
0,1,4
1,2,4
2,3,4
3,4,4
4,0,4
0,2,3
1,3,3
2,4,3
3,0,3
4,1,3
5,6,4
6,7,4
7,8,4
8,9,4
9,5,4
5,7,3
6,8,3
7,9,3
8,5,3
9,6,3
10,11,4
11,12,4
12,13,4
13,14,4
14,10,4
10,12,3
11,13,3
12,14,3
13,10,3
14,11,3
2,5,1
4,7,1
7,10,1
9,12,1
1,11,1
3,14,1
````
3.
创建临时图，并将 CSV 数据导入图中。
````
'''
CREATE TEMPORARY GRAPH IF NOT EXISTS #louvain_demo_g
TYPED louvain_demo_gt
'''
````
````
'''
USE #louvain_demo_g
IMPORT INTO GRAPH {
NODE (v@Person {id:id, cid:id}) FROM DATAFILE {
PATH: "file:///examples/algorithms/louvain/louvain_node.csv",
FORMAT: "CSV",
DELIMITER: ','
},
EDGE (id:src)-[e@KNOWS {weight:weight}]->(id:dst) FROM DATAFILE {
PATH: "file:///examples/algorithms/louvain/louvain_edge.csv",
FORMAT: "CSV",
DELIMITER: ','
}
}
'''
````
导入成功后，在控制台执行以下查询核对点数：
````
'''
USE #louvain_demo_g
MATCH (n)
RETURN count(n) AS node_count
'''
````
`node_count`应为`15`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。
4.
创建外层迭代所需的内部工作图类型。
````
'''
CREATE GRAPH TYPE IF NOT EXISTS louvain_work_gt AS {
NODE TYPE community (
LABEL community {
id INT PRIMARY KEY,
cid INT
}
),
EDGE TYPE edge (
community
) ~[LABEL edge {
weight DOUBLE,
MULTIEDGE KEY()
}]~ (
community
)
}
'''
````
### 2. 创建过程[]()[]()
按本节顺序依次创建`louvain_inner_phase`、`louvain_load_work_graph`和`louvain_detect_communities`三个过程。全部创建成功后，再执行下一节的调用。
#### louvain_inner_phase
该统一过程可在任意图层执行一次完整的 Louvain 优化遍历。通过`is_init`参数控制行为，可同时处理原始图和粗化工作图，避免代码重复。关键区别在于导出阶段点与社区映射的处理方式。
````
'''
CREATE OR REPLACE PROCEDURE louvain_inner_phase(
is_init BOOLEAN, // true = 第一层（原始图），false = 粗化图
max_iter INT, // 最大迭代次数
resolution DOUBLE, // 社区划分粒度（分辨率）
nodes TABLE, // [输出] 用于记录点与社区映射的临时表
edges TABLE // [输出] 用于记录下一层粗化图的连边的临时表
) AS {
// ------------------------------------------------------------
// Section 0: 当前 Louvain 单层迭代使用的工作状态和聚合器
// is_init = true → 第一层（原始导入图）；局部移动后每个点都有 @community_primary_id。
// is_init = false → 后续层（粗化图）；只有 active_set 中的点（社区代表）有 @community_primary_id；
// 非代表点通过 node2_community_id 回溯。
// node2_community_id 无条件声明，但仅在 is_init = false 时填充。
// ------------------------------------------------------------
VALUE total_weight SumAgg = 0
VALUE community_weight MapAgg>
NODE VALUE node_weight SumAgg = 0
NODE VALUE node_community_weight MapAgg>
NODE VALUE community_id SumAgg = 0
NODE VALUE community_primary_id SumAgg = 0
NODE VALUE best_move TopKAgg<1, delta_q DOUBLE DESC, community_id INT64 DESC, community_primary_id INT64 DESC>
VALUE new_active OrAgg = true
VALUE iter = 0
VALUE node2_community_id MapAgg>
NODE VALUE community_edge_weight MapAgg>
VALUE modularity_q SumAgg = 0
VALUE community_cnt SumAgg = 0
VALUE active_set ACTIVE_SET
// ------------------------------------------------------------
// Section 1: 图统计量初始化
// - total_weight: 无向图总边权 m
// - node_weight: 每个点的加权度
// Note: MATCH (s)-[e]-(t) 会扫描每条无向边两次，因此最后需要除以 2。
// 在粗化图（is_init = false）中，active_set 仅包含社区代表点，因为只有它们有边。
// ------------------------------------------------------------
MATCH (s)-[e]-(t)
PER PATH {
SET @total_weight += e.weight
SET s.@node_weight += e.weight
}
FINALLY {
SET active_set = s
}
SET @total_weight = @total_weight / 2
LOG_DEBUG("Iter start, total_weight = ", @total_weight)
// ------------------------------------------------------------
// Section 2: 初始划分设置
// - 从 singleton 社区开始：community_id = element_id(s)。
// - 延迟构建 community_weight，直到第一次迁移遍历完成后再统一物化。
// ------------------------------------------------------------
MATCH (s)
PER NODE (s) {
SET s.@community_id = element_id(s)
SET s.@community_primary_id = s.id
}
// ------------------------------------------------------------
// Section 3: 局部移动迭代（Louvain 核心）
// 反复把点迁移到能提升 ΔQ 的邻居社区，直到没有点迁移或达到 max_iter。
// ------------------------------------------------------------
IF max_iter > 0 THEN {
LOG_DEBUG("--------------- iter == ",iter)
SET @new_active = false
SET iter = iter + 1
// 3.1 singleton 初始轮。
// 此时 community_weight(c) = node_weight(c)，因此无需预先构建整张 map。
MATCH (s)-[e]-(t)
WHERE s IN active_set AND s.id <= t.id
PER PATH {
// 在 singleton 阶段，community_id 等于 element_id(s)。
// 每条无向边只在较小端点存一次，需要时从另一端镜像读取。
SET s.@node_community_weight += TUPLE(t.@community_id, e.weight)
}
MATCH (s)-[e]-(t)
WHERE s IN active_set AND ((s.id < t.id AND iter % 2 = 0) OR (s.id > t.id AND iter % 2 = 1))
PER PATH {
VALUE edge_to_target DOUBLE = 0.0
VALUE delta DOUBLE = 0.0
IF s.id <= t.id THEN {
SET edge_to_target = s.@node_community_weight.get(t.@community_id)
} ELSE {
SET edge_to_target = t.@node_community_weight.get(s.@community_id)
}
SET delta = edge_to_target
- s.@node_community_weight.get(s.@community_id)
+ (resolution / @total_weight) * s.@node_weight * (s.@node_weight - t.@node_weight)
SET s.@best_move += RECORD {
delta_q: delta,
community_id: t.@community_id,
community_primary_id: t.@community_primary_id
}
}
MATCH (s)
WHERE s IN active_set
PER NODE (s) {
VALUE move_list = s.@best_move
IF length(move_list) <> 0 THEN {
VALUE move = move_list[0]
IF move.delta_q > 0 THEN {
SET @new_active += true
SET s.@community_id = move.community_id
SET s.@community_primary_id = move.community_primary_id
}
}
SET s.@node_community_weight.clear()
SET s.@best_move.clear()
}
// 第一次迭代结束后，以 community_primary_id 为键统一构建 community_weight。
MATCH (s)
WHERE s IN active_set
PER NODE (s) {
SET @community_weight += TUPLE(s.@community_primary_id, s.@node_weight)
}
} ELSE {
MATCH (s)
WHERE s IN active_set
PER NODE (s) {
SET @community_weight += TUPLE(s.@community_primary_id, s.@node_weight)
}
}
// 3.2 后续迭代复用基于 community_weight 的通用公式。
WHILE iter < max_iter AND @new_active THEN {
LOG_DEBUG("--------------- iter == ",iter)
SET @new_active = false
SET iter = iter + 1
// 3.2.1 为每个点累计其到各邻居社区的总边权。
MATCH (s)-[e]-(t)
WHERE s IN active_set
PER PATH {
SET s.@node_community_weight += TUPLE(t.@community_id, e.weight)
}
// 3.2.2 在分辨率参数 γ 下构建迁移候选及其 ΔQ。
// 奇偶轮交替可以减少单轮中的更新冲突。
MATCH (s)-[e]-(t)
WHERE s IN active_set AND ((s.id < t.id AND iter % 2 = 0) OR (s.id > t.id AND iter % 2 = 1))
PER PATH {
VALUE delta = s.@node_community_weight.get(t.@community_id)
- s.@node_community_weight.get(s.@community_id)
+ (resolution / @total_weight) * s.@node_weight *
(@community_weight.get(s.@community_primary_id)
- @community_weight.get(t.@community_primary_id))
SET s.@best_move += RECORD {
delta_q: delta,
community_id: t.@community_id,
community_primary_id: t.@community_primary_id
}
}
// 3.2.3 应用每个点的最佳正收益迁移，并同步刷新相关状态。
MATCH (s)
WHERE s IN active_set
PER NODE (s) {
VALUE move_list = s.@best_move
IF length(move_list) <> 0 THEN {
VALUE move = move_list[0]
IF move.delta_q > 0 THEN {
SET @new_active += true
SET @community_weight += TUPLE(s.@community_primary_id, -s.@node_weight)
SET s.@community_id = move.community_id
SET s.@community_primary_id = move.community_primary_id
SET @community_weight += TUPLE(s.@community_primary_id, s.@node_weight)
}
}
SET s.@node_community_weight.clear()
SET s.@best_move.clear()
}
}
LOG_DEBUG("louvain_inner done, iter = ", iter)
// ------------------------------------------------------------
// Section 4: 构建社区间粗化边权
// 为下一层聚合社区之间的边权。
// 若输入中存在自环，则按一半计入以保持无向图语义一致。
// community_id 直接存储代表点的 element_id，因此无需 primaryid_2_nodeid 映射即可通过 NODE(...) 寻址。
// ------------------------------------------------------------
MATCH (s)-[e]-(t)
WHERE s.id <= t.id
PER PATH {
VALUE s_comm = s.@community_id
VALUE t_comm = t.@community_id
VALUE s_primary = s.@community_primary_id
VALUE t_primary = t.@community_primary_id
IF s.id = t.id THEN {
SET NODE(s_comm).@community_edge_weight += TUPLE(s_primary, e.weight / 2)
} ELSE {
IF s_comm = t_comm THEN {
SET NODE(s_comm).@community_edge_weight += TUPLE(s_primary, e.weight)
} ELSE {
SET NODE(s_comm).@community_edge_weight += TUPLE(t_primary, e.weight)
}
}
}
// ------------------------------------------------------------
// Section 5: 构建点 → 社区映射以支持回溯
// active_set 在粗化图中仅覆盖社区代表点（非代表点无边）。
// 此映射使导出步骤可通过 node2_community_id.get(s.cid) 将每个粗化点追溯到其新社区。
// ------------------------------------------------------------
MATCH (s)
WHERE s IN active_set
PER NODE (s) {
SET @node2_community_id += TUPLE(s.id, s.@community_primary_id)
}
// ------------------------------------------------------------
// Section 6: 计算当前划分的模块度 Q(γ)
// Q(γ) = Σ_c [ e_c/m - γ·(a_c/(2m))^2 ]
// e_c: 社区 c 的内部边权和（每条无向边只计一次）
// a_c: 社区 c 中所有点的总度权重 (= @community_weight.get(c))
// m: 总边权 (= @total_weight)
// ------------------------------------------------------------
MATCH (s)
WHERE s IN active_set
PER NODE (s) {
VALUE a_c = @community_weight.get(s.id)
VALUE e_c DOUBLE = 0.0
IF s.@community_edge_weight.contains_key(s.id) THEN {
SET e_c = s.@community_edge_weight.get(s.id)
}
IF a_c <> 0 THEN {
SET @modularity_q += e_c / @total_weight - resolution * (a_c / (2.0 * @total_weight)) * (a_c / (2.0 * @total_weight))
SET @community_cnt += 1
}
}
LOG_INFO("louvain modularity Q = ", @modularity_q, ", community_cnt = ", @community_cnt)
SET @community_weight.clear()
// ------------------------------------------------------------
// Section 7: 导出粗化图和原始点回溯表
// - edges: 下一轮外层迭代所需的社区级加权边
// - nodes: init 模式 → cid = s.@community_primary_id（直接，所有点都有）
// inner 模式 → cid = @node2_community_id.get(s.cid)（一步映射，
// 非代表点也可追踪其新社区）
// ------------------------------------------------------------
MATCH (s)
PER NODE (s) {
IF is_init THEN {
EXPORT s.id AS id, s.@community_primary_id AS cid INTO nodes
} ELSE {
// 孤立点的 cid 为 id（=cid）本身
VALUE key = s.cid
VALUE out_cid = key
IF @node2_community_id.contains_key(key) THEN {
SET out_cid = @node2_community_id.get(key)
}
EXPORT s.id AS id, out_cid AS cid INTO nodes
}
IF s.@community_edge_weight.size() <> 0 THEN {
VALUE community_edge_weight_list = s.@community_edge_weight
VALUE i = 0
VALUE list_size = size(community_edge_weight_list)
WHILE (i < list_size) THEN {
VALUE r = community_edge_weight_list[i]
EXPORT s.id AS src, r._0 AS dst, r._1 AS weight INTO edges
SET i = i + 1
}
}
}
}
'''
````
#### louvain_load_work_graph
该过程用于将上一层输出的`nodes`和`edges`中间结果导入内部工作图，构造下一层继续迭代所需的粗化社区图。
````
'''
CREATE OR REPLACE PROCEDURE louvain_load_work_graph(nodes TABLE, edges TABLE) AS {
IMPORT INTO GRAPH {
NODE (v@community {id:id, cid:cid}) FROM nodes,
EDGE (id:src)~[e@edge{weight:weight}]~(id:dst) FROM edges
} OPTIONS {PRIMARY_KEY_AS_NODE_ID:true}
}
'''
````
#### louvain_detect_communities
最后的对外入口过程负责协调外层迭代：首层以`is_init = true`调用`louvain_inner_phase`，后续层以`is_init = false`在工作图上调用`louvain_inner_phase`，并在层间通过`louvain_load_work_graph`重建粗化图，最终返回原始点到最终社区的映射。
````
'''
CREATE OR REPLACE PROCEDURE louvain_detect_communities(
max_layer INT, // 最大允许浓缩多少层
max_iter INT, // 每层内部最多允许搬家多少次
resolution DOUBLE // 模块度分辨率
) RETURNS (node_id INT, community_id INT) AS {
// 1. 声明内部使用的"工作图"和"中间表"，用于层与层之间的数据交接
GRAPH g TYPED louvain_work_gt
TABLE nodes TYPED TABLE {id INT, cid INT}
TABLE edges TYPED TABLE {src INT, dst INT, weight DOUBLE}
VALUE i = 0
// 2. 开始"层层套娃"的大循环
WHILE (i < max_layer) THEN {
IF (i = 0) THEN {
// 第 0 层：在最原始的业务数据图上跑第一次划分（is_init = true）
CALL louvain_inner_phase(true, max_iter, resolution, nodes, edges) FINISH
} ELSE {
// 第 1 层及以后：切换到临时工作图 g（里面装的是上一轮缩略后的超级点）上继续划分（is_init = false）
USE g
CALL louvain_inner_phase(false, max_iter, resolution, nodes, edges) FINISH
}
// 3. 如果还没达到设定的最大层数，就需要做“清场”和“重建”准备进入下一层
IF (i <> max_layer - 1) THEN {
// 清空旧的工作图
SET g.clear()
USE g
// 把刚才算出来的中间表（nodes和edges）转换成一张全新的工作图
CALL louvain_load_work_graph(nodes, edges) FINISH
// 图建好后，清空中间表，留给下一轮装数据用
SET nodes.clear()
SET edges.clear()
}
SET i = i + 1 // 进入下一层
}
// 4. 循环结束，nodes 表里存放的就是最终结果。把它读取出来展示给用户。
FOR r IN nodes
RETURN r.id AS node_id, r.cid AS community_id
}
'''
````
### 3. 调用入口过程
以下调用最多粗化`6`层，每层最多迭代`6`次，分辨率为`1.0`。按需要选择一种结果查看方式。
-
查看最终形成了几个社区
````
'''
USE #louvain_demo_g
CALL louvain_detect_communities(6, 6, 1.0)
RETURN count(DISTINCT community_id) AS community_cnt
'''
````
对于上面的示例图，期望结果为：
````
+---------------+
| community_cnt |
+---------------+
| 3 |
+---------------+
````
-
查看每个原始点最终属于哪个社区
````
'''
USE #louvain_demo_g
CALL louvain_detect_communities(6, 6, 1.0)
RETURN node_id, community_id
'''
````
返回：
````
+---------+--------------+
| node_id | community_id |
+---------+--------------+
| 0 | 0 |
| 1 | 0 |
| 2 | 0 |
| 3 | 0 |
| 4 | 0 |
| 5 | 8 |
| 6 | 8 |
| 7 | 8 |
| 8 | 8 |
| 9 | 8 |
| 10 | 13 |
| 11 | 13 |
| 12 | 13 |
| 13 | 13 |
| 14 | 13 |
+---------+--------------+
````
Note
`community_id`的具体数值（如 8, 13, 0）取决于内部生成的超级点 ID，属正常现象，只要相同社区的点拥有相同的 ID 即可。