Python 处理树和网络详解

网络是节点对之间包含*n*ODE和边的对象。它们可以用来表示各种各样的实际情况，例如分发和调度。从数学上讲，网络对于组合问题的可视化非常有用，并且可以形成丰富而迷人的理论。

当然，有几种不同类型的网络。我们将主要处理简单网络，其中边连接两个不同的节点（因此没有自循环），任何两个节点之间最多有一条边，并且所有边都是双向的。树是一种不存在循环的特殊网络；也就是说，没有节点列表，其中每个节点通过边连接到下一个节点，最后一个节点连接到第一个节点。树的理论特别简单，因为它们用最少的边连接多个节点。完整网络是一个网络，其中每个节点通过边缘连接到其他节点。

可以定向网络，其中每条边都有一个源节点和一个目标节点，或者可以携带附加属性，例如权重。加权网络在某些应用中特别有用。还有一些网络，我们允许两个给定节点之间有多条边。

在本章中，我们将学习如何创建、操作和分析网络，然后应用网络算法解决各种问题。

In the literature, especially in mathematical texts, networks are more commonly called graphs. Nodes are sometimes called vertices. We favor the term network to avoid confusion with the more common usage of graph to mean a plot of a function.

本章将介绍以下配方：

让我们开始吧！

在本章中，我们将主要使用 NetworkX 包处理树和网络。可以使用您最喜欢的软件包管理器安装此软件包，例如pip:

          python3.8 -m pip install networkx

我们通常以别名nx导入此文件，遵循官方 NetworkX 文档中建立的约定，使用以下import语句：

import networkx as nx

本章的代码可以在 GitHub 存储库的的Chapter 05文件夹中找到 https://github.com/PacktPublishing/Applying-Math-with-Python/tree/master/Chapter%2005 。

查看以下视频以查看代码的运行：https://bit.ly/2WJQt4p 。

为了解决大量可以表示为网络问题的问题，我们首先需要一种用 Python 创建网络的方法。为此，我们将利用 NetworkX 包及其提供的例程和类来创建、操作和分析网络。

在这个配方中，我们将用 Python 创建一个表示网络的对象，并向该对象添加节点和边。

准备

正如我们在技术要求一节中提到的，我们需要使用以下import语句以别名nx导入 NetworkX 包：

import networkx as nx

怎么做。。。

按照以下步骤创建简单图形的 Python 表示：

1. 我们需要创建一个新的Graph对象来存储构成图形的节点和边：

G = nx.Graph()

2. 接下来，我们需要使用add_node方法为网络添加节点：

G.add_node(1)
G.add_node(2)

3. 为了避免重复调用此方法，我们可以使用add_nodes_from方法从 iterable（如列表）中添加节点：

G.add_nodes_from([3, 4, 5, 6])

4. 接下来，我们需要在使用add_edge方法或add_edges_from方法添加的节点之间添加边，这两种方法分别添加单个边或边列表（作为元组）：

G.add_edge(1, 2)  # edge from 1 to 2
G.add_edges_from([(2, 3), (3, 4), (3, 5), (3, 6), (4, 5), (5, 6)])

5. 最后，我们通过分别访问nodes和edges属性来检索图中当前节点和边的视图：

print(G.nodes)
print(G.edges)
# [1, 2, 3, 4, 5, 6]
# [(1, 2), (2, 3), (3, 4), (3, 5), (3, 6), (4, 5), (5, 6)]

它是如何工作的。。。

NetworkX 包添加了几个类和例程，用于使用 Python 创建、操作和分析网络。Graph类是最基本的类，用于表示在任何给定节点之间不包含多条边且其边是无向（双向）的网络。

一旦创建了一个空白的Graph对象，我们就可以使用本配方中描述的方法添加新的节点和边。在这个配方中，我们创建了包含整数值的节点。但是，节点可以包含除None.之外的任何可散列 Python 对象。此外，相关数据可以通过传递给add_node方法的关键字参数添加到节点。使用add_nodes_from方法时，还可以通过提供包含节点对象的元组列表和属性字典来添加属性。add_nodes_from方法用于批量添加节点，而add_node方法用于将单个节点连接到现有网络。

网络中的边是包含两个（不同）节点的元组。在一个简单的网络中，如基本Graph类所表示的网络，在任意两个给定节点之间最多只能有一条边。通过add_edge或add_edges_from方法添加边，分别向网络添加单个边或边列表。对于节点，边可以通过属性字典保存任意关联的数据。特别是，可以通过在添加边时提供weight属性来添加权重。我们将在创建定向和加权网络配方中提供有关加权图的更多详细信息。

nodes和edges属性分别保存构成网络的节点和边。nodes属性返回一个NodesView对象，它是节点及其关联数据的类似字典的接口。类似地，edges属性返回一个EdgeView对象。这可用于检查单个边及其关联数据。

还有更多。。。

Graph类表示简单网络，这些网络中的节点最多由一条边连接，且边不定向。我们将在创建定向和加权网络配方中讨论定向网络。有一个单独的类用于表示网络，其中一对节点之间可以有多条边，称为MultiGraph。所有网络类型都允许自环，这在文献中的“简单网络”中有时是不允许的，其中简单网络通常指没有自环的无向网络。

所有网络类型都提供了添加节点和边以及检查当前节点和边的各种方法。也有将网络复制到其他类型网络或提取子网络的方法。NetworkX 包中还有几个实用程序例程，用于生成标准网络和向现有网络添加子网络。

NetworkX 还提供各种例程，用于将网络读写为不同的文件格式，如 GraphML、JSON 和 YAML。例如，我们可以使用nx.write_graphml例程将网络写入 GraphML 文件，并使用nx.read_graphml例程读取网络。

分析网络的第一步通常是绘制网络，这可以帮助我们识别网络的一些突出特征。（当然，图纸可能具有误导性，因此我们在分析时不应过分依赖它们。）

在此配方中，我们将描述如何使用 NetworkX 包中的网络绘图工具来可视化网络。

准备

对于该配方，我们需要导入名为nx的 NetworkX 包，如技术要求部分所述。我们还需要 Matplotlib 包。为此，我们通常使用以下import语句将pyplot模块导入为plt：

import matplotlib.pyplot as plt

怎么做。。。

以下步骤概述了如何使用 NetworkX 中的绘图例程绘制简单网络对象：

1. 首先，我们创建一个简单的示例网络来绘制：

G = nx.Graph()

G.add_nodes_from(range(1, 7))
G.add_edges_from([
    (1, 2), (2, 3), (3, 4), (3, 5), 
    (3, 6), (4, 5), (5, 6)
])

2. 接下来，我们为其创建新的 MatplotlibFigure和Axes对象，准备使用plt中的subplots例程绘制网络：

fig, ax = plt.subplots()

3. 现在，我们可以创建一个布局，用于在图形上定位节点。对于该图形，我们将使用shell_layout例程使用 shell 布局：

layout = nx.shell_layout(G)

4. 我们可以使用draw例程在图形上绘制网络。由于我们已经创建了 MatplotlibFigure和Axes，我们将提供ax关键字参数。我们还将使用with_labels关键字参数向节点添加标签，并指定我们刚刚使用pos参数创建的布局：

nx.draw(G, ax=ax, pos=layout, with_labels=True)
ax.set_title("Simple network drawing")

下图显示了最终的图纸：

Figure 5.1: A drawing of a simple network arranged using a shell layout

它是如何工作的。。。

draw例程是专门用于绘制网络的专用绘图例程。我们创建的布局指定了每个节点将放置的坐标。我们使用了一个外壳布局，它以同心圆的方式排列节点，这是由网络的节点和边缘决定的。默认情况下，draw例程创建随机布局。

draw例程有许多关键字参数，用于自定义绘制网络的外观。在这个配方中，我们添加了with_labels关键字参数，根据节点所持有的对象来标记图中的节点。这些节点包含整数，这就是上图中的节点用整数标记的原因。

我们还使用plt.subplots例程分别创建了一组轴。这不是绝对必要的，因为如果没有提供，draw例程将自动创建新的图形和轴。

还有更多。。。

NetworkX 包提供了几个布局生成例程，类似于我们在本配方中使用的shell_layout例程。布局只是一个字典，由节点索引，其元素是节点应绘制位置的x和y坐标。用于创建布局的 NetworkX 例程表示对大多数情况都有用的常见布局，但如果需要，也可以创建自定义布局。NetworkX 文档中提供了不同布局创建例程的完整列表。还有一些快捷绘图例程，它们将使用特定布局，需要单独创建布局；例如，draw_shell例程将使用与本配方中给出的draw调用等效的 shell 布局绘制网络。

draw例程使用许多关键字参数来自定义图形的外观。例如，有一些关键字参数来控制节点的大小、颜色、形状和透明度。我们还可以添加箭头（用于定向边）和/或仅从网络中绘制一组特定的节点和边。

除了用于分析图形的节点数和边数之外，网络还具有各种基本特征。例如，节点的度是从该节点开始（或结束）的边数。度越高，表示节点与网络其余部分的连接越好。

在本食谱中，我们将学习如何访问基本属性并计算与网络相关的各种基本度量。

准备

像往常一样，我们需要导入名为nx的 NetworkX 包。我们还需要导入名为plt的 Matplotlibpyplot模块。

怎么做。。。

按照以下步骤访问网络的各种基本特征：

1. 创建一个我们将在本配方中分析的示例网络，如下所示：

G = nx.Graph()
G.add_nodes_from(range(10))
G.add_edges_from([
    (0, 1), (1, 2), (2, 3), (2, 4), 
    (2, 5), (3, 4), (4, 5), (6, 7),
    (6, 8), (6, 9), (7, 8), (8, 9)
])

2. 接下来，绘制网络并以圆形布局布置节点是一种很好的做法：

fig, ax = plt.subplots()
nx.draw_circular(G, ax=ax, with_labels=True)
ax.set_title("Simple network")

结果图如下图所示。正如我们所见，网络分为两个不同的部分：

Figure 5.2: Simple network drawn in a circular arrangement. There are two distinct components visible in this network

3. 接下来，我们使用nx.info例程来显示一些关于网络的基本信息：

print(nx.info(G))
# Name: 
# Type: Graph
# Number of nodes: 10
# Number of edges: 12
# Average degree: 2.4000

4. 现在，我们使用Graph对象的degree属性来检索特定节点的度：

for i in [0, 2, 7]:
    degree = G.degree[i]
    print(f"Degree of {i}: {degree}")
# Degree of 0: 1
# Degree of 2: 4
# Degree of 7: 2

5. 我们可以使用connected_components例程获取网络的连接组件，该例程返回一个我们制作成列表的生成器：

components = list(nx.connected_components(G))
print(components)
# [{0, 1, 2, 3, 4, 5}, {8, 9, 6, 7}]

6. 我们使用density例程计算网络的密度，该例程返回介于 0 和 1 之间的浮点值。这表示与节点相交的边与节点上可能的边总数的比例：

density = nx.density(G)
print("Density", density)
# Density 0.26666666666666666

7. 最后，我们可以通过使用check_planarity例程确定网络是否为平面——也就是说，不需要绘制两条相交的边：

is_planar, _ = nx.check_planarity(G)
print("Is planar", is_planar)
# Is planar True

它是如何工作的。。。

info例程生成网络的一个小摘要，包括网络类型（在本配方中是一个简单的Graph类型）、节点和边的数量以及网络中节点的平均度。可以使用degree属性访问网络中某个节点的实际度数，该属性提供了一个类似字典的接口来查找每个节点的度数。

如果一组节点中的每个节点通过一条边或一系列边连接到其他节点，则称该组节点为连接的。网络的连接组件是连接的最大节点集。任何两个明显相连的组件都是明显脱节的。每个网络都可以分解为一个或多个连接的组件。我们在本配方中定义的网络有两个相连的组件，{0, 1, 2, 3, 4, 5}和{8, 9, 6, 7}。这些在上图中清晰可见，其中第一个连接的组件绘制在第二个连接的组件上方。在这个图中，我们可以沿着网络的边缘跟踪从组件中的任何节点到任何其他节点的路径；例如，从 0 到 5。

网络的密度测量网络中的边数与网络中节点数给定的总可能边数之比。一个完整网络的密度为 1，但通常密度小于 1。

如果网络可以在平面上绘制而不需要交叉边，则网络是平面的。非平面网络的最简单示例是具有五个节点的完整网络。具有最多四个节点的完整网络是平面的。对在纸上绘制这些网络的方式进行一些实验，将显示一个不包含交叉边的图形。此外，任何包含至少有五个节点的完整图的网络都不是平面的。平面网络在理论上很重要，因为它们相对简单，但它们在应用中出现的网络中不太常见。

还有更多。。。

除了网络类上的方法外，NetworkX 包中还有许多其他例程可用于访问网络中节点和边的属性。例如，nx.get_node_attributes从网络中的每个节点获取一个命名属性。

图分析中的一个有力工具是邻接矩阵，如果从节点i到节点j、有边，则邻接矩阵的条目a_ij=1，否则为 0。对于大多数网络，邻接矩阵将是稀疏的（大多数条目为 0）。对于非定向网络，矩阵也将是对称的（a_ij=a_ji）。有许多其他矩阵可以与网络相关联。我们将在中简要讨论这些，还有更多。。。此配方的一部分。**

**在此配方中，我们将生成网络的邻接矩阵，并学习如何从该矩阵中获得网络的一些基本属性。

准备

对于此配方，我们需要以名称nx导入 NetworkX 包，并以名称np导入 NumPy 模块。

怎么做。。。

以下步骤概述了如何生成网络的邻接矩阵，并从该矩阵导出网络的一些简单属性：

1. 首先，我们将生成一个网络，以便在整个配方中使用。我们将生成一个具有五个节点和五条边的随机网络，同时使用种子进行再现：

G = nx.dense_gnm_random_graph(5, 5, seed=12345)

2. 为了生成邻接矩阵，我们使用 NetworkX 中的adjacency_matrix例程。默认情况下，这将返回一个稀疏矩阵，因此我们还将使用todense方法将其转换为完整的 NumPy 数组进行演示：

matrix = nx.adjacency_matrix(G).todense()
print(matrix)
# [[0 0 1 0 0]
#  [0 0 1 1 0]
#  [1 1 0 0 1]
#  [0 1 0 0 1]
#  [0 0 1 1 0]]

3. 取邻接矩阵的n次方，我们得到从一个节点到另一个节点的长度为n的路径数：

paths_len_4 = np.linalg.matrix_power(matrix, 4)
print(paths_len_4)
# [[ 3 5  0  0 5]
#  [ 5 9  0  0 9]
#  [ 0 0 13 10 0]
#  [ 0 0 10  8 0]
#  [ 5 9  0  0 9]]

它是如何工作的。。。

dense_gnm_random_graph例程生成一个（密集的）随机网络，从具有n节点和m边的所有网络家族中统一选择。在配方中，n=5和m=5。稠密前缀表示，与节点相比，对于边缘数量相对较多的稠密网络，该例程使用的算法应比备选算法gnm_random_graph更快。

网络的邻接矩阵很容易生成，特别是在稀疏形式下，当图相对较小时。对于更大的网络，这可能是一个昂贵的操作，因此可能不实用，特别是如果您将其转换为完整的矩阵，正如我们在本配方中看到的那样。通常不需要这样做，因为我们可以简单地使用adjacency_matrix例程生成的稀疏矩阵和 SciPysparse模块中的稀疏线性代数工具。

矩阵幂提供关于给定长度的路径数的信息。通过追踪矩阵乘法的定义可以很容易地看出这一点。请记住，当两个给定节点之间存在边（路径长度为 1）时，邻接矩阵的条目为 1。

还有更多。。。

网络邻接矩阵的特征值提供了一些关于网络结构的附加信息，如网络色数的界。（有关网络着色的更多信息，请参见网络着色配方。）有一个单独的例程用于计算邻接矩阵的特征值。例如，我们可以使用adjacency_spectrum例程生成网络邻接矩阵的特征值。涉及与网络相关的矩阵特征值的方法通常称为谱方法。

还有其他与网络相关的矩阵，如关联矩阵和拉普拉斯矩阵。网络的关联矩阵为M×N矩阵，其中M为节点数，N为边数。如果节点i出现在边缘j中，则该节点具有第 1 个条目i-j，否则为 0。网络的拉普拉斯矩阵定义为L=D-a矩阵，其中D是包含网络中节点度的对角矩阵，a是网络的邻接矩阵。这两种矩阵都有助于分析网络。

简单网络（如前面的配方中所述）对于描述边的方向不重要且边的权重相等的网络非常有用。实际上，大多数网络都携带额外的信息，如权重或方向。

在本配方中，我们将创建一个有向加权网络，并探索此类网络的一些基本特性。

准备

对于这个配方，我们需要 NetworkX 包，以名称nx（通常情况下）导入，Matplotlibpyplot模块作为plt导入，NumPy 包作为np导入。

怎么做。。。

以下步骤概述了如何创建具有权重的定向网络，以及如何探索我们在前面的配方中讨论的一些特性和技术：

1. 为了创建定向网络，我们使用 NetworkX 中的DiGraph类，而不是简单的Graph类：

G = nx.DiGraph()

2. 通常，我们使用add_node或add_nodes_from方法向网络添加节点：

G.add_nodes_from(range(5))

3. 要添加加权边，可以使用add_edge方法并提供weight关键字参数，也可以使用add_weighted_edges_from方法：

G.add_edge(0, 1, weight=1.0)
G.add_weighted_edges_from([
    (1, 2, 0.5), (1, 3, 2.0), (2, 3, 0.3), (3, 2, 0.3),
    (2, 4, 1.2), (3, 4, 0.8)
])

4. 接下来，我们用箭头绘制网络，以指示每条边的方向。我们还为该地块提供了自己的位置：

fig, ax = plt.subplots()
pos = {0: (-1, 0), 1: (0, 0), 2: (1, 1), 3: (1, -1), 4: (2, 0)}
nx.draw(G, ax=ax, pos=pos, with_labels=True)
ax.set_title("Weighted, directed network")

下图显示了结果图：

Figure 5.3: A weighted, directed network

5. 有向矩阵的邻接矩阵的创建方式与简单网络相同，但生成的矩阵将不是对称的：

adj_mat = nx.adjacency_matrix(G).todense()
print(adj_mat)
# [[0\. 1\. 0\. 0\. 0\. ]
# [0\. 0\. 0.5 2\. 0\. ]
# [0\. 0\. 0\. 0.3 1.2]
# [0\. 0\. 0.3 0\. 0.8]
# [0\. 0\. 0\. 0\. 0\. ]]

它是如何工作的。。。

DiGraph类表示有向网络，其中添加边时节点的顺序很重要。在这个方法中，我们为连接节点 2 和 3 添加了两条边，每个方向一条。在一个简单的网络（T1 类）中，添加第二条边不会添加额外的边。然而，对于有向网络（T2 类），添加边时节点的顺序决定了方向。

加权边没有什么特别之处，除了附加到边上的weight属性。（可以通过关键字参数将任意数据附加到网络中的边缘或节点。）add_weighted_edges_from方法只需将相应的权重值（元组中的第三个值）添加到所讨论的边缘。权重可以添加到任何网络中的任何边，而不仅仅是此配方中显示的定向网络。

当绘制定向网络时，draw例程会自动向边添加箭头。可以通过传递arrows=False关键字参数来关闭此行为。有向网络或加权网络的邻接矩阵也不同于简单网络的邻接矩阵。在有向网络中，矩阵通常不是对称的，因为边可能存在于一个方向，但不存在于另一个方向。对于加权网络，条目可以不同于 1 或 0，而是相应边的权重。

还有更多。。。

加权网络出现在许多应用中，例如用距离或速度来描述交通网络。通过为网络中的边提供“容量”（作为权重或其他属性），也可以使用网络检查通过网络的流量。NetworkX 有多个分析网络流量的工具，例如通过nx.maximum_flow例程查找通过网络的最大流量。

定向网络向网络添加方向信息。许多现实世界的应用产生了具有单向边缘的网络，例如工业过程或供应链网络中的网络。正如我们将在本章中看到的那样，这些额外的方向信息会对许多网络算法产生影响。

网络出现的一个常见问题是如何在网络中的两个节点之间找到最短（或者更准确地说，是最高回报）的路由。例如，这可能是两个城市之间的最短距离，其中节点表示城市，边缘是连接成对城市的道路。在这种情况下，边的权重将是它们的长度。

在这个配方中，我们将找到网络中两个节点之间的最短路径。

准备

对于此配方，我们需要像往常一样导入名为nx的 NetworkX 包，导入名为plt的 Matplotlibpyplot模块，以及来自 NumPy 的随机数生成器对象：

from numpy.random import default_rng
rng = default_rng(12345) # seed for reproducibility

怎么做。。。

按照以下步骤查找网络中两个节点之间的最短路径：

1. 首先，我们将使用gnm_random_graph和seed为本演示创建一个随机网络：

G = nx.gnm_random_graph(10, 17, seed=12345)

2. 接下来，我们将绘制具有圆形排列的网络，以查看节点如何相互连接：

fig, ax = plt.subplots()
nx.draw_circular(G, ax=ax, with_labels=True)
ax.set_title("Random network for shortest path finding")

在下图中可以看到结果图。在这里，我们可以看到从节点 7 到节点 9 没有直接边：

Figure 5.4: A randomly generated network with 10 nodes and 17 edges

3. 现在，我们需要为每条边添加权重，以便某些路线在最短路径方面优于其他路线：

for u, v in G.edges:
    G.edges[u, v]["weight"] = rng.integers(5, 15)

4. 接下来，我们将使用nx.shortest_path例程计算从节点 7 到节点 9 的最短路径：

path = nx.shortest_path(G, 7, 9, weight="weight")
print(path)
# [7, 5, 2, 9]

5. 我们可以使用nx.shortest_path_ length例程找到该最短路径的长度：

length = nx.shortest_path_length(G, 7, 9, weight="weight")
print("Length", length)
# Length 32

它是如何工作的。。。

shortest_path例程计算每对节点之间的最短路径。或者，当提供源节点和目标节点时（这就是我们在本配方中所做的），它会计算两个指定节点之间的最短路径。我们提供了可选的weight关键字参数，使算法根据边缘的“权重”属性找到最短路径。此参数更改“最短”的含义，默认值为“最少边”。

寻找两个节点之间最短路径的默认算法是 Dijkstra 算法，这是计算机科学和数学课程的主要内容。这是一个很好的通用算法，但不是特别有效。其他路由查找算法包括 A算法。通过使用带有附加启发式信息的 A算法来指导节点选择，可以获得更高的效率。

还有更多。。。

在网络中，有许多算法可用于寻找两个节点之间的最短路径。还有用于查找最大加权路径的变体。

在网络中查找路径有几个相关问题，例如旅行推销员问题和路线检查问题。在旅行推销员问题中，我们发现一个循环（从同一节点开始和结束的路径）访问网络中的每个节点，总权重最小（或最大）。在路径检查问题中，我们寻求穿越网络中每一条边并返回起点的最短周期（按权重）。旅行推销员问题被认为是 NP 难问题，但路线检查问题可以在多项式时间内求解。

图论中一个著名的问题是 Königsberg 的桥，它要求在网络中找到一条路径，该路径恰好遍历网络中的每条边一次。事实证明，正如 Euler 所证明的，在 Königsberg 桥问题中找到这样一条路径是不可能的。一条恰好穿过每条边一次的路径称为欧拉回路。允许欧拉电路的网络称为欧拉。事实上，网络是欧拉的当且仅当每个节点都有偶数度。克尼斯伯格桥问题的网络表示可以在下图中看到。其中的边表示河流上的不同桥梁，而节点表示不同的陆地。我们可以看到，所有四个节点都有奇数度，这意味着不可能有一条路径恰好穿过每条边一次：

Figure 5.5: A network representing the Königsberg bridge problem

边表示节点表示的不同地块之间的桥梁。

有各种与网络相关的量，用于测量网络的特性。例如，节点的聚类系数度量附近节点之间的互连性（此处，附近表示通过边连接）。实际上，它测量相邻节点与形成完整网络或集团的距离。

节点的聚类系数度量由边连接的相邻节点的比例；也就是说，两个相邻节点与给定节点形成三角形。我们计算三角形的数量，然后根据节点的阶数除以可能形成的三角形的总数。在数值上，简单无权网络中节点u处的聚类系数由以下等式给出：

这里，T_u是u处的三角形数量，分母是u处可能的三角形总数。如果u 的度数（从u】到的边数是 0 或 1，那么我们将c_u设置为 0。

在本配方中，我们将学习如何计算网络中节点的聚类系数。

准备

对于此配方，我们需要将 NetworkX 包作为nx导入，将 Matplotlibpyplot模块作为plt导入。

怎么做。。。

以下步骤说明如何计算网络中节点的群集系数：

1. 首先，我们需要创建一个示例网络来处理：

G = nx.Graph()
complete_part = nx.complete_graph(4)
cycle_part = nx.cycle_graph(range(4, 9))
G.update(complete_part)
G.update(cycle_part)
G.add_edges_from([(0, 8), (3, 4)])

2. 接下来，我们将绘制网络，以便我们可以比较我们将要计算的聚类系数。这将允许我们查看这些节点在网络中的显示方式：

fig, ax = plt.subplots()
nx.draw_circular(G, ax=ax, with_labels=True)
ax.set_title("Network with different clustering behavior")

下图显示了结果图：

Figure 5.6: Sample network for testing clustering

3. 现在，我们可以使用nx.clustering例程计算网络中节点的聚类系数：

cluster_coeffs = nx.clustering(G)

4. nx.clustering例程的输出是网络中节点上的字典。因此，我们可以打印一些选定的节点，如下所示：

for i in [0, 2, 6]:
    print(f"Node {i}, clustering {cluster_coeffs[i]}")
# Node 0, clustering 0.5
# Node 2, clustering 1.0
# Node 6, clustering 0

5. 可以使用nx.average_clustering例程计算网络中所有节点的平均聚类系数：

av_clustering = nx.average_clustering(G)
print(av_clustering)
# 0.3333333333333333

它是如何工作的。。。

节点的聚类系数衡量该节点的邻域与完整网络的距离（所有节点都相互连接）。在这个配方中，我们可以看到有三个不同的计算值：0 的聚类系数为 0.5，2 的聚类系数为 1.0，6 的聚类系数为 0。这意味着连接到节点 2 的节点形成一个完整的网络，这是因为我们以这种方式设计了我们的网络。（节点 0-4 在设计上形成了一个完整的网络。）节点 6 的邻域远不是完整的，因为它的任何一个邻域之间都没有互连边。

平均聚类值是网络中所有节点上聚类系数的简单平均值。它与全局聚类系数（使用 NetworkX 中的nx.transitivity例程计算）并不完全相同，但它确实让我们了解到网络作为一个整体离完整网络有多近。全局聚类系数测量整个网络中三角形数量与三元组数量的比率，三元组是由至少两条边连接的三个节点组成的集合。

平均聚类之间的差异非常细微。全局聚类系数衡量网络作为一个整体的聚类，但平均聚类系数衡量网络的平均局部聚类程度。这种差异在风车网络中最为明显，风车网络由一个节点组成，该节点由一个由偶数个节点组成的圆圈包围。所有节点都连接到中心，但圆上的节点仅以交替模式连接。外部节点的局部聚类系数为 1，而中心节点的局部聚类系数为 1/（2N-1，其中N表示连接到中心节点的三角形数量，而全局聚类系数为 3/（2N-1）。

还有更多。。。

聚类系数与网络中的派系相关。团是一个完整的子网络（所有节点通过一条边连接）。网络理论中的一个重要问题是寻找网络中的最大团，这通常是一个非常困难的问题（这里，最大平均数“不能变大”）。

网络在调度问题中也很有用，在调度问题中，您需要将活动安排到不同的插槽中，以避免冲突。例如，我们可以使用网络安排课程，以确保选择不同选项的学生不必同时在两个班级上课。在此场景中，节点将表示不同的类，边将指示有学生同时参加这两个类。我们用来解决这类问题的过程称为网络着色。此过程涉及为网络中的节点分配尽可能少的颜色，以便没有两个相邻节点具有相同的颜色。

在本食谱中，我们将学习如何为网络着色以解决一个简单的调度问题。

准备

对于此配方，我们需要将 NetworkX 包作为nx导入，将 Matplotlibpyplot模块作为plt导入。

怎么做。。。

请按照以下步骤解决网络着色问题：

1. 首先，我们将创建一个用于此配方的示例网络：

G = nx.complete_graph(3)
G.add_nodes_from(range(3, 7))
G.add_edges_from([
    (2, 3), (2, 4), (2, 6), (0, 3), (0, 6), (1, 6),
    (1, 5), (2, 5), (4, 5)
])

2. 接下来，我们将绘制网络，以便在生成网络时能够理解其颜色。为此，我们将使用draw_circular例程：

fig, ax = plt.subplots()
nx.draw_circular(G, ax=ax, with_labels=True)
ax.set_title("Scheduling network")

下图显示了结果图：

Figure 5.7: Example network for a simple scheduling problem

3. 我们将使用nx.greedy_color例程生成着色：

coloring = nx.greedy_color(G)
print("Coloring", coloring)
# Coloring {2: 0, 0: 1, 1: 2, 5: 1, 6: 3, 3: 2, 4: 2}

4. 要查看此着色中使用的实际颜色，我们将从coloring字典中生成一组值：

different_colors = set(coloring.values())
print("Different colors", different_colors)
# Different colors {0, 1, 2, 3}

它是如何工作的。。。

nx.greedy_color例程使用多种可能的策略之一为网络着色。默认情况下，它按从最大到最小的顺序工作。在我们的例子中，首先将颜色 0 指定给节点 2（度数为 6），然后将颜色 1 指定给节点 0（度数为 4），依此类推。将为此序列中的每个节点选择第一种可用颜色。这不一定是网络着色的最有效算法。

显然，任何网络都可以通过为每个节点分配不同的颜色来着色，但在大多数情况下，需要的颜色更少。在配方中，网络有七个节点，但只需要四种颜色。所需的最小颜色数称为网络的色数。

还有更多。。。

网络的着色问题有几种形式。一个这样的变化是列表着色问题，在该问题中，我们为网络寻找一种着色，其中每个节点从预定义的可能颜色列表中获得一种颜色。这个问题显然比一般的着色问题更难。

一般的着色问题有令人惊讶的结果。例如，每个平面网络最多可以使用四种不同的颜色进行着色。这是图论中一个著名的定理，称为四色定理，1977 年由 Appel 和 Haken 证明。

网络可以解决各种各样的问题。通信和分发是两个明显的应用领域。例如，我们可能希望找到一种方法，将货物配送到距离特定点最小的道路网络中的多个城市（节点）。对于这样的问题，我们需要研究最小生成树和支配集。

在此配方中，我们将在网络中找到最小生成树和支配集。

准备

对于这个配方，我们需要导入名为nx的 NetworkX 包和名为plt的 Matplotlibpyplot模块。

怎么做。。。

按照以下步骤查找网络的最小生成树和支配集：

1. 首先，我们将创建一个样本网络来分析：

G = nx.gnm_random_graph(15, 22, seed=12345)

2. 接下来，与往常一样，我们将在进行任何分析之前绘制网络：

fig, ax = plt.subplots()
pos = nx.circular_layout(G)
nx.draw(G, pos=pos, ax=ax, with_labels=True)
ax.set_title("Network with minimum spanning tree overlaid")

3. 可使用nx.minimum_ spanning_tree例程计算最小生成树：

min_span_tree = nx.minimum_spanning_tree(G)
print(list(min_span_tree.edges))
# [(0, 13), (0, 7), (0, 5), (1, 13), (1, 11),
#   (2, 5), (2, 9), (2, 8), (2, 3), (2, 12),
#   (3, 4), (4, 6), (5, 14), (8, 10)]

4. 接下来，我们将在绘图上覆盖最小生成树的边：

nx.draw_networkx_edges(min_span_tree, pos=pos, ax=ax, width=1.5,
   edge_color="r")

5. 最后，我们将使用nx.dominating_set例程为网络找到一个支配集，即网络中的每个节点都与该集中的至少一个节点相邻的集：

dominating_set = nx.dominating_set(G)
print("Dominating set", dominating_set)
# Dominating set {0, 1, 2, 4, 10, 14}

覆盖最小生成树的网络图如下图所示：

Figure 5.8: The network drawn with the minimum spanning tree overlaid

它是如何工作的。。。

网络的生成树是包含所有节点的网络中包含的树。最小生成树是包含尽可能少的边的生成树，或者具有最低的总权重。最小生成树对于网络上的分布问题非常有用。寻找最小生成树的一个简单算法是简单地选择边（如果网络加权，则首先选择最小权重的边），这样它就不会创建循环，直到不再可能。

网络的支配集是一组顶点，其中网络中的每个节点都与支配集中的至少一个节点相邻。支配集在通信网络中有着广泛的应用。我们经常对寻找最小支配集感兴趣，但这在计算上很困难。事实上，测试是否存在小于给定大小的支配集是 NP 完全的。然而，对于某些图类，有一些寻找最小支配集的有效算法。非正式地说，问题在于，一旦确定了最小规模支配集的候选对象，就必须验证是否不存在规模较小的支配集。如果你事先不知道所有可能的支配集，这显然是非常困难的。

有几本关于图论的经典著作，包括 Bollobsás 和 Diestel 的著作：

• 迪斯特，R.，2010 年。图论。柏林：斯普林格。
• *博洛巴，B.，2010 年。现代图论。纽约州纽约市：斯普林格。***