LOUVAIN——社交网络挖掘之大规模网络的社区发现算法

===

算法来源

该算法来源于文章Fast unfolding of communities in large networks，简称为Louvian。

算法原理

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

其中需要理解的核心点有：

• a、模块度Modularity的定义，这个定义是描述社区内紧密程度的值Q；
• b、模块度增量delta Q，即把一个孤立的点放入一个社区C后，计算Modularity的变化，其中计算过程的要点是，首先计算1个点的Modularity，和社区C的Modularity，再计算合并后新社区的Modularity，新社区的Modularity减去前两个Modularity就是delta Q。

对上述公式的理解是，将delta Q展开其等价于1/2 *( k_i,in/m - Sum_tot/m *ki/m )，其中k_i,in/m表示的是将孤立的节点和社区C放在一起对整个网络Modularity的影响，而Sum_tot/m和ki/m分别表示孤立的节点和社区C分开式分别对整个网络Modularity的影响，所以他们的差值就反应了孤立的节点放入社区C前后对整个网络Modularity的影响。

算法的计算过程如下：

• a、每个点作为一个community，然后考虑每个community的邻居节点，合并到community，然后看delta Q；找到最大的正delta Q，合并点到community；多进行几轮，至不再变动，那么结束；
  其中存在的问题是，不同的节点访问顺序将导致不同的结果，试验中发现这个顺序对结果影响不大，但是会在一定程度上影响计算时间。

• b、将新的community作为点，重复上述过程。那么如何确定新的点之前的权重呢？答案是将两个community之间相邻的点之间的权重和作为两个community退化成一个点后的新的权重。

该算法的优点主要有3个：a、易于理解；b、非监督；和c、计算快速，最后我们可以得到的结果是层次化的社区发现结果。

spark实现

https://github.com/Sotera/spark-distributed-louvain-modularity

Louvain结果示意图

算法的改进

还有其加速实现的论文，文章的题目是：A New Randomized Algorithm for Community Detection in Large Networks，其实现方式比较直接，就是考虑一个点周围的百分之多少点进行归并。可以在spark下面通过类似于多路归并来实现。

其他参考资料

• http://www.cnblogs.com/allanspark/p/4197980.html
• https://www.quora.com/Is-there-a-simple-explanation-of-the-Louvain-Method-of-community-detection