一、简介

1、社区

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

2、louvain与Modularity

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

二、Modularity

1、Modularity模块度

Modularity模块度定义：

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

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

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

因此该图的模块度为：

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

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

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

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

社区1内部边13条()，结点度之和为 ()。
社区2内部边8条()，结点度之和为 ()。
左图的模块度为：

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

社区1内部边5条()，结点度之和为 ()。
社区2内部边17条()，结点度之和为 ()。
右图的模块度为：

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

三、louvain算法

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

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

1、louvain算法步骤

louvain算法步骤

（1）初始化，将每个节点看作一个独立社区
（2）尝试把节点i分配到相邻节点所在社区，计算分配前与分配后的模块度变化，并记录最大的社区，如果，则将该节点分配到该社区。
（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

参考资料

[1] 社区检测：https://zhuanlan.zhihu.com/p/41105026
https://www.jianshu.com/p/4ebe42dfa8ec
[2] python-louvain函数文档：https://python-louvain.readthedocs.io/_/downloads/en/latest/pdf/
[3] 06年《Modularity and Community structure in networks 》一文：https://wenku.baidu.com/view/15394e520912a216147929cc.html