这个图聚类Python工具火了：社群结构可视化、检测 |开源子豪发自凹非寺量子位报道|公

子豪发自凹非寺量子位报道|公众号QbitAI
最近，又有一款Python可视化工具火了。
这一次，功能是针对图聚类问题的社群结构进行检测、可视化。

文章图片
该项目的帖子在reddit上一经发布，就被顶到了“机器学习板块”的榜首。

文章图片
一起来看看它究竟都能用来做什么吧~
功能亮点
这款工具叫作communities ，是一个Python库，用于图聚类问题的社群结构检测。
它支持多种算法，包括：
Louvain算法；Girvan-Newman算法；层次聚类算法；光谱聚类算法；Bron-Kerbosch算法。更赞的是， communities还可以实现这些算法的可视化。
具体了解一下～
导入算法并插入矩阵
这里以Louvain算法为例。
这是一种基于模块度的社群发现算法，也是贪心算法。
它根据顶点的共享边将顶点排列成社群结构，也就是说，它将节点分为几个社群，每个社群之间共享很少的连接，但是同一社群的节点之间共享许多连接。
最终，让整个社群网络呈现出一种模块聚集的结构，实现整个社群网络的模块度的最大化。
所以首先，我们需要构建一个表示无向图的邻接矩阵，可以加权，也可以不加权，矩阵为2Dnumpy数组。
n*n矩阵则表示有n个节点，矩阵的每个位置分别表示各节点之间边的关系，有边则为1 ，没有边则为0 。
然后，只需从communities.algorithms中导入算法并插入矩阵。
importnumpyasnpfromcommunities.algorithmsimportlouvain_methodadj_matrix=np.array([[0,1,1,0,0,0],[1,0,1,0,0,0],[1,1,0,1,0,0],[0,0,1,0,1,1],[0,0,0,1,0,1],[0,0,0,1,1,0]])communities,_=louvain_method(adj_matrix)#>>>[{0,1,2},{3,4,5}]接下来输出社群列表，每个社群即为一组节点。
实现可视化，并进行颜色编码
利用communities将图进行可视化，将节点分到社群中并进行颜色编码，还可以选择深色或浅色背景、保存图片、选择图片的分辨率等等。
draw_communities(adj_matrix:numpy.ndarray,communities:list,dark:bool=False,filename:str=None,seed:int=1)
其中各参数的具体含义为：
adj_matrix(numpy.ndarray)：图的邻接矩阵；dark(bool,optional(default=False))：如果为True,则绘图为深色背景，否则为浅色背景；filename(strorNone,optional(default=None))：通过filename路径可以将图另存为PNG格式;设置None则是用交互方式显示图；dpi(intorNone,optional(default=None))：每英寸的点数，控制图像的分辨率；seed(int,optional(default=2))：随机种子。具体到Louvain算法的可视化，代码是这样的：
fromcommunities.algorithmsimportlouvain_methodfromcommunities.visualizationimportdraw_communitiesadj_matrix=[...]communities,frames=louvain_method(adj_matrix)draw_communities(adj_matrix,communities)

文章图片
动画呈现算法
communities还可以动画呈现节点分配到社群的过程。
louvain_animation(adj_matrix:numpy.ndarray,frames:list,dark:bool=False,duration:int=15,filename:str=None,dpi:int=None,seed:int=2)
其中各参数的含义如下：
adj_matrix(numpy.ndarray)：图的邻接矩阵；frames(list)：算法每次迭代的字典列表；每个字典都有俩个键：“C”包含节点到社群的查找表， “Q”表示图的模块度数值；此字典列表是louvain_method的第二个返回值；dark(bool,optional(default=False))：如果为True,则动画为深色背景和配色方案，否则为浅色方案；duration(int,optional(default=15))：动画所需的持续时间，以秒为单位；filename(strorNone,optional(default=None))：通过filename路径将动画存为GIF；设置None则以交互方式展示动画；dpi(intorNone,optional(default=None))：每英寸点数，控制动画的分辨率；seed(int,optional(default=2))：随机种子。例如，空手道俱乐部网络中Louvain算法的动画呈现：
fromcommunities.algorithmsimportlouvain_methodfromcommunities.visualizationimportlouvain_animationadj_matrix=[...]communities,frames=louvain_method(adj_matrix)louvain_animation(adj_matrix,frames)

文章图片
我们可以看到Louvain算法的动态过程：
首先扫描数据中的所有节点，将每个节点看做一个独立的社群；接下来，遍历每个节点的邻居节点，判断是否将该节点加入邻居节点所在的社群，以提升模块度；这一过程重复迭代，直到每一个节点的社群归属稳定；最后，将所有在同一个社群的节点压缩成一个新节点，计算新节点的权重，直到整个图的模块度稳定。大家可以通过文末链接，自行尝试一下其他算法～