✓ 文件回写 ✓ 属性回写 ✓ 直接返回 ✓ 流式返回 ✓ 统计值

概述

Louvain（鲁汶）是一个广受认可和应用的社区识别算法，它是以其作者的位置命名的——来自比利时鲁汶大学的 Vincent D. Blondel 等人。该算法是以最大化图的模块度（Modularity）为首要目标进行计算的，并且由于其较高的效率和优质的结果而受到欢迎。

• V.D. Blondel, J. Guillaume, R. Lambiotte, E. Lefebvre, Fast unfolding of communities in large networks (2008)
• H. Lu, Parallel Heuristics for Scalable Community Detection (2014)

基本概念

模块度

在许多网络中，节点自然地会形成群组或社区（Community），特点是社区内的节点连接密集，而社区之间的连接则较稀疏。

考虑一个与 G 对应的等价网络 G'。在 G' 中，社区划分和边的总数与 G 中相同，但边是随机放置的。如果 G 表现出良好的社区结构，G 中社区内部的边数与总边数之比应该高于 G' 中预期的比例。实际比例与预期值之间的差异越大，说明在 G 中的社区结构越显著。这就是模块度（Modularity）的原始概念。模块度是评估社区划分质量的最广泛使用的方法之一，Louvain 算法就是旨在找到使得模块度最大的社区划分结果。

模块度的取值范围为 -1 到 1。接近 1 的值表示更明显的社区结构，而负值则意味着划分不具有意义。对于连通图，模块度的取值范围为 -0.5 到 1。

考虑图中边的权重，模块度（Q）的定义如下：

其中，

• m 是图中所有边的权重之和；
• A_ij 是节点 i 和节点 j 之间边的权重和，且 2m = ∑_ijA_ij；
• k_i 是与节点 i 相连的所有边的权重之和；
• C_i 表示节点 i 所属的社区，当 C_i = C_j 时，δ(C_i, C_j) 为 1，否则为 0。

请留意， 是节点 i 和 j 之间随机放置边时的预期边权重之和，A_ij 和 都除以 2m 是因为一个社区内每对不同的节点会被考虑两次，例如 A_ab = A_ba， = 。

我们也可以将上式写成如下形式：

其中，

• $\sum _{\mathrm{in}}^c$ 是社区 C 内部边的权重之和，即社区内部权重度（Intra-community Weight）；
• $\sum _{\mathrm{tot}}^c$ 是与社区 C 中节点相连的边的权重之和，即社区总权重度（Total-community Weight）；
• m 的含义与上面相同，且 2m = ∑_c$\sum _{\mathrm{tot}}^c$。

上图中的节点被划分至 3 个社区，以社区 C₁ 为例：

• = A_aa + A_ab + A_ac + A_ad + A_ba + A_ca + A_da = 1.5 + 1 + 0.5 + 3 + 1 + 0.5 + 3 = 10.5
• ()² = k_ak_a + k_ak_b + k_ak_c + k_ak_d + k_bk_a + k_bk_b + k_bk_c + k_bk_d + k_ck_a + k_ck_b + k_ck_c + k_ck_d + k_dk_a + k_dk_b + k_dk_c + k_dk_d + = (k_a + k_b + k_c + k_d)² = (6 + 2.7 + 2.8 + 3)² = 14.5²

Louvain

Louvain 算法开始时，图中的每个节点都在自己的社区中。然后算法进行多次迭代，每轮迭代由两个阶段组成。

第一阶段：模块度优化

对于每个节点 i，考虑其邻居节点 j，计算将节点 i 从当前社区重新分配到节点 j 所在的社区而产生的模块度增益（ΔQ）。当 ΔQ 大于预设的正阈值时，将节点 i 放入使 ΔQ 最大的社区中。如果无法达到预设的增益，节点 i 则留在原来的社区中。

以上图为例，当前在同一社区的节点用同一颜色表示。如果现在考虑节点 d，将其重新分配至社区 {a,b}、{c} 或 {e,f} 分别所产生的模块度增益如下：

• ΔQ_d→{a,b} = Q_{a,b,d} - (Q_{a,b} + Q_{d}) = 52/900
• ΔQ_d→{c} = Q_{c,d} - (Q_{c} + Q_{d}) = 72/900
• ΔQ_d→{e,f} = Q_{d,e,f} - (Q_{e,f} + Q_{d}) = 36/900

如果 ΔQ_d→{c} 大于预设的模块度增益阈值，则将节点 d 移至社区 {c}，否则 d 仍留在原来的社区。

按顺序将这个过程应用于所有节点，并重复执行，直到没有任何节点的移动可以改善模块度，或者达到最大循环次数，第一阶段完成。

第二阶段：社区聚合

在第二阶段，每个社区被压缩成一个节点，每个聚合节点带有一条自环边，其权重等于社区内部权重。新节点之间边的权重是两个对应社区中节点之间边的权重之和。

社区聚合减少了图中的节点和边的数量，同时保持局部及全图的权重度不变。聚合后，社区内的节点被视为一个整体，但它们不再是孤立地进行模块度优化，从而实现了分层（迭代）的社区划分效果。

完成第二阶段后，对聚合图进行另一次迭代。迭代会一直进行，直至没有任何变化，达到最大的模块度。

特殊说明

• 如果节点 i 存在自环边，在计算 k_i 时，自环边的权重只计算一次。
• Louvain 算法忽略边的方向，按照无向边进行计算。
• Louvain 算法的输出结果可能会因为节点的考虑顺序不同而有所差异，但这不会对获得的模块度产生很大的影响。

语法

• 命令：algo(louvain)
• 参数：

示例

示例图如下：

文件回写

algo(louvain).params({ 
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1,
  edge_schema_property: 'weight'
}).write({
  file:{
    filename_community_id: 'communityID',
    filename_ids: 'ids',
    filename_num: 'num'
  }
})

统计值：community_count = 4, modularity = 0.464280
结果：文件 communityID、ids、num

M,2
N,2
K,2
L,2
J,8
I,8
G,13
H,8
F,8
C,12
E,12
D,12
A,12
B,13

8,J,I,H,F,
12,C,E,D,A,
2,M,N,K,L,
13,G,B,

8,4
12,4
2,4
13,2

属性回写

algo(louvain).params({ 
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1,
  edge_schema_property: 'weight'
}).write({
  db:{
    property: 'communityID'
  }
})

统计值：community_count = 4, modularity = 0.464280
结果：每个节点的社区号回写至名为 communityID 的点属性下

直接返回

algo(louvain).params({ 
  phase1_loop_num: 6, 
  min_modularity_increase: 0.5,
  edge_schema_property: 'weight'
}) as results, stats
return results, stats

结果：results 和 stats

流式返回

algo(louvain).params({ 
  phase1_loop_num: 6, 
  min_modularity_increase: 0.5,
  edge_schema_property: 'weight'
}).stream() as results
group by results.community_id
return table(results.community_id, max(results._uuid))

结果：table(results.community_id, max(results._uuid))

algo(louvain).params({ 
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1,
  order: "desc"
}).stream({
  mode: 2
}) as results
return results

结果：results

统计返回

algo(louvain).params({ 
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1
}).stats() as stats
return stats

结果：stats

算法效率

Louvain 算法通过优化的贪心算法实现了比之前的社区检测算法更低的时间复杂度，通常认为是 O(N*logN)，其中 N 是图中节点的数量，其结果也更直观。例如，在一个包含 10,000 个节点的图中，Louvain 算法的复杂度大约是 O(40000)；在一个包含 1 亿节点的连通图中，算法的复杂度大约是 O(800000000)。

然而，仔细观察算法的过程，我们会发现，Louvain 算法的复杂度不仅取决于节点的数量，还取决于边的数量。粗略地说，可以近似为 O(N * E/N) = O(E)，其中 E 是图中边的数量。这是因为 Louvain 算法的主要逻辑是计算连接到每个节点的边的权重。

下表显示了 Clauset, Newman and Moore、Pons and Latapy、Wakita and Tsurumi 以及 Louvain 这几个社区检测算法在不同大小的图上的性能差异。对于每个算法/网络，它给出了获得的模块度和计算时间，空记录表示计算时间超过了 24 小时。可以清楚地看到，Louvain 算法在模块度和效率方面取得了显著的（指数级）提升。

系统架构和编程语言的选择对 Louvain 算法的效率和最终结果都会产生影响。例如，用 Python 串行实现的 Louvain 算法可能需要数小时来处理约 1 万个节点的小图。此外，所使用的数据结构也会影响性能，因为该算法会频繁计算节点度和边的权重。

原生 Louvain 算法采用 C++，但是它是串行实现的。通过尽可能多地使用并行计算，可以减少时间消耗，从而提高算法的效率。

对于中等规模包含数千万个节点和边的图集，Ultipa 的 Louvain 算法可以实时完成。对于包含超过 1 亿个节点和边的大图，可以在几秒钟到几分钟内完成。此外，Louvain 算法的效率还受到其他因素的影响，例如数据是否写回到数据库属性或磁盘文件。这些操作会影响算法的整体计算时间。

这是 Louvain 算法在包含 500 万个节点和 1 亿条边的图上运行的模块性和执行时间记录。计算过程大约需要 1 分钟，而其他额外的操作，比如写回到数据库或生成磁盘文件，会增加约 1 分钟的执行时间。