数据结构与算法（Python版）第2版 课件 chap14 NetWorkX

NetworkX

定义：NetworkX是一个用于创建、操作和研究复杂网络结构的Python库，基于图论提供了丰富的数据结构和算法.特点：灵活的数据结构，支持无向图、有向图、加权图等，节点和边可带属性.大量的图论算法，如遍历、最短路径、社区发现、中心性等.简单易用的可视化工具.

安装：使用pipinstallnetworkx命令进行安装

.导入：在Python脚本中通过importnetworkxasnx导入NetworkX库

.无向图：使用nx.Graph()创建，如G=nx.Graph().【例】无向图importnetworkxasnximportmatplotlib.pyplotaspltG=nx.Graph()#创建一个空的无向图G.add_edge(1,2

,weight=4.2)#添加一个从节点1到节点2的边，权重为4.2G.add_nodes_from([3,4])#添加多个节点nx.draw(G,with_labels=True)plt.show()有向图：使用nx.DiGraph()创建，如DG=nx.DiGraph().

【例】有向图importnetworkxasnximportmatplotlib.pyplotaspltDG=nx.DiGraph()#创建一个空的有向图DG.add_edge(1,2)#添加一个从节点1到节点2的边DG.add_edge(3,4)#添加一个从节点3到节点4的边nx.draw(DG,with_labels=True)plt.show()节点（Node）：可以是任意可哈希的对象，通过add_node()或add_nodes_from()方法添加节点.

（1）标量属性1）节点权重：可以为节点设置权重，权重可以是整数、浮点数等。例如，在一个物流配送网络中，节点代表配送点，可以为节点设置“库存量”属性作为权重。权重高的节点表示该配送点库存量大，可能在物流调度中需要优先考虑。在图算法中，节点权重可以影响节点的选择和路径的计算，如在某些最短路径算法变体中，会考虑节点权重来优化路径。2）节点标签：可以给节点添加标签，标签可以是字符串等类型。例如，在一个社交网络中，节点代表用户，可以为节点添加“用户类型（普通用户、VIP用户等）”的标签。在分析用户行为或者进行个性化推荐时，可以根据节点标签来区分不同类型的用户。

节点（Node）：可以是任意可哈希的对象，通过add_node()或add_nodes_from()方法添加节点.（2）向量属性1）节点位置：在一些需要空间布局的场景中，可以为节点设置位置属性，通常是一个二维或三维坐标。例如，在地理信息系统（GIS）相关的网络中，节点代表地理实体（如城市、监测站点等），位置属性可以用于在地图上准确地绘制节点。在图的可视化中，根据节点位置属性可以生成更符合实际地理分布的图形。2）节点特征向量：在机器学习和数据挖掘中，节点特征向量是很重要的属性。例如，在一个社交网络中，节点特征向量可以包括用户的年龄、性别、兴趣爱好等多个维度的信息。这些特征向量可以用于节点分类、社区发现等任务。在图神经网络中，节点特征向量是网络学习的重要输入，通过学习节点特征向量的表示，可以挖掘图中的复杂模式。边（Edge）：表示节点之间的关系，使用add_edge()或add_edges_from()方法添加边.（1）标量属性1）边权重：边权重是最常见的边属性之一。它可以表示边的重要性、成本、距离等多种含义。例如，在一个交通网络中，边权重可以表示道路的长度；在通信网络中，边权重可以表示链路的带宽。在最短路径算法（如Dijkstra算法）中，边权重是关键因素，算法会根据边权重来计算从起点到终点的最短路径。权重高的边在某些情况下可能表示优先选择的路径（如带宽大的链路），在其他情况下可能表示需要避免的路径（如距离长的道路）。2）边容量：在流网络中，边容量是一个重要的属性。它表示边能够承载的最大流量。例如，在一个供水网络中，边代表管道，边容量可以表示管道的最大供水量。在网络流算法（如最大流最小割算法）中，边容量用于计算网络的最大流量，通过合理分配流量在各条边上的分布，可以实现资源的最优利用。

边（Edge）：表示节点之间的关系，使用add_edge()或add_edges_from()方法添加边.（2）向量属性1）边标签：可以为边添加标签，用于区分不同类型的边。例如，在一个语义网络中，节点代表概念，边代表概念之间的关系，边标签可以表示关系的类型（如“属于”“包含”“相似于”等）。在知识图谱中，边标签是构建知识体系的关键，通过分析边标签可以理解概念之间的语义联系。2）边特征向量：类似于节点特征向量，边特征向量可以包含多个维度的信息。例如，在一个电力传输网络中，边特征向量可以包括电压等级、传输线路类型（架空线、电缆等）、建设年代等多个属性。这些特征向量可以用于边的分类、故障诊断等任务。在图数据挖掘中，边特征向量可以和节点特征向量一起，为图的分析提供更丰富的信息。图的遍历：深度优先搜索（DFS）：nx.dfs_edges()等函数。广度优先搜索（BFS）：nx.bfs_edges()等函数。最短路径：nx.shortest_path()函数可计算两个节点之间的最短路径.中心性度量：度中心性：nx.degree_centrality()函数计算节点的度中心性，衡量节点的连接数量.中介中心性：nx.betweenness_centrality()函数计算节点的中介中心性，衡量节点在最短路径中的重要程度.社区发现：如munity.greedy_modularity_communities()函数可用于发现图中的社区结构。可视化展示基本绘图：使用nx.draw()函数进行简单绘图，可设置节点大小、颜色、标签等参数.布局调整：spring_layout：类似多中心放射状排列节点.circular_layout：节点在圆环上均匀分布.random_layout：节点随机分布.shell_layout：节点在同心圆上分布.spectral_layout：根据图