介绍

图（Graph）是一种表示对象之间关系的抽象数据结构。图由节点（Vertex）和边（Edge）组成，节点表示对象，边表示对象之间的关系。图可以用于建模各种实际问题，如社交网络、交通网络、电力网络等。

NetworkX是一个用Python编写的库，专门用于创建、操作和研究复杂网络的结构、动态和功能。它提供了简单易用的接口来处理图论和网络结构。NetworkX适用于处理大型网络结构，并提供了许多内置的图算法，如路径寻找、图的构建和修改、节点属性操作等。

• NetworkX官方文档（网站）：https://networkx.org/；
• 使用pip安装：pip install networkx并回车。

基本概念

无向图（Undirected Graph）

import networkx as nx

# 创建一个无向图
G = nx.Graph()

# 添加节点
G.add_node(1)
G.add_nodes_from([2, 3])

# 添加边
G.add_edge(1, 2)
G.add_edges_from([(2, 3), (1, 3)])

# 查看图的节点和边
print("图的节点: ", G.nodes(), "; 图的边: ", G.edges(), '.')

# 可视化
nx.draw(G, node_size=500, with_labels=True)

有向图（Directed Graph）

有向图的创建方式很简单，只需要把上面无向图的对象：

# 创建一个无向图
G = nx.Graph()

换成：

# 创建一个有向图
G = nx.DiGraph()

即可。

有权图（Directed Graph）

创建有权图时需要添加权重信息，且可视化的代码略有不同：

import networkx as nx
import matplotlib.pyplot as plt

# 创建一个带权重的无向图
G = nx.Graph()

# 添加带权重的边
G.add_edges_from([
    (2, 3, {'diameter': 1.0,'length': 12.0}),
    (1, 3, {'diameter': 2.0,'length': 10.0}),
    (2, 1, {'diameter': 3.0,'length': 8.0})
])

# 提取权重信息
edge_weights = nx.get_edge_attributes(G, 'length')

# 可视化图
pos = nx.spring_layout(G)  # 选择布局算法，这里使用弹簧布局
nx.draw(G, pos, with_labels=True, font_weight='bold', node_size=700, node_color='skyblue', font_color='black')

# 绘制权重标签
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_weights)

# 显示图形
plt.show()

# 查看图的节点和边
print("图的节点: ", G.nodes(), "; 图的边: ", G.edges(data=True), '.')

邻接矩阵

邻接矩阵（Adjacency Matrix）： 邻接矩阵是一个二维矩阵，其中的行和列分别对应图中的节点。矩阵的元素表示节点之间是否存在边。对于无向图，邻接矩阵是对称的；对于有向图，邻接矩阵不一定对称。

# 获取邻接矩阵(默认是稀疏矩阵格式)
adj_matrix = nx.adjacency_matrix(G)

# 将稀疏矩阵转换为密集矩阵(如果需要)
dense_adj_matrix = adj_matrix.todense()

请注意，如果你的图是有向图，你可以使用 nx.adjacency_matrix(G, directed=True) 来获取有向图的邻接矩阵。如果你想要自定义矩阵的表示方式，你可以使用 toarray() 方法将稀疏矩阵转换为 NumPy 数组。

度、平均度、度分布、度矩阵以及常见复杂网络常见度分布

下面的演示均以：

G.add_edges_from([  # Fig. 7
    (0, 1), (0, 2), (0, 7),
    (1, 0), (1, 2), (1, 3), (1, 4), (1, 7),
    (2, 0), (2, 1), (2, 3),
    (3, 1), (3, 2), (3, 4), (3, 5), (3, 7),
    (4, 1), (4, 3), (4, 5), (4, 6), (4, 7),
    (5, 3), (5, 4), (5, 6),
    (6, 4), (6, 5),
    (7, 0), (7, 1), (7, 3), (7, 4)
])

为示例。

度

度（Degree）的定义：

• 对于无向图 G，节点 i 的度 $ \text{degree}(i) $ 是与节点 i 相连的边的数量。
• 对于有向图 G，节点 i 的入度 $ \text{in-degree}(i) $ 是指向节点 i 的边的数量，出度 $ \text{out-degree}(i) $ 是从节点 i 出发的边的数量。

NetworkX求度：

# 获取节点的度
degrees = dict(G.degree())

print("节点的度：", degrees)

节点的度： {0: 3, 1: 5, 2: 3, 7: 4, 3: 5, 4: 5, 5: 3, 6: 2}

平均度

平均度（Average Degree）是图中所有节点的度的平均值。

• 对于无向图 G，平均度 $ \langle k \rangle $ 可以通过所有节点的度之和除以节点数得到。
• 对于有向图 G，同样可以计算平均入度和平均出度。

# 计算平均度
average_degree = sum(dict(G.degree()).values()) / len(G)

print("平均度：", average_degree)

平均度： 3.75

度分布

度分布（Degree Distribution）描述了图中节点的度的分布情况，即度为 k 的节点有多少个。度分布是图结构的一个重要特征，它可以帮助我们了解网络中节点的连接模式。

# 获取度分布
degree_distribution = nx.degree_histogram(G)

# 绘制度分布直方图
plt.bar(range(len(degree_distribution)), degree_distribution, tick_label=range(len(degree_distribution)))
plt.xlabel("Degree")
plt.ylabel("Frequency")
plt.title("Degree Distribution")
plt.show()

度矩阵

度矩阵（Degree Matrix）是一个表示图中节点度信息的对角矩阵。对于一个无向图，度矩阵的定义如下：

1. 对于无向图 G，其度矩阵 $ D $ 是一个 $ n \times n $ 的矩阵，其中 $ n $ 是图中的节点数。
2. $ D $ 的对角线元素 $ D_{ii} $ 表示节点 $ i $ 的度，即与节点 $ i $ 相连的边的数量。

# 获取度矩阵
np.diag(list(dict(G.degree()).values()))

复杂网络常见度分布

在复杂网络理论中，度分布描述了网络中各节点的连接数（即度）的分布情况。不同类型的网络具有不同的度分布特性。典型复杂网络的度分布有：泊松分布、幂律分布（Power-Law Distribution）、指数分布等。

泊松分布

大多数节点的度数集中在较小的数值范围内，这是典型的泊松分布特征，符合Erdős-Rényi随机图模型的特点。

import networkx as nx
import matplotlib.pyplot as plt

# 参数设置
n = 500  # 节点数
p = 0.05  # 每对节点间存在边的概率

# 使用 Erdős-Rényi 模型创建随机图
G = nx.erdos_renyi_graph(n, p)

# 准备绘制网络结构图和度分布统计图
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(16, 6))

# 在左边绘制网络图
nx.draw(G, ax=ax1, node_size=30, with_labels=False)
ax1.set_title("Erdős-Rényi Network (n={}, p={})".format(n, p))

# 在右边绘制度分布统计图
degrees = [G.degree(n) for n in G.nodes()]
ax2.hist(degrees, bins=range(min(degrees), max(degrees) + 1), density=True)
ax2.set_title("Degree Distribution")
ax2.set_xlabel("Degree")
ax2.set_ylabel("Frequency")

plt.show()

幂律分布

Barabási-Albert 模型生成的网络展现了显著的幂律分布特征，即大多数节点拥有较少的连接，而少数节点（枢纽节点）拥有非常多的连接。

m = 5
n = 200  # 节点数
G = nx.barabasi_albert_graph(n, m)

指数分布

大多数节点具有较低的度数，而只有少数节点具有较高的度数。这反映了指数分布的特点，即概率随着度数的增加而迅速减少。由于指数分布的特性，大多数节点集中在较低的度数区间，而高度数的节点数量迅速减少。

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt

# 参数设置
m = 5
n = 1000  # 节点数

# 由于NetworkX没有直接生成指数分布网络的函数，我们可以手动创建一个具有指数分布度的网络
# 创建一个空的图
G = nx.Graph()

# 添加节点
G.add_nodes_from(range(n))

# 生成一个符合指数分布的度序列
degree_sequence = np.random.exponential(scale=m, size=n).astype(int)

# 为了确保总度数为偶数（每条边两个端点），如果是奇数则调整
if sum(degree_sequence) % 2 != 0:
    degree_sequence[0] += 1

# 生成具有指定度序列的随机图（可能会有多重边和自环）
G = nx.configuration_model(degree_sequence)

# 转换为简单图（无多重边和自环）
G = nx.Graph(G)
G.remove_edges_from(nx.selfloop_edges(G))

# 准备绘制网络结构图和度分布统计图
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(16, 6))

# 在左边绘制网络图
nx.draw(G, ax=ax1, node_size=30, with_labels=False)
ax1.set_title("Exponential Distribution Network (n={}, scale={})".format(n, m))

# 在右边绘制度分布统计图
degrees = [d for n, d in G.degree()]
ax2.hist(degrees, bins=range(min(degrees), max(degrees) + 1), density=True)
ax2.set_title("Degree Distribution")
ax2.set_xlabel("Degree")
ax2.set_ylabel("Frequency")
plt.show()

Quote / 参考

幂律分布与指数分布看起来没有什么差别啊？

幂律分布：

• 长尾特性：幂律分布的一个显著特点是它的长尾特性。这意味着即使是非常大的值也有可能出现，尽管其频率较低。
• 对数坐标下的直线：在对数-对数坐标图中，幂律分布呈现为一条直线。
• 现实世界的例子：社交网络中的连接分布、互联网链接的分布、城市的人口分布等。

指数分布：

• 迅速衰减：指数分布的特点是随着值的增加，其概率迅速减少。这意味着大值出现的可能性比幂律分布要小得多。
• 半对数坐标下的直线：在半对数坐标图中（即纵坐标为对数坐标），指数分布表现为一条直线。
• 现实世界的例子：无线电活动的持续时间、顾客在商店的停留时间等。

拉普拉斯矩阵

拉普拉斯矩阵（Laplacian Matrix）有多种定义方式，其中最常见的计算方法是使用度矩阵减去邻接矩阵。假设无向图 G 有 n 个节点，其邻接矩阵为 A，度矩阵为 D。标准拉普拉斯矩阵 L 的计算如下：

1. 计算度矩阵 D 的对角线元素，即每个节点的度：$ D_{ii} = \sum_{j} A_{ij} $；
2. 计算拉普拉斯矩阵 L：$ L = D - A $。

# 获取邻接矩阵和度矩阵
adj_matrix = nx.adjacency_matrix(G).toarray()
degree_matrix = np.diag(list(dict(G.degree()).values()))

# 计算标准拉普拉斯矩阵
laplacian_matrix = degree_matrix - adj_matrix

请注意，对于有向图，可以使用 nx.directed_laplacian_matrix 函数来计算有向图的拉普拉斯矩阵。同样，还有对称归一化拉普拉斯矩阵和随机游走拉普拉斯矩阵等不同定义方式。

路径和距离

在图论中，路径和距离是描述图中节点之间连接关系和位置关系的重要概念。

• 路径（Path）：在图中，路径是指图中的一系列节点，其中任意相邻两个节点之间都有边相连。路径的长度是指路径上边的数量。如果路径中的所有节点都是不同的，则路径是简单路径。
• 距离（Distance）：在图中，两个节点之间的距离是指连接这两个节点的最短路径的长度。如果两个节点之间没有路径相连，则它们之间的距离通常被定义为无穷大。

获取图中的所有最短路径和距离：

# 获取所有节点对之间的最短路径和距离
all_shortest_paths = dict(nx.all_pairs_shortest_path(G))
all_shortest_distances = dict(nx.all_pairs_shortest_path_length(G))

# 打印最短路径和距离
all_info = []
for source in all_shortest_paths:
    for target in all_shortest_paths[source]:
        paths = all_shortest_paths[source][target]
        distance = all_shortest_distances[source][target]
        print(f"最短路径从节点 {source} 到节点 {target}: {paths}, 距离: {distance}")

集聚系数、平均集聚系数与全局集聚系数

演示实例：

G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)])
nx.draw(G, node_size=500, with_labels=True)

在图论中，集聚系数（Clustering Coefficient）是用于度量节点周围邻居之间连接紧密程度的指标。它可以帮助我们了解图中的局部连接性。有三种主要的集聚系数：节点的集聚系数、平均集聚系数和全局集聚系数。

节点的集聚系数是一个节点邻居之间实际存在的边数与可能存在的最大边数之比。对于一个无向图中的节点 $i$，其集聚系数 $C_i$ 的计算方式如下：

$$ C_i = \frac{2 \times \text{实际存在的边数}}{\text{邻居节点数} \times (\text{邻居节点数} - 1)} $$

这个值在 [0, 1] 范围内，表示节点的邻居之间连接紧密的程度。

# 计算节点的集聚系数
node_clustering = nx.clustering(G)
print("节点的集聚系数:", node_clustering)

节点的集聚系数: {1: 1.0, 2: 1.0, 3: 1.0, 4: 1.0, 5: 1.0}

以节点2为例，节点2的邻居节点是1、3、4、5。节点1、3、4、5可能存在的最大边数组合为$C_4^2 = \frac{4 \times 3}{2 \times 1} = 6$.

$$ C_n^k = \frac{n!}{k!(n-k)!} $$

节点1、3、4、5实际存在的连接情况是：

1: [1, 3], [1, 4], [1, 5]
3: [3, 4], [3, 5]
4: [4, 5]

共有6种。因此，节点2的聚集系数为1.

平均集聚系数是图中所有节点的集聚系数的平均值。对于一个无向图 $G$，其平均集聚系数 $C$ 的计算方式如下：

$$ C = \frac{1}{n} \sum_{i=1}^{n} C_i $$

其中，$n$ 是图中的节点数。

# 计算平均集聚系数
average_clustering = nx.average_clustering(G)
print("平均集聚系数:", average_clustering)

全局集聚系数是图中所有闭合三角形的数量与所有可能的闭合三角形的数量的比值。闭合三角形是由三个节点和它们之间的边组成的子图。对于一个无向图 $G$，其全局集聚系数 $C_{\text{global}}$ 的计算方式如下：

$$ C_{\text{global}} = \frac{\text{3×闭合三元组的数量}}{\text{连接三元组的数量}} $$

连接三元组（Open Triplet）是图论中的一个概念，它指的是在图中任选三个节点，其中至少有两个节点是相互连接的。这种三元组被称为“开放的”，因为它们不一定构成一个闭合的三角形。连接三元组是用来计算图的集聚系数的一个重要概念。

在具体的定义中，连接三元组通常包含以下两种情况：

1. 闭合三元组（Closed Triplet）：这是图中的三个节点，它们之间的每一对节点都相互连接。换句话说，这三个节点形成了一个闭合的三角形。
2. 非闭合三元组：这也是图中的三个节点，但它们之间不是每一对节点都相互连接。这意味着虽然其中两个节点之间有边相连，但至少有一对节点之间没有直接的连线，因此不形成闭合的三角形。

在计算图的全局集聚系数时，会考虑图中所有可能的连接三元组。全局集聚系数是闭合三元组数量与连接三元组总数量的比例。这个比例说明了在所有可能形成三角形的节点组合中，有多少实际形成了闭合的三角形。

例如，在社交网络分析中，闭合三元组可能表示一种更强的社会关系，因为如果A认识B，B认识C，且A也认识C，这可能意味着这三个人之间有更紧密的社交联系。而非闭合的三元组则可能表示潜在的、未完全形成的社交联系。

平均集聚系数关注的是每个节点的局部连接性，而全局集聚系数关注的是整个图中的全局连接性。

# 计算全局集聚系数
global_clustering = nx.transitivity(G)
print("全局集聚系数:", global_clustering)

全局集聚系数: 1.0

上面的示例图是一个完全图（任意两个顶点都是相连的），在完全图中，每一组三个节点都会形成一个闭合三角形，所以闭合三元组的数量等于连接三元组的数量。因此，全局集聚系数是 1.0。

实际存在的闭合三角形的数量（闭合三元组的数量）：

from itertools import combinations

# 获取图中所有可能的闭合三角形数量
all_triangles_count = 0

for node in G.nodes():  # 遍历所有节点
    neighbors = set(G.neighbors(node))  # 获取该节点的所有邻居节点
    for pair in combinations(neighbors, 2):  # 获取所有邻居节点的两两组合
        if G.has_edge(pair[0], pair[1]):  # 检查这个两两组合之间是否有边(因为它俩都是node的邻居节点，因此它俩肯定与node相连)，如果它俩相连，那么就说明node与pair[0]、pair[1]构成了三角形.
            all_triangles_count += 1

上面的代码等同于：

# 获取图中实际存在的闭合三角形数量(也需要除以3)
actual_triangles_count = sum(nx.triangles(G).values()) 

需要注意的是：all_triangles_count需要除以3得到的才是闭合三元组的数量，因为闭合三元组中的三个顶点会在不同的组合中进行重复计算。

连接三元组的数量：

open_triplets_count = 0

for node in G.nodes():
    neighbors_count = len(list(G.neighbors(node)))
    open_triplets_count += (neighbors_count * (neighbors_count - 1)) // 2

# open_triplets_count 现在就是图中连接三元组的总数量

从 $n$ 个数中随机挑选出 2 个的组合数可以用组合数学中的公式来计算，这个公式是 $ C(n, 2) $ 或者 $ \binom{n}{2} $，可以表示为：

$$ C(n, 2) = \frac{n!}{2!(n-2)!} = \frac{n \times (n-1)}{2} $$

图的连通性

连通性描述的是图中节点之间是否存在路径相连的性质。一个图是连通的，意味着从图中的任意一个节点到另一个节点都存在路径。

G = nx.Graph()
G.add_nodes_from([i for i in range(1, 8)])
G.add_edges_from([(1, 2), (1, 3), (2, 3), (4, 7), (5, 6), (5, 7), (6, 7)])
nx.draw(G, node_size=500, with_labels=True)

# 查看图的连通性
nx.is_connected(G)

什么叫做图的连通性？在无向图中，如果对于每一对不同的顶点 $u$ 和 $v$，都存在至少一条由边连接的路径从 $u$ 到 $v$，则该图是连通的。请注意这个概念并不等同于完全图的概念，完全图的概念是每一对不同的顶点 $u$ 和 $v$都直接相连，而连通图的每一对不同的顶点 $u$ 都可以达到 $v$，两者可以不直接相连。

通过创建两个图来展示不同的连通性：

# 创建具有较强连通性的图（低Fiedler值）
G_strong = nx.Graph()
G_strong.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 1), (1, 3), (2, 4)])

# 创建具有较弱连通性的图（高Fiedler值）
G_weak = nx.Graph()
G_weak.add_edges_from([(1, 2), (2, 3), (3, 4)])

# 绘制这两个图
plt.figure(figsize=(12, 6))

# 绘制具有较强连通性的图
plt.subplot(1, 2, 1)
nx.draw(G_strong, with_labels=True, node_color='lightblue', node_size=700)
plt.title("Strongly Connected Graph")

# 绘制具有较弱连通性的图
plt.subplot(1, 2, 2)
nx.draw(G_weak, with_labels=True, node_color='lightgreen', node_size=700)
plt.title("Weakly Connected Graph")

plt.show()

可以看出，左边的图具有更高的连通性，其应该具有更高的高Fiedler值，表明要将图分割成孤立的子图，需要切断更多的边。这通常表示图在整体上更加紧密连接，没有明显的弱连接点。右边的图具有更低的连通性，表明图可以通过切断较少的边来分割成不同的部分。这通常发生在图中存在一个或多个"瓶颈"区域，这些区域的边相对较少，是连接大的图区域的桥梁。

通过对两个图结构的拉普拉斯矩阵进行特征值分解发现，左边图结构的Fiedler值为4.0，而右边的为0.586左右。因此，说明左边图结构的连通性更强。

Thinking/ 思考

两点自己的思考：

1. 对于一个管网系统来说，Fiedler似乎可以反应该管网的冗余性，Fiedler值越大说明该管网中网状结构越多。
2. 如果对一个管网进行切分，是否可以设计一种算法，来使得切出来的这个分区的Fiedler值最小，这样就保证了“切最少的管道”就可以得到了这个分区。

链接密度

Link Density（链接密度）通常是用于网络分析中的一个概念，特别是在图论和社交网络分析中。它描述了网络中链接（或边）的数量与网络中可能存在的最大链接数量之间的比例。换句话说，它衡量了网络的饱和度或连接紧密程度。

$$ \text{Link Density} = \frac{2E}{N(N-1)} $$

其中：

• $ E $ 是图中实际存在的边的数量。
• $ N $ 是图中节点的数量。

对于一个有向图，由于边的方向性，计算公式略有不同：

$$ \text{Link Density} = \frac{E}{N(N-1)} $$

在这个公式中：

• $ E $ 仍然代表边的数量。
• $ N $ 代表节点的数量。
• 因子“2”在无向图中用于考虑每条边连接两个不同的节点，而在有向图中则不需要。

解释：

• 当Link Density接近1时，表示网络中的节点之间几乎全部相互连接，这是一个高度紧密的网络。
• 当Link Density接近0时，表示网络中的节点之间很少连接，这是一个稀疏网络。

举例：

import networkx as nx
import matplotlib.pyplot as plt

# 创建一个完全连接的网络（Link Density = 1）
G1 = nx.complete_graph(5)

# 创建一个稀疏连接的网络（较小的Link Density）
G2 = nx.Graph()
G2.add_edges_from([(0, 1), (1, 2), (3, 4)])  # 只添加几条边

# 绘制这两个网络
plt.figure(figsize=(12, 6))

# 绘制完全连接的网络
plt.subplot(121)
nx.draw(G1, with_labels=True, node_color='lightblue', node_size=800)
plt.title("Link Density = 1")

# 绘制稀疏连接的网络
plt.subplot(122)
nx.draw(G2, with_labels=True, node_color='lightgreen', node_size=800)
plt.title("Link Density < 1")

plt.show()

其实可以发现，对于一个图，如果Link Density=1，那么其就是一个完全图。

网格系数

网格系数（Meshedness Coefficient）是图论中用于特别衡量平面图的一个指标。它测量图中有界面的数量与具有相同顶点数量的其他平面图可能拥有的面的数量之间的比例。这个系数有助于理解图中的网格程度或互连程度。

• 网格系数为0表示树状结构，没有循环，代表最小的连通性。
• 系数为1代表最大平面图，表示高度互连的结构，具有最大数量的面。

在平面图中计算网格系数涉及计算有界面的数量（f）并将其与具有相同顶点数的图的最大可能面数进行比较。网格系数（M）的计算公式为：

$$ M = \frac{f - 1}{2v - 5} $$

其中：

• $ f $ 是图中有界面的数量；
• $ v $ 是图中顶点的数量。

Tips / 提示

什么叫做有界面的数量？在图论和网络分析中，"有界面的数量"（或简称为"面"）是指平面图中被边界包围的区域的数量。

编写一个计算网格系数的函数：

# 在NetworkX中计算网格系数
def calculate_meshedness(G):
    """计算网格系数"""
    # 计算有界面的数量：边的数量 - 顶点的数量 + 1
    f = G.number_of_edges() - G.number_of_nodes() + 1
    # 计算网格系数
    v = G.number_of_nodes()
    if v > 2:
        M = (f - 1) / (2 * v - 5)
    else:
        M = 0  # 对于少于3个顶点的图，网格系数无意义
    return M

代数连通性

代数连通性（Algebraic Connectivity）是图的拉普拉斯矩阵的第二小的特征值。

在 NetworkX 中，可以使用 nx.algebraic_connectivity(G) 函数来计算图 $G$ 的代数连通性。这个函数内部会完成上述的计算步骤，并返回代数连通性的值。

代数连通性通常也被称为Fiedler值。有关其更详细的解释，请看下面“特征值分解的意义”章节。

点中心性

点中心性（degree centrality）是最基本的中心性度量之一，它反映了节点的连接数相对于网络中可能的连接数的比例。在无向图中，点中心性简单地等于某个节点的邻接节点数（或者说是边数）除以可能的最大邻接节点数（即网络中节点总数减去1）。

对于网络中的节点 ( v )，其点中心性 ( C_D(v) ) 可以通过以下公式计算：

$$ C_D(v) = \frac{\text{节点 } v \text{ 的度数}}{N - 1} $$

其中，( N ) 是网络中节点的总数。

在 NetworkX 中，可以使用 degree_centrality(G) 函数来计算所有节点的点中心性。这个函数返回一个字典，其中键是节点，值是对应节点的点中心性。

中心点优势

Central-point dominance（中心点优势）是网络分析中的一个度量，用来量化网络中最中心节点的控制力相对于网络中其他节点的控制力。它是由Linton Freeman在1977年提出的。这个度量是基于中心性的概念，特别是点中心性（point centrality）。

在某个网络中，中心点优势是由网络中点中心性最高的节点（即最中心的节点）的点中心性值，减去网络中所有节点的点中心性平均值，再除以最大可能的差值来计算的。

计算步骤如下：

1. 计算网络中每个节点的点中心性（可以是接近中心性、介数中心性或特征向量中心性等）。
2. 找到具有最高点中心性的节点。
3. 计算该节点的点中心性与所有节点的点中心性平均值的差值。
4. 除以最大可能的差值，这通常是最中心节点的点中心性减去最小可能的点中心性（通常是1/n，其中n是节点总数）。

公式表示为：

$$ CPD = \frac{C_{max} - \overline{C}}{Max(C_{max} - C_i)} $$

其中：

• $ CPD $ 是中心点优势。
• $ C_{max} $ 是最高点中心性。
• $ \overline{C} $ 是所有节点点中心性的平均值。
• $ Max(C_{max} - C_i) $ 是最高点中心性与任意节点中心性之差的最大可能值。

在 NetworkX 中没有直接计算中心点优势的函数，但可以使用已有的中心性计算函数和一些额外的计算步骤来求解。

中心点优势的具体含义包括：

1. 网络权力集中度：CPD较高意味着网络中有一个或几个节点拥有远高于其他节点的中心性，表明网络中的权力或影响力可能非常集中。
2. 脆弱性和稳健性：当一个网络的CPD很高时，网络可能对最中心节点的移除或故障非常敏感。这可能会影响网络的整体功能和稳定性。
3. 信息流动和效率：一个中心点优势很高的网络可能会有更有效的信息流动，因为中心节点可以作为信息流动的枢纽。然而，这也可能导致信息过度集中，使得网络对于中心节点的依赖度增加。

Thinking/ 思考

在给水管网的图结构中，中心点优势（Central Point Dominance, CPD）可以有以下几种现实意义：

1. 关键节点的识别：高中心点优势意味着给水管网中存在一个或几个关键节点，这些节点对整个网络的运作至关重要。例如，这可能是主要的水源地、水处理中心或主要的分配点。
2. 网络脆弱性分析：如果给水管网的中心点优势很高，这可能表明网络对单个节点或几个节点的依赖性很大。这样的网络可能对于这些关键节点的故障或损坏特别敏感，从而影响整个网络的供水能力。
3. 优化和升级规划：通过分析中心点优势，可以识别那些对整个给水管网至关重要的节点，从而有助于优先考虑这些节点的维护、升级或加固，以提高网络的整体效率和可靠性。
4. 应急响应和风险管理：在应对突发情况（如管道破裂、污染事件等）时，了解中心点优势可以帮助决策者优先处理那些对整个网络影响最大的节点，从而更有效地减轻整体影响。
5. 提高供水效率：通过优化中心节点的运作，可以提高整个给水系统的供水效率和效果，确保水资源的合理分配和使用。

因此，在给水管网的管理和优化中，理解和分析中心点优势是非常重要的，它有助于指导网络设计、运维、危机管理和改进策略。

实际数据分析表明，CPD与管网节点数呈现略微正相关关系，这表明节点数越多的管网中，网络对单个节点或几个节点的依赖性越大。这是为什么呢？不科学啊？不应该是越大的管网抵抗风险的能力越强吗？

关键比例

"Critical Fraction"（关键比例）是网络科学中的一个概念，通常用于描述网络在遭受随机故障或有意攻击时维持功能的能力。具体来说，它指的是导致网络失去大规模连通性或功能的最小比例的节点或边的移除。这个概念在理解和评估网络的鲁棒性和脆弱性方面非常重要。

举个🌰，创建两个随机图结构：

import networkx as nx

# 创建两个网络
G_A = nx.erdos_renyi_graph(100, 0.05)  # 网络A
G_B = nx.watts_strogatz_graph(100, 4, 0.1)  # 网络B

# 准备绘制网络结构图和度分布统计图
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(16, 6))

# 在左边绘制网络图
nx.draw(G_A, ax=ax1, node_size=50, with_labels=False)
nx.draw(G_B, ax=ax2, node_size=50, with_labels=False)

ax1.set_title("Graph A")
ax2.set_title("Graph B")
plt.show()

定义一个计算关键比例的函数：

import random


def calculate_critical_fraction(G: nx.Graph, iter_num: int = 100) -> float:
    """
    图结构关键比例计算函数
    :param G: 图结构对象, nx.Graph格式
    :param iter_num: 随机循环数量, 通过多次重复移除节点的实验, 并计算每次实验的关键比例, 然后取这些实验的平均值.
    :return: 多次计算关键比例的平均值,范围[0, 1]
    """
    ratio = []

    for _ in range(iter_num):
        # 复制原始网络
        G_temp = G.copy()
        # 计算原始网络中最大连通分量的节点数
        original_size = max(len(c) for c in nx.connected_components(G_temp))
        for i in range(len(G_temp)):
            # 随机选择并移除一个节点
            node_to_remove = random.choice(list(G_temp.nodes()))
            G_temp.remove_node(node_to_remove)

            # 计算移除节点后网络中最大连通分量的节点数
            largest_cc_size = max(len(c) for c in nx.connected_components(G_temp))
            if largest_cc_size <= original_size / 2:  # 如果移除节点后, 网络中最大连通分量的节点数小于原始网络中的1/2
                ratio.append(i)
                break

    # 返回平均关键比例
    return sum(ratio) / len(ratio) / len(G)

对比两个图结构的关键比例：

critical_fraction_A = calculate_critical_fraction(G_A.copy())
critical_fraction_B = calculate_critical_fraction(G_B.copy())

print("Critical Fraction of Network A:", critical_fraction_A)
print("Critical Fraction of Network B:", critical_fraction_B)

Critical Fraction of Network A: 0.45640000000000003
Critical Fraction of Network B: 0.3701

比较两个网络的平均关键比例，发现$CF_A>CF_B$，说明网络B在面临随机故障时更加脆弱。

Thinking/ 思考

感觉“关键比例”这个概念不适合用于对比两个给水管网在面临随机故障时的脆弱性。因为给水管网中节点的重要性并是仅仅是看哪个节点的度比较大（给水管网中节点的度都在1~4之间）。关键比例仅仅对比两个管网在随机减少节点后，具有最大连通分量的节点数量，这对于给水管网来说并不合理。

图的特征值分解

下面的讲解以Introduction to Graph Signal Processing中P19页的Fig. 10（图1，连通图）、P14页的Fig. 7（图2，非连通图）为例。

G_strong = nx.Graph()
G_strong.add_edges_from([
    (0, 1), (0, 2), (0, 7),
    (1, 2), (1, 3), (1, 4), (1, 7),
    (2, 3),
    (3, 4), (3, 5), (3, 7),
    (4, 5), (4, 6), (4, 7),
    (5, 6)
])

G_weak = nx.Graph()
G_weak.add_edges_from([
    (0, 1), (0, 2),
    (1, 2),
    (3, 4), (3, 5), (3, 7),
    (4, 5), (4, 6), (4, 7),
    (5, 6)
])

# 绘制这两个图
plt.figure(figsize=(12, 6))

plt.subplot(1, 2, 1)
nx.draw(G_strong, with_labels=True, node_color='lightblue', node_size=700)
plt.title("Strongly Connected Graph")

plt.subplot(1, 2, 2)
nx.draw(G_weak, with_labels=True, node_color='lightgreen', node_size=700)
plt.title("Weakly Connected Graph")

plt.show()

特征值分解的意义

邻接矩阵更倾向于揭示图的整体连通性，而拉普拉斯矩阵的特征值和特征向量则更多地用于研究图的局部结构特征，如社区结构或者图的连通分量。

为什么拉普拉斯矩阵的第一个特征值总是0？

拉普拉斯矩阵的第一个特征值总是0，其对应的特征向量是一个所有元素都相同的向量。这代表图中所有节点的均匀分布。

拉普拉斯矩阵 $ L $ 的第一个特征值总是 0 的原因与拉普拉斯矩阵的定义和图的性质有关。拉普拉斯矩阵 $ L $ 定义为度矩阵 $ D $ 减去邻接矩阵 $ A $，即 $ L = D - A $。

这里是为什么其第一个特征值总是 0：

1. 和为零的行（列）：在拉普拉斯矩阵中，每一行的和（以及每一列的和，因为 $ L $ 是对称的）都是 0。这是因为每一行的非对角元素（即 $-A$ 的部分）与对角线上的元素（即 $ D $ 的部分，它是节点的度数）相加抵消。换句话说，对于每个节点 $ i $，它的度数 $ D_{ii} $ 等于与它相连的边的数量，而 $ -A $ 中的元素表示与节点 $ i $ 相连的邻居节点，因此当你在一行中把这些值加起来时，结果是 0。
2. 恒等特征向量：由于每行的和为零，这意味着全 1 向量（所有元素都是 1 的向量）是拉普拉斯矩阵的一个特征向量，因为 $ L \times \textbf{1} = \textbf{0} $（其中 $\textbf{1}$ 是全1向量，$\textbf{0}$ 是零向量）。这意味着乘以全 1 向量后，每行的元素相加都得到 0，这与零向量相匹配。
3. 特征值 0 的意义：特征值 0 对应的特征向量表示图中所有节点的均匀分布，它反映了图的连通性。对于连通图，特征值 0 是唯一的，它的代数重数（特征值的重复次数）等于图的连通分量的数量。因此，对于连通图，特征值 0 的代数重数是 1。如果图不是完全连通的，特征值 0 的代数重数将等于图的连通分量数量。

简而言之，拉普拉斯矩阵的每一行和每一列的和为零这个属性保证了第一个特征值必定是0。这与图的基本性质密切相关，特别是与图的连通性有关。

其他特征值的意义：

1. 第二个特征值（Fiedler值）和特征向量：

   • 第二个最小的特征值通常被称为Fiedler值，它在图的谱聚类和社区检测中非常重要。Fiedler值的大小可以表示图的连通性：Fiedler值越小，图的连通性越弱。
   • 对应的Fiedler向量可以用来识别图中的社区或集群。通过分析Fiedler向量的组件，可以将图划分为不同的部分，其中每个部分相对内部紧密连接，而与其他部分的连接较少。

2. 其他特征值和特征向量：

   • 更高的特征值和对应的特征向量可以揭示图的更复杂的结构特征，如多层次的社区结构。
   • 在某些情况下，这些特征向量也用于嵌入技术，将图的节点映射到低维空间，以便于可视化和进一步分析。

特征值分解

下面对上面的示例图进行拉普拉斯矩阵的特征值分解。

拉普拉斯矩阵

首先，获取图结构的拉普拉斯矩阵：

# 获取拉普拉斯矩阵
L = nx.laplacian_matrix(G).toarray()
L

$$ \begin{bmatrix} 3 & -1 & -1 & -1 & 0 & 0 & 0 & 0 \\ -1 & 5 & -1 & -1 & -1 & -1 & 0 & 0 \\ -1 & -1 & 3 & 0 & -1 & 0 & 0 & 0 \\ -1 & -1 & 0 & 4 & -1 & -1 & 0 & 0 \\ 0 & -1 & -1 & -1 & 5 & -1 & -1 & 0 \\ 0 & -1 & 0 & -1 & -1 & 5 & -1 & -1 \\ 0 & 0 & 0 & 0 & -1 & -1 & 3 & -1 \\ 0 & 0 & 0 & 0 & 0 & -1 & -1 & 2 \\ \end{bmatrix} VS \begin{bmatrix} 2 & -1 & -1 & 0 & 0 & 0 & 0 & 0 \\ -1 & 2 & -1 & 0 & 0 & 0 & 0 & 0 \\ -1 & -1 & 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 & -1 & -1 & -1 & 0 \\ 0 & 0 & 0 & -1 & 4 & -1 & -1 & -1 \\ 0 & 0 & 0 & -1 & -1 & 3 & 0 & -1 \\ 0 & 0 & 0 & -1 & -1 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & -1 & -1 & 0 & 2 \\ \end{bmatrix} $$

需要注意的是，返回的拉普拉斯矩阵的行列顺序并不与图中的顺序相同，矩阵中的行列数据是按照节点的添加顺序来的。如何查看节点的顺序：

list(G.nodes())
# [0, 1, 2, 7, 3, 4, 5, 6]

对于图1来说，因为节点7添加的早，所以排在节点3之前。也就是说，拉普拉斯矩阵中第4行代表的是第7个元素的连接情况。

特征值

#求矩阵特征值以及特征向量
eig_value, eig_vector = np.linalg.eig(L)
eig_value

特征值及其可视化：

$$ [4.44089210e-16, 1.13357211e+00, 3.05427452e+00, 3.31740297e+00, 4.00000000e+00, 5.67905993e+00, 6.47332881e+00, 6.34236165e+00] $$

def autolabel(rects):
    for rect in rects:
        height = rect.get_height()
        height_pos = height + .1 if height >= -0.1 else height - .1
        plt.text(
            rect.get_x() + rect.get_width() / 2,
            height_pos,
            '{:.5f}'.format(height),
            size=10,
            family="Times new roman",
            horizontalalignment='center',
            verticalalignment='center'
        )


fig = plt.bar([i for i in range(len(eig_value))], np.sort(eig_value))
autolabel(fig)

plt.title('Eigenvalues')
plt.show()

图1有一个接近零的特征值，表明图是连通的。图2特征值有两个接近于零的值，这与图中的两个连通分量相对应。特征值为0的数量恰好等于图的连通分量的数量。

图2的 Fiedler 值（最小非0值）为1.58，该 Fiedler 值对应的特征向量是：

$$ \begin{bmatrix} 0. \\ 0. \\ 0. \\ -0.4472136 \\ -0.4472136 \\ -0.4472136 \\ -0.4472136 \\ -0.4472136 \\ \end{bmatrix} $$

说明，该 Fiedler 值代表的是3、4、5、6、7节点对应的连通分量的连通性。

总结：图1的连通性更强，因为其特征值中仅有一个为0；图2包含两个连通分量，因为其特征值中包含两个0。图2中3、4、5、6、7节点组成的连通分量的连通性要高于图1整体的连通性。因为图2中3、4、5、6、7节点组成的连通分量的 Fiedler 值为1.58，大于图1整体的连通分量1.13。

Fiedler 值也被称为代数连通性，它反映了图的稀疏性或稠密性。一个较高的Fiedler值意味着图具有较强的连通性，而较低的Fiedler 值则意味着图可能容易被分割成独立的组件。

Thinking/ 思考

管网数据分析表明：随着管网中节点数的增多，Fiedler 值（代数连通性）越来越小，说明越大的管网环状比例越小。是不是可以这样理解为：大部分管网新建的时候都是城区环状管网，随着城市的发展，开始逐渐向周围以支状管网扩散，这就导致了大型管网的环状比例都较小。

特征向量

特征向量（图1）：

$$ \begin{bmatrix} 0.35355339 & 0.40809973 & -0.38534069 & -0.32322928 & 0.61237244 & 0.10317586 & -0.24182446 & 0.10660991 \\ 0.35355339 & 0.21821011 & 0.07059821 & -0.06640201 & -0.20412415 & 0.58748394 & 0.64631494 & 0.11603433 \\ 0.35355339 & 0.36261755 & -0.3221172 & 0.67753284 & -0.20412415 & -0.23709192 & -0.00834996 & -0.28766179 \\ 0.35355339 & 0.18086105 & 0.27243317 & -0.5085369 & -0.20412415 & -0.62680632 & 0.20197088 & -0.18470141 \\ 0.35355339 & 0.05048967 & 0.33222523 & 0.17458035 & -0.20412415 & -0.05547633 & -0.37548832 & 0.7388255 \\ 0.35355339 & -0.15837433 & 0.24016423 & -0.13207484 & -0.20412415 & 0.41726191 & -0.52854257 & -0.52883224 \\ 0.35355339 & -0.40809973 & 0.38534069 & 0.32322928 & 0.61237244 & -0.10317586 & 0.24182446 & -0.10660991 \\ 0.35355339 & -0.65380405 & -0.59330365 & -0.14509945 & -0.20412415 & -0.08537128 & 0.06409502 & 0.14633561 \\ \end{bmatrix} $$

将特征值从小到大排序，然后可视化特征向量：

def plot_eigenvectors(value, vector):
    vector = vector[:, np.argsort(value)]
    value = np.sort(value)

    # plt.figure(dpi=100)
    fig, ax_arr = plt.subplots(len(value), 1, sharex='col', sharey='row', figsize=(5, 2 * len(value)))
    fig.subplots_adjust(hspace=0.05, wspace=0.03)

    for i in range(len(value)):
        ax_arr[i].stem([i for i in range(len(value))], vector[:, i])
        ax_arr[i].set_ylabel(f'$u_{{{i}}}(n)$')


plot_eigenvectors(eig_value, eig_vector)

上面两个图是按照特征值排序后的特征向量，下面依次来解释特征向量有着什么样的含义：

• 第一个特征向量的含义：对于任何图，拉普拉斯矩阵的第一个特征值总是0。对于零特征值，其对应的特征向量（通常是一个所有元素都相等的向量）实际上表示了图中所有节点的一种“平均”状态或者均匀状态。对于连通图（图1），这反映了图中所有节点在某种意义上是等价的，没有任何节点是孤立的。对于非连通图（图2），对于非连通图，拉普拉斯矩阵的零特征值的个数等于图的连通分量的数量，每个零特征值的特征向量反映了对应连通分量中的节点关系。例如图2的第一个特征向量有三个值不为0，那么就说明图2的第一个连通分量中有三个元素；第二个特征向量有四个值不为0，那么就说明第二个连通分量中有四个元素。总的来说，连通图的第一个特征向量不反映任何局部结构或节点间的差异，而是显示了图作为一个整体的特性，即全局特征。
• Fiedler向量（第二个特征向量）：在Fiedler向量中，正值和负值分别代表了图中的不同群体，这种划分往往揭示了图的潜在社区结构，其中社区内部的节点比跨社区的节点更紧密地连接。例如图1中，Fiedler向量的前5个值为负值，后3个为正值，这说明图1更容易分为两个簇：前5个节点（0、1、2、7、3）、后3个节点（4、5、6）。

Thinking/ 思考

除了可以根据Fiedler向量对图中节点进行简单的正负划分外，还可以根据不同值的接近程度进行更为细致的划分。例如，假设一个Fiedler向量为[-100,-99,-1,2,3,6,7,8]：

1. 基本的二分法：首先，根据Fiedler向量的正负符号，可以将图分为两个主要群体：

   • 第一个群体：包含节点1、2、3（对应于Fiedler向量中的值为-100, -99, -1）；
   • 第二个群体：包含节点4、5、6、7、8（对应于Fiedler向量中的值为2, 3, 6, 7, 8）。

2. 更细致的分组：在每个主要群体内，可以根据Fiedler向量值的接近程度进行更细致的分组：

   • 在第一个主要群体中，节点1和2（Fiedler向量值为-100和-99）更接近彼此，而节点3（值为-1）相对较远；
   • 在第二个主要群体中，节点4和5（Fiedler向量值为2和3）更接近彼此，而节点6、7、8（值为6, 7, 8）更接近彼此。

如果Fiedler向量的这种特性，在管网的图结构中，是否可以对管网中的节点进行分类，分为不同的簇，进而达到简化管网的目的？