引言#

NetworkX 的结构可以通过其源代码的组织方式看出。 该包提供了用于图对象的类、用于创建标准图的生成器、用于读取现有数据集的 IO 例程、用于分析结果网络的算法以及一些基本的绘图工具。

NetworkX API 大部分由函数提供，这些函数以图对象作为参数。图对象的方法仅限于基本操作和报告。这提供了代码和文档的模块化。 这也使得新手可以逐步了解该包的功能。 每个模块的源代码都很容易阅读，通过阅读这些 Python 代码是了解网络算法的好方法，但我们也花了大量精力使文档足够详尽且友好。 如果您有建议或问题，请通过加入 NetworkX Google 小组联系我们。

类名采用 CamelCase（每个单词的首字母大写）命名。 函数、方法和变量名采用 lower_case_underscore（小写并用下划线表示单词间的空格）命名。

NetworkX 基础#

启动 Python 后，以推荐的方式导入 networkx 模块：

import networkx as nx

为了避免重复，在文档中我们假设 NetworkX 已经以这种方式导入。

如果导入 networkx 失败，说明 Python 找不到已安装的模块。检查您的安装和 PYTHONPATH。

以下基本图类型作为 Python 类提供：

Graph

  • 该类实现了一个无向图。它忽略两个节点之间的多条边，但允许节点自身之间的自环边。

DiGraph

  • 有向图，即带有方向边的图。提供了有向图常用的操作（是 Graph 的子类）。

MultiGraph

  • 一个灵活的图类，允许节点对之间存在多条无向边。这种额外的灵活性会导致一些性能下降，但通常不显著。

MultiDiGraph

  • MultiGraph 的有向版本。

空的图对象可以通过以下方式创建：

G = nx.Graph()
G = nx.DiGraph()
G = nx.MultiGraph()
G = nx.MultiDiGraph()

所有图类都允许任何 hashable 对象作为节点。可哈希对象包括字符串、元组、整数等。任意边属性如权重和标签都可以与边关联。

图的内部数据结构基于邻接列表表示，使用 Python dictionary 数据结构实现。 图的邻接结构实现为一个以节点为键，值为以邻居节点为键的字典的字典。与该边相关的边属性则与邻居节点相关联。这种“字典的字典”结构允许在大图中快速添加、删除和查找节点及其邻居。底层数据结构直接由类定义中的方法（编程接口“API”）访问。而所有函数则仅通过这些 API 方法操作图对象，而不是直接作用于数据结构。这种设计允许将基于“字典的字典”的数据结构替换为实现相同方法的替代数据结构。

图#

使用 NetworkX 时首先要做的选择是使用哪种类型的图对象。图（网络）是一组节点以及一组节点对组成的边。属性通常与节点和/或边相关联。NetworkX 图对象根据网络的两个主要属性有不同的类型：

  • 有向：边是否有向？边对 (u, v) 的顺序是否重要？有向图通过类名中的“Di”前缀指定，例如 DiGraph。我们做出这种区分是因为许多经典的图属性在有向图中定义不同。

  • 多重边：每对节点之间是否允许多条边？可以想象，多条边需要不同的数据结构，尽管聪明的用户可以设计边数据属性来支持这种功能。我们提供了使用“Multi”前缀的标准数据结构和接口，例如 MultiGraph。

基本图类的名称分别是： Graph, DiGraph, MultiGraph 和 MultiDiGraph。

节点和边#

指定图时需要做出的下一个选择是使用哪种类型的节点和边。

如果您只关心网络的拓扑结构，那么使用整数或字符串作为节点是合理的，并且您不必担心边数据。如果您已经有一个数据结构来描述节点，只要该结构是 hashable 的，就可以直接使用。如果不可哈希，可以使用唯一标识符表示节点，并将数据分配为 node attribute。

边通常有数据与之关联。可以将任意数据作为 edge attribute 与边关联。如果数据是数值型的，并且意图表示_加权_图，则使用“weight”关键字作为属性名。某些图算法（如 Dijkstra 最短路径算法）默认使用此属性名获取每条边的权重。

可以在添加边时使用关键字/值对分配属性。您可以使用任何关键字命名您的属性，然后使用该属性关键字查询边数据。

一旦决定了如何编码节点和边，以及是否有无向/有向图及是否有多重边，就可以开始构建网络了。

图的创建#

NetworkX 图对象可以通过三种方式之一创建：

  • 图生成器——创建网络拓扑的标准算法。

  • 从现有（通常是文件）数据源导入数据。

  • 显式添加边和节点。

显式添加和删除节点/边是最容易描述的。每个图对象提供操作图的方法。例如，

G = nx.Graph()
G.add_edge(1, 2)  # 默认边数据=1
G.add_edge(2, 3, weight=0.9)  # 指定边数据

边属性可以是任何内容：

import math
G.add_edge('y', 'x', function=math.cos)
G.add_node(math.cos)  # 任何可哈希对象都可以作为节点

您可以一次添加多条边：

elist = [(1, 2), (2, 3), (1, 4), (4, 2)]
G.add_edges_from(elist)
elist = [('a', 'b', 5.0), ('b', 'c', 3.0), ('a', 'c', 1.0), ('c', 'd', 7.3)]
G.add_weighted_edges_from(elist)

更多示例请参见 教程。

一些基本的图操作如并集和交集在 operators module 文档中描述。

图生成器如 binomial_graph() 和 erdos_renyi_graph() 提供在 graph generators 子包中。

要从 GML、GraphML、边列表文本文件等格式导入网络数据，请参见 reading and writing graphs 子包。

图的报告#

类视图提供节点、邻居、边和度的基本报告。这些视图提供属性的迭代、成员查询和数据属性查找。视图引用图数据结构，因此对图的更改会反映在视图中。这类似于 Python 3 中的字典视图。如果需要在迭代时更改图，则需要使用例如 for e in list(G.edges):。视图提供类似集合的操作，例如并集和交集，以及类似字典的属性数据查找和迭代，使用 G.edges[u, v]['color'] 和 for e, datadict in G.edges.items():。方法 G.edges.items() 和 G.edges.values() 是从 Python 字典熟悉的。此外，G.edges.data() 提供特定属性迭代，例如 for e, e_color in G.edges.data('color'):。

可以通过两种方式获得边的基本图关系。可以查找节点的邻居，也可以查找边。我们开玩笑地称专注于节点/邻居的人为节点中心论者，而专注于边的人为边中心论者。NetworkX 的设计者倾向于节点中心论，并将边视为节点之间的关系。可以通过我们选择的查找表示法看到这一点，例如 G[u] 提供邻居（邻接），而边查找是 G.edges[u, v]。 大多数稀疏图的数据结构本质上是邻接表，因此符合这种观点。最终，不管以哪种方式检查图都是没有关系的。G.edges 删除了无向边的重复表示，而跨所有节点报告邻居会自然地报告两个方向。

任何比边、邻居和度更复杂的属性由函数提供。例如 nx.triangles(G, n) 给出包含节点 n 作为顶点的三角形数量。这些函数在代码和文档中归类在 algorithms 下。

算法#

NetworkX 提供了许多图算法。这些算法包括最短路径和广度优先搜索（见 traversal），聚类和同构算法等。我们还没有开发许多其他算法。如果您实现了一个可能对他人有用的图算法，请通过 NetworkX Google 小组 或 GitHub Developer Zone 通知我们。

作为示例，这里是使用 Dijkstra 算法查找最短加权路径的代码：

G = nx.Graph()
e = [('a', 'b', 0.3), ('b', 'c', 0.9), ('a', 'c', 0.5), ('c', 'd', 1.2)]
G.add_weighted_edges_from(e)
print(nx.dijkstra_path(G, 'a', 'd'))

['a', 'c', 'd']

绘图#

虽然 NetworkX 并非设计为网络绘图工具，但我们提供了一个简单的绘图包接口和一些简单的布局算法。我们通过（推荐的）pygraphviz 包或 pydot 接口连接到优秀的 Graphviz 布局工具如 dot 和 neato。 绘图可以使用外部程序或 Matplotlib Python 包完成。可以实现交互式 GUI 接口，尽管未提供。绘图工具在 drawing 模块中提供。

基本绘图函数本质上是在散点图上放置节点，使用通过字典提供的位置或通过布局函数计算的位置。这些点之间的线条即为边。

import matplotlib.pyplot as plt
G = nx.cubical_graph()
subax1 = plt.subplot(121)
nx.draw(G)   # 默认 spring_layout
subax2 = plt.subplot(122)
nx.draw(G, pos=nx.circular_layout(G), node_color='r', edge_color='b')
../_images/2adabb3b71bb636dee76d0beda69f7432c46cf0ef3acf0e15222a3168bddf64c.png

更多想法请参见 examples。

数据结构#

NetworkX 使用“字典的字典的字典”作为基本网络数据结构。这允许快速查找并为大型稀疏网络提供合理的存储。键是节点，因此 G[u] 返回一个由邻居键入的邻接字典，对应的值是边属性字典。一个邻接数据结构的视图通过类似字典的对象 G.adj 提供，例如 for node, nbrsdict in G.adj.items():。 表达式 G[u][v] 返回边属性字典本身。 也可以使用列表字典，但不会允许快速边检测，也不方便存储边数据。

字典的字典的字典数据结构的优势：

  • 通过两次字典查找找到和删除边。

  • 相较于“列表”，具有稀疏存储的快速查找功能。

  • 相较于“集合”，可以附加数据到边。

  • G[u][v] 返回边属性字典。

  • n in G 测试节点 n 是否在图 G 中。

  • for n in G: 迭代整个图。

  • for nbr in G[n]: 迭代邻居。

例如，这里是一个具有边 (A, B) 和 (B, C) 的无向图表示。

G = nx.Graph()
G.add_edge('A', 'B')
G.add_edge('B', 'C')
print(G.adj)

{'A': {'B': {}}, 'B': {'A': {}, 'C': {}}, 'C': {'B': {}}}

数据结构会针对每个基础图类稍微变形。 对于 DiGraph，提供了两个字典的字典的字典结构，一个用于后继（G.succ），一个用于前驱（G.pred）。 对于 MultiGraph/MultiDiGraph，我们使用字典的字典的字典的字典[1]，其中第三个字典以边键标识，第四个字典包含两个节点之间的边属性。

图提供两种边数据属性的接口：邻接和边。因此 G[u][v]['width'] 等同于 G.edges[u, v]['width']。

G = nx.Graph()
G.add_edge(1, 2, color='red', weight=0.84, size=300)
print(G[1][2]['size'])
print(G.edges[1, 2]['color'])

300
red

脚注

都无所谓。G.edges 删除了无向边的重复表示，而跨所有节点的邻居报告自然会报告两个方向。

任何比边、邻居和度更复杂的属性都由函数提供。例如，nx.triangles(G, n) 给出包含节点 n 作为顶点的三角形数量。这些函数在代码和文档中分组在 algorithms 术语下。

算法#

NetworkX 提供了许多图算法。这些包括最短路径和广度优先搜索（见 traversal），聚类和同构算法等。我们还没有开发许多算法。如果您实现了可能对他人有用的图算法，请通过 NetworkX Google 小组 或 GitHub Developer Zone 告诉我们。

例如，以下是使用 Dijkstra 算法找到最短加权路径的代码：

G = nx.Graph()
e = [('a', 'b', 0.3), ('b', 'c', 0.9), ('a', 'c', 0.5), ('c', 'd', 1.2)]
G.add_weighted_edges_from(e)
print(nx.dijkstra_path(G, 'a', 'd'))

['a', 'c', 'd']

绘图#

虽然 NetworkX 不是为网络绘图工具设计的，但我们提供了一个简单的绘图包接口和一些简单的布局算法。 我们通过（推荐的）pygraphviz 包或 pydot 接口与优秀的 Graphviz 布局工具（如 dot 和 neato）接口。 可以使用外部程序或 Matplotlib Python 包进行绘图。虽然不提供，但也可以实现交互式 GUI 界面。 绘图工具在 drawing 模块中提供。

基本绘图功能本质上是使用您通过字典提供的位置或通过布局函数计算的位置将节点放置在散点图上。边是这些点之间的线。

import matplotlib.pyplot as plt
G = nx.cubical_graph()
subax1 = plt.subplot(121)
nx.draw(G)   # 默认 spring_layout
subax2 = plt.subplot(122)
nx.draw(G, pos=nx.circular_layout(G), node_color='r', edge_color='b')
../_images/5e1ed269839c7756b884f98a584e2357aad260f7a264e01b4b5e1e5c36fd7549.png

有关更多想法，请参见 examples。

数据结构#

NetworkX 使用“字典的字典的字典”作为基本网络数据结构。这允许对大规模稀疏网络进行快速查找并提供合理的存储。键是节点，因此 G[u] 返回一个邻接字典，以邻居为键到边属性字典。邻接数据结构的视图通过类似字典的对象 G.adj 提供，例如 for node, nbrsdict in G.adj.items():。表达式 G[u][v] 返回边属性字典本身。也可以使用字典列表，但不允许快速边检测，也不方便存储边数据。

字典的字典的字典数据结构的优势：

  • 通过两次字典查找找到边并删除边。

  • 比“列表”更优，因为查找快且存储稀疏。

  • 比“集合”更优，因为数据可以附加到边上。

  • G[u][v] 返回边属性字典。

  • n in G 测试节点 n 是否在图 G 中。

  • for n in G: 迭代遍历图。

  • for nbr in G[n]: 迭代遍历邻居。

例如，这是一个包含边 \((A, B)\) 和 \((B, C)\) 的无向图表示：

G = nx.Graph()
G.add_edge('A', 'B')
G.add_edge('B', 'C')
print(G.adj)

{'A': {'B': {}}, 'B': {'A': {}, 'C': {}}, 'C': {'B': {}}}

数据结构根据每个基本图类稍微改变。对于 DiGraph，提供了两个字典的字典的字典结构，一个用于后继（G.succ），一个用于前驱（G.pred）。对于 MultiGraph/MultiDiGraph，我们使用字典的字典的字典的字典[1]，第三个字典以边键标识符为键，第四个字典包含两个节点之间的边属性。

图提供两种接口访问边数据属性：邻接和边。因此 G[u][v]['width'] 与 G.edges[u, v]['width'] 相同。

G = nx.Graph()
G.add_edge(1, 2, color='red', weight=0.84, size=300)
print(G[1][2]['size'])
print(G.edges[1, 2]['color'])

300
red

注释

On this page