louvain算法

在社交网络中，有的用户之间的连接较为紧密，有的用户之间的连接关系较为稀疏，在这样的的网络中，连接较为紧密的部分可以被看成一个社区，其内部的节点之间有较为紧密的连接，而在两个社区间则相对连接较为稀疏，这便称为社团结构。

louvain是基于模块度（modularity）进行社区发现，该算法的优点在于速度快，可以在较短时间内实现大规模网络以不同粒度的社区划分，并且无需指定社区的数量，当模块度不再增益时候，迭代便自动停止。

louvain简介

算法思想：Louvain算法的优化目标为最大化整个数据的模块度

实现步骤：

1、先令每个节点自己属于一个社区，此时网络中有几个节点便有几个社区，计算此时的模块度

2、然后令节点 $i$ 不再属于自己而是和节点 $j$ 一个社区，计算此时的模块度

3、两个步骤就使得此时的网络出现了模块度增量，则模块划分方法就是将 $i$ 节点划分到使模块度增量最大且大于0的那个节点中去

4、将步骤3中划分出来的社区聚合为一个节点，重构整个网络

实现代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

G = nx.Graph()
# 创建节点
G.add_nodes_from([i for i in range(14)])
# 创建关系
G.add_edges_from([(0,1),(0,2),(0,3),(1,2),(1,3),(2,4),(4,5),(4,7),(5,6),(5,7),(5,8),(6,8),(7,8),(7,10),(8,9),(9,10),(9,12),(9,13),(10,11),(10,12),(11,12),(11,13),(12,13)])
# 画出图
nx.draw_networkx(G)
plt.show()


1
2
3
4
5
6
7
8
9

# 调用louvain算法，partition储存分类结果
partition = community.best_partition(G)
print("聚类结果",partition)
# 查看模块度，modularity储存分类结果
modularity = community.modularity(partition,G)
print("聚类模块度",modularity)
values = [partition.get(node) for node in G.nodes]
nx.draw_spring(G,node_color = values, with_labels=True)
plt.show()