「图论入门」从基础概念到NetworkX

介绍

图（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 数组。

关联矩阵

在 networkx 库中，nx.incidence_matrix(G) 用于生成图 G 的关联矩阵（Incidence Matrix）。关联矩阵和邻接矩阵不同，它是一种表示图中节点与边之间关系的矩阵。

对于一个包含 $ N $ 个节点和 $ M $ 条边的图，其关联矩阵是一个 $ N \times M $ 的矩阵，其中矩阵的行对应图中的节点，列对应图中的边。关联矩阵中的元素定义如下：

• 如果边 $ e $ 与节点 $ v $ 相连，则矩阵中对应位置的值为 1（或者对于有向图，出边为 -1，入边为 1）；
• 如果边 $ e $ 与节点 $ v $ 不相连，则对应位置的值为 0。

举个例子：

# 创建一个图
G = nx.Graph()
G.add_edges_from([(0, 1), (0, 2), (1, 2)])

# 获取关联矩阵
inc_matrix = nx.incidence_matrix(G)

# 绘制节点和边
pos = nx.spring_layout(G)  # 生成节点的布局
nx.draw(G, pos, node_size=500, with_labels=True)

# 为每条边创建一个标签（例如，使用边的索引作为标签）
edge_labels = {edge: i for i, edge in enumerate(G.edges())}

# 将边的标签添加到图中
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=20)

获取关联矩阵：

inc_matrix.toarray()

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

下面的演示均以：

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 / 参考

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

幂律分布：

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

指数分布：

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

平均近邻度

平均近邻度（Average Nearest Neighbor Degree, Average Neighbor Degree）是指网络中一个节点的邻居节点的平均度数。这个指标可以用来判断网络中的节点是否倾向于与相似或不同度数的其他节点相连。

平均近邻度的计算方法是：

• 对于网络中的每个节点，计算其所有邻居节点的度数。
• 对这些度数求平均值。
• 重复此过程，计算所有节点的平均近邻度。

公式为：

$$ k_{nn,i} = \frac{1}{k_i} \sum_{j \in \mathcal{N}(i)} k_j $$

其中，$ \mathcal{N}(i) $ 是节点 $ i $ 的邻居集合，$ k_i $ 是节点 $ i $ 的度数，$ k_j $ 是 $ i $ 的邻居节点 $ j $ 的度数。

相关性(匹配)系数

相关性(匹配)系数（Assortativity Coefficient, Degree Correlation Coefficient）衡量的是网络中高度数的节点倾向于与其他高度数的节点相连（正相关），还是与低度数的节点相连（负相关）。

相关性系数的计算方法是：

• 计算网络中每对连接节点的度数乘积。
• 对这些乘积求平均值。
• 计算度数的平均值的平方和度数平方的平均值。
• 将这些值代入皮尔逊相关系数的公式中。

公式为：

$$ r = \frac{M^{-1} \sum_{i,j} A_{ij} k_i k_j - [M^{-1} \sum_{i} k_i]^2}{M^{-1} \sum_{i} k_i^2 - [M^{-1} \sum_{i} k_i]^2} $$

其中，$ A_{ij} $ 是邻接矩阵中的元素，$ k_i $ 和 $ k_j $ 是节点的度数，$ M $ 是边的总数。

下面举个例子对比分析下平均近邻度与相关性(匹配)系数：

创建两个网络结构：

# 创建两个不同的网络结构
# 网络1：经典的Erdős-Rényi随机图
G1 = nx.erdos_renyi_graph(n=100, p=0.05)
# 网络2：Barabási-Albert无标度网络
G2 = nx.barabasi_albert_graph(n=100, m=2)

计算两个网络的相关性（匹配）系数：

G1_r = nx.degree_pearson_correlation_coefficient(G1)
G2_r = nx.degree_pearson_correlation_coefficient(G2)

计算两个网络的平均近邻度：

average_neighbor_degree_G1 = nx.average_neighbor_degree(G1)
average_neighbor_degree_G2 = nx.average_neighbor_degree(G2)

# 计算两个网络的平均近邻度的平均值
G1_and =sum(average_neighbor_degree_G1.values()) / len(average_neighbor_degree_G1)
G2_and = sum(average_neighbor_degree_G2.values()) / len(average_neighbor_degree_G2)

绘图可视化观察：

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

ax1.set_title(f"Graph A, r={round(G1_r, 3)}, and={round(G1_and, 3)}")
ax2.set_title(f"Graph B, r={round(G2_r, 3)}, and={round(G2_and, 3)}")
plt.show()

• 相关性（匹配）系数：两个网络都显示出负相关性，但Barabási-Albert无标度网络（Graph B）的负相关性更强。这表明在无标度网络中，网络中的枢纽（高度数的节点）更可能与度数较低的节点相连，这是典型的无标度网络特性。
• 平均近邻度：Barabási-Albert无标度网络的平均近邻度高于Erdős-Rényi随机图。这反映了无标度网络中节点连接的非均匀性，其中一些节点（即枢纽）与大量其他节点相连，从而提高了平均近邻度。

总的来说，这两个网络展现出不同的结构特征，无标度网络的节点连通性更加集中和不均匀，而随机图则表现出更均匀的连接模式。这些特性在网络的稳定性和动态行为上有重要影响，例如在信息传播或疾病传播的研究中。

拉普拉斯矩阵

拉普拉斯矩阵（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.laplacian_matrix(G)：返回G的拉普拉斯矩阵；
• nx.directed_laplacian_matrix(G)：返回有向图的拉普拉斯矩阵；
• nx.normalized_laplacian_matrix(G)：返回G的标准化拉普拉斯矩阵。

路径和距离

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

• 路径（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}")

节点间最短路径和距离

获取节点间最短路径和距离：

i, j = 1, 3
print(nx.shortest_path(G, i, j), nx.shortest_path_length(G, i, j))

获取节点间的所有路径

# 寻找所有简单路径
paths = list(nx.all_simple_paths(G, 6, 0))

print("所有简单路径:")
for path in paths:
    print(path)

# 独立路径的数量
print("独立路径的数量:", len(paths))

这个代码计算了从节点 6 到节点 0 的所有简单路径。请注意，这些路径可能在某些较复杂的图结构中共享边。如果你的网络足够大或复杂，计算所有独立路径的数量可能会变得非常困难，甚至不可行，因为可能的路径数量随着网络的大小和复杂性指数级增长。

离心率

离心率（Eccentricity）用于描述一个节点到图中所有其他节点的最短路径中最长的那一个。对于图中的节点 v，其离心率定义为从 v 到图中所有其他节点的最短路径的最大长度。公式表示为：

$$ \text{Eccentricity}(v) = \max_{u \in G} d(v, u) $$

其中，d(v, u) 是节点 v 和 u 之间的最短路径长度。

• 如果不指定节点 v，nx.eccentricity(G) 返回一个字典，包含图 G 中每个节点的离心率。
• 如果指定节点 v，nx.eccentricity(G, v) 返回节点 v 的离心率。

• 离心率仅适用于连通图。在不连通的图中，某些节点间可能不存在路径，因此无法计算离心率。
• 在有向图中，应考虑路径的方向性，这可能影响离心率的计算结果。

网络直径

网络直径是图论中的一个重要概念，它指的是网络中所有节点对的最短路径中最长的那一个。

对于连通图：

# 计算直径
diameter = nx.diameter(G)
print("网络的直径是:", diameter)

如果图不连通（即存在不可达的节点对），这个函数将会抛出错误。在处理不连通图时，你可能需要先找出图中的连通分量，然后分别计算每个连通分量的直径。

G = nx.Graph()

G.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),
    (8,9),(9,10),(10,8)
])

nx.draw(G, node_size=500, with_labels=True)

# 找出所有连通分量
connected_components = nx.connected_components(G)

# 遍历每个连通分量，并计算其直径
for i, component in enumerate(connected_components):
    subgraph = G.subgraph(component)
    diameter = nx.diameter(subgraph)
    print(f"连通分量 {i+1} 的直径是: {diameter}")

离心率（Eccentricity）和图的直径（Diameter）是图论中两个密切相关的概念，它们都与图中节点间距离的概念有关。

1. 离心率（Eccentricity）：公式表示为：$ \text{eccentricity}(v) = \max_{u \in G} d(v, u) $，其中 $ d(v, u) $ 是节点 $ v $ 到节点 $ u $ 的最短路径长度。
2. 图的直径（Diameter）：$ \text{diameter}(G) = \max_{v \in G} \text{eccentricity}(v) $。

图的直径实际上是图中所有节点离心率的最大值。换句话说，直径是图中具有最大离心率的节点的离心率。一个节点的离心率告诉我们从该节点到达图中任何其他节点所需的最长距离。而图的直径则告诉我们在整个图中，任意两个节点之间的最长最短路径长度。

在一个连通图中，最远的节点对的最短路径长度等于该图的直径。

因此，离心率和直径都是衡量图中节点间距离的重要指标，但离心率着重于单个节点与其他所有节点的最远距离，而直径关注的是整个图中任意两个节点间的最远距离。

效率、平均局部效率、全局效率

1. 节点对之间的效率（Efficiency between Node Pairs）:

   • 定义：节点对之间的效率是衡量这两个节点之间路径效率的指标。它是节点间最短路径的倒数。
   • 公式：$E_{ij} = \frac{1}{d(i, j)}$，其中，$ E_{ij} $ 是节点 $ i $ 和节点 $ j $ 之间的效率，$ d(i, j) $ 是它们之间的最短路径长度。
   • NetworkX代码：nx.efficiency(G, 3, 7)。

2. 平均局部效率（Average Local Efficiency）:

   • 定义：平均局部效率是网络中每个节点的局部效率的平均值。局部效率是一个节点的邻居间效率的平均值。
   • 公式：$E_{local}(i) = \frac{1}{N_i} \sum_{j, h \in G_i, j \neq h} \frac{1}{d(j, h)}$，其中，$ G_i $ 是节点 $ i $ 的邻居子图，$ N_i $ 是子图中节点的数量，$ d(j, h) $ 是子图中节点 $ j $ 和 $ h $ 之间的最短路径长度。
   • NetworkX代码：nx.local_efficiency(G)。

3. 全局效率（Global Efficiency）:

   • 定义：全局效率是网络中所有节点对效率的平均值。它反映了网络整体的交换或通信效率。
   • 公式：$E_{global} = \frac{1}{N(N-1)} \sum_{i \neq j \in G} \frac{1}{d(i, j)}$，其中，$ N $ 是图中的节点总数。
   • NetworkX代码：nx.global_efficiency(G)。

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

演示实例：

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值与图连通性的关系

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

# 创建具有较强连通性的图（低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值，表明要将图分割成孤立的子图，需要切断更多的边。这通常表示图在整体上更加紧密连接，没有明显的弱连接点。右边的图具有更低的连通性，表明图可以通过切断较少的边来分割成不同的部分。这通常发生在图中存在一个或多个"瓶颈"区域，这些区域的边相对较少，是连接大的图区域的桥梁。

[photos]

[/photos]

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

Thinking/ 思考

两点自己的思考：

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

遍历所有连通分量

请查看上面“网络直径”一节中，如何遍历图中所有连通分量并获取其网络直径。

节点对之间的连通性

在图论中，节点连通性是指在不破坏图的连通性的情况下，可以从图中移除的最小节点数，以便特定的两个节点不再连通。换句话说，它是指在保持图的连通性的前提下，需要移除的节点数，才能使得这两个节点不再通过任何路径相连。

获取所有节点对之间的连通性：

from networkx.algorithms import approximation as approx

# 计算所有节点对之间的节点连通性：独立路径数量
print(approx.all_pairs_node_connectivity(G))

获取单个节点对之间的连通性：

approx.local_node_connectivity(G, 6, 0)

上面的代码返回结果是2，就代表图中节点6与节点0之间的连通性是2。也就说明，如果要破坏节点2与节点6之间的连通性，最少要移除两条边才可以。

全局连通性

全局连通性是指整个图的最小节点连通性，也就是在保持图连通的情况下，需要从图中移除的最少节点数，使得图变得不连通。

approx.node_connectivity(G)

函数将返回图 $G$ 的节点连通性，即使图变得不连通所需移除的最少节点数。这个值为整个图的一个全局度量，而不是针对特定节点对的。

一个特殊的图结构——柏拉图式的八面体图：

G2 = nx.octahedral_graph() # 柏拉图式的八面体图
nx.draw(G2, node_size=500, with_labels=True)

print(approx.all_pairs_node_connectivity(G2))
print(approx.node_connectivity(G2))

这个图结构所有节点间的连通性都是4。因此，其全局连通性也是4。

NetworkX中关于连通分量的一些其他操作

获取连通组件（子图）的数量：

print(nx.number_connected_components(G))

对所有联通分量按照节点数的多少排序，获取最大连通子图并绘图：

Gcc = sorted(nx.connected_components(G), key=len, reverse=True)

# 获取最大连通子图
largest_cc = G.subgraph(Gcc[0])
nx.draw(largest_cc, node_size=500, with_labels=True)

复制连通分量，并进行修改：

# largest_cc.add_edge(3,6) # 连通子图不支持修改：NetworkXError: Frozen graph can't be modified
# 可以复制，在复制的图上修改
LCC = largest_cc.copy()
LCC.add_edge(3,6)
nx.draw(LCC, node_size=500, with_labels=True)

链接密度

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()

在NetworkX中获取图结构的连接密度：

print(nx.density(G1), nx.density(G2))

其实可以发现，对于一个图，如果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 $，其度中心性（Degree Centrality） $ C_D(v) $ 可以通过以下公式计算：

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

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

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

其他几种中心性

1. 特征向量中心性（Eigenvector Centrality）:

   • 定义：特征向量中心性考虑了一个节点的邻居的重要性。一个节点的特征向量中心性高，如果它连接到许多其他具有高中心性的节点。
   • 公式：$ C_E(v) = \frac{1}{\lambda} \sum_{t \in M(v)} C_E(t) $
     其中，$ C_E(v) $ 是节点 $ v $ 的特征向量中心性，$ M(v) $ 是与 $ v $ 直接相连的节点集合，$ \lambda $ 是特征值。

2. 接近度中心性（Closeness Centrality）:

   • 定义：接近度中心性基于节点到网络中所有其他节点的平均最短路径长度。距离越短，接近度中心性越高。
   • 公式：$ C_C(v) = \frac{N-1}{\sum_{t \neq v} d(v, t)} $，其中$ C_C(v) $ 是节点 $ v $ 的接近度中心性，$ d(v, t) $ 是节点 $ v $ 到 $ t $ 的最短路径长度。

3. 介数中心性（Betweenness Centrality）:

   • 定义：介数中心性是基于节点在网络中所有最短路径中出现的频率。一个节点的介数中心性高，如果更多的最短路径通过它。
   • 公式：$ C_B(v) = \sum_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}} $，其中，$ C_B(v) $ 是节点 $ v $ 的介数中心性，$ \sigma_{st} $ 是节点 $ s $ 到 $ t $ 的所有最短路径的数量，$ \sigma_{st}(v) $ 是经过节点 $ v $ 的那些路径的数量。

4. PageRank中心性（PageRank Centrality）:

   • 定义：PageRank是衡量网页重要性的算法，但也可用于网络中。一个节点的PageRank高，如果有许多其他高PageRank的节点指向它。
   • 公式：$ PR(v) = \frac{1-d}{N} + d \sum_{t \in M(v)} \frac{PR(t)}{L(t)} $，其中，$ PR(v) $ 是节点 $ v $ 的PageRank值，$ M(v) $ 是指向 $ v $ 的节点集合，$ L(t) $ 是节点 $ t $ 的出度，$ d $ 是阻尼系数（通常设为0.85）。

如何在NetworkX中获得：

# 度中心性（Degree Centrality）
nx.degree_centrality(G)

# 特征向量中心性（Eigenvector Centrality）
nx.eigenvector_centrality(G)

# 接近度中心性（Closeness Centrality）
nx.closeness_centrality(G)

# 介数中心性（Betweenness Centrality）
nx.betweenness_centrality(G)

# PageRank中心性（PageRank Centrality）
nx.pagerank(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之间）。关键比例仅仅对比两个管网在随机减少节点后，具有最大连通分量的节点数量，这对于给水管网来说并不合理。

K核值

节点的 k-核（k-core）是一个网络分析中的概念，用于识别网络中的一个最大子图，在这个子图中，每个节点至少与 k 个其他节点相连。计算一个网络中所有节点的 k-核值的过程涉及到逐步移除度数小于 k 的节点，直到所有剩余的节点度数都大于或等于 k。

举个例子就明白了，创建一个图结构：

# 创建图
G = nx.Graph()
G.add_node('W')
G.add_edges_from([('A', 'B'), ('A', 'C'), ('A', 'D'),
                 ('B', 'C'), ('C', 'D'), ('E', 'F'), ('B', 'D'), ('B', 'G'), ('G', 'C')])

nx.draw(G, node_size=500, with_labels=True)

分别获取并绘制上面图结构中K核值为1、2、3的节点：

import matplotlib.pyplot as plt
plt.rcParams.update({
'font.size': 20,
'font.family': ['Times New Roman', 'SimSun']
})

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

k_1 = nx.k_core(G, k=1)
k_2 = nx.k_core(G, k=2)
k_3 = nx.k_core(G, k=3)

# 在左边绘制网络图
nx.draw(k_1, ax=ax1, node_size=500, with_labels=True, node_color='r')
nx.draw(k_2, ax=ax2, node_size=500, with_labels=True, node_color='g')
nx.draw(k_3, ax=ax3, node_size=500, with_labels=True, node_color='b')

ax1.set_title('K=1')
ax2.set_title('K=2')
ax3.set_title('K=3')
plt.show()

这个时候就很容易明白K核值的定义了：nx.k_core(G, k=1)返回的是图结构中度≥1的节点；nx.k_core(G, k=2)返回的是图结构中度≥2的节点；nx.k_core(G, k=3)返回的是图结构中度≥3的节点。

打印单个节点的K核值：

for node, k_core in k_core_values.items():
    print("节点", node, "的K核值是", k_core)

我们会发现打印结果与上面的分析结论是一样的。

度同配性

如果网络中度数相似的节点倾向于相互连接，即高度数的节点倾向于与其他高度数的节点相连，低度数的节点倾向于与其他低度数的节点相连，这种现象称为度同配（Assortative Mixing）。

度同配性（Degree Assortativity）度同配性系数是一个介于 -1 和 1 之间的数值，用来量化度同配性的程度。系数接近 1 表示强同配性，即网络中类似度数的节点倾向于相互连接。系数接近 -1 表示强异配性，即网络中不同度数的节点倾向于相互连接。

在 networkx 中，可以使用 nx.degree_assortativity_coefficient(G) 来计算图 G 的度同配性系数。这个函数会考虑图中每个节点的度数，并计算整个网络的度同配性。

度同配性系数的计算涉及到评估网络中节点的度数（即每个节点的连接数）之间的相关性。具体计算方法基于皮尔逊相关系数，但是针对的是节点的度数而不是节点的特征或标签。

计算步骤：

1. 准备数据：

   • 对于每条边，考虑其两个端点的度数。例如，如果一条边连接度为2的节点和度为3的节点，则这条边对应于（2,3）和（3,2）两组度数对。

2. 计算平均度数和方差：

   • 计算网络中所有节点度数的平均值和方差。

3. 计算协方差：

   • 对于所有边的度数对，计算它们的协方差。协方差测量两个变量（在这里是度数）之间的总体偏差。

4. 应用皮尔逊相关系数公式：

   • 使用下面的公式计算度同配性系数：$r = \frac{\sum_{xy} xy(e_{xy} - a_x a_y)}{\sigma_a \sigma_b}$。其中，$ e_{xy} $ 是连接度数为 $ x $ 和 $ y $ 的节点的边的比例，$ a_x $ 是度数为 $ x $ 的节点的比例，$ \sigma_a $ 和 $ \sigma_b $ 是度分布的标准差。

桥连接

（这个🌉名词实在是不知道怎么翻译……）

在图论中，桥是指图中的一条边，移除它会导致图的连通性分量增加。换句话说，桥是连接图中两个部分的唯一边，移除它会使这两部分变得不连通。举个例子：

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

G_weak = G_strong.copy()
G_weak.remove_edge(3, 5)

# 绘制这两个图
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(f"Graph with a bridge{list(nx.bridges(G_strong))[0]}")

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

plt.show()

上面的左图中，边 (3, 5)就是一个Bridge，因为当切断这条边时，该图就会变成两个连通分量。

桥连接分析网络的结构稳定性和脆弱性时非常有用，特别是在识别网络中的关键连接或潜在的脆弱点方面。

在NetworkX 库中：

• nx.has_bridges(G)：返回一个Bool值，返回 True，则表示图 G 中至少有一条边是桥；如果返回 False，则表示图中没有桥。
• nx.bridges(G)：返回一个可迭代对象，包含了网络中的所有桥。

补充个知识点，还有个东西叫做“本地桥”，在NetworkX 库中使用nx.local_bridges(G)即可获取。

还是举个例子来说明吧：

import networkx as nx

# 创建一个图
G = nx.Graph()
G.add_edges_from([
    ('A', 'B'),
    ('B', 'C'),
    ('C', 'D'),
    ('D', 'A'),
])

# 找出所有桥
print("图中的桥:")
for bridge in nx.bridges(G):
    print(bridge)

# 找出所有本地桥
print("\n图中的本地桥:")
for local_bridge in nx.local_bridges(G, with_span=True):
    print(local_bridge)

nx.draw(G, with_labels=True, node_color='lightblue', node_size=700)

在上面的图结构中，没有桥，因为断开任何一条边也不能让图变成两个连通分量。所谓“本地桥”是指，桥两端的节点在桥断开后，没有共同的节点相连。

将上面的图结构中，添加一个点E，使其与点A、点D相连，那么桥 (A, D ) 就不是本地桥了：

G.add_edges_from([
    ('E', 'A'),
    ('E', 'D')
])

# 找出所有桥
print("图中的桥:")
for bridge in nx.bridges(G):
    print(bridge)

# 找出所有本地桥
print("\n图中的本地桥:")
for local_bridge in nx.local_bridges(G, with_span=True):
    print(local_bridge)

nx.draw(G, with_labels=True, node_color='lightblue', node_size=700)

图的特征值分解

下面的讲解以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()

[photos]

[/photos]

图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)

[photos]

[/photos]

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

• 第一个特征向量的含义：对于任何图，拉普拉斯矩阵的第一个特征值总是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向量的这种特性，在管网的图结构中，是否可以对管网中的节点进行分类，分为不同的簇，进而达到简化管网的目的？

NetworkX中获取特征值（谱）

获取邻接矩阵的特征值：

print(np.real(nx.adjacency_spectrum(G)))

计算拉普拉斯矩阵的特征值：

print(np.real(nx.laplacian_spectrum(G)))

NetworkX中常见图（网络）生成器

完全图（全连接图）

# 生成包含n个节点的完全图（全连接图）
n = 10
G1 = nx.complete_graph(10)
pos = nx.circular_layout(G1)
nx.draw(G1, pos, node_size=500, node_color='red', with_labels=True)

星型图

# 生成包含n个节点的星型图
n = 10
G2 = nx.star_graph(n-1)
pos = nx.spring_layout(G2)
nx.draw(G2, pos, node_size=500, node_color='red', with_labels=True)

ER随机图

# 生成包含n个节点，连边概率为p的ER随机图
n, p = 20, 0.2
G3 = nx.erdos_renyi_graph(n, p)
nx.draw(G3, node_size=500, node_color='red', with_labels=True)

WS小世界网络

# 生成包含n个节点，重连概率为p的WS小世界网络
n, k, p = 20, 4, 0.2

# 当p=0时，便退化成了k近邻规则网络
G4 = nx.watts_strogatz_graph(n, k, p)
pos = nx.circular_layout(G4)
nx.draw(G4, pos, node_size=500, node_color='red', with_labels=True)

BA无标度网络

# 生成包含n个节点，参数m=2的BA无标度网络
n, m = 50, 2
G5 = nx.barabasi_albert_graph(n, m)
pos = nx.spring_layout(G5)
nx.draw(G5, pos, node_size=500, node_color='red', with_labels=True)

外部变量（数据）创建图结构

dict对象

将字典数据转化为网络：

d = {0: {1: {"weight": 1}, 2: {"weight": 2}}, 1: {2: {"weight": 3.5}}}
G = nx.Graph(d)
# 或者
# G = nx.from_dict_of_dicts(d)
edge_width = nx.get_edge_attributes(G, "weight")
# print(width)
nx.draw(G, node_size=500, node_color='red', with_labels=True, width=list(edge_width.values()))

反过来把网络转换成字典数据：

print(nx.to_dict_of_dicts(G))

list对象

转化为list对象：

edgelist = nx.to_edgelist(G)
print(edgelist)

从list格式创建：

G = nx.from_edgelist(edgelist)

array对象

转化为array对象（邻接矩阵）格式：

nx.adjacency_matrix(G)

从array对象（邻接矩阵）格式转化：

nx.from_numpy_array(A)

DataFrame对象

df = pd.read_excel("edges.xlsx")
G = nx.from_pandas_edgelist(df, 'source', 'target','weight', create_using = nx.Graph())
# 若为有向图，create_using = nx.DiGraph()
# 若为无权无向网络则：G = nx.from_pandas_edgelist(df, 'source', 'target', create_using = nx.Graph())
edge_width = nx.get_edge_attributes(G, "weight")
nx.draw(G, node_size=500, node_color='red', with_labels=True, width=list(edge_width.values()))

NetworkX可视化

常用属性值

设置节点大小与节点颜色：

nx.draw(G, node_size=100, node_color="red")

更加复杂的格式：

# 当设置的属性较多时，可以将其保存在字典中，以**不定长参数传入
options = {
    'pos': nx.spring_layout(G),
    'node_size': 300,
    'node_color': "red",
    'edge_color': "gray",
    'width': 1.0, # 连边粗细
    'with_labels': True,
}
nx.draw(G, **options)

布局方式

networkx 库提供了多种布局算法来可视化图，每种布局算法都有其独特的特性和适用场景。以下是一些常用的布局算法：

1. Spring Layout（Fruchterman-Reingold Force-directed Algorithm）:

   • 实现了所谓的“弹簧”布局算法（也称为Fruchterman-Reingold算法），它是一种力导向图绘制算法。
   • 使用方法：nx.spring_layout(G)

2. Circular Layout:

   • 将节点放置在一个圆上，通常用于突出循环结构。
   • 使用方法：nx.circular_layout(G)

3. Random Layout:

   • 将节点随机放置在画布上，用于快速生成节点位置。
   • 使用方法：nx.random_layout(G)

4. Spectral Layout:

   • 基于图的拉普拉斯特征向量（使用拉普拉斯矩阵的第二小和第三小的特征值对应的特征向量，这两个特征向量用于在二维空间中定义节点的位置），尝试将连接的节点放置得更近。
   • 使用方法：nx.spectral_layout(G)

5. Shell Layout:

   • 将图中的节点排列在同心圆上，适用于层级结构。
   • 使用方法：nx.shell_layout(G)

6. Kamada-Kawai Layout:

   • 基于路径长度的力导向算法，旨在使路径长度在图上的表现与其在几何空间中的长度相匹配。
   • 使用方法：nx.kamada_kawai_layout(G)

7. Bipartite Layout:

   • 专门用于二分图的布局，将节点分为两组，每组形成一列。
   • 使用方法：nx.bipartite_layout(G, nodes)

8. Planar Layout:

   • 如果图是平面图，这个算法会找到一个平面布局（即让所有的边都不相交）。
   • 使用方法：nx.planar_layout(G)

[photos]

[/photos]

点定位与边权重的设置

创建一个有权无向图：

G = nx.Graph()
edge_list = [(0, 1, 2), (0, 2, 8), (0, 3, 1), (1, 2, 6),
             (1, 4, 1), (2, 3, 7), (2, 4, 5), (2, 5, 1),
             (2, 6, 2), (3, 6, 9), (4, 5, 3), (4, 7, 8),
             (5, 6, 4), (5, 7, 6), (6, 7, 3)]
G.add_weighted_edges_from(edge_list)
nx.draw(G, node_size=500, with_labels=True)

自定义节点的位置并将边的权重作为图中边的宽度进行绘制：

# 自定义各个节点的坐标
pos = {0: (-2, 0), 1: (-1, 1), 2: (-1, 0), 3: (-1, -1),
       4: (1, 1), 5: (1, 0), 6: (1, -1), 7: (2, 0)}

# 提取边的权重并作为标签
e_labels = nx.get_edge_attributes(G, 'weight')

e_width = [G.get_edge_data(*e)['weight'] for e in G.edges()]

options = {
    'pos': pos,
    'node_size': 500,
    'node_color': "red",
    'edge_color': "gray",
    'width': e_width,
    'with_labels': True,
}
nx.draw(G, **options)
nx.draw_networkx_edge_labels(G, pos, edge_labels=e_labels)

以节点度区分颜色

G = nx.barabasi_albert_graph(20, 2)
# 绘制网络图，按度值大小设定节点大小和颜色
# 设置节点大小与度成正比
nodesize = [G.degree(i) * 100 for i in G.nodes()]
node_colors = [G.degree(i) for i in G.nodes()]
options = {
    'pos': nx.spring_layout(G),
    'node_size': nodesize,
    'node_color': node_colors,
    'cmap': plt.cm.cool,  # 设置节点colormap
    'edge_color': "gray",
    'with_labels': True,
}
nx.draw(G, **options)
plt.show()

更高阶的玩法

• 更多NetworkX可视化案例见：https://networkx.org/documentation/stable/auto_examples/index.html；
• Gephi是网络图可视化领域中无敌的软件：https://gephi.org/。

实战——FackBook社交网络分析

说明

这个案例来自NetworkX官方网站，通过对10个FackBook朋友圈社交网络的分析，来复习下图论中的一些基本概念以及相关NetworkX包的使用。请注意：

• 每个节点代表一个FackBook匿名用户，每条边表示两个用户之间的朋友关系；
• FackBook朋友圈社交网络为无权无向图；
• 节点0, 107, 348, 414, 686, 698, 1684, 1912, 3437, 3980为spotlight nodes，也就是上面提到的10个朋友圈的主人，这也就意味着他们是图结构中的核心节点。

引包

import pandas as pd
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from random import randint

读取文件并创建图

facebook_df = pd.read_csv(
    "./data/facebook_combined.txt.gz",
    compression="gzip",
    sep=" ",
    names=["start_node", "end_node"],
)
facebook_df

读取到的DataFrame共有88234行，每一行代表一个边（即一个连接关系）：

根据DataFrame创建一个图结构：

G = nx.from_pandas_edgelist(facebook_df, "start_node", "end_node")

接下来就是进行图的可视化。因为默认情况下我们并不清楚图的数据结构是什么样的，因此选择随机布局（nx.random_layout(G)）来绘制图形：

fig, ax = plt.subplots(figsize=(15, 9))
ax.axis("off")
plot_options = {"node_size": 10, "with_labels": False, "width": 0.15}
nx.draw_networkx(G, pos=nx.random_layout(G), ax=ax, **plot_options)

显然，从上面的可视化结果中我们看不出来任何信息。因为默认的随机布局看起来杂乱无章。

nx.spring_layout(G)可以根据节点和边的关系对图结构进行布局，但是考虑到本图结构中节点数众多，可以通过设置其参数iterations来避免算法迭代次数过多：

pos = nx.spring_layout(G, iterations=15, seed=666)
fig, ax = plt.subplots(figsize=(20, 20))
ax.axis("off")
plot_options = {"node_size": 2, "with_labels": False, "width": 0.05}
nx.draw_networkx(G, pos=pos, ax=ax, **plot_options)

经过重新布局后，图中的结构似乎有那么一丝“拨云见日”了。①：图结构有聚类的性质，不同的节点分为几个大类；②：少数节点拥有较高的度，符合社交网络的度分布情况。

图结构的基本拓扑属性

查看节点数与边数：

G.number_of_nodes(), G.number_of_edges()

平均度（即图中每个节点平均有几个邻居）：

np.mean([d for _, d in G.degree()])

或者：

sum(dict(G.degree()).values()) / len(G)

图结构中有很多属性与路径有关，例如网络直径和平均最短路径。计算这两个属性值都需要涉及到计算图中所有节点对之间的最短路径，这一个非常消耗计算资源的步骤。

shortest_path_lengths = dict(nx.all_pairs_shortest_path_length(G))

shortest_path_lengths返回的结果是一个dict-of-dict格式的对象：

shortest_path_lengths[42][0], shortest_path_lengths[1][32]  # 节点42到节点0的最短路径、节点1到节点32的最短路径

有上面离心率和直径的基本概念可以得之：$ \text{diameter}(G) = \max_{v \in G} \text{eccentricity}(v) $。因此，可以通过：

diameter = max(nx.eccentricity(G, sp=shortest_path_lengths).values())
diameter

求图中所有节点的离心率最大值来“曲线”求图的直径，通过参数sp=shortest_path_lengths来使用计算好的最短路径来求，避免了计算资源的消耗。

同理，对于求平均最短路径而言，我们可以使用*nx.average_shortest_path_length()命令直接求，但是这样会造成计算资源的浪费。因此，仍可以通过上面计算的shortest_path_lengths来“曲线”求解：

# Compute the average shortest path length for each node
average_path_lengths = [
    np.mean(list(spl.values())) for spl in shortest_path_lengths.values()
]
# The average over all nodes
np.mean(average_path_lengths)

求得平均最短路径为3.6，这说明在社交网络中一份“信息”的平均传递人数是3.6。😂这说明，当你把一个“秘密”在互联网上告诉了另一个人，另一个人是有很大概率告诉另外一个人的。这也说明了“三人成虎”是有科学依据的。😂

查看最短路径的直方图分布情况：

plt.rcParams.update({
'font.size': 20,
'font.family': ['Times New Roman', 'SimSun']
})

# We know the maximum shortest path length (the diameter), so create an array
# to store values from 0 up to (and including) diameter
path_lengths = np.zeros(diameter + 1, dtype=int)

# Extract the frequency of shortest path lengths between two nodes
for pls in shortest_path_lengths.values():
    pl, cnts = np.unique(list(pls.values()), return_counts=True)
    path_lengths[pl] += cnts

# Express frequency distribution as a percentage (ignoring path lengths of 0)
freq_percent = 100 * path_lengths[1:] / path_lengths[1:].sum()

# Plot the frequency distribution (ignoring path lengths of 0) as a percentage
fig, ax = plt.subplots(figsize=(15, 8))
ax.bar(np.arange(1, diameter + 1), height=freq_percent)
ax.set_title("Distribution of shortest path length in G")
ax.set_xlabel("Shortest Path Length")
ax.set_ylabel("Frequency (%)")

查看网络密度：

nx.density(G)

网络密度为0.0108，远远小于1，说明社交网络也是一个稀疏网络。也很容易理解，中国有14亿人，你认识的有几个呢？

获取连通组件（子图）的数量：

nx.number_connected_components(G)

返回结果为1。说明，整个社交网络都是连通的。

FaceBook社交网络中心性分析

度中心性

采用度中心性进行计算：

degree_centrality = nx.centrality.degree_centrality(G)  # save results in a variable to use again, nx.degree_centrality(G)也可以

(sorted(degree_centrality.items(), key=lambda item: item[1], reverse=True))[:8]

返回的结果中有一些有意思的信息：节点107、1684、1912、3437以及节点0都是spotlight nodes，因此其具有更好的中心性也无可厚非。但节点2543、2347、1888也就有非常高的度中心性，说明这三个人可能非常喜欢吃瓜🍉🍉🍉。

获取度排名前8的选手：

(sorted(G.degree, key=lambda item: item[1], reverse=True))[:8]

获取网络中心性分布直方图：

plt.figure(figsize=(15, 8))
plt.hist(degree_centrality.values(), bins=25)
plt.xticks(ticks=[0, 0.025, 0.05, 0.1, 0.15, 0.2])  # set the x axis ticks
plt.title("Degree Centrality Histogram ")
plt.xlabel("Degree Centrality")
plt.ylabel("Counts")

以节点度为节点的大小和颜色区分，可视化网络结构：

import matplotlib.pyplot as plt

node_size = [
    v**2 * 10000 for v in degree_centrality.values()
]

plt.figure(figsize=(20, 20))
nx.draw_networkx(G, pos=pos, node_size=node_size, with_labels=False, width=0.15,node_color = node_size,
cmap= plt.cm.cool)
plt.axis("off")

介数中心性

对于一个节点的介数中心性，简单来讲就是一个网络中所有任意两节点之间最短路径中有几条经过了该节点。反映到社交网络中，介数中心性反映了该节点影响他人能力的大小。例如：当一个人有很高的介数中心性，说明社交网络中的很多信息都需要经过她/他来传播。

计算介数中心性排名前八的用户：

betweenness_centrality = nx.centrality.betweenness_centrality(
    G
)  # save results in a variable to use again
(sorted(betweenness_centrality.items(), key=lambda item: item[1], reverse=True))[:8]

在介数中心性排名前八的用户中，节点0, 107, 1684, 1912, 3437的度中心性也在前八之中，说明这些节点不仅仅是spotlight nodes，其对于社交网络中信息的传播也十分重要。而对于节点567, 1085，其度中心性远远落后于前八的值：

degree_centrality[567],  degree_centrality[1085]  # (0.015601783060921248, 0.016344725111441305)

但是两者却拥有了很高的介数中心性，说明两者虽然在影响力上并不大，但是在信息传播过程中却非常重要（有点像吃瓜群众）。

接近度中心性

接近度中心性在控制社交网络中虚假信息的传播方面非常有研究价值。如果一个节点（用户）有很高的接近度中心性，那么说明其发布的信息更容易在短时间内就迅速影响到一大批人。

计算接近度中心性排名前八的用户：

closeness_centrality = nx.centrality.closeness_centrality(
    G
)  # save results in a variable to use again
(sorted(closeness_centrality.items(), key=lambda item: item[1], reverse=True))[:8]

聚类系数

查看图平均聚类系数：

nx.clustering(G).values()

所有节点聚类系数的直方图分布：

plt.figure(figsize=(15, 8))
plt.hist(nx.clustering(G).values(), bins=50)
plt.title("Clustering Coefficient Histogram ")
plt.xlabel("Clustering Coefficient")
plt.ylabel("Counts")

桥检测

nx.has_bridges(G)

结果返回True，说明图结构中存在“易破坏的点”。

bridges = list(nx.bridges(G))
print(len(bridges))

for i in bridges:
    print(i)

结果返回75，说明图结构中存在75个桥。之所以存在这么多的桥是因为该社交网络仅使用了10个spotlight nodes，对于每个spotlight nodes的朋友节点的朋友圈并没有考虑。

查看本地桥数量：

local_bridges = list(nx.local_bridges(G, with_span=False))
len(local_bridges)

可视化桥与本地桥：

plt.figure(figsize=(20, 20))
nx.draw_networkx(G, pos=pos, node_size=10, with_labels=False, width=0.15)
nx.draw_networkx_edges(
    G, pos, edgelist=local_bridges, width=0.5, edge_color="lawngreen"
)  # green color for local bridges
nx.draw_networkx_edges(
    G, pos, edgelist=bridges, width=0.5, edge_color="r"
)  # red color for bridges
plt.axis("off")

度同配性

计算社交网络的度同配性：

nx.degree_assortativity_coefficient(G)

或者：

nx.degree_pearson_correlation_coefficient(
    G
)  # use the potentially faster scipy.stats.pearsonr function.

显示FB社交网络的度同配性为0.064，比较接近于0。说明：用户的社交关系在度数上既不显示同配也不显示异配的特征（non-assortative）。

网络社区分类

networkx 库提供了多种社区检测算法，其中 nx.community.label_propagation_communities(G) 和 nx.community.asyn_fluidc(G, k, seed=0) 是两种不同的社区发现算法。它们在社区检测的方法和理论基础上有所不同。

1. 标签传播算法（Label Propagation）:

   • 函数：nx.community.label_propagation_communities(G)
   • 原理：此算法基于网络中节点的标签传播。最初，每个节点被赋予一个唯一的标签，然后在迭代过程中，每个节点会采用其邻居中最常见的标签。最终，具有相同标签的节点被分为同一个社区。
   • 特点：这种算法简单且运行速度快，但它可能不稳定，即不同的运行可能产生不同的结果。此算法适用于大型网络，但可能不适合发现重叠社区或具有层次结构的社区。

2. 异步流体社区检测（Asynchronous Fluid Communities）:

   • 函数：nx.community.asyn_fluidc(G, k, seed=0)
   • 原理：这是一种基于流体动力学的社区检测方法。算法试图通过模拟 k 个流体的扩散来确定社区。每个流体源（源自一个节点）扩散到网络，逐渐形成社区，直到达到稳定状态。
   • 特点：这种算法适用于中等大小的网络，并且需要预先指定社区数量（k）。它通常能够找到比较均衡的社区结构，但对于非常大的网络，算法的效率和效果可能受限。

两者的不同之处：

• 算法原理：标签传播算法依赖于标签的传播和统一，而异步流体社区检测基于流体动力学的模型。
• 社区数量：标签传播算法不需要预先指定社区的数量，它会自然形成，而异步流体社区检测需要预先指定社区数量 k。
• 适用性：标签传播算法适用于大型网络且运行快速，但可能不够稳定；异步流体社区检测适用于中等规模的网络，需要预设社区数量，可能对社区大小更加均衡。

标签传播算法：

colors = ["" for x in range(G.number_of_nodes())]  # initialize colors list
counter = 0
for com in nx.community.label_propagation_communities(G):
    color = "#%06X" % randint(0, 0xFFFFFF)  # creates random RGB color
    counter += 1
    for node in list(
            com
    ):  # fill colors list with the particular color for the community nodes
    colors[node] = color
    
        
plt.figure(figsize=(15, 9))
plt.axis("off")
nx.draw_networkx(
    G, pos=pos, node_size=10, with_labels=False, width=0.15, node_color=colors
)    

异步流体社区检测可视化：

colors = ["" for x in range(G.number_of_nodes())]
for com in nx.community.asyn_fluidc(G, 8, seed=0):
    color = "#%06X" % randint(0, 0xFFFFFF)  # creates random RGB color
    for node in list(com):
        colors[node] = color
        
plt.figure(figsize=(15, 9))
plt.axis("off")
nx.draw_networkx(
    G, pos=pos, node_size=10, with_labels=False, width=0.15, node_color=colors
)