社区发现算法——Louvain 算法

Louvain 算法

原始论文为：《Fast unfolding of communities in large networks》。

所以又被称为Fast unfolding算法。

Louvain算法是一种基于模块度的社区发现算法。其基本思想是网络中节点尝试遍历所有邻居的社区标签，并选择最大化模块度增量的社区标签。在最大化模块度之后，每个社区看成一个新的节点，重复直到模块度不再增大。

首先复习下模块度：

在这里插入图片描述
这里引入了权重方便扩展到有权图，但其实对于无权图，可以看做所有边权重为1，这时候就等于用节点的度计算，用度理解一样。

算法详述：

模块度优化阶段：每个节点将自己作为自己社区标签。每个节点遍历自己的所有邻居节点，尝试将自己的社区标签更新成邻居节点的社区标签，选择模块度增量最大(贪婪思想)的社区标签，直到所有节点都不能通过改变社区标签来增加模块度。

也就是说，首先将每个节点指定到唯一的一个社区，然后按顺序将节点在这些社区间进行移动。怎么移动呢？假设有一节点 i ，它有三个邻居节点 j1, j2, j3，我们分别尝试将节点 i 移动到 j1, j2, j3 所在的社区，并计算相应的 modularity 变化值ΔQ，哪个变化值最大就将节点 i 移动到相应的社区中去（当然，这里我们要求最大的 modularity 变化值要为正，如果变化值均为负，则节点 i 保持不动）。按照这个方法反复迭代，直到网络中任何节点的移动都不能再改善总的 modularity 值为止。

移动到一个社区C中所获得的模块化Q增益可以很容易地计算出来：

= $\frac{1}{2m}(k_{i,in}-{Σ_{tot}ki\over m})$

其中 $Σ_{in}$ 是在社区C内的链路的权重总和(权重为1时就等于度数)，如果是初始情况，即一个节点作为一个社区时，它就为这个节点自己到自己的连接，这时候仍然需要起点加weight，终点加weight（即使这个时候起点和终点为同一节点，对于无环图权为0）

$Σ_{tot}$ 是关联到C中的节点的链路上的权重的总和

ki是关联到节点i的链路的权重的总和

ki,in是从节点i连接到C中的节点的链路的总和

m是网络中的所有链路的权重的总和
网络凝聚阶段：每个社区合并为一个新的超级节点，超级节点的边权重为原始社区内所有节点的边权重之和，形成一个新的网络。

将第一个阶段得到的社区视为新的“节点”（一个社区对应一个），重新构造子图，两个新“节点”之间边的权值为相应两个社区之间各边的权值的总和。如这个图所示，如果第一个阶段得到的社区有以下三个，那么第二个阶段的任务就是将这三个社分别看一个新的节点，然后将任意两个新节点之间的所有连线的权重相加得到的和，作为这两个新节点之间的连线的权重。

在这里插入图片描述

上述两个阶段迭代进行，直到模块度不再增大。
下图很好的描述了这两个阶段。第一次迭代，经过模块度优化阶段，总的 modularity 值不再改变，算法将16个节点划分成4个社区；在网络凝聚阶段，4个社区被凝聚成4个超级节点，并重新更新了边权重。之后就进入第二次迭代中。

在这里插入图片描述

算法通过引入分步迭代的思想(类比EM算法)，避免陷入贪婪思想导致的局部最优。

算法流程：

1、初始时将每个顶点当作一个社区，社区个数与顶点个数相同。
2、依次将每个顶点与之相邻顶点合并在一起，计算它们最大的模块度增益是否大于0，如果大于0，就将该结点放入模块度增量最大的相邻结点所在社区。
3、迭代第二步，直至算法稳定，即所有顶点所属社区不再变化。
4、将各个社区所有节点压缩成为一个结点，社区内点的权重转化为新结点环的权重，社区间权重转化为新结点边的权重。
5、重复步骤1-3，直至算法稳定。

可以看到Louvain 算法与FN算法非常相似，我觉得最大的不同时Louvain 算法在凝聚阶段是将整个社区看做一个新的超节点来看，而FN算法是以社区的观点来凝聚。

算法优缺点

优点

1、时间复杂度低，适合大规模的网络。
2、社区划分结果稳定，有具体指标能够评估社区划分好坏。
3、消除了模块化分辨率的限制。由于模块度是全局指标，最大化的时候很难发现小型的社区，很容易将小型社区合并。而算法第一次迭代是以单个节点作为社区的粒度，规避了这种问题。
4、天然自带层次化的社区划分结果，每一次迭代的社区划分结果都可以保留下来，作为社区划分的中间结果，可供选择。

缺点

1、社区过大，不能及时收敛。如果我们将模块度类比为损失函数的话，Fast Unfolding在模块度优化阶段采用的贪婪思想很容易将整个社区划分“过拟合”。因为Fast Unfolding是针对点遍历，很容易将一些外围的点加入到原本紧凑的社区中，导致一些错误的合并。这种划分有时候在局部视角是优的，但是全局视角下会变成劣的。

Python代码如下：代码与数据下载

class Louvain:def __init__(self, G):self._G = Gself._m = 0  # 边数量 图会凝聚动态变化self._cid_vertices = {}  # 需维护的关于社区的信息(社区编号,其中包含的结点编号的集合)self._vid_vertex = {}  # 需维护的关于结点的信息(结点编号，相应的Vertex实例)for vid in self._G.keys():# 刚开始每个点作为一个社区self._cid_vertices[vid] = {vid}# 刚开始社区编号就是节点编号self._vid_vertex[vid] = Vertex(vid, vid, {vid})# 计算边数  每两个点维护一条边self._m += sum([1 for neighbor in self._G[vid].keys() if neighbor > vid])# 模块度优化阶段def first_stage(self):mod_inc = False  # 用于判断算法是否可终止visit_sequence = self._G.keys()# 随机访问random.shuffle(list(visit_sequence))while True:can_stop = True  # 第一阶段是否可终止# 遍历所有节点for v_vid in visit_sequence:# 获得节点的社区编号v_cid = self._vid_vertex[v_vid]._cid# k_v节点的权重(度数)  内部与外部边权重之和k_v = sum(self._G[v_vid].values()) + self._vid_vertex[v_vid]._kin# 存储模块度增益大于0的社区编号cid_Q = {}# 遍历节点的邻居for w_vid in self._G[v_vid].keys():# 获得该邻居的社区编号w_cid = self._vid_vertex[w_vid]._cidif w_cid in cid_Q:continueelse:# tot是关联到社区C中的节点的链路上的权重的总和tot = sum([sum(self._G[k].values()) + self._vid_vertex[k]._kin for k in self._cid_vertices[w_cid]])if w_cid == v_cid:tot -= k_v# k_v_in是从节点i连接到C中的节点的链路的总和k_v_in = sum([v for k, v in self._G[v_vid].items() if k in self._cid_vertices[w_cid]])delta_Q = k_v_in - k_v * tot / self._m  # 由于只需要知道delta_Q的正负，所以少乘了1/(2*self._m)cid_Q[w_cid] = delta_Q# 取得最大增益的编号cid, max_delta_Q = sorted(cid_Q.items(), key=lambda item: item[1], reverse=True)[0]if max_delta_Q > 0.0 and cid != v_cid:# 让该节点的社区编号变为取得最大增益邻居节点的编号self._vid_vertex[v_vid]._cid = cid# 在该社区编号下添加该节点self._cid_vertices[cid].add(v_vid)# 以前的社区中去除该节点self._cid_vertices[v_cid].remove(v_vid)# 模块度还能增加 继续迭代can_stop = Falsemod_inc = Trueif can_stop:breakreturn mod_inc# 网络凝聚阶段def second_stage(self):cid_vertices = {}vid_vertex = {}# 遍历社区和社区内的节点for cid, vertices in self._cid_vertices.items():if len(vertices) == 0:continuenew_vertex = Vertex(cid, cid, set())# 将该社区内的所有点看做一个点for vid in vertices:new_vertex._nodes.update(self._vid_vertex[vid]._nodes)new_vertex._kin += self._vid_vertex[vid]._kin# k,v为邻居和它们之间边的权重 计算kin社区内部总权重 这里遍历vid的每一个在社区内的邻居   因为边被两点共享后面还会计算  所以权重/2for k, v in self._G[vid].items():if k in vertices:new_vertex._kin += v / 2.0# 新的社区与节点编号cid_vertices[cid] = {cid}vid_vertex[cid] = new_vertexG = collections.defaultdict(dict)# 遍历现在不为空的社区编号 求社区之间边的权重for cid1, vertices1 in self._cid_vertices.items():if len(vertices1) == 0:continuefor cid2, vertices2 in self._cid_vertices.items():# 找到cid后另一个不为空的社区if cid2 <= cid1 or len(vertices2) == 0:continueedge_weight = 0.0# 遍历 cid1社区中的点for vid in vertices1:# 遍历该点在社区2的邻居已经之间边的权重(即两个社区之间边的总权重  将多条边看做一条边)for k, v in self._G[vid].items():if k in vertices2:edge_weight += vif edge_weight != 0:G[cid1][cid2] = edge_weightG[cid2][cid1] = edge_weight# 更新社区和点 每个社区看做一个点self._cid_vertices = cid_verticesself._vid_vertex = vid_vertexself._G = Gdef get_communities(self):communities = []for vertices in self._cid_vertices.values():if len(vertices) != 0:c = set()for vid in vertices:c.update(self._vid_vertex[vid]._nodes)communities.append(list(c))return communitiesdef execute(self):iter_time = 1while True:iter_time += 1# 反复迭代，直到网络中任何节点的移动都不能再改善总的 modularity 值为止mod_inc = self.first_stage()if mod_inc:self.second_stage()else:breakreturn self.get_communities()

参考结果如下：

社区 1 [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 16, 17, 19, 21]
社区 2 [32, 33, 8, 14, 15, 18, 20, 22, 26, 29, 30]
社区 3 [23, 24, 25, 27, 28, 31]
0.388560157790927
算法执行时间0.002000093460083008