來源：機(jī)器之心

熟知社區(qū)發(fā)現(xiàn)算法，你不能錯(cuò)過這個(gè) Python 庫。它涵蓋 Louvain 算法、Girvan-Newman 算法等多種社區(qū)發(fā)現(xiàn)算法，還具有可視化功能。

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

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

最近，機(jī)器之心在 GitHub 上發(fā)現(xiàn)了一個(gè)可以發(fā)現(xiàn)圖中社區(qū)結(jié)構(gòu)的 Python 庫 communities，該庫由軟件工程師 Jonathan Shobrook 創(chuàng)建。

項(xiàng)目地址：https://github.com/shobrook/communities

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

• Louvain 算法

• Girvan-Newman 算法

• 層次聚類

• 譜聚類

• Bron-Kerbosch 算法

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

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

$ pip install communities

對于這個(gè) Python 庫，很多網(wǎng)友給予了高度評價(jià)，表示會(huì)去嘗試。

算法詳解

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)化的目標(biāo)是最大化整個(gè)圖屬性結(jié)構(gòu)（社區(qū)網(wǎng)絡(luò)）的模塊度。

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

示例代碼如下：

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

示例代碼如下：

from communities.algorithms import girvan_newmanadj_matrix = [...] communities, _ = girvan_newman(adj_matrix)

層次聚類

hierarchical_clustering(adj_matrix : numpy.ndarray, metric : str = "cosine", linkage : str = "single", n : int = None) -> list

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

示例代碼如下：

from communities.algorithms import hierarchical_clusteringadj_matrix = [...] communities = hierarchical_clustering(adj_matrix, metric="euclidean", linkage="complete")

譜聚類

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

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

示例代碼如下：

from communities.algorithms import spectral_clusteringadj_matrix = [...] communities = spectral_clustering(adj_matrix, k=5)

Bron-Kerbosch 算法

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

Bron-Kerbosch 算法實(shí)現(xiàn)用于最大團(tuán)檢測（maximal clique detection）。圖中的最大團(tuán)是形成一個(gè)完整圖的節(jié)點(diǎn)子集，如果向該子集中添加其他節(jié)點(diǎn)，則它將不再完整。將最大團(tuán)視為社區(qū)是合理的，因?yàn)閳F(tuán)是圖中連接最緊密的節(jié)點(diǎn)群。因?yàn)橐粋€(gè)節(jié)點(diǎn)可以是多個(gè)社區(qū)的成員，所以該算法有時(shí)會(huì)識(shí)別重疊的社區(qū)。

示例代碼如下：

from communities.algorithms import bron_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)

可視化圖（graph），將節(jié)點(diǎn)分組至它們所屬的社區(qū)和顏色編碼中。返回代表繪圖的 matplotlib.axes.Axes。示例代碼如下：

from communities.algorithms import louvain_method from communities.visualization import draw_communitiesadj_matrix = [...] communities, frames = louvain_method(adj_matrix)draw_communities(adj_matrix, communities)

可視化圖如下：

Louvain 算法的動(dòng)圖展示

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)用可以實(shí)現(xiàn)動(dòng)圖展示，其中每個(gè)節(jié)點(diǎn)的顏色代表其所屬的社區(qū)，并且同一社區(qū)中的節(jié)點(diǎn)聚類結(jié)合在一起。

示例代碼如下：

from communities.algorithms import louvain_method from communities.visualization import louvain_animationadj_matrix = [...] communities,?frames?=?louvain_method(adj_matrix)louvain_animation(adj_matrix, frames)

動(dòng)圖展示如下：

參考鏈接：

https://www.codenong.com/cs105912940/

https://www.reddit.com/r/MachineLearning/comments/lozys9/p_i_made_communities_a_library_of_clustering/

推薦閱讀

誤執(zhí)行了rm -fr /*之后，除了跑路還能怎么辦？！

程序員必備58個(gè)網(wǎng)站匯總

大幅提高生產(chǎn)力：你需要了解的十大Jupyter Lab插件

總結(jié)

以上是生活随笔為你收集整理的这个Python库助你发现网络图的社区结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。