概述
Louvain(鲁汶)算法是基于模块度(modularity)计算的社区识别算法,是以模块度最大化为目标的一种对顶点进行聚类的迭代过程。该算法由比利时鲁汶大学的 Vincent D.Blondel 等人于 2008 年提出,因其能以较高的效率计算出令人满意的社区识别结果,是近年来最多被提及和使用的社区识别算法。
算法的相关资料如下:
- 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)
基本概念
权重度
权重度是考虑了边上权重的度的计算。鲁汶算法在计算模块度时用到了节点权重度和社区权重度两个概念。
- 节点权重度是指以该点为端点的所有边的权重和,包括该点的邻边(连接至其它点)以及自环边(连接至该点自身)。
- 社区权重度是指一个社区内所有节点权重度的和。
- 社区内部权重度是指在计算一个社区的权重度时,仅考虑两个端点均在该社区内的边;或者说,从该社区的权重度中去掉该社区和其它社区之间的边的权重,即为该社区的内部权重度。
- 全图权重度是指图中所有节点权重度的和。如果将全图划分为多个社区,由于图中每个点属于并且仅属于一个社区,全图权重度也等于这些社区权重度的和。
社区压缩
鲁汶算法中使用了大量的社区压缩,即在不改变局部权重度以及全图权重度的前提下,通过最大限度地减少点、边数量来提高后续(迭代)计算速度。社区内的点在压缩后将作为一个整体进行模块度优化的计算,且不再拆分,从而实现了层级化(迭代化)的社区划分效果。
社区压缩是将社区内的所有节点用一个聚合点来表示,该社区的内部权重度即为此聚合点的自环边权重,每两个社区之间的边权重和即为相应两个聚合点之间的边权重。
模块度
从几何意义上讲,模块度试图通过计算权重度来对比社区内及社区间节点联系的紧密程度。
假设 2m
为全图的权重度,C
是图中任意一个社区,Σ(tot)
为 C
的权重度,Σ(in)
为 C
的内部权重度,则模块度 Q
可以表示为:
模块度的取值范围为 [-1, 1],对于连通图(或连通子图)而言,模块度范围为 [-1/2, 1]。模块度的意义是反映社区划分的好坏,模块度的数值越高,社区划分越合理。
在进行算法的程序设计时,模块度使用以下公式进行计算:
上式中,2m
是全图权重度;i
和 j
是图中任意两点;当 i
和 j
属于同一社区时,δ
为 1,否则 δ
为 0。
模块度增益
模块度增益是指社区划分改变后,模块度比原先增加了多少。鲁汶算法在调整某个点的社区归属时,通过计算模块度增益来决定是否要对该点进行调整。模块度增益阈值是一个大于 0 的浮点型数据,作用是计算当 ΔQ
未超过该数值时,则判定模块度没有改进。
模块度优化是一个 NP 难(NP-Hard)问题,鲁汶算法采用了启发式算法(Heuristic Algorithm),用多轮复合迭代的方式来优化模块度。每轮大循环分为两个阶段:
- 第一阶段:迭代。在该阶段的最初,将每个点看作一个单独的社区;在每一轮迭代中,为每个点计算是否能找到一个它的邻居所在的社区,如果将该点分配过去能够产生最大且为正的
ΔQ
,即能够最大程度增加模块度,如果能找到,则将该点调整至新社区;用同样的方法对下一个点进行计算和调整;所有点都计算调整完毕后,进入下一轮迭代。第一阶段按此规则循环迭代直至没有点可以被重新分配,或迭代轮数达到限制。 - 第二阶段:社区压缩。对第一阶段划分的各个社区进行压缩,得到一张新图。如果压缩后的新图与本轮大循环开始时图的结构一致,即模块度没有提升,则算法结束,否则将新图作为下一轮大循环的初始图。
特殊处理
孤点、不连通图
如果图中存在孤点,该孤点必然自成一个社区,无论经过多少轮循环迭代,都无法和其它节点合并。原因是孤点没有邻边,即孤点对任何其它社区或节点的 k(i,in)
为 0,移入其它社区时所产生的 ΔQ
为负值。
对于不连通图,各个连通分量之间没有邻边,不同连通分量内的点不能合并,因此各个不连通的区域都是独立的社区,鲁汶算法的社区划分仅在连通分量内部有意义。
自环边
鲁汶算法在计算权重度时对自环边的处理与节点度算法 algo(degree)
不同。在节点度算法中,每条自环边被计算两次,在鲁汶算法中,每条自环边仅计算一次。
如上图所示,在节点度算法中,红色节点的权重度为 1 + 0.5 + 3 + 1.5 * 2 = 7.5
,而在鲁汶算法中,该点的权重度为 1 + 0.5 + 3 + 1.5 = 6
。
有向边
对于有向边,鲁汶算法会忽略边的方向,按照无向边进行计算。
结果和统计值
以下图为例,图中边的权重均为 1,运行鲁汶算法,设置模块度增益阈值为 0.01,第一阶段最大迭代轮数为 5:
算法结果 1:返回点及其社区号,即 _uuid
、community
两列
_uuid | community_id |
---|---|
11 | 2 |
12 | 2 |
13 | 2 |
14 | 2 |
6 | 13 |
7 | 13 |
8 | 13 |
9 | 13 |
10 | 13 |
1 | 11 |
2 | 11 |
3 | 11 |
4 | 11 |
5 | 11 |
算法结果 2:返回各社区及其点数量,即 community_id
、count
两列
community_id | count |
---|---|
2 | 4 |
13 | 5 |
11 | 5 |
算法统计值:社区数量 community_count
以及模块度 modularity
community_count | modularity |
---|---|
3 | 0.434948979591837 |
命令和参数配置
- 命令:
algo(louvain)
params()
参数配置项如下:
名称 | 类型 |
默认值 |
规范 |
描述 |
---|---|---|---|---|
phase1_loop_num | int | 5 | >=1 | 算法第一阶段最大迭代轮数 |
min_modularity_increase | float | 0.01 | 0~1 | 模块度增益阈值 |
edge_schema_property | []@<schema>?.<property> |
/ | 数值类的边属性,需LTE | 边权重所在的一个或多个属性名称,带不带 schema 均可;无该属性的边不参与计算;忽略表示所有边权重为 1 |
limit | int | -1 | >=-1 | 需要返回的结果条数,-1 或忽略表示返回所有结果 |
order | string | / | ASC 或 DESC,大小写均可 | 排序规则,仅在流式返回执行方式且 mode 设置为 2(community:id/count )时有效 |
示例:在图上运行鲁汶算法,设置模块度增益阈值为 0.1,算法第一阶段迭代 3 轮
algo(louvain).params({
phase1_loop_num: 3,
min_modularity_increase: 0.1
}) as com
return com
算法执行
任务回写
1. 文件回写
配置项 | 各列数据 |
---|---|
filename_community_id | _id ,community_id |
filename_ids | community_id ,_id ,_id ,... |
filename_num | community_id ,count |
示例:在图上运行鲁汶算法,设置模块度增益阈值为 0.1,算法第一阶段迭代 5 轮,将算法结果分别回写至名为 communityID、ids 和 num 的文件
algo(louvain).params({
phase1_loop_num: 5,
min_modularity_increase: 0.1
}).write({
file:{
filename_community_id: "communityID",
filename_ids: "ids",
filename_num: "num"
}
})
2. 属性回写
配置项 | 回写内容 | 类型 | 数据类型 |
---|---|---|---|
property | community_id |
点属性 | int64 |
示例:在图上运行鲁汶算法,设置模块度增益阈值为 0.1,算法第一阶段迭代 5 轮,将算法结果回写至名为 communityID 的点属性中
algo(louvain).params({
phase1_loop_num: 5,
min_modularity_increase: 0.1
}).write({
db:{
property: "communityID"
}
})
3. 统计回写
统计项名称 | 数据类型 | 描述 |
---|---|---|
community_count |
int | 社区数量 |
modularity |
double | 模块度 |
示例:在图上运行鲁汶算法,使用默认的模块度增益阈值 0.01 和算法第一阶段 5 轮迭代,将算法统计值回写至任务信息
algo(louvain).params().write()
直接返回
别名序号 |
类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNode | 点及其社区号 | _uuid , community_id |
1 | KV | 社区数量、模块度 | community_count , modularity |
示例:在图上运行鲁汶算法,设置模块度增益阈值为 0.1,算法第一阶段迭代 5 轮,将算法结果和统计值分别定义为别名 results 和 stats 并返回
algo(louvain).params({
phase1_loop_num: 5,
min_modularity_increase: 0.1
}) as results, stats
return results, stats
流式返回
stream()
参数配置项如下:
名称 |
类型 |
默认值 |
规范 |
描述 |
---|---|---|---|---|
mode | int | 1 | 1 或 2 | 1 代表返回各点的社区号,2 代表返回各社区的点数量 |
别名序号 |
类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode 或 []perCommunity | 点及其社区号或社区及其点数量 | _uuid , community_id 或 community_id , count |
示例:在图上运行鲁汶算法,设置模块度增益阈值为 0.1,算法第一阶段迭代 5 轮,将算法结果(社区及其点数量)定义为别名 results,返回结果并按照社区点数量降序排列
algo(louvain).params({
phase1_loop_num: 5,
min_modularity_increase: 0.1,
order: "desc"
}).stream({
mode: 2
}) as results
return results
示例:在图上运行鲁汶算法,设置模块度增益阈值为 0.1,算法第一阶段迭代 5 轮,将算法结果(点及其社区号)定义为别名 results,返回结果并按照点的 UUID 升序排列
algo(louvain).params({
phase1_loop_num: 5,
min_modularity_increase: 0.1
}).stream() as results
return results order by results._uuid
实时统计
别名序号 |
类型 |
描述 |
列名 |
---|---|---|---|
0 | KV | 社区数量、模块度 | community_count , modularity |
示例:在图上运行鲁汶算法,设置模块度增益阈值为 0.1,算法第一阶段迭代 5 轮,将算法统计值定义为别名 stats 并返回
algo(louvain).params({
phase1_loop_num: 5,
min_modularity_increase: 0.1
}).stats() as stats
return stats
算法效率
通过优化的贪心算法(Greedy Optimization),鲁汶社区识别算法的时间复杂度一般认为可以达到较之前的社区划分算法而言更低的 O(N*LogN)
,其中 N
为图中顶点的数量,并且算法结果也更为直观。也就是说,在有 1 万个节点的图中,理论上鲁汶算法的复杂度为 O(40000)
;而在 1 亿个顶点的连通图中,算法复杂度为 O(800000000)
。实际上,从上面详细的算法步骤拆解中可以看出,鲁汶算法的复杂度既与点数量相关,也与边数量相关,粗略地看,算法复杂度应该是 O(N * E/N) = O(E)
,其中 E
为图中边的数量——因为鲁汶社区识别中最主要的算法逻辑是对每一个顶点所关联的边权重进行计算。
下图是鲁汶算法原作者在其论文中提供的与其它社区识别算法比较的效果示意图,可以看出,鲁汶算法在模块度与效率两个维度都实现了大幅(指数级)提升:
即便都是鲁汶算法的实现,由于系统架构、数据结构、编程语言等的差异,最终实现的效果与算法效率会存在巨大差异。例如,用 Python 实现的串行的鲁汶社区识别,即便是在万级的小图中,也会耗时数小时;另外,由于算法频繁地计算点的度以及边权重,数据结构的差异也会导致巨大的性能差异。原生鲁汶算法采用 C++ 实现,不过是一种串行实现方式,因此,通过尽可能的并行计算,也可以降低时耗,进而提升算法效率。
在千万级点边的中等大小图数据集上,Ultipa 鲁汶算法可以完全以实时的方式完成;对于亿级以上的大图,可以在秒-分钟级完成。另外,如果进行磁盘文件回写或数据库属性回写等操作,也会影响整个算法的时耗。下表中展示的是在 500 万节点、1 亿条边的图集上运行鲁汶算法的模块度以及执行时耗,请注意,因为要回写数据库以及生成磁盘文件,计算过程 ~1 分钟,而回写与文件生成耗时额外的 ~1 分钟。
结果一致性
受节点顺序、并行计算以及启发式算法在局部数据的执行逻辑等因素影响,鲁汶算法的社区划分结果可能在每次执行时都会有所不同,但整体趋势不会有大的变化(如上表所示)。