社区发现算法-Louvain - 简书
简介
Louvain算法[1]是一种基于多层次优化Modularity[2]的算法,它的优点是快速、准确,被[3]认为是性能最好的社区发现算法之一。Modularity函数最初被用于衡量社区发现算法结果的质量,它能够刻画发现的社区的紧密程度。那么既然能刻画社区的紧密程度,也就能够被用来当作一个优化函数,即将结点加入它的某个邻居所在的社区中,如果能够提升当前社区结构的modularity。</br>
Modularity的定义如下:
其中,m表示网络中边的数量,A为邻接矩阵,如果ci,cj相同则$\delta(ci,cj)$=1否则为0。</br>
如果当前结点所在的社区只有它自己,那么在计算将它加入到其它社区时的modularity的变化有个技巧来加速计算,Louvain的高效性也在一定程度上受益于此,它为:
</br>
Louvain算法包括两个阶段,在步骤一它不断地遍历网络中的结点,尝试将单个结点加入能够使modularity提升最大的社区中,直到所有结点都不再变化。在步骤二,它处理第一阶段的结果,将一个个小的社区归并为一个超结点来重新构造网络,这时边的权重为两个结点内所有原始结点的边权重之和。迭代这两个步骤直至算法稳定。它的执行流程如图所示:
</br>
## ****代码实现
GraphX是Spark上的一个图处理框架,它在RDD的基础之上封装出VertexRDD以及EdgeRDD,由这两个封装出的RDD便可构成图结构,详细请见官网:
## ****文献
1: Fast unfolding of communities in large networks
2: Finding community structure in very large networks
3: Community detection algorithms: A comparative analysis