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增益可以很容易地计算出来：
= 1 2 m ( k i , i n − Σ t o t k i m ) \frac{1}{2m}(k_{i,in}-{Σ_{tot}ki\over m}) 2m1(ki,in−mΣtotki)
其中 Σ i n Σ_{in} Σin是在社区C内的链路的权重总和(权重为1时就等于度数)，如果是初始情况，即一个节点作为一个社区时，它就为这个节点自己到自己的连接，这时候仍然需要起点加weight，终点加weight（即使这个时候起点和终点为同一节点，对于无环图权为0）
Σ t o t Σ_{tot} Σ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 = G
self._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]._cid
if w_cid in cid_Q:
continue
else:
# 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 = False
mod_inc = True
if can_stop:
break
return mod_inc
# 网络凝聚阶段
def second_stage(self):
cid_vertices = {}
vid_vertex = {}
# 遍历社区和社区内的节点
for cid, vertices in self._cid_vertices.items():
if len(vertices) == 0:
continue
new_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的每一个在社区内的邻居 因为边被两点共享后面还会计算 所以权重/2
for 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_vertex
G = collections.defaultdict(dict)
# 遍历现在不为空的社区编号 求社区之间边的权重
for cid1, vertices1 in self._cid_vertices.items():
if len(vertices1) == 0:
continue
for cid2, vertices2 in self._cid_vertices.items():
# 找到cid后另一个不为空的社区
if cid2 <= cid1 or len(vertices2) == 0:
continue
edge_weight = 0.0
# 遍历 cid1社区中的点
for vid in vertices1:
# 遍历该点在社区2的邻居已经之间边的权重(即两个社区之间边的总权重 将多条边看做一条边)
for k, v in self._G[vid].items():
if k in vertices2:
edge_weight += v
if edge_weight != 0:
G[cid1][cid2] = edge_weight
G[cid2][cid1] = edge_weight
# 更新社区和点 每个社区看做一个点
self._cid_vertices = cid_vertices
self._vid_vertex = vid_vertex
self._G = G
def 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 communities
def execute(self):
iter_time = 1
while True:
iter_time += 1
# 反复迭代，直到网络中任何节点的移动都不能再改善总的 modularity 值为止
mod_inc = self.first_stage()
if mod_inc:
self.second_stage()
else:
break
return self.get_communities()
参考结果如下：文章来源：https://www.toymoban.com/news/detail-806791.html
社区 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文章来源地址https://www.toymoban.com/news/detail-806791.html
到了这里，关于社区发现算法——Louvain 算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
