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

來源丨任識算法

編輯丨Python數(shù)據科學

推薦閱讀： 終于來了，【第三期】 彭濤Python 爬蟲特訓營！!

網絡是由一些緊密相連的節(jié)點組成的，并且根據不同節(jié)點之間連接的緊密程度，網絡也可視為由不同簇組成。簇內的節(jié)點之間有著更為緊密的連接，不同簇之間的連接則相對稀疏。這種簇被稱為網絡中的社區(qū)結構（community structure）。

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

最近，在 GitHub 上發(fā)現(xiàn)了一個可以發(fā)現(xiàn)圖中社區(qū)結構的 Python 庫 communities，該庫由軟件工程師 Jonathan Shobrook 創(chuàng)建。

項目地址：https://github.com/shobrook/communities

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

• 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）的社區(qū)發(fā)現(xiàn)算法，Louvain 算法在效率和效果上都表現(xiàn)比較好，并且能夠發(fā)現(xiàn)層次性的社區(qū)結構，其優(yōu)化的目標是最大化整個圖屬性結構（社區(qū)網絡）的模塊度。

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)?->?list
    

Bron-Kerbosch 算法實現(xiàn)用于最大團檢測（maximal clique detection）。圖中的最大團是形成一個完整圖的節(jié)點子集，如果向該子集中添加其他節(jié)點，則它將不再完整。將最大團視為社區(qū)是合理的，因為團是圖中連接最緊密的節(jié)點群。因為一個節(jié)點可以是多個社區(qū)的成員，所以該算法有時會識別重疊的社區(qū)。 示例代碼如下：

      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），將節(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/

···? END? ···

我們爬蟲第三期來了，加入我們，學更實用，更值錢的 Python 技術！

從0到1系統(tǒng)掌握Python 技術（入門進階）

2個企業(yè)實戰(zhàn)項目，4大常用工具

掌握24種反爬策略手段，成為真正爬蟲高手

能抓取市面上90%的網站

掌握主流爬蟲技術，就業(yè)找工作 真正全方位幫助大家從0到1，從 Python 入門到進階，轉行找爬蟲工作。