生物医学网络科学Biomedical Network Science
Example04 / 11

共识动力学与代数连通度

所属专题
同步与协同动力学
下载
Notebook · .py

共识动力学 dx/dt = -L x。在 4 种网络（N=60，平均度 4 的环、两种 WS 小世界网络，以及完全图）上， 从相同的随机初值出发，记录偏离平均值的误差 ||x - mean(x0)|| 降到初始的 1% 所需的时间， 并与拉普拉斯矩阵的第二小特征值（代数连通度 mu_2）比较。 解读：mu_2 越大，收敛越快；收敛时间约 ∝ 1/mu_2，因此 mu_2*时间 在各网络间量级相近。

Output输出图

共识动力学与代数连通度：输出图 1

Output文字输出

ring       mu2 = 0.0547  收敛时间 = 65.09  mu2*时间 = 3.56
WS p=0.1   mu2 = 0.1560  收敛时间 = 14.97  mu2*时间 = 2.33
WS p=0.5   mu2 = 0.5657  收敛时间 = 5.12  mu2*时间 = 2.90
complete   mu2 = 60.0000  收敛时间 = 0.08  mu2*时间 = 4.50

Code代码

# 共识动力学 dx/dt = -L x。在 4 种网络（N=60，平均度 4 的环、两种 WS 小世界网络，以及完全图）上，
# 从相同的随机初值出发，记录偏离平均值的误差 ||x - mean(x0)|| 降到初始的 1% 所需的时间，
# 并与拉普拉斯矩阵的第二小特征值（代数连通度 mu_2）比较。
# 解读：mu_2 越大，收敛越快；收敛时间约 ∝ 1/mu_2，因此 mu_2*时间 在各网络间量级相近。
import numpy as np
import networkx as nx

N = 60
nets = {
    "ring": nx.watts_strogatz_graph(N, 4, 0.0, seed=1),
    "WS p=0.1": nx.connected_watts_strogatz_graph(N, 4, 0.1, seed=1),
    "WS p=0.5": nx.connected_watts_strogatz_graph(N, 4, 0.5, seed=1),
    "complete": nx.complete_graph(N),
}
x0 = np.random.default_rng(0).standard_normal(N)

def consensus_time(G, x0, dt=0.01, tol=0.01, tmax=2000):
    L = nx.laplacian_matrix(G, nodelist=range(N)).toarray().astype(float)
    x = x0.copy(); e0 = np.linalg.norm(x0 - x0.mean()); t = 0.0
    while np.linalg.norm(x - x0.mean()) > tol * e0 and t < tmax:
        x = x - dt * (L @ x); t += dt
    return t

for name, G in nets.items():
    L = nx.laplacian_matrix(G, nodelist=range(N)).toarray().astype(float)
    mu2 = np.sort(np.linalg.eigvalsh(L))[1]
    t = consensus_time(G, x0, dt=0.01 if name != "complete" else 0.001)
    print("%-10s mu2 = %.4f  收敛时间 = %.2f  mu2*时间 = %.2f" % (name, mu2, t, mu2 * t))

# 作图：用特征分解得到误差的解析衰减曲线 ||x(t) - mean|| = ||sum_k e^{-mu_k t} (v_k·x0) v_k||
import matplotlib.pyplot as plt
fig, ax = plt.subplots(figsize=(6.4, 4.2))
tt = np.logspace(-2, 3, 300)
for (name, G), ls in zip(nets.items(), ["-", "--", "-.", ":"]):
    mu, V = np.linalg.eigh(nx.laplacian_matrix(G, nodelist=range(N)).toarray().astype(float))
    c = V.T @ (x0 - x0.mean())
    err = np.sqrt(((np.exp(-np.outer(tt, mu)) * c) ** 2).sum(1)) / np.linalg.norm(c)
    ax.loglog(tt, err, ls=ls, lw=2, label="%s (mu2 = %.3f)" % (name, mu[1]))
ax.axhline(0.01, c="0.6", lw=0.8)
ax.set_ylim(1e-3, 1.5); ax.set_xlabel("time t"); ax.set_ylabel("relative disagreement")
ax.legend(fontsize=8); ax.set_title("Consensus is faster with larger algebraic connectivity")
plt.tight_layout(); plt.show()

Run在浏览器中运行

首次加载 Python 环境约需 20–40 秒；可以修改参数后重新运行。

共识动力学与代数连通度