使用 Python/NetworkX 进行图形数据科学

已发表: 2022-03-11

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

我们经常使用表格来概括地表示信息。 但是图使用了一种专门的数据结构：一个节点代表一个元素，而不是一个表格行。 一条边连接两个节点以指示它们的关系。

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

左边是一个蛋白质相互作用图，上面有许多大小和颜色不同的点，以及它们之间的不同颜色的线。大多数点（节点）形成一个大的中央集群，但有些点仅在边缘成对、三胞胎或四胞胎连接，与主集群断开连接。右侧是 Twitter 交互图，其中节点为亚像素大小，大致分为三组：由小污点和大部分灰色的小点组成的轻云；以及围绕前两组的外部灰色模糊环之前的白色缓冲区。
左图来源：TITZ、Bjorn 等人。 “梅毒螺旋体的二元蛋白质相互作用组……” PLoS One, 3, no. 5（2008 年）。

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

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

Python中的“图论”图入门

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

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

使用 NetworkX 创建新图很简单：

 import networkx as nx G = nx.Graph()

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

如何将节点添加到图形

我们可以通过将Graph()的返回值与.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

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

如何将边添加到图形

与节点技术类似，我们可以使用.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}

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

如何从图（和加权图）生成图像

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

只需快速调用nx.draw(G) ：

用黑线连接它们的六个红点。四个形成一个四边形，其中一个角连接到其余两个。

让我们通过调用nx.draw()使较重的边缘相应地变粗：

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

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

与上一张图像类似，但点位置略有偏移，两条线突出（一条粗三倍，另一条粗五倍）。

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

使用电影《星球大战：第四集》中的数据进行图形数据科学

为了更容易解释和理解我们的结果，我们将使用这个数据集。 节点代表重要角色，而边缘（此处未加权）表示场景中的共同出现。

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

首先，我们将使用nx.draw(G_starWars, with_labels = True)可视化数据：

一个更繁忙的图表，有 19 个蓝点（每个都标有一个大写的字符名称），其中许多蓝点之间的线条均匀粗线。

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

Python NetworkX 可视化布局

为什么每个节点都位于上图中的位置？

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

NetworkX 有其他布局，它们使用不同的标准来定位节点，例如circular_layout ：

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

结果：

在节点和边的存在方面完全相同的图，但蓝点形成一个圆圈。 （注意：并非椭圆中的每一对相邻点都共享一条边。）

这种布局是中性的，因为节点的位置不取决于其重要性——所有节点都被平等地表示。 （圆形布局还可以帮助可视化单独的连接组件——在任何两个节点之间都有路径的子图——但在这里，整个图是一个大的连接组件。）

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

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

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

 nx.draw_kamada_kawai(G_starWars, with_labels = True)

这会产生这种形状：

又是同一张图。它看起来更像第一个，但蓝点分布更均匀，重叠边缘更少。

在没有任何特殊干预的情况下，该算法将主要角色（如卢克、莱娅和 C-3PO）置于中心，将不太突出的角色（如卡米和多多纳将军）置于边缘。

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

节点分析：Degree 和 PageRank

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

一个节点的一个基本指标是它的度数：它有多少条边。 星球大战角色节点的程度衡量他们与多少其他角色共享场景。

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

作为一个整体，度数没有考虑到各个边缘的细节。 给定的边是连接到其他孤立的节点还是连接到与整个网络连接的节点？ 谷歌的 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 有很多联系，但其中很多都带有不重要的角色。

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

社区检测算法

在分析网络时，分离社区可能很重要：彼此高度连接但与社区外节点连接最少的节点组。

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

最著名的之一是标签传播。 在其中，每个节点都以一个唯一的标签开始，在一个社区中。 节点的标签根据相邻节点的大部分标签进行迭代更新。

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

使用 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 中使用图数据科学的智能洞察

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

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

图数据科学推荐读物

社区检测算法
赵洋、雷内·阿尔格斯海默和克劳迪奥·泰松。 “人工网络社区检测算法的比较分析。” 科学报告，6，没有。 30750 (2016)。

图深度学习
托马斯·基普夫。 “图卷积网络”。 2016 年 9 月 30 日。

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

科恩，埃利尔。 “PyData 特拉维夫聚会：Node2vec。” YouTube。 2018 年 11 月 22 日。视频，21:09。 https://www.youtube.com/watch?v=828rZgV9t1g。