Sec Hotspot 首页  排行榜  收藏本站  技术博客  RSS
统计信息
已收录文章数量:18742 篇
已收录公众号数量:91 个
本站文章为爬虫采集,如有侵权请告知
已收录微信公众号
阿里云先知 网安寻路人 网信中国 区块链大本营 白说区块链 区块链投资家 区块链官微 区块链铅笔Blockchain HACK学习呀 二道情报贩子 合天智汇 小白帽学习之路 小米安全中心 弥天安全实验室 SAINTSEC SecPulse安全脉搏 TideSec安全团队 360安全卫士 游侠安全网 计算机与网络安全 安全祖师爷 安全学习那些事 腾讯安全联合实验室 黑客技术与网络安全 安全圈 腾讯御见威胁情报中心 Python开发者 Python之禅 编程派 Python那些事 Python程序员 安全威胁情报 吾爱破解论坛 行长叠报 安在 i春秋 嘶吼专业版 E安全 MottoIN 网信防务 网安杂谈 数说安全 互联网安全内参 漏洞战争 安全分析与研究 邑安全 ChaMd5安全团队 天融信阿尔法实验室 安全牛 SecWiki 安全学术圈 信安之路 漏洞感知 浅黑科技 Secquan圈子社区 奇安信集团 奇安信 CERT 国舜股份 雷神众测 盘古实验室 美团安全应急响应中心 瓜子安全应急响应中心 顺丰安全应急响应中心 蚂蚁金服安全响应中心 携程安全应急响应中心 滴滴安全应急响应中心 字节跳动安全中心 百度安全应急响应中心 腾讯安全应急响应中心 网易安全应急响应中心 OPPO安全应急响应中心 京东安全应急响应中心 Bypass CNNVD安全动态 安恒应急响应中心 天融信每日安全简报 奇安信威胁情报中心 看雪学院 黑白之道 水滴安全实验室 安全客 木星安全实验室 云鼎实验室 绿盟科技安全预警 白帽汇 深信服千里目安全实验室 腾讯玄武实验室 长亭安全课堂 FreeBuf 绿盟科技 nmask
熟知社区发现算法,你不能错过这个 Python 库
本文来自公众号:Python那些事   2021.02.23 08:17:41


(点击上方快速关注并设置为星标,一起学Python)

机器之心报道

编辑:杜伟、陈萍


熟知社区发现算法,你不能错过这个 Python 库。它涵盖 Louvain 算法、Girvan-Newman 算法等多种社区发现算法,还具有可视化功能。

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

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

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


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

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

  • Louvain 算法

  • Girvan-Newman 算法

  • 层次聚类

  • 谱聚类

  • Bron-Kerbosch 算法


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


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

$ pip install communities

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


算法详解

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)

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)

层次聚类

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")

谱聚类

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

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

示例代码如下:

from communities.algorithms import spectral_clustering
adj_matrix = [...]communities = spectral_clustering(adj_matrix, k=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_methodfrom 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 算法在图中的应用可以实现动图展示,其中每个节点的颜色代表其所属的社区,并且同一社区中的节点聚类结合在一起。

示例代码如下:

from communities.algorithms import louvain_methodfrom 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/

(完)


看完本文有收获?请转发分享给更多人
关注「P ython那些事」,做全栈开发工程师
点「在看」的人都变好看了哦