概述

Leiden（莱顿）算法是一种社区检测算法，旨在最大化图的模块度。它是为了解决广泛使用的Louvain算法可能存在的社区连通性不良甚至是不连通的问题而提出的。Leiden算法比Louvain算法效率更高，并且能保证所有社区都是连通的。该算法也是以其作者所在地命名的。

• V.A. Traag, L. Waltman, N.J. van Eck, From Louvain to Leiden: guaranteeing well-connected communities (2019)
• V.A. Traag, P. Van Dooren, Y. Nesterov, Narrow scope for resolution-limit-free community detection (2011)

基本概念

模块度

模块度（Modularity）的概念在Louvain算法中有所介绍。Leiden算法使用的是扩展的模块度公式，以处理不同密度的社区：

γ > 0是调节社区内部和社区之间连接密度的分辨率参数。当γ > 1时，会形成更多、更小且连接紧密的社区；当γ < 1时，会形成更少、更大但连接相对不那么紧密的社区。

Leiden

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

第一阶段：快速模块度优化

Louvain算法在第一阶段会一直遍历图中的所有节点，直到没有任何节点移动能增加模块度。Leiden算法则采用一种更高效的方法，它遍历完图中所有的节点一次后，只会访问那些邻居节点发生了变化的节点。为了实现这一点，Leiden算法使用一个队列，初始化时按随机顺序将图中的所有节点添加到队列中。

然后，重复下面的步骤直到队列为空：

• 从队列最前端移除一个节点。
• 将该节点分配至能获得最大模块度增益（ΔQ）的不同社区；如果加入任何社区都不能获得大于0的增益，则保留该节点在原社区。
• 如果该节点被移动到另一个社区，将所有不属于该节点新社区且不在队列中的邻居节点添加到队列尾端。

第一阶段以原图或聚合图的一种社区划分P结束。

第二阶段：社区优化

本阶段旨在获得一个基于P优化的社区划分P_refined，以确保所有的社区有良好的连通性。

初始化P_refined时，原图或聚合图中的每个节点都在自己的社区中，接着按如下方式对P中的每个社区C进行优化。

1. 只考虑在C内部连接良好的节点：

其中，

• W(v,C-v)是节点v与C中其余节点间的边权重之和；
• k_v是与节点v相连的所有边的权重之和；
• $\sum _{\mathrm{tot}}^c$是社区C中与所有节点相连的边的权重之和。

以上图中的社区C₁为例，其中

• m = 18.1
• = k_a + k_b + k_c + k_d = 6 + 2.7 + 2.8 + 3 = 14.5

设置γ为1.2，则：

• W(a, C₁) - γ/m ⋅ k_a ⋅ ( - k_a) = 4.5 - 1.2/18.1*6*(14.5 - 6) = 1.12
• W(b, C₁) - γ/m ⋅ k_b ⋅ ( - k_b) = 1 - 1.2/18.1*2.7*(14.5 - 2.7) = -1.11
• W(c, C₁) - γ/m ⋅ k_c ⋅ ( - k_c) = 0.5 - 1.2/18.1*2.8*(14.5 - 2.8) = -1.67
• W(d, C₁) - γ/m ⋅ k_d ⋅ ( - k_d) = 3 - 1.2/18.1*3*(14.5 - 3) = 0.71

在这种情况下，社区C₁中只有节点a和d被认为是连接良好的。

2. 按随机顺序访问每个节点v，如果它在P_refined中仍处于自己独立的社区，则将其随机合并到一个能使模块度增加的社区C'∈P_refined，同时C'必须也是与C连接良好的：

在这个阶段，每个节点并不一定会贪心地与产生最大模块度增益的社区合并。然而，与某个社区合并产生的增益越大，该社区被选择的可能性就越大。选择社区的随机程度由参数θ > 0决定：

在社区合并过程中引入随机性，可以更广泛地探索分区空间。

在完成优化阶段后，P中的社区通常会被拆分为P_refined中的多个社区，但并不总是如此。

第三阶段：社区聚合

聚合图是基于P_refined创建的，但聚合图中的社区划分是基于P的。聚合过程与Louvain算法相同。

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

特殊说明

• 如果节点i存在自环边，在计算k_i时，自环边的权重只计算一次。
• Leiden算法忽略边的方向，按照无向边进行计算。

语法

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

示例

文件回写

algo(leiden).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'
  }
})

属性回写

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

直接返回

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

流式返回

algo(leiden).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))

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

统计返回

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