介绍#

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

大多数networkx API都是由以图形对象为参数的函数提供的。图形对象的方法仅限于基本的操作和报告。这提供了代码和文档的模块化。它还使新来者更容易分阶段了解该软件包。每个模块的源代码都是为了易于阅读,而阅读这个python代码实际上是了解更多网络算法的好方法,但是我们已经花了很多精力使文档足够友好。如果您有任何建议或问题,请通过加入 NetworkX Google group .

类的命名使用 CamelCase (每个单词开头的大写字母)。函数、方法和变量名是 lower_case_underscore (小写,下划线表示单词之间的空格)。

NETWorkX基础#

启动python后,使用导入networkx模块(推荐的方法)

>>> import networkx as nx

为了避免重复,在文档中,我们假设networkx是以这种方式导入的。

如果导入networkx失败,则意味着python找不到已安装的模块。检查您的安装和 PYTHONPATH .

以下基本图形类型作为python类提供:

Graph

此类实现一个无向图。它忽略两个节点之间的多个边。它允许节点和自身之间的自循环边。

DiGraph

有向图,即有向边的图。提供对有向图(图的子类)通用的操作。

MultiGraph

一个灵活的图形类,允许节点对之间有多个无向边。额外的灵活性会导致性能下降,尽管通常不显著。

MultiDiGraph

多图表的定向版本。

使用创建类似于空图形的对象

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

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

图形内部数据结构基于邻接列表表示,并使用python实现 dictionary 数据结构。图形邻接结构被实现为一个python字典;外部字典由节点键控到值,这些值本身就是字典,由相邻节点键控到与该边缘关联的边缘属性。这种“dict of dicts”结构允许快速添加、删除和查找大型图中的节点和邻居。通过类定义中的方法(编程接口“api”)直接访问底层数据结构。另一方面,所有函数仅通过这些API方法而不是直接作用于数据结构来操作类似图形的对象。这种设计允许用实现相同方法的替代数据结构替换基于dicts的“dicts of dicts”数据结构。

#

使用networkx时要做的第一个选择是使用什么类型的图形对象。图(网络)是节点的集合,以及作为节点对的边的集合。属性通常与节点和/或边关联。根据网络的两个主要属性,networkx图形对象具有不同的风格:

  • 定向:边缘 定向的 ?边缘对\((u,v)\)的顺序重要吗?有向图由类名中的“di”前缀指定,例如 DiGraph() . 我们之所以有这样的区别,是因为对于有向图,许多经典的图属性都有不同的定义。

  • 多边缘:每对节点之间允许多个边缘吗?正如您可能想象的那样,多个边缘需要不同的数据结构,尽管聪明的用户可以设计边缘数据属性来支持此功能。我们使用前缀“multi”为这类图形提供了标准的数据结构和接口,例如, MultiGraph() .

基本图形类命名为: GraphDiGraphMultiGraphMultiDiGraph

节点和边#

在指定图形时,您必须做的下一个选择是使用什么类型的节点和边。

如果您只关心网络的拓扑结构,那么使用整数或字符串作为节点是有意义的,您不必担心边缘数据。如果您已经有了一个数据结构来描述节点,那么您可以简单地使用该结构作为节点,只要它是 hashable . 如果它不可哈希,则可以使用唯一标识符来表示节点并将数据指定为 node attribute .

边缘通常有与其相关联的数据。任意数据可以作为 edge attribute . 如果数据是数字,目的是表示 加权的 然后对属性使用“weight”关键字。一些图算法,例如dijkstra的最短路径算法,默认情况下使用这个属性名来获取每个边的权重。

添加边时,可以使用关键字/值对将属性指定给边。可以使用任何关键字命名属性,然后使用该属性关键字查询边缘数据。

一旦你决定了如何编码节点和边,以及你是否有一个无向/有向图有或没有多边,你就可以建立你的网络了。

图形创建#

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

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

  • 从预先存在的(通常是文件)源导入数据。

  • 显式添加边和节点。

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

>>> import networkx as nx
>>> G = nx.Graph()
>>> G.add_edge(1, 2)  # default edge data=1
>>> G.add_edge(2, 3, weight=0.9)  # specify edge data

边缘属性可以是任何内容:

>>> import math
>>> G.add_edge('y', 'x', function=math.cos)
>>> G.add_node(math.cos)  # any hashable can be a node

一次可以添加多个边:

>>> 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、edge list文本文件)导入网络数据,请参见 reading and writing graphs 分包。

图形报告#

类视图提供节点、邻居、边和度的基本报告。这些视图提供对属性的迭代,以及成员查询和数据属性查找。视图引用图形数据结构,因此对图形的更改反映在视图中。这类似于Python3中的字典视图。如果要在迭代时更改图形,则需要使用例如 for e in list(G.edges): . 视图提供了类似集合的操作,例如联合和交集,以及类似dict的数据属性查找和迭代,使用 G.edges[u, v]['color']for e, datadict in G.edges.items(): . 方法 G.edges.items()G.edges.values() 从python dicts中熟悉。此外 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 group 或是吉特鲁布 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包进行绘制。交互式图形用户界面是可能的,但没有提供。绘图工具在模块中提供 drawing .

基本绘图功能基本上使用字典提供的位置将节点放置在散点图上,或者使用布局功能计算位置。边缘是这些点之间的线。

>>> import matplotlib.pyplot as plt
>>> G = nx.cubical_graph()
>>> subax1 = plt.subplot(121)
>>> nx.draw(G)   # default spring_layout
>>> subax2 = plt.subplot(122)
>>> nx.draw(G, pos=nx.circular_layout(G), node_color='r', edge_color='b')

(png, hires.png, pdf)

../_images/introduction-7.png

examples 更多的想法。

数据结构#

NetworkX使用“字典字典字典”作为基本的网络数据结构。这允许快速查找大型稀疏网络的合理存储。关键是节点,所以 G[u] 返回由边缘属性字典的邻居键控的相邻字典。dict-like对象提供了相邻数据结构的视图。 G.adj 例如 for node, nbrsdict in G.adj.items(): . 表达式 G[u][v] 返回边缘属性字典本身。列表字典也是可能的,但不允许快速边缘检测,也不方便存储边缘数据。

dict的优点dicts的数据结构:

  • 使用两个字典查找查找查找边并删除边。

  • 更喜欢“列表”,因为使用稀疏存储进行快速查找。

  • 更喜欢“设置”,因为数据可以附加到边缘。

  • 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': {}}}

对于每个基础图类,数据结构都会稍微变形。对于有向图,提供了两个有向图结构的有向图,一个用于后继图。 (G.succ )一个给前任 (G.pred )对于多图表/多图表,我们使用的是dict的dict或dict的dict 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'])
300
>>> print(G.edges[1, 2]['color'])
red

脚注

1

“一路往下都是字典。”