由此衍生出來的社區(qū)發(fā)現(xiàn)(community detection)算法用來發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu),這類算法包括Louvain 算法、Girvan-Newman 算法以及 Bron-Kerbosch 算法等。
最近,在 GitHub 上發(fā)現(xiàn)了一個可以發(fā)現(xiàn)圖中社區(qū)結(jié)構(gòu)的 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)網(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
Bron-Kerbosch 算法實現(xiàn)用于最大團檢測(maximal clique detection)。圖中的最大團是形成一個完整圖的節(jié)點子集,如果向該子集中添加其他節(jié)點,則它將不再完整。將最大團視為社區(qū)是合理的,因為團是圖中連接最緊密的節(jié)點群。因為一個節(jié)點可以是多個社區(qū)的成員,所以該算法有時會識別重疊的社區(qū)。示例代碼如下:
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/
審核編輯 :李倩
-
算法
+關(guān)注
關(guān)注
23文章
4580瀏覽量
92362 -
可視化
+關(guān)注
關(guān)注
1文章
1154瀏覽量
20823 -
python
+關(guān)注
關(guān)注
54文章
4759瀏覽量
84299
原文標題:發(fā)現(xiàn)一個寶藏 Python 庫,玩社區(qū)發(fā)現(xiàn)算法的不能錯過!
文章出處:【微信號:AndroidPush,微信公眾號:Android編程精選】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
評論