熟悉社区发现算法的，你不能错过这个Python库。它涵盖了Louvain算法、Girvan-Newman算法等多种社区发现算法，还具有可视化功能。网络是由一些紧密相连的节点组成的，根据不同节点之间的连接程度，网络也可以看作是由不同的簇组成的。一个集群中的节点之间的联系比较紧密，而不同集群之间的联系则比较稀疏。这样的集群在网络中称为社区结构。由此衍生的社区发现算法用于发现网络中的社区结构，此类算法包括Louvain算法、Girvan-Newman算法和Bron-Kerbosch算法。近日，机器之心在GitHub上发现了一个Python库社区，可以发现图中的社区结构，由软件工程师JonathanShobrook创建。项目地址：https://github.com/shobrook/communities首先，该库可以实现以下社区发现算法：Louvain算法Girvan-Newman算法层次聚类谱聚类Bron-Kerbosch算法其次，用户还可以使用社区库进行可视化以上算法。下图是Louvain算法在Zachary的空手道俱乐部网络中的可视化结果：库的安装方法也很简单，社区pip安装即可。代码如下：$pipinstallcommunities对于这个Python库，很多网友都给予了很高的评价，表示要试试看。算法解释Louvain算法louvain_method(adj_matrix:numpy.ndarray,n:int=None)->list该算法出自文章《Fast unfolding of communities in large networks》，简称Louvian。Louvain算法作为一种基于Modularity的社区发现算法，在效率和效果上表现更好，能够发现层次化的社区结构。其优化目标是最大化整个图属性结构（社区网络）的模块化。Louvain的算法对图模块化最大化的社区执行贪婪搜索。如果一个图具有高密度的种群内边和低密度的种群间边，则它被称为模图。示例代码如下：fromcommunities.algorithmssimportlouvain_methodadj_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算法迭代地删除边缘以创建更多连接的组件。每个组件都被视为一个社区，当模块性不能再增加时，算法将停止删除边缘。示例代码如下：fromcommunities.algorithmsimportgirvan_newmanadj_matrix=[...]communities,_=girvan_newman(adj_matrix)hierarchical_clustering(adj_matrix:numpy.ndarray,metric:str="cosine",linkage:str="single",n:int=None)->list层次聚类实现了自下而上的层次聚类算法。每个节点都从自己的社区开始，然后，随着层次结构的建立，最相似的社区被合并。社区将被合并，直到模块化没有进一步的进展。示例代码如下：fromcommunities.algorithmssimporthierarchical_clusteringadj_matrix=[...]communities=hierarchical_clustering(adj_matrix,metric="euclidean",linkage="complete")谱聚类spectral_clustering(adj_matrix:numpy.ndarray,k:int)->列出这一类算法假设邻接矩阵的特征值包含有关社区结构的信息。示例代码如下：fromcommunities.algorithmssimportspectral_clusteringadj_matrix=[...]communities=spectral_clustering(adj_matrix,k=5)Bron-Kerbosch算法bron_kerbosch(adj_matrix:numpy.ndarray,pivot:bool=False)->listBron-Kerbosch算法为实施最大集团检测。图中的最大团是形成完整图的节点子集，如果将其他节点添加到该子集，则该图不再完整。将最大团视为社区是合理的，因为团是图中连接最紧密的节点组。因为一个节点可以是多个社区的成员，所以该算法有时会识别出重叠的社区。示例代码如下：fromcommunities.algorithmsimportbron_kerboschadj_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)可视化图形，将节点分组到它们所属的社区中，并对它们进行颜色编码。返回表示绘图的matplotlib.axes.Axes。示例示例：fromCommunities.algorithmsimportlouvain_methodfromcommunities.visualizationimportdraw_communitiesadj_matrix=[...]社区，frames=louvain_method（adjmatrix）,dark:bool=False,duration:int=15,filename:str=None,dpi:int=None,seed:int=2)在图中应用Louvain算法可以实现动画显示，其中颜色每个节点的代表它所属的社区，同一社区内的节点聚集在一起。示例代码如下：fromcommunities.algorithmssimportlouvain_methodfromcommunities.visualizationimportlouvain_animationadj_matrix=[...]communities,frames=louvain_method(adj_matrix)louvain_animation(adj_matrix,frames)动画展示如下：
