【Python】发现一个宝藏 Python 库，玩社区发现算法的不能错过！

由此衍生出来的社区发现（community detection）算法用来发现网络中的社区结构，这类算法包括 Louvain 算法、Girvan-Newman 算法以及 Bron-Kerbosch 算法等。

首先，该库可以实现以下几种社区发现算法：

其次，用户还可以使用 communities 库来可视化上述几种算法，下图为空手道俱乐部（Zachary's karate club）网络中 Louvain 算法的可视化结果：

该库的安装方法也非常简单，可采用 pip 的方式安装 communities，代码如下：

import numpy as np

from communities.algorithms import louvain_method

adj_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)

>> communities
[{0, 1, 2}, {3, 4, 5}]

对于这个 Python 库，很多网友给予了高度评价，表示会去尝试。

算法详解

1、Louvain 算法

louvain_method(adj_matrix : numpy.ndarray, n : int = None) -> list

该算法来源于文章《Fast unfolding of communities in large networks》，简称为 Louvian。

作为一种基于模块度（Modularity）的社区发现算法，Louvain 算法在效率和效果上都表现比较好，并且能够发现层次性的社区结构，其优化的目标是最大化整个图属性结构（社区网络）的模块度。

Louvain 算法对最大化图模块性的社区进行贪婪搜索。如果一个图具有高密度的群体内边缘和低密度的群体间边缘，则称之为模图。

示例代码如下：

from communities.algorithms import louvain_methodad

j_matrix = [...]

communities, _ = louvain_method(adj_matrix)

2、Girvan-Newman 算法

girvan_newman(adj_matrix : numpy.ndarray, n : int = None) -> list

该算法来源于文章《Community structure in social and biological networks》。

Girvan-Newman 算法迭代删除边以创建更多连接的组件。每个组件都被视为一个 community，当模块度不能再增加时，算法停止去除边缘。

示例代码如下：

from communities.algorithms import girvan_newman

adj_matrix = [...]

communities, _ = girvan_newman(adj_matrix)

3、层次聚类

hierarchical_clustering(adj_matrix : numpy.ndarray, metric : str = "cosine", linkage : str = "single", n : int = None) -> list

层次聚类实现了一种自底向上、分层的聚类算法。每个节点从自己 的社区开始，然后，随着层次结构的建立，最相似的社区被合并。社区会一直被合并，直到在模块度方面没有进一步的进展。

示例代码如下：

from communities.algorithms import hierarchical_clustering

adj_matrix = [...]

communities = hierarchical_clustering(adj_matrix, metric="euclidean", linkage="complete")

4、谱聚类

spectral_clustering(adj_matrix : numpy.ndarray, k : int) -> list

这种类型的算法假定邻接矩阵的特征值包含有关社区结构的信息。

示例代码如下：

from communities.algorithms import spectral_clustering

adj_matrix = [...]

communities = spectral_clustering(adj_matrix, k=5)

5、Bron-Kerbosch 算法

bron_kerbosch(adj_matrix : numpy.ndarray, pivot : bool = False) -> list

louvain_method(adj_matrix : numpy.ndarray, n : int = None) -> list0

可视化

绘图

louvain_method(adj_matrix : numpy.ndarray, n : int = None) -> list1

可视化图（graph），将节点分组至它们所属的社区和颜色编码中。返回代表绘图的 matplotlib.axes.Axes。示例代码如下：

louvain_method(adj_matrix : numpy.ndarray, n : int = None) -> list2

可视化图如下：

Louvain 算法的动图展示

louvain_method(adj_matrix : numpy.ndarray, n : int = None) -> list3

Louvain 算法在图中的应用可以实现动图展示，其中每个节点的颜色代表其所属的社区，并且同一社区中的节点聚类结合在一起。

示例代码如下：

louvain_method(adj_matrix : numpy.ndarray, n : int = None) -> list4

动图展示如下：

参考链接：

https://www.codenong.com/cs105912940/

https://www.reddit.com/r/MachineLearning/comments/lozys9/p_i_made_communities_a_library_of_clustering/

louvain_method(adj_matrix : numpy.ndarray, n : int = None) -> list5

louvain_method(adj_matrix : numpy.ndarray, n : int = None) -> list6

《统计学习方法》的代码复现专辑