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

一、概述

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

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

二、

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

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

# coding=utf-8
import collections
import random
 
def load_graph(path):
    G 

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系

开通VIP 解锁文章