小世界网络与无标度网络

1. 小世界网络的定义与Watts-Strogatz模型

1.1 小世界效应的定义

• 小世界效应（Small-world effect）是指在一个大型网络中，任意两个节点之间的平均最短路径长度远小于网络规模，但节点间的连接仍然表现出较强的局部聚集性。
• 现实中的许多网络（如社交网络、交通网络、互联网等）都呈现出小世界效应。

1.2 Watts-Strogatz模型

Watts-Strogatz模型（WS模型）是用来生成小世界网络的经典模型。该模型包含以下步骤：

1. 从一个环状的网络开始，每个节点和其最近的k个邻居连接，形成一个规则网络。
2. 以概率p重新连接每一条边，即将边连接的两个节点之间的链接随机改变。这个步骤使得原本的局部连接性被打破，从而增加了远距离的连接。
3. 当p接近0时，网络接近于一个规则网络；当p接近1时，网络趋于一个随机网络。

公式：

• 平均路径长度 $L(p)$：
  $$L(p)=\frac{1}{N(N-1)}\sum _{i=1}^N\sum _{j\ne i}^{N}d(i,j)$$
  其中 $d(i,j)$ 是节点i与节点j之间的最短路径长度，$N$ 是网络中的节点数。

• 聚集系数 $C(p)$：
  $$C(p)=\frac{1}{N}\sum _{i=1}^N\frac{2e_i}{k_i(k_i-1)}$$
  其中 $e_i$ 是节点i的邻居之间的实际边数，$k_i$ 是节点i的度数。

1.3 课堂案例与计算

通过构建一个简单的Watts-Strogatz模型的网络，演示如何计算小世界网络的聚集系数和路径长度。

import networkx as nx
import matplotlib.pyplot as plt

# 创建一个具有10个节点、每个节点初始连接2个邻居的规则网络
n = 10  # 节点数
k = 2  # 每个节点的邻居数
p = 0.1  # 随机重连概率
G = nx.watts_strogatz_graph(n, k, p)

# 绘制网络
plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True, node_color='skyblue', edge_color='gray')
plt.title('Watts-Strogatz Small World Network')
plt.show()

# 计算小世界网络的聚集系数与平均路径长度
clustering_coefficient = nx.average_clustering(G)
average_path_length = nx.average_shortest_path_length(G)

print(f"聚集系数: {clustering_coefficient}")
print(f"平均路径长度: {average_path_length}")

在这个案例中，网络的度为2，我们设置p=0.1来模拟随机重连。计算出该网络的聚集系数和平均路径长度，展示小世界效应。

2. 无标度网络与Barabási-Albert模型

2.1 无标度网络的特性

无标度网络（Scale-free Network）是一类具有幂律分布的网络，即度分布遵循幂律规律。大部分节点的连接数较小，少数节点具有非常高的连接度，这些节点称为枢纽节点（hubs）。

• 度分布的幂律特征：
  $$P(k)\sim k^{-\gamma }$$
  其中，$P(k)$ 是度为k的节点的概率，$\gamma$ 是幂律指数，通常在网络中具有值2到3。

2.2 Barabási-Albert模型（BA模型）

BA模型是无标度网络的经典生成模型，其生成过程遵循以下步骤：

1. 从一个初始的小网络开始（例如两个节点连接）。
2. 逐渐添加新节点，每个新节点与已有的节点连接，连接的概率与已有节点的度成正比（即优先连接到度数较高的节点）。

公式：

• 新节点与旧节点连接的概率：
  $$P(\text{new node connects to node i})=\frac{k_i}{{\sum }_j{k}_j}$$
  其中，$k_i$ 是节点i的度数。

2.3 课堂案例与计算

通过构建一个简单的Barabási-Albert模型网络，演示如何计算度分布。

import networkx as nx
import matplotlib.pyplot as plt

# 创建一个具有20个节点的Barabási-Albert无标度网络
n = 20  # 节点数
m = 2  # 每个新节点连接的边数
G = nx.barabasi_albert_graph(n, m)

# 绘制网络
plt.figure(figsize=(8, 6))
nx.draw(G, with_labels=True, node_color='lightgreen', edge_color='gray')
plt.title('Barabási-Albert Scale-Free Network')
plt.show()

# 计算并绘制度分布
degree_sequence = [d for n, d in G.degree()]
plt.hist(degree_sequence, bins=range(min(degree_sequence), max(degree_sequence) + 1), alpha=0.75, color='orange')
plt.title('Degree Distribution of Barabási-Albert Network')
plt.xlabel('Degree (k)')
plt.ylabel('Frequency')
plt.show()

在这个案例中，我们生成一个20节点的无标度网络，并绘制其度分布图。根据度分布，学生可以观察到无标度网络呈现出幂律分布的特性。

3. 复杂网络的幂律分布与网络的度分布

3.1 幂律分布

在无标度网络中，节点的度分布通常符合幂律分布，即度分布的概率密度函数满足：
$$P(k)\sim k^{-\gamma }$$
这意味着大部分节点的度数较小，只有少数节点度数非常高。

3.2 网络的度分布

度分布是指网络中具有不同度数的节点的比例分布。对于无标度网络，度分布通常呈现出长尾特性，少数节点有很高的度，而大部分节点的度较低。

3.3 课堂活动：仿真模型与动态演化

学生通过仿真模型，探索小世界网络与无标度网络的生成机制，并计算其度分布。可以提供以下问题来加深理解：

• 如何修改Watts-Strogatz模型的重连概率p，并观察小世界效应如何变化？
• 在Barabási-Albert模型中，如何改变新节点连接的边数m，并观察度分布的变化？

4. 应用：复杂网络在互联网和社交网络中的应用

4.1 信息传播与病毒传播建模

在小世界网络和无标度网络中，信息传播和病毒传播具有不同的模式。小世界网络中信息传播速度较快，而无标度网络中，病毒可能通过枢纽节点迅速扩散。

4.2 课堂活动与练习：病毒传播模型

通过模拟SIR（易感-感染-恢复）模型，学生可以观察不同网络中病毒传播的差异。下面是Python代码实现：

import numpy as np
import matplotlib.pyplot as plt

# SIR模型
def sir_model(G, beta, gamma, steps=100):
    infected = {node: False for node in G.nodes()}
    recovered = {node: False for node in G.nodes()}
    infected_nodes = np.random.choice(list(G.nodes()), size=2, replace=False)
    for node in infected_nodes:
        infected[node] = True
    
    S, I, R = [], [], []
    
    for _ in range(steps):
        new_infected = set()
        new_recovered = set()
        
        for node in G.nodes():
            if infected[node]:
                # Infect neighbors
                for neighbor in G.neighbors(node):
                    if not infected[neighbor] and np.random.rand() < beta:
                        new_infected.add(neighbor)
                # Recover after infection
                if np.random.rand() < gamma:
                    new_recovered.add(node)
        
        for node in new_infected:
            infected[node] = True
        for node in new_recovered:
            infected[node] = False
            recovered[node] = True
        
        S.append(sum([not infected[node] and not recovered[node] for node in G.nodes()]))
        I.append(sum([infected[node] for node in G.nodes()]))
        R.append(sum([recovered[node] for node in G.nodes()]))
    
    return S, I, R

# 创建Barabási-Albert网络
G = nx.barabasi_albert_graph(100, 2)

# 模拟病毒传播
S, I, R = sir_model(G, beta=0.3, gamma=0.1, steps=50)

# 绘制结果
plt.plot(I, label='Infected')
plt.plot(R, label='Recovered')
plt.xlabel('Time Steps')
plt.ylabel('Number of Nodes')
plt.legend()
plt.title('Virus Spread in a Barabási-Albert Network')
plt.show()

通过这个例子，学生可以看到在无标度网络中，病毒如何通过枢纽节点快速传播。

总结

• 小世界网络与无标度网络在许多现实网络中广泛存在，了解它们的生成机制和特性能够帮助学生理解复杂系统的行为。
• 通过具体的数学公式、Python代码实现、图表和案例分析，学生能够深入理解这些网络模型的动态演化以及其在现实生活中的应用。