【Python】發(fā)現(xiàn)一個寶藏 Python 庫，玩社區(qū)發(fā)現(xiàn)算法的不能錯過！
由此衍生出來的社區(qū)發(fā)現(xiàn)（community detection）算法用來發(fā)現(xiàn)網(wǎng)絡中的社區(qū)結構，這類算法包括 Louvain 算法、Girvan-Newman 算法以及 Bron-Kerbosch 算法等。
首先，該庫可以實現(xiàn)以下幾種社區(qū)發(fā)現(xiàn)算法：
Louvain 算法 Girvan-Newman 算法 層次聚類 譜聚類 Bron-Kerbosch 算法
其次，用戶還可以使用 communities 庫來可視化上述幾種算法，下圖為空手道俱樂部（Zachary's karate club）網(wǎng)絡中 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 庫，很多網(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ū)結構，其優(yōu)化的目標是最大化整個圖屬性結構（社區(qū)網(wǎng)絡）的模塊度。
Louvain 算法對最大化圖模塊性的社區(qū)進行貪婪搜索。如果一個圖具有高密度的群體內邊緣和低密度的群體間邊緣，則稱之為模圖。
示例代碼如下：
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 算法迭代刪除邊以創(chuàng)建更多連接的組件。每個組件都被視為一個 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層次聚類實現(xiàn)了一種自底向上、分層的聚類算法。每個節(jié)點從自己 的社區(qū)開始，然后，隨著層次結構的建立，最相似的社區(qū)被合并。社區(qū)會一直被合并，直到在模塊度方面沒有進一步的進展。
示例代碼如下：
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這種類型的算法假定鄰接矩陣的特征值包含有關社區(qū)結構的信息。
示例代碼如下：
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) -> listfrom 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），將節(jié)點分組至它們所屬的社區(qū)和顏色編碼中。返回代表繪圖的 matplotlib.axes.Axes。示例代碼如下：
from communities.algorithms import louvain_method
from 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 算法在圖中的應用可以實現(xiàn)動圖展示，其中每個節(jié)點的顏色代表其所屬的社區(qū)，并且同一社區(qū)中的節(jié)點聚類結合在一起。
示例代碼如下：
from communities.algorithms import louvain_method
from 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/
往期精彩回顧
適合初學者入門人工智能的路線及資料下載 (圖文+視頻)機器學習入門系列下載 機器學習及深度學習筆記等資料打印 《統(tǒng)計學習方法》的代碼復現(xiàn)專輯 機器學習交流qq群955171419，加入微信群請掃碼