Louvain 算法

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

所以又被称为Fast unfolding算法。

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

首先复习下模块度：

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

算法详述：

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

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

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

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

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

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

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

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

   m是网络中的所有链路的权重的总和

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

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

上述两个阶段迭代进行，直到模块度不再增大。
  下图很好的描述了这两个阶段。第一次迭代，经过模块度优化阶段，总的 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()

参考结果如下：

社区 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