前几天有个作业,要求在karate数据集上做一个社团检测,其实就是一个聚类。简单介绍一下数据集,空手道俱乐部(karate)数据集包含34个节点,由于管理不善,分裂成了两个社团,更多有关数据集和复杂网络的内容参见这里:Mark Newman
由于数据集是gml格式的,搜了一下python可以用igraph这个库来读取,详细了解了一下发现这个包还带了社团检测的函数,所以直接调包了,顺便研究了一下网上的代码做了个可视的结果,把聚类结果直接画出来。
1、先期准备
我在Windows下的python版本是3.5,写这个需要装两个包,igraph和cairo,igraph用来读图和社团检测,cairo用来进行绘图,比较不凑巧的是这两个包在Windows下都不能正常pip,需要找别人编译好的第三方包,(官方推荐),找到对应版本的包下载下来然后pip。
2、社团检测
社团检测这里用的是igraph的community_label_propagation()
,这个函数我追踪源码进不去,查了一下用的是标签传播算法(LPA)。
LPA的思路比较简单,这里简单说明一下:初始所有节点都有一个不同的标签,每轮迭代针对单个节点考虑与它直接相连的节点,将出现次数最多的标签赋给这个节点,持续这个过程直到所有节点的标签都不再变化。
LPA感觉非常像KNN,由于不需要计算到所有点的距离,复杂度应该不会太高,不过这个算法不够稳定,具有一定的随机性,这一点在下面会再次提到。
3、聚类结果绘制
绘图使用cairo,它的plot函数可以接收一个map类型的参数,用来传递图里一组节点的标签、颜色、大小等设置,map里的键是属性名,值是一个存储了各个节点对应属性值的列表,基本就是下面这样:
visual_style = {}
visual_style["vertex_label"] = g.vs["name"]
visual_style["vertex_color"] = ['' for i in range(g.vcount())]
下面贴两张绘制出来的结果,聚类结果不太稳定,在1~4个类之间波动,大部分是2、3个的情况。
最后附代码:
from igraph import *
# 预置部分颜色用于绘图
colors_type = ["yellow", "red", "green", "coral", "alice blue", "cyan", "pink"]
if __name__ == '__main__':
g = Graph.Read_GML("karate.gml") # 读图
g.vs["name"] = [str(i+1) for i in range(g.vcount())]
visual_style = {}
# 设置节点显示的名字
visual_style["vertex_label"] = g.vs["name"]
# 使用标签传递算法进行聚类
v = g.community_label_propagation()
print(v)
# 根据聚类结果对节点进行染色
visual_style["vertex_color"] = ['' for i in range(g.vcount())]
for i in range(len(v)):
for j in v[i]:
visual_style["vertex_color"][j] = colors_type[i]
# 可视化聚类结果 打印到屏幕
plot(g, None, **visual_style)