Python NetworkX图论库基础操作与算法详解

NetworkX图结构基础

NetworkX是Python生态中用于构建和操作复杂图结构的核心库，提供了丰富的图分析算法。图作为一种数据结构，由顶点（Nodes）和边（Edges）组成，并可选包含属性。其中，顶点代表数据实体，边由两个顶点唯一确定，用以表示实体间的关系。顶点和边均可附加额外属性，以存储更详尽的信息。

在使用NetworkX创建无向图时，系统允许边连接的两个顶点相同，即支持自循环（Self-loop）；但不允许两个顶点间存在多条平行边（Parallel edges）。边和顶点均可自定义属性，这些属性以键值对（Key:Value）的形式存储，用于描述节点或边的具体特征。

图的初始化与创建

一、图的初始化与创建

在开始构建图之前，需导入NetworkX模块，通常约定使用别名nx。若图中边无方向性，则称为无向图。创建图实例后，可通过调用help(g)查看相关的帮助文档以获取使用指南。

import networkx as nx

g=nx.Graph()#创建空的无向图 g=nx.DiGraph()#创建空的有向图

顶点（Node）管理

二、顶点（Node）管理

图中的每个节点（Node）都拥有一个关键的ID属性，用于唯一标识该节点。ID可以是整数或字符串类型。除了ID外，节点还可以定义其他自定义属性。

1. 添加顶点

向图中添加顶点时，支持单次添加一个或多个顶点，但必须提供顶点的ID属性。添加完成后，调用g.nodes()可获取所有顶点的视图，返回NodeView对象；若设置data=True参数，即g.nodes(data=True)，则返回NodeDataView对象，其中包含每个顶点的ID及其他自定义属性。

g.add_node(1)
g.add_nodes_from([2,3,4])
g.nodes()
#NodeView((1, 2,3,4))

在添加顶点时，除ID外，还可同时指定自定义属性，例如名称或权重：

>>> g.add_node(1,name='n1',weight=1)
>>> g.add_node(2,name='n2',weight=1.2)

2. 查看顶点属性

通过内部属性_node可以获取图中所有顶点及其属性的信息。_node返回一个字典，其Key为顶点的ID，Value为包含其他属性的字典。

>>> g._node
{1: {'name': 'n1', 'weight': 1}, 2: {'name': 'n2', 'weight': 1.2}, 3: {}, 4: {}}
>>>g.nodes(data=True)

可以通过顶点的ID直接查看其特定属性：

>>> g.node[1]
{'name': 'n1', 'weight': 1}
>>> g.node[1]['name']
'n1 new'

利用g.nodes()并配合特定条件筛选，可以查看符合条件的顶点：

 >>> list(g.nodes(data=True))
 [(1, {'time': '5pm'}), (3, {'time': '2pm'})]

3. 删除顶点

使用remove函数可从图中删除顶点。由于ID能唯一标识顶点，通常需传递ID作为参数来执行删除操作。

g.remove_node(node_ID)
g.remove_nodes_from(nodes_list)

4. 更新顶点属性

更新顶点属性主要有两种方式：一是使用字典结构的_update函数，二是通过索引直接设置新值：

>>> g._node[1].update({'name':'n1 new'})
>>> g.node[1]['name']='n1 new'
{1: {'name': 'n1 new', 'weight': 1}, 2: {'name': 'n2', 'weight': 1.2}, 3: {}, 4: {}}

5. 删除顶点属性

使用del命令可以移除顶点的特定属性。

del g.nodes[1]['room']

6. 检查顶点存在性

判断顶点是否存在于图中，可使用n in g语法，或调用相关函数进行验证：

g.has_node(n)


边（Edge）管理

三、边（Edge）管理

边用于表示两个顶点间的关系，由这两个顶点的ID唯一确定。为表达复杂关系，通常会给边添加权重（weight）属性；为区分关系类型，也可设置关系属性。

1. 添加边

边由对应顶点的名称构成，例如顶点2和3之间的边记作e=(2,3)。通过add_edge(node1,node2)可向图添加一条边，或通过add_edges_from(list)批量添加多条边。若添加边时顶点不存在，NetworkX会自动创建相应顶点。

g.add_edge(2,3)
g.add_edges_from([(1,2),(1,3)])
g.edges()
#EdgeView([(1, 2), (1, 3), (2, 3)])

可以向边中增加属性，例如权重或关系类型：

g.add_edge(1, 2, weight=4.7, relationship='renew')

由于权重是图中非常常用且重要的属性，NetworkX内置了专门用于添加边时设置权重的函数。该函数参数为三元组，前两个字段为顶点ID（用于标识边），第三个字段为边的权重值：

g.add_weighted_edges_from([(1,2,0.125),(1,3,0.75),(2,4,1.2),(3,4,0.375)])


在添加边时，也可以一次性添加多条边，并为不同的边设置不同的属性：

g.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])

2. 查看边的属性

查看边的属性即查看边数据（data）。要查看所有边及其属性，可使用：

>>> g.edges(data=True)
EdgeDataView([(1, 2, {}), (1, 3, {}), (2, 3, {})])

查看特定边的信息有两种方式：

>>> g[1][2]
>>> g.get_edge_data(1,2)
{'weight': 0.125, 'relationship': 'renew', 'color': 'blue'}

3. 删除边

边由两个顶点的ID构成的元组表示，通过 edge=(node1,node2) 来标识边，进而从图中定位并删除该边：

g.remove_edge(edge)
g.remove_edges_from(edges_list)

4. 更新边的属性

更新边属性有两种方式：一是使用update函数，二是通过属性赋值实现：

g[1][2]['weight'] = 4.7
g.edge[1][2]['weight'] = 4
g[1][2].update({"weight": 4.7})
g.edges[1, 2].update({"weight": 4.7}) 

5. 删除边的属性

使用del命令可以删除边的特定属性。

del g[1][2]['name']

6. 检查边存在性

验证一条边是否存在于图中。

g.has_edge(1,2)

图的属性与视图

四、图的属性与视图

图的属性主要涉及相邻数据、节点和边。

1. 邻接视图（adj）

adj返回AdjacencyView视图，该视图展示了与顶点相邻的顶点及其属性。这是一个只读的字典结构，Key为顶点，Value为顶点的属性数据。

>>> g.adj[1][2]
{'weight': 0.125, 'relationship': 'renew', 'color': 'blue'}
>>> g.adj[1]
AtlasView({2: {'weight': 0.125, 'relationship': 'renew', 'color': 'blue'}, 3: {'weight': 0.75}})

2. 边视图（edges）

图的边由两个顶点唯一确定，且边具有属性，因此边由两个顶点和边的属性共同构成：

>>> g.edges
EdgeView([(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)])
>>> g.edges.data()
EdgeDataView([(1, 2, {'weight': 0.125, 'relationship': 'renew', 'color': 'blue'}), 
(1, 3, {'weight': 0.75}), 
(2, 3, {'weight': 8}), 
(2, 4, {'weight': 1.2}), 
(3, 4, {'weight': 0.375})])

EdgeView仅提供边的基本信息，可通过属性g.edges或函数g.edges()获得图的边视图。

EdgeDataView提供图的边及其属性，可通过EdgeView对象调用data()函数获得。

3. 节点视图（nodes）

图的顶点由顶点和顶点的属性构成。

>>> g.nodes
NodeView((1, 2, 3, 4))
>>> g.nodes.data()
NodeDataView({1: {'name': 'n1 new', 'weight': 1}, 2: {'name': 'n2', 'weight': 1.2}, 3: {}, 4: {}})

NodeView通过属性g.nodes或函数g.nodes()获得。

NodeDataView提供图的节点及其属性，可通过NodeView对象调用data()函数获得。

4. 度（degree）

对于无向图，顶点的度是指与该顶点相连的边的数量；对于有向图，顶点的度分为入度（指向该顶点的边）和出度（背离该顶点的边）。

通过g.degree或g.degree()可获得DegreeView对象：

图的遍历算法

五、图的遍历算法

图的遍历是指按照图中各顶点间的边，从任一顶点出发，对图中所有顶点访问且仅访问一次。根据优先顺序的不同，图遍历通常分为深度优先搜索（DFS）和广度优先搜索（BFS）。

1. 查看顶点的相邻顶点

查看顶点的相邻顶点有多种方式，以下代码均用于返回顶点1的相邻顶点，g[n]表示图g中与顶点n相邻的所有顶点：

g[n]
g.adj[n]
g.neighbors(n)

其中，g.neighbors(n)是g.adj[n]的迭代器版本。

2. 查看图的相邻关系

该函数返回顶点n及其相邻节点的信息：

>>> for n, nbrs in g.adjacency():
...   print(n)
...   print(nbrs)

3. 图的遍历实现

深度优先遍历算法：

首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的相邻顶点； 当当前顶点没有未访问过的相邻顶点时，则回到上一个顶点，继续试探别的相邻顶点，直到所有的顶点都被访问过。 深度优先遍历算法的思想是：从一个顶点出发，一条路走到底；如果此路走不通，就返回上一个顶点，继续走其他路。

广度优先遍历算法：

从顶点v出发，依次访问v的各个未访问过的相邻顶点；

分别从这些相邻顶点出发依次访问它们的相邻顶点；

广度优先遍历算法的思想是：以v为起点，按照路径的长度，由近至远，依次访问和v有路径相通且路径长度为1,2...，n的顶点。

在进行图遍历时，需要访问顶点的相邻顶点，这需要用到adjacency()函数。例如，g是一个无向图，n是顶点，nbrs是顶点n的相邻顶点，是一个字典结构：

for n,nbrs in g.adjacency(): 
  print (n, nbrs)
  for nbr,attr in nbrs.items():
    # nbr表示跟n连接的顶点，attr表示这两个点连边的属性集合
    print(nbr,attr）

图的可视化绘制

六、图的可视化绘制

使用NetworkX模块的draw()函数构造图，并结合matplotlib库将图显示出来：

nx.draw(g)
import matplotlib.pyplot as plt
plt.show()

可以修改顶点和边的颜色以增强可视化效果：

g = nx.cubical_graph()
nx.draw(g, pos=nx.spectral_layout(g), nodecolor='r', edge_color='b')
plt.show()

完整的示例代码如下所示：

from matplotlib import pyplot as plt
import networkx as nx
g=nx.Graph()
g.add_nodes_from([1,2,3])
g.add_edges_from([(1,2),(1,3)])
nx.draw_networkx(g)
plt.show()

PageRank算法应用

七、计算PageRank值

在计算每个顶点的PageRank（简称PR）值时，可使用NetworkX模块中的pagerank()函数。该函数根据顶点的边和边的权重来计算顶点的PR值：

pagerank(g, alpha=0.85, personalization=None, max_iter=100, tol=1e-06, nstart=None, weight='weight', dangling=None)

常用参数注释如下：

g：无向图会被转换为有向图，一条无向边转换为两条有向边。

alpha：阻尼参数，默认值为0.85。

weight：默认值为weight，表示使用edge的weight属性作为权重；如果没有指定，那么把edge的权重设置为1。

1. 示例演示

例如，创建一个有向图，包含三个顶点（A、B和C），两条边（A指向B，A指向C），边的权重均为0.5：

g=nx.DiGraph()
g.add_weighted_edges_from([('A','B',0.5),('A','C',0.5)])
print( nx.pagerank(g))
#{'A': 0.259740259292235, 'C': 0.3701298703538825, 'B': 0.3701298703538825}

修改边的权重，并查看顶点的PR值：

g['A']['C']['weight']=1
print( nx.pagerank(g))  
# {'A': 0.259740259292235, 'C': 0.40692640737443164, 'B': 0.3333333333333333}

2. 查看各顶点PR值

根据图创建PageRank，并查看各个顶点的PageRank值。

pr=nx.pagerank(g)
#page_rank_value=pr[node]
for node, pageRankValue in pr.items():
  print("%s,%.4f" %(node,pageRankValue))