基于社区发现机制研究论文

社区是一个子图，包含顶点和边，同一社区内结点与结点之间的连接很紧密，而社区与社区之间的连接比较稀疏。

Louvain算法是一种基于图数据的社区发现算法，通过模块度（Modularity）来衡量一个社区的紧密程度。被认为是性能最好的社区发现算法之一。

Modularity模块度定义：

其中 表示图中边的数量， 表示社区， 表示社区 内边的数量， 表示社区c节点的度之和

计算案例 [1] 例如将图划分为三个社区，计算该图的模块度

这个图包含23条边，包含3个社区 社区1内部边5条( )，结点度之和为 ( )。 社区2内部边7条( )，结点度之和为 ( )。 社区3内部边8条( )，结点度之和为 ( )。

因此该图的模块度为：

模块度值越大，说明社区划分的越好，社区越紧密。

模块度用来衡量一个社区的紧密程度

（1）计算左图模块度 左图包含23条边，包含2个社区

（2）计算右图模块度 右图包含23条边，包含2个社区

可以发现该图划分为三个社区的模块度值最大，划分为三个社区会比划分为两个社区更好。

Louvain算法是一种基于图数据的社区发现算法，通过模块度（Modularity）来衡量一个社区的紧密程度。

louvain如何使用Modularity来实现社区的发现？

louvain算法步骤

探索一下该步骤： 结点0 ：分配到相邻结点1，2，3所在社区 分配前模块度：；分配到{1}模块度：，分配到{2}模块度：，分配到{3}模块度：；根据最大模块度差异把结点0和3组合为一个社区。

结点1 ：分配到相邻结点0，2，3所在社区{0，3}，{2} 分配前模块度：；分配到{0，3}模块度：，{2}模块度：； 根据最大模块度差异把结点1和2组合为一个社区，此时{1,2},{0,3}

结点2 ：分配到相邻结点0，1，4所在社区{0，3}，{1}，{4} 分配前模块度：；分配到{0，3}模块度：，分配到{1}模块度：，分配到{4}模块度：。 根据最大模块度差异把结点2和3组合为一个社区，此时{0,2,3},{1},{4} 发现结点2的所属社区发生了变化

结点1 ：分配到相邻结点0,2,3所在社区{0,2,3} 分配前模块度：；分配到{0,2,3}模块度：，比原社区{1}的模块度大，形成新的社区{0,1,2,3}

···

python-louvain提供函数，该函数通过计算最大模块度实现社区发现，是louvain算法的封装。

（1）图关系构建

（2）社区发现

（3）验证上述左图、右图的计算结果

[1] 社区检测： [2] python-louvain函数文档： [3] 06年《Modularity and Community structure in networks 》一文：