社区发现算法：Louvain

发表于 更新于
Louvain（鲁汶）算法是基于模块度（modularity）计算的社区识别算法。

社区是一种局部性结构，该局部性结构内部连接紧密，而不同的局部性结构之间连接稀疏，这种局部性结构是社区。
Louvain（鲁汶）算法是基于模块度（modularity）计算的社区识别算法，是以最大化模块度为目标的一种对顶点进行聚类的迭代过程。该算法由比利时鲁汶大学的 Vincent D.Blondel 等人于2008年提出，因其能以较高的效率计算出令人满意的社区识别结果，而成为近年来最多被提及和使用的社区识别算法。主要用于社交网虚假账号识别、消费群体划分及商品推荐、银行卡伪冒和欺诈团伙识别、银行理财产品、保险产品推荐、企业集团及家族企业识别等领域。

安装python-louvain

1
pip install python-louvain

使用python-louvain

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from community import community_louvain
import matplotlib.cm as cm
import matplotlib.pyplot as plt
import networkx as nx

# load the karate club graph
G = nx.karate_club_graph()

# 对图数据进行社群划分
partition = community_louvain.best_partition(G)

# 查看分组情况
print(partition)

#在实际应用的时候，我们一般转换成DataFrame
import pandas as pd
pd.DataFrame({'Id':partition.keys(),'Group':partition.values()})

# draw the graph
pos = nx.spring_layout(G)

# color the nodes according to their partition
cmap = cm.get_cmap('viridis', max(partition.values()) + 1)
nx.draw_networkx_nodes(G, 
                       pos, 
                       partition.keys(), 
                       node_size=40,
                       cmap=cmap, 
                       node_color=list(partition.values())
                      )
nx.draw_networkx_edges(G, pos, alpha=0.5)
plt.show()