發(fā)現(xiàn)一個寶藏Python庫，玩社區(qū)發(fā)現(xiàn)算法的不能錯過！

由此衍生出來的社區(qū)發(fā)現(xiàn)（community detection）算法用來發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，這類算法包括Louvain 算法、Girvan-Newman 算法以及 Bron-Kerbosch 算法等。

首先，該庫可以實現(xiàn)以下幾種社區(qū)發(fā)現(xiàn)算法：

• Louvain 算法
• Girvan-Newman 算法
• 層次聚類
• 譜聚類
• Bron-Kerbosch 算法

其次，用戶還可以使用 communities 庫來可視化上述幾種算法，下圖為空手道俱樂部（Zachary's karate club）網(wǎng)絡(luò)中 Louvain 算法的可視化結(jié)果：

該庫的安裝方法也非常簡單，可采用 pip 的方式安裝 communities，代碼如下：

importnumpyasnp

fromcommunities.algorithmsimportlouvain_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 庫，很多網(wǎng)友給予了高度評價，表示會去嘗試。

算法詳解

1、Louvain 算法

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

該算法來源于文章《Fast unfolding of communities in large networks》，簡稱為 Louvian。

作為一種基于模塊度（Modularity）的社區(qū)發(fā)現(xiàn)算法，Louvain 算法在效率和效果上都表現(xiàn)比較好，并且能夠發(fā)現(xiàn)層次性的社區(qū)結(jié)構(gòu)，其優(yōu)化的目標是最大化整個圖屬性結(jié)構(gòu)（社區(qū)網(wǎng)絡(luò)）的模塊度。

Louvain 算法對最大化圖模塊性的社區(qū)進行貪婪搜索。如果一個圖具有高密度的群體內(nèi)邊緣和低密度的群體間邊緣，則稱之為模圖。

示例代碼如下：

fromcommunities.algorithmsimportlouvain_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 算法迭代刪除邊以創(chuàng)建更多連接的組件。每個組件都被視為一個 community，當模塊度不能再增加時，算法停止去除邊緣。

示例代碼如下：

fromcommunities.algorithmsimportgirvan_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

層次聚類實現(xiàn)了一種自底向上、分層的聚類算法。每個節(jié)點從自己 的社區(qū)開始，然后，隨著層次結(jié)構(gòu)的建立，最相似的社區(qū)被合并。社區(qū)會一直被合并，直到在模塊度方面沒有進一步的進展。

示例代碼如下：

fromcommunities.algorithmsimporthierarchical_clustering

adj_matrix=[...]

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

4、譜聚類

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

這種類型的算法假定鄰接矩陣的特征值包含有關(guān)社區(qū)結(jié)構(gòu)的信息。

示例代碼如下：

fromcommunities.algorithmsimportspectral_clustering

adj_matrix=[...]

communities=spectral_clustering(adj_matrix,k=5)

5、Bron-Kerbosch 算法

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

fromcommunities.algorithmsimportbron_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），將節(jié)點分組至它們所屬的社區(qū)和顏色編碼中。返回代表繪圖的 matplotlib.axes.Axes。示例代碼如下：

fromcommunities.algorithmsimportlouvain_method

fromcommunities.visualizationimportdraw_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 算法在圖中的應(yīng)用可以實現(xiàn)動圖展示，其中每個節(jié)點的顏色代表其所屬的社區(qū)，并且同一社區(qū)中的節(jié)點聚類結(jié)合在一起。

示例代碼如下：

fromcommunities.algorithmsimportlouvain_method

fromcommunities.visualizationimportlouvain_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/

審核編輯 ：李倩