Louvain 算法来源于文章2010年的论文Fast unfolding of communities in large networks，简称为Louvian [1]。
算法原理
Louvain算法是基于模块度（Modularity）的社区发现算法，该算法在效率和效果上都表现比较好，并且能够发现层次性的社区结构，其优化的目标是最大化整个图属性结构（社区网络）的模块度。
其中需要理解的核心点有：
- 模块度Modularity的定义，这个定义是描述社区内紧密程度的值；
- 模块度增量，即把一个孤立的点放入一个社区C后，计算Modularity的变化，其中计算过程的要点是，首先计算1个点的Modularity，和社区C的Modularity，再计算合并后新社区的Modularity，新社区的Modularity减去前两个Modularity就是。
对上述公式的理解是，将展开其等价于，其中,表示的是将孤立的节点和社区C放在一起对整个网络 Modularity 的影响，而 和 分别表示孤立的节点和社区C分开式分别对整个网络Modularity的影响，所以他们的差值就反应了孤立的节点放入社区C前后对整个网络Modularity的影响。
算法的计算过程如下：每个点作为一个community，然后考虑每个community的邻居节点，合并到community，然后看；找到最大的正，合并点到community；多进行几轮，至不再变动，那么结束；
其中存在的问题是，不同的节点访问顺序将导致不同的结果，实验中发现这个顺序对结果影响不大，但是会在一定程度上影响计算时间。将新的community作为点，重复上述过程。那么如何确定新的点之前的权重呢？答案是将两个community之间相邻的点之间的权重和作为两个community退化成一个点后的新的权重。
该算法的优点主要有3个：
- 易于理解
- 非监督
- 计算快速
最后我们可以得到的结果是层次化的社区发现结果。
spark实现: https://github.com/Sotera/spark-distributed-louvain-modularity
算法的改进: 还有其加速实现的论文，例如[2], 其实现方式比较直接，就是考虑一个点周围的百分之多少点进行归并。可以在spark下面通过类似于多路归并来实现。
参考资料：
- BLONDEL V D, GUILLAUME J-L, LAMBIOTTE R, 等. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): P10008.
- Kirianovskii I , Granichin O , Proskurnikov A . A New Randomized Algorithm for Community Detection in Large Networks**The results of the paper have been obtained at IPME RAS under support of Russian Foundation for Basic Research (RFBR) grant 16-07-00890[J]. IFAC-PapersOnLine, 2016, 49(13):31-35.
- AllanSpark, Louvain社区发现算法 https://www.cnblogs.com/allanspark/p/4197980.html