Communitydetection｜模块度含义理解｜Louvain算法

利用图拓扑结构中蕴藏的信息&＃xff0c;从复杂网络中解析出存在密切联系的节点&＃xff08;团伙&＃xff09;。

度量社区划分优劣的指标&＃xff0c;直观上表示某社团划分状态下&＃xff0c;社团内部连边数量与该划分下随机连边数量的差值。
计算公式如下&＃xff1a;
Q&＃61;12m∑i,j[Aij−kikj2m]δ(ci,cj)&＃61;12m∑i,jAijδ(ci,cj)−∑i,jkikj2mδ(ci,cj)Q&＃61;\frac{1}{2m}\sum_{i,j}[A_{ij}-\frac{k_ik_j}{2m}]\delta(c_i,c_j)&＃61;\frac{1}{2m}\sum_{i,j}A_{ij}\delta(c_i,c_j)-\sum_{i,j}\frac{k_ik_j}{2m}\delta(c_i,c_j)Q&＃61;2m1​i,j∑​[Aij​−2mki​kj​​]δ(ci​,cj​)&＃61;2m1​i,j∑​Aij​δ(ci​,cj​)−i,j∑​2mki​kj​​δ(ci​,cj​)
δ(ci,cj)\delta(c_i,c_j)δ(ci​,cj​)&＃xff1a;i, j在同一社团内部取1&＃xff0c;否则取0

∑i,jAijδ(ci,cj)\sum_{i,j}A_{ij}\delta(c_i,c_j)∑i,j​Aij​δ(ci​,cj​)&＃xff1a;社团内部连边数量之和

kj2mδ(ci,cj)\frac{k_j}{2m}\delta(c_i,c_j)2mkj​​δ(ci​,cj​)&＃xff1a;社团内部随机连边&＃xff0c;连到节点j 的概率&＃xff0c;kikj2mδ(ci,cj)\frac{k_ik_j}{2m}\delta(c_i,c_j)2mki​kj​​δ(ci​,cj​)&＃xff1a;随机连边&＃xff0c;i, j之间连接的边数&＃xff0c;∑i,jkikj2mδ(ci,cj)\sum_{i,j}\frac{k_ik_j}{2m}\delta(c_i,c_j)∑i,j​2mki​kj​​δ(ci​,cj​)&＃xff1a;随机连边&＃xff0c;社团内部连边总数

因此&＃xff0c;两项差值越大&＃xff0c;证明社团内部联系相对越紧密&＃xff0c;社团划分的效果越好。

注&＃xff1a;分母是2m而非m的原因&＃xff1a;知乎_无向图louvain讲解

模块度增益

ΔQ&＃61;Q′−(Qi&＃43;Q2)\Delta Q&＃61;Q&＃39;-(Q_i&＃43;Q_2)ΔQ&＃61;Q′−(Qi​&＃43;Q2​)

即合并后的社团模块度减去合并前两社团模块度之和

遍历每一种社团划分方法显然是不现实的。
Louvain算法是一种启发式迭代算法&＃xff1a;
1&＃xff09;将图中的每个节点看成一个独立的社区&＃xff0c;社区的数目与节点个数相同&＃xff1b;
2&＃xff09;对每个节点i&＃xff0c;依次尝试把节点i分配到其每个邻居节点所在的社区&＃xff0c;计算分配前与分配后的模块度变化Δ&＃x1d444;&＃xff0c;并记录Δ&＃x1d444;最大的那个邻居节点&＃xff0c;如果&＃x1d45a;&＃x1d44e;&＃x1d465;Δ&＃x1d444;>0&＃xff0c;则把节点i分配Δ&＃x1d444;最大的那个邻居节点所在的社区&＃xff0c;否则保持不变&＃xff1b;
3&＃xff09;重复2&＃xff09;&＃xff0c;直到所有节点的所属社区不再变化&＃xff1b;
4&＃xff09;对图进行压缩&＃xff0c;将所有在同一个社区的节点压缩成一个新节点&＃xff0c;社区内节点之间的边的权重转化为新节点的环的权重&＃xff0c;社区间的边权重转化为新节点间的边权重&＃xff1b;
5&＃xff09;重复1&＃xff09;直到整个图的模块度不再发生变化。

参考文章&＃xff1a;
博客园_模块度与Louvain社区发现算法