Python NetworkX图形数据科学使用指南(图论)

2021年11月30日00:16:16 发表评论 746 次浏览

数据以前所未有的方式淹没了我们——我们如何希望对其进行分析?图形(网络,而不是条形图)提供了一种优雅的方法。了解如何开始使用 Python NetworkX 库来描述、可视化和分析“图论”数据集,包括详细的Python NetworkX使用示例

Python NetworkX图形数据科学使用指南(图论)
Python NetworkX用法指南

我们被数据淹没了。不断扩展的数据库和电子表格充满了隐藏的业务洞察力。当数据如此之多时,我们如何分析数据并得出结论?图形(网络,而不是条形图)提供了一种优雅的方法。

我们经常使用表格来概括地表示信息。但是图使用了一种特殊的数据结构:一个节点代表一个元素,而不是一个表格行。一个边缘连接两个节点来表示他们的关系。

这种图数据结构使我们能够从独特的角度观察数据,这就是为什么图数据科学被用于从分子生物学到社会科学的各个领域:

Python NetworkX图形数据科学使用指南(图论)
左图来源:TITZ、Björn 等。“梅毒螺旋体的二元蛋白质相互作用组……” PLoS One, 3, no. 5 (2008)。

右图来源:ALBANESE、Federico 等。“在 Twitter 上使用文本挖掘和图形机器学习预测移动的个人。” (2020 年 8 月 24 日):arXiv:2008.10749 [cs.SI]

那么开发人员如何利用图数据科学呢?让我们转向最常用的数据科学编程语言:Python。

Python NetworkX用法指南:图论入门

Python 开发人员可以使用多个图形数据库,例如 NetworkX、igraph、SNAP 和图形工具。除了优点和缺点之外,它们在处理和处理 Python 图形数据结构方面具有非常相似的接口。

我们将使用流行的NetworkX库。它易于安装和使用,并支持我们将使用的社区检测算法。

使用 NetworkX 创建新图很简单:

import networkx as nx
G = nx.Graph()

G还不是一个图,没有节点和边。

如何向图中添加节点

Python如何使用NetworkX?我们可以通过链接Graph()with .add_node()(或.add_nodes_from()列表中的多个节点)的返回值来向网络添加一个节点。我们还可以通过将字典作为参数传递给节点来添加任意特征或属性,正如我们用node 4和 所示node 5

G.add_node("node 1")
G.add_nodes_from(["node 2", "node 3"])
G.add_nodes_from([("node 4", {"abc": 123}), ("node 5", {"abc": 0})])
print(G.nodes)
print(G.nodes["node 4"]["abc"]) # accessed like a dictionary

这将输出:

['node 1', 'node 2', 'node 3', 'node 4', 'node 5']
123

但是节点之间没有边,它们是孤立的,数据集并不比一个简单的表好。

如何向图中添加边

Python NetworkX使用示例:与节点技术类似,我们可以使用.add_edge()两个节点的名称作为参数(或.add_edges_from()用于列表中的多个边),并且可以选择包含属性字典:

G.add_edge("node 1", "node 2")
G.add_edge("node 1", "node 6")
G.add_edges_from([("node 1", "node 3"), 
                  ("node 3", "node 4")])
G.add_edges_from([("node 1", "node 5", {"weight" : 3}), 
                  ("node 2", "node 4", {"weight" : 5})])

NetworkX 库支持这样的图,其中每条边都可以有一个权重。例如,在节点是用户而边是交互的社交网络图中,权重可以表示给定用户对之间发生了多少交互——一个高度相关的指标。

NetworkX 在使用 时列出了所有边G.edges,但不包括它们的属性。如果我们想要边属性,我们可以使用G[node_name]来获取连接到节点的所有内容或G[node_name][connected_node_name]获取特定边的属性:

print(G.nodes)
print(G.edges)
print(G["node 1"])
print(G["node 1"]["node 5"])

这将输出:

['node 1', 'node 2', 'node 3', 'node 4', 'node 5', 'node 6']
[('node 1', 'node 2'), ('node 1', 'node 6'), ('node 1', 'node 3'), ('node 1', 'node 5'), ('node 2', 'node 4'), ('node 3', 'node 4')]
{'node 2': {}, 'node 6': {}, 'node 3': {}, 'node 5': {'weight': 3}}
{'weight': 3}

但是以这种方式阅读我们的第一张图是不切实际的。值得庆幸的是,有一个更好的代表。

Python NetworkX用法指南:如何从图形(和加权图形)生成图像

可视化图形是必不可少的:它可以让我们快速而清晰地看到节点和网络结构之间的关系。

nx.draw(G)只需快速致电:

Python NetworkX图形数据科学使用指南(图论)

让我们通过我们的nx.draw()调用使更重的边缘相应地更厚:

weights = [1 if G[u][v] == {} else G[u][v]['weight'] for u,v in G.edges()]
nx.draw(G, width=weights)

我们为失重边缘提供了默认厚度,如结果所示:

Python NetworkX图形数据科学使用指南(图论)

我们的方法和图算法将变得更加复杂,因此下一步是使用更知名的数据集。

使用电影《星球大战:第四集》中的数据绘制数据科学图

为了更容易解释和理解我们的结果,我们将使用这个数据集。节点代表重要人物,边(此处未加权)表示场景中的共同出现。

注意:数据集来自 Gabasova, E. (2016)。星球大战社交网络。DOI:https : //doi.org/10.5281/zenodo.1411479

Python如何使用NetworkX?首先,我们将使用以下方法可视化数据nx.draw(G_starWars, with_labels = True)

Python NetworkX图形数据科学使用指南(图论)

通常一起出现的角色,如 R2-D2 和 C-3PO,看起来紧密相连。相比之下,我们可以看到达斯维达并没有与欧文分享场景。

Python NetworkX 可视化布局

为什么每个节点都位于它在上图中的位置?

这是默认spring_layout算法的结果。它模拟弹簧的力,吸引连接的节点并排斥断开的节点。这有助于突出连接良好的节点,这些节点最终位于中心。

Python NetworkX使用示例:NetworkX 有其他布局使用不同的标准来定位节点,例如circular_layout

pos = nx.circular_layout(G_starWars)
nx.draw(G_starWars, pos=pos, with_labels = True)

结果:

Python NetworkX图形数据科学使用指南(图论)

这种布局是中性的,因为节点的位置不依赖于它的重要性——所有节点都被平等地表示。(圆形布局还可以帮助可视化单独的连接组件——在任意两个节点之间具有路径的子图——但在这里,整个图是一个大的连接组件。)

我们看到的两种布局都有一定程度的视觉混乱,因为边缘可以自由地与其他边缘交叉。但是 Kamada-Kawai 是另一种类似力导向的算法spring_layout,它定位节点以最小化系统的能量。

这减少了边缘交叉,但要付出代价:它比其他布局慢,因此不强烈推荐用于具有许多节点的图形。

这个有一个专门的绘图功能:

nx.draw_kamada_kawai(G_starWars, with_labels = True)

这会产生这种形状:

Python NetworkX图形数据科学使用指南(图论)

在没有任何特殊干预的情况下,该算法将主要角色(如卢克、莱娅和 C-3PO)置于中心,将不太显眼的角色(如卡米和多多娜将军)置于边界处。

可视化具有特定布局的图形可以为我们提供一些有趣的定性结果。尽管如此,定量结果是任何数据科学分析的重要组成部分,因此我们需要定义一些指标。

节点分析:度和PageRank

Python NetworkX用法指南:现在我们可以清楚地可视化我们的网络,我们可能会对表征节点感兴趣。有多个指标描述了节点的特征,在我们的示例中,描述了字符的特征。

节点的一个基本度量是它的度数:它有多少条边。度的星球大战他们有多少其他角色共享的场景与人物的节点的措施。

degree()函数可以计算一个字符或整个网络的度数:

print(G_starWars.degree["LUKE"])
print(G_starWars.degree)

两个命令的输出:

15
[('R2-D2', 9), ('CHEWBACCA', 6), ('C-3PO', 10), ('LUKE', 15), ('DARTH VADER', 4), ('CAMIE', 2), ('BIGGS', 8), ('LEIA', 12), ('BERU', 5), ('OWEN', 4), ('OBI-WAN', 7), ('MOTTI', 3), ('TARKIN', 3), ('HAN', 6), ('DODONNA', 3), ('GOLD LEADER', 5), ('WEDGE', 5), ('RED LEADER', 7), ('RED TEN', 2)]

可以使用一行代码完成根据程度从高到低对节点进行排序:

print(sorted(G_starWars.degree, key=lambda x: x[1], reverse=True))

输出:

[('LUKE', 15), ('LEIA', 12), ('C-3PO', 10), ('R2-D2', 9), ('BIGGS', 8), ('OBI-WAN', 7), ('RED LEADER', 7), ('CHEWBACCA', 6), ('HAN', 6), ('BERU', 5), ('GOLD LEADER', 5), ('WEDGE', 5), ('DARTH VADER', 4), ('OWEN', 4), ('MOTTI', 3), ('TARKIN', 3), ('DODONNA', 3), ('CAMIE', 2), ('RED TEN', 2)]

只是一个总数,度数不考虑单个边缘的细节。给定的边是连接到其他孤立的节点还是连接到与整个网络连接的节点?Google 的 PageRank 算法会汇总此信息以衡量节点在网络中的“重要性”。

PageRank 指标可以解释为代理从一个节点随机移动到另一个节点。连接更好的节点有更多的路径通过它们,所以代理会更频繁地访问它们。

这样的节点会有更高的 PageRank,我们可以用 NetworkX 库来计算:

pageranks = nx.pagerank(G_starWars) # A dictionary
print(pageranks["LUKE"])
print(sorted(pageranks, key=lambda x: x[1], reverse=True))

这将打印卢克的等级和我们按等级排序的字符:

0.12100659993223405
['OWEN', 'LUKE', 'MOTTI', 'DODONNA', 'GOLD LEADER', 'BIGGS', 'CHEWBACCA', 'LEIA', 'BERU', 'WEDGE', 'RED LEADER', 'RED TEN', 'OBI-WAN', 'DARTH VADER', 'CAMIE', 'TARKIN', 'HAN', 'R2-D2', 'C-3PO']

欧文是PageRank最高的角色,超过了最高等级的卢克。分析:虽然欧文不是与其他角色分享场景最多的角色,但他是一个与卢克本人、R2-D2、C-3PO等许多重要角色分享场景的角色。

相比之下,C-3PO 是排名第三的角色,也是 PageRank 最低的角色。尽管 C-3PO 有很多联系,但其中很多都是无关紧要的角色。

要点:使用多个指标可以更深入地了解图形节点的不同特征。

社区检测算法

Python如何使用NetworkX?在分析网络时,分离社区可能很重要:节点组彼此高度连接,但与社区外的节点连接最少。

对此有多种算法。它们中的大多数都可以在无监督机器学习算法中找到,因为它们为节点分配了一个标签,而无需之前对它们进行标记。

最著名的方法之一是标签传播。在其中,每个节点都以一个唯一的标签开始,在一个社区中。根据相邻节点的大多数标签迭代更新节点的标签。

标签在网络中扩散,直到所有节点与其大多数邻居共享一个标签。彼此紧密连接的节点组最终具有相同的标签。

Python NetworkX使用示例:使用 NetworkX 库,运行这个算法只需要三行 Python 代码:

from networkx.algorithms.community.label_propagation import label_propagation_communities

communities = label_propagation_communities(G_starWars)
print([community for community in communities])

输出:

[{'R2-D2', 'CAMIE', 'RED TEN', 'RED LEADER', 'OBI-WAN', 'DODONNA', 'LEIA', 'WEDGE', 'HAN', 'OWEN', 'CHEWBACCA', 'GOLD LEADER', 'LUKE', 'BIGGS', 'C-3PO', 'BERU'}, {'DARTH VADER', 'TARKIN', 'MOTTI'}]

在这个集合列表中,每个集合代表一个社区。熟悉这部电影的读者会注意到,该算法设法完美地将“好人”与“坏人”区分开来,在不使用任何真实(社区)标签或元数据的情况下有意义地区分了角色。

Python NetworkX用法指南总结

我们已经看到,开始使用图数据科学工具比听起来要简单得多。一旦我们使用 Python 中的 NetworkX 库将数据表示为图形,几行短代码就可以说明问题。我们可以可视化我们的数据集,测量和比较节点特征,并通过社区检测算法合理地集群节点。

拥有使用 Python 从网络中提取结论和见解的技能使开发人员能够与数据科学服务管道中常见的工具和方法集成。从搜索引擎到航班调度再到电气工程,这些方法可以轻松应用于广泛的环境。

社区检测算法
Zhao Yang、René Algesheimer 和 Claudio Tessone。“人工网络上社区检测算法的比较分析。” 科学报告,6,没有。30750 (2016)。

图深度学习
Thomas Kipf。“图卷积网络。” 2016 年 9 月 30 日。

图数据科学的应用
Albanese、Federico、Leandro Lombardi、Esteban Feuerstein 和 Pablo Balenzuela。“在 Twitter 上使用文本挖掘和图形机器学习预测移动的个人。” (2020 年 8 月 24 日):arXiv:2008.10749 [cs.SI]。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: