基于Modularity的社区发现

作者: 巴拉巴拉_9515 | 来源:发表于2020-03-11 16:47 被阅读0次

基于Modularity的社区发现
第一篇随便写写（用Markdown）
社区发现算法-Louvain
模块、复用
Modularity
模块的封装性分析-读书笔记
社区发现
社区发现
豆瓣-第52个APP
图算法-群体发现(Louvain)

一、简介

1、社区

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

2、louvain与Modularity

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

二、Modularity

1、Modularity模块度

Modularity模块度定义：
$Q = \sum_c( \frac{E_c}{m}-(\frac{\sum tot}{2m})^2)$

其中 $m$ 表示图中边的数量， $c$ 表示社区， $E_c$ 表示社区 $c$ 内边的数量， $\sum tot$ 表示社区c节点的度之和

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

这个图包含23条边，包含3个社区
社区1内部边5条( $E_1=5$ )，结点度之和为 $2+3+3+3=11$
( $\sum tot=11$ )。
社区2内部边7条( $E_2=7$ )，结点度之和为 $3+4+4+4+2=17$
( $\sum tot=17$ )。
社区3内部边8条( $E_3=8$ )，结点度之和为 $4+3+4+3+4=18$
( $\sum tot=18$ )。

因此该图的模块度为：
$Q=[\frac{5}{23}-(\frac{11}{46})^2] + [\frac{7}{23}-(\frac{17}{46})^2] + [\frac{8}{23}-(\frac{18}{46})^2]=0.523$

2、模块度与社区紧密关系

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

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

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

社区1内部边13条( $E_1=13$ )，结点度之和为 $2+3+3+3+3+4+4+4+2=28$ ( $\sum tot=28$ )。
社区2内部边8条( $E_1=8$ )，结点度之和为 $4+3+3+4+4=18$ ( $\sum tot=18$ )。
左图的模块度为：
$Q=[\frac{13}{23}-(\frac{28}{46})^2] + [\frac{8}{23}-(\frac{18}{46})^2]=0.3894$

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

社区1内部边5条( $E_1=5$ )，结点度之和为 $2+3+3+3=11$ ( $\sum tot=11$ )。
社区2内部边17条( $E_1=17$ )，结点度之和为 $3+4+2+4+4+4+4+3+4+3 = 35$ ( $\sum tot=35$ )。
右图的模块度为：
$Q=[\frac{5}{23}-(\frac{11}{46})^2] + [\frac{17}{23}-(\frac{35}{46})^2]=0.3204$

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

三、louvain算法

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

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

1、louvain算法步骤

louvain算法步骤

（1）初始化，将每个节点看作一个独立社区
（2）尝试把节点i分配到相邻节点所在社区，计算分配前与分配后的模块度变化 $\Delta Q$ ，并记录 $\Delta Q$ 最大的社区，如果 $Max \Delta Q > 0$ ，则将该节点分配到该社区。
（3）重复操作步骤（2）直到所有节点的所属社区不再变化

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

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

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

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

···

2、python-louvain

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

3、案例计算

（1）图关系构建

import networkx as nx
import community
import matplotlib.pyplot as plt

# 使用networkx建立图形
G = nx.Graph()
G.add_nodes_from([0,1,2,3,4,5,6,7,8,9,10,11,12,13])
G.add_edges_from([(3, 0), (3, 1), (1, 0), (1, 2), (0, 2), (2, 4), (4, 7), (4, 5), (5, 7), (5, 6), (5, 8), (6, 8), (7, 8), (7, 10), (8, 9), (9, 10), (9, 12), (9, 13), (10, 12), (10, 11), (11, 13), (11, 12), (12,13)])
nx.draw(G,with_labels=True)
plt.show()

（2）社区发现

# louvain社区发现
partition = community.best_partition(G)
# {0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 2, 10: 2, 11: 2, 12: 2, 13: 2}
# 最大模块度
community.modularity(partition,G)
# 0.5226843100189036

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

s1 = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 1, 10: 1, 11: 1, 12: 1, 13: 1}
community.modularity(s1,G)
# 结果为：0.3894139886578449

s2 = {0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 9: 1, 10: 1, 11: 1, 12: 1, 13: 1}
community.modularity(s2,G)
# 结果为：0.3204158790170131