首页 文章详情

发现一个宝藏 Python 库,玩社区发现算法的不能错过!

日常学python | 27 2022-11-28 00:34 0 0 0
UniSMS (合一短信)

来源丨任识算法

编辑丨Python数据科学


推荐阅读: 终于来了,【第三期】 彭涛Python 爬虫特训营!!

网络是由一些紧密相连的节点组成的,并且根据不同节点之间连接的紧密程度,网络也可视为由不同簇组成。簇内的节点之间有着更为紧密的连接,不同簇之间的连接则相对稀疏。这种簇被称为网络中的社区结构(community structure)。

由此衍生出来的社区发现(community detection)算法用来发现网络中的社区结构,这类算法包括 Louvain 算法、Girvan-Newman 算法以及 Bron-Kerbosch 算法等。

最近,在 GitHub 上发现了一个可以发现图中社区结构的 Python 库 communities,该库由软件工程师 Jonathan Shobrook 创建。

6fbbe371ae5b54b35be7d91df7d822d5.webp

项目地址:https://github.com/shobrook/communities

首先,该库可以实现以下几种社区发现算法:

  • Louvain 算法
  • Girvan-Newman 算法
  • 层次聚类
  • 谱聚类
  • Bron-Kerbosch 算法

其次,用户还可以使用 communities 库来可视化上述几种算法,下图为空手道俱乐部(Zachary's karate club)网络中 Louvain 算法的可视化结果:

5dba8eb5945206ced1d2edff0e3dafa2.webp图片

该库的安装方法也非常简单,可采用 pip 的方式安装 communities,代码如下:

      import numpy as np

from communities.algorithms import louvain_method

adj_matrix = np.array([[011000],
                       [101000], 
                       [110100], 
                       [001011],   
                       [000101],
                       [000110]])

communities, _ = louvain_method(adj_matrix)

>> communities
[{012}, {345}]

对于这个 Python 库,很多网友给予了高度评价,表示会去尝试。

a74f2dafd19faa910a687ea4d9b8bafd.webp图片


算法详解

1、Louvain 算法

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

该算法来源于文章《Fast unfolding of communities in large networks》,简称为 Louvian。

作为一种基于模块度(Modularity)的社区发现算法,Louvain 算法在效率和效果上都表现比较好,并且能够发现层次性的社区结构,其优化的目标是最大化整个图属性结构(社区网络)的模块度。

Louvain 算法对最大化图模块性的社区进行贪婪搜索。如果一个图具有高密度的群体内边缘和低密度的群体间边缘,则称之为模图。

示例代码如下:

      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 算法迭代删除边以创建更多连接的组件。每个组件都被视为一个 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
    

层次聚类实现了一种自底向上、分层的聚类算法。每个节点从自己 的社区开始,然后,随着层次结构的建立,最相似的社区被合并。社区会一直被合并,直到在模块度方面没有进一步的进展。

示例代码如下:

      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
    

这种类型的算法假定邻接矩阵的特征值包含有关社区结构的信息。

示例代码如下:

      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 算法实现用于最大团检测(maximal clique detection)。图中的最大团是形成一个完整图的节点子集,如果向该子集中添加其他节点,则它将不再完整。将最大团视为社区是合理的,因为团是图中连接最紧密的节点群。因为一个节点可以是多个社区的成员,所以该算法有时会识别重叠的社区。 示例代码如下:
      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),将节点分组至它们所属的社区和颜色编码中。返回代表绘图的 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)

可视化图如下:

3a6c9e5c9b490b62b110de74f39206cd.webp

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 算法在图中的应用可以实现动图展示,其中每个节点的颜色代表其所属的社区,并且同一社区中的节点聚类结合在一起。

示例代码如下:

      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)

动图展示如下:

a6663a1f54a75554309c758ed82baf28.webp图片

参考链接:

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

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

···  END  ···

我们爬虫第三期来了,加入我们,学更实用,更值钱的 Python 技术!


              

                


e03dad71471ac88d2e8796f78b925b07.webp


从0到1系统掌握Python 技术(入门进阶)

2个企业实战项目,4大常用工具

掌握24种反爬策略手段,成为真正爬虫高手

能抓取市面上90%的网站

掌握主流爬虫技术,就业找工作 真正全方位帮助大家从0到1,从 Python 入门到进阶,转行找爬虫工作。

f0515fcb08657859cbde75ed165c5873.webp
good-icon 0
favorite-icon 0
收藏
回复数量: 0
    暂无评论~~
    Ctrl+Enter