实现、动态展示多种社区发现算法，这个Python库助你发现网络图的社区结构 机器之心报道 编辑：杜伟、陈萍熟知社区发现算法，你不能错过这个 Python 库。它涵盖 Louvain 算法、Girvan-Newman 算法等多种社区发现算法，还具有可视化功能。 网络是由一些紧密相连的节点组成的，并且根据不同节点之间连接的紧密程度，网络也可视为由不同簇组成。簇内的节点之间有着更为紧密的连接，不同簇之间的连接则相对稀疏。这种簇被称为网络中的社区结构（community structure）。 由此衍生出来的社区发现（community detection）算法用来发现网络中的社区结构，这类算法包括 Louvain 算法、Girvan-Newman 算法以及 Bron-Kerbosch 算法等。 最近，机器之心在 GitHub 上发现了一个可以发现图中社区结构的 Python 库 communities，该库由软件工程师 Jonathan Shobrook 创建。 项目地址：https://github.com/shobrook/communities 首先，该库可以实现以下几种社区发现算法： Louvain 算法 Girvan-Newman 算法 层次聚类 谱聚类 Bron-Kerbosch 算法 其次，用户还可以使用 communities 库来可视化上述几种算法，下图为空手道俱乐部（Zachary's karate club）网络中 Louvain 算法的可视化结果： 该库的安装方法也非常简单，可采用 pip 的方式安装 communities，代码如下： $ pip install communities 对于这个 Python 库，很多网友给予了高度评价，表示会去尝试。 算法详解 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) 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) 层次聚类 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") 谱聚类 spectral_clustering(adj_matrix : numpy.ndarray, k : int) - list 这种类型的算法假定邻接矩阵的特征值包含有关社区结构的信息。 示例代码如下： from communities.algorithms import spectral_clustering adj_matrix = [...]communities = spectral_clustering(adj_matrix, k=5) Bron-Kerbosch 算法 bron_kerbosch(adj_matrix : numpy.ndarray, pivot : bool = False) - list Bron-Kerbosch 算法实现用于最大团检测（maximal clique detection）。图中的最大团是形成一个完整图的节点子集，如果向该子集中添加其他节点，则它将不再完整。将最大团视为社区是合理的，因为团是图中连接最紧密的节点群。因为一个节点可以是多个社区的成员，所以该算法有时会识别重叠的社区。 示例代码如下： from communities.algorithms import bron_kerbosch adj_matrix = [...]communities = bron_kerbosch(adj_matrix, pivot=True) 可视化 绘图 draw_communities(adj_matrix : numpy.ndarray, communities : list, dark : bool = False, filename : str = None, seed : int = 1) 可视化图（graph），将节点分组至它们所属的社区和颜色编码中。返回代表绘图的 matplotlib.axes.Axes。示例代码如下： from communities.algorithms import louvain_methodfrom communities.visualization import draw_communities adj_matrix = [...]communities, frames = louvain_method(adj_matrix) draw_communities(adj_matrix, communities) 可视化图如下： Louvain 算法的动图展示 louvain_animation(adj_matrix : numpy.ndarray, frames : list, dark : bool = False, duration : int = 15, filename : str = None, dpi : int = None, seed : int = 2) Louvain 算法在图中的应用可以实现动图展示，其中每个节点的颜色代表其所属的社区，并且同一社区中的节点聚类结合在一起。 示例代码如下： from communities.algorithms import louvain_methodfrom communities.visualization import louvain_animation adj_matrix = [...]communities,frames=louvain_method(adj_matrix) louvain_animation(adj_matrix, frames) 动图展示如下： 参考链接：https://www.codenong.com/cs105912940/https://www.reddit.com/r/MachineLearning/comments/lozys9/p_i_made_communities_a_library_of_clustering/ 百万级文献分析，十万字深入解读2020-2021 全球AI技术发展趋势报告报告内容涵盖人工智能顶会趋势分析、整体技术趋势发展结论、六大细分领域（自然语言处理、计算机视觉、机器人与自动化技术、机器学习、智能基础设施、数据智能技术、前沿智能技术）技术发展趋势数据与问卷结论详解，最后附有六大技术领域5年突破事件、Synced Indicator 完整数据。 识别下方二维码，立即购买报告。 ?THE END 转载请联系本公众号获得授权 投稿或寻求报道：content@jiqizhixin.com