图算法（十三）：Louvain算法【适用场景：用于社团发掘、层次化聚类等场景】【基于模块度的社区发现算法，其优化目标是最大化整个社区网络的模块度】

秒速五厘米 2023-09-28 08:29 94阅读 0赞

## 一、概述 ##

Louvain算法是基于模块度的社区发现算法，该算法在效率和效果上都表现较好，并且能够发现层次性的社区结构，其优化目标是最大化整个社区网络的模块度。

**适用场景**：Louvain算法适用于社团发掘、层次化聚类等场景。

## 二、 ##

Louvain算法：一种基于模块度的图算法模型，与普通的基于模块度和模块度增益不同的是，该算法速度很快，而且对一些点多边少的图，进行聚类效果特别明显。  
算法流程：

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

# coding=utf-8
    import collections
    import random
     
    def load_graph(path):
        G = collections.defaultdict(dict)
        with open(path) as text:
            for line in text:
                vertices = line.strip().split()
                v_i = int(vertices[0])
                v_j = int(vertices[1])
                w = float(vertices[2])
                G[v_i][v_j] = w
                G[v_j][v_i] = w
        return G
     
    class Vertex():
        def __init__(self, vid, cid, nodes, k_in=0):
            self._vid = vid
            self._cid = cid
            self._nodes = nodes
            self._kin = k_in  # 结点内部的边的权重
     
    class Louvain():
        def __init__(self, G):
            self._G = G
            self._m = 0  # 边数量
            self._cid_vertices = {
       
        }  # 需维护的关于社区的信息(社区编号,其中包含的结点编号的集合)
            self._vid_vertex = {
       
        }  # 需维护的关于结点的信息(结点编号，相应的Vertex实例)
            for