Louvain算法,louvain算法python

　　LOUVAIN——面向社会网络挖掘的大规模网络社区发现算法===

　　该算法来自《大型网络中社区的快速展开》一文，简称Louvian。

　　Louvain算法是基于模块性的社区发现算法。它是高效和有效的，并且可以发现分层的社区结构。其优化目标是最大化整个图属性结构(社区网络)的模块化。

　　需要了解的重点是：A、模块化的定义，这是描述社区中紧密度的值Q；b，模块性增量Q，即在一个社区C中放置一个孤立点后，计算模块性的变化。计算过程的要点是：首先计算一个点的模块度和社区C的模块度，然后计算合并后新社区的模块度。新社区的模块度减去前两个模块度就是delta Q，对上面公式的理解是将Delta Q展开等价于1/2 *( k_i，in/m-Sum_tot/m *ki/m)，其中k_i，in/m表示将孤立节点和社区C放在一起对整个网络模块度的影响。而Sum_tot/m和ki/m分别代表孤立节点和社区C分裂对整个网络模块性的影响，所以它们的差异反映了孤立节点在被放入社区C前后对整个网络模块性的影响.

　　算法的计算过程如下：A、将每个点视为一个社区，然后考虑每个社区的邻居节点，合并到社区中，然后delta Q；被看着；找到最大的正delta Q，将点合并到社区；再进行几轮，直到没有变化，然后结束；

　　问题是不同的节点访问顺序会导致不同的结果。实验中发现，这个顺序对结果影响不大，但会在一定程度上影响计算时间。

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

　　这种算法有三个优点：a、容易理解；b .无监督；而c，计算速度快，最后我们能得到的结果就是层次化的社区发现结果。

　　火花实现https://github.com/Sotera/spark-distributed-louvain-modularity

　　卢万结果图

　　还有一篇关于算法的改进和加速实现的论文。论文题目是：一种新的大型网络社区发现随机化算法。它的实现方式比较直接，就是考虑一个点周围的点的百分比来合并。可以在spark下通过类似的多路合并实现。

　　其他参考文献http://www.cnblogs.com/allanspark/p/4197980.html3359 www . quora . com/is-a-simple-explain-the-Louvain-method-of-community-detection

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。