复杂网络动力学基础课程

发表于 Waline： 阅读次数：

我在之前打数模的时候学了一点复杂网络，虽然学的很浅，感觉还是挺有意思的。

但这个考试完全打消了我对这个学科的喜爱，或者说觉得它不应该作为有考试的课程。这场考试完全就是背诵结论，弄得我毫无兴趣。现在陷入了人生的大思考。

考卷结构大概是 20 分名词解释（10 题），40 分填空（40 个空），余下的证明和计算。我有一个证明题没弄对，填空一堆不记得了，经验公式也不太好推出来，烦躁。

这个课本来是大四下的课，所以像这样背多分，不容易挂，也没人有意见，但是我基本上就惨了，祈求老师能给我分高一点吧。

还是把考前搞的提纲粘出来，要好好背。也有好多考了提纲里没有，要好好看课件。

数理统计

符号

随机变量 \(X\)，观测值 \(x\)，分布函数 CDF \(F(x)=P\{X\le x\}\)，概率密度函数 PDF \(f(x)=F'(x)\)

若 \(Y=g(X)\)，且 \(\int g(x)f(x)\ \mathrm d x\) 绝对收敛，则 \(E[Y]=\int g(x)f(x)\ \mathrm d x\)

公式与概念

极大似然估计

设其分布为 \(p(x;\theta)\)，似然函数 \(L(\theta)=\prod_i p(x_i;\theta)\)，极大似然估计值 \(\hat\theta=\arg\max_\theta L(\theta)\)

高斯积分

\[ \int_{-\infty}^{+\infty}e^{-ax^2}=\sqrt{\dfrac{\pi}{a}} \]

伽马函数

\[ \Gamma(x)=\int_0^\infty t^{x-1}e^{-t}\ \mathrm d t \]

有 \(\Gamma(x+1)=x\Gamma(x)\)，\(\Gamma(n+1)=n!\)（\(n\) 是整数）；\(\Gamma(1/2)=\sqrt{\pi}\)

贝塔函数

\[ B(\alpha,\beta)=\int_0^1x^{\alpha-1}(1-x)^{\beta-1}\ \mathrm dx=\dfrac{\Gamma(\alpha)\Gamma(\beta)}{\Gamma(\alpha+\beta)} \]

其中 \(\alpha, \beta>0\)

矩母函数

对一非负随机变量 \(X\)，其矩母函数定义为 \[ m_X(t)=E[e^{tX}]=\int e^{tx}f(x)\ \mathrm d x \] 其中 \(-\infty<t<h\)，\(h\) 是一个正数

样本 \(k\) 阶原点矩 \(A_k=\dfrac{1}{n}\sum_i X_i^k\)，\(v_k(X)=\int x^kf(x)\ \mathrm d x\)，中心矩 \(B_k=\dfrac{1}{n}\sum_i \left(X_i-\overline X\right)^k\)

对矩母函数（关于 \(t\)）在原点泰勒展开 \[ m_X(t)=\sum_{k=0}^\infty \dfrac{E[X^k]t^k}{k!} \] 则 \(X\) 的 \(k\) 阶原点矩 \(E[X^k]\) 就是 \(m_X(t)\) 的 \(k\) 阶导数

特征函数

\[ \phi_X(t)=E[e^{\mathrm i tX}]=\int e^{\mathrm i tx}f(x) \]

类似傅里叶变换 \(F(\omega)=\displaystyle\int f(t)e^{-\mathrm j\omega t}\ \mathrm d t\)

概率母函数

对于非负离散随机变量 \(X\)，其概率母函数定义为 \[ g_X(t)=E[t^{X}]=\sum_{k=0} ^{\infty}t^kP\{X=k\}=\sum_{k=0} ^{\infty}t^kp(k) \] 类似 Z 变换 \(X(Z)=\sum_{n=0}^{\infty}x(n)Z^{-n}\)

有 \(g_X(t)=m_X(\ln t)\)

常用概率分布

柯西分布

不存在期望和方差 \[ f_{x_0,\gamma}(x)=\dfrac{1}{\pi\gamma\left[1+\left(\dfrac{1-x_0}{\gamma}\right)\right]} \]

高斯分布

\[ f_X(x)=\dfrac{e^{-\dfrac{(x-\mu)^2}{2\sigma^2}}}{\sqrt{2\pi}\sigma} \]

其矩母函数 \(m_X(t)=e^{\mu t+\dfrac{\sigma^2}{2}t^2}\)

泊松分布

离散型概率分布（\(\lambda>0\)） \[ P\{N=k\}=\dfrac{e^{-\lambda}\lambda^k}{k!} \] 矩母函数 \(m_N(t)=e^{\lambda(e^t-1)}\)

二项分布

\(X\sim B(n,p)\) \[ P\{X=k\}=\binom{n}{k}p^k(1-p)^{n-k} \]

卡方分布

独立同分布的正态平方和 \(X_1^2+X_2^2+\cdots+X_n^2\sim\chi^2(n)\)

期望 \(n\)，方差 \(2n\)

t 分布

设 \(X\sim N(0,1)\)，\(Y\sim \chi^2(n)\)，\(t=\dfrac{X}{\sqrt{Y/n}}\sim t(n)\)

估计小样本正态分布方差未知的均值

F 分布

设 \(U\sim \chi^2(m)\)，\(V\sim\chi^2(n)\)，\(F=\dfrac{U/m}{V/n}\sim F(m, n)\)

Gamma 分布

\[ f_X(x)=\dfrac{x^{\alpha -1}e^{-x/\beta}}{\beta^\alpha\Gamma(\alpha)} \]

其中 \(x>0\)，\(\alpha,\beta>0\)

若 \(\alpha=1\)，其为指数分布；若 \(\beta=2\)，\(\alpha=n/2\)，则是自由度 \(n\) 的 \(\chi^2\) 分布

\(\alpha=k+1\)，\(\beta=1\) 时其为 Poisson 分布（\(k\) 为整数）

矩母函数 \(m_X(t)=\dfrac{1}{(1-\beta t)^\alpha}\)，\(k\) 阶原点矩 \(E[X^k]=\dfrac{\beta^k\Gamma(\alpha+k)}{\Gamma(\alpha)}\)

可加性：若 \(X_i\sim\text{Gamma}(\alpha_i,\beta)\)，则 \(\sum_i X_i\sim\text{Gamma}(\sum_i \alpha_i,\beta)\)

假设检验

一般过程

  1. 原假设（零假设） \(H_0\)，对立假设 \(H_1\)
  2. 选定检验统计量 \(g(X_1,X_2,\cdots,X_n)\)，确定 \(H_0\) 成立时统计量 \(g\) 的分布 \(D\)
  3. 计算显著水平 \(0<p<1\) 下 \(H_0\) 的临界值 \(g'\)，使 \(F_D(g')= p\)，则接受域 \(S_0=\{g\ |\ g>g'\}\)
  4. 判断 \(g\) 是否在接受域

显著性水平 \(p=P\{\text{refuse } H_0\ |\ H_0 \text{ holds}\}\)（以真为假）（第一类错误）

功效 \(\eta=P\{\text{accept } H_0\ |\ H_0 \text{ doesn't hold}\}\)（以假为真）（第二类错误）

Q-Q Plot 检验

实际与理论的分位数点比较

Kolmogorov-Smirnov 检验

经验分布函数 EDF \(F_n(x)\) 与分布函数的距离，统计量 \[ T=\sup_x |F_n(x)-F(x)| \] 临界值表

\(p\) 1% 5% 10%
\(T_c\) \(1.63/\sqrt{n}\) \(1.36/\sqrt{n}\) \(1.22/\sqrt{n}\)

Pearson-chi2 检验

取检验量 \(\chi^2=\sum_i\dfrac{(A_i-T_i)^2}{T_i}\)，其中 \(A_i\)，\(T_i\) 分别为区间 \([c_{i-1},c_i)\) 中的实际频数和理论频数

矩阵

共轭转置 \(A^\mathrm H=({A^*})^\mathrm T\)

Hermite 矩阵 \(A^{\mathrm H}=A\)

正则矩阵 \(A^{\mathrm H}A=AA^{\mathrm H}\)

正交矩阵 \(U^{\mathrm T}U=I\)

置换矩阵 \(P\)（初等矩阵）

可约矩阵 \(L\) 存在上三角分解（满秩）

实对称不可约矩阵 \(L\) 的每一行元素和为零，则（1）\(0\) 是重特征值；（2）其他特征值小于零；（3）存在正交矩阵 \(\Phi\)，\(L^\mathrm T\phi_i=\lambda_i\phi_i\)

Schur 分解：\(Q^\mathrm TAQ\) 有上三角分块，每块阶数不大于 2，\(Q\) 为正交矩阵

LDU 分解：\(A=LDU\)，\(L\) 单位下三角，\(D\) 对角，\(U\) 单位上三角

Shur 补定理（线性矩阵不等式）： \[ X=\begin{bmatrix} X_{11}&X_{12}\\ X_{12}^\mathrm T&X_{22} \end{bmatrix} \] 下列三个条件等价

  • \(X<0\)
  • \(X_{11}<0\)，\(X_{22}-X_{12}^\mathrm TX_{11}^{-1}X_{12}<0\)
  • \(X_{22}<0\)，\(X_{11}-X_{12}^\mathrm TX_{22}^{-1}X_{12}<0\)

网络特征的数学描述

网络静态几何特征

平均度

\[ \left<k\right>=\dfrac{1}{N}\sum_{i=1}^{N}k_i=\dfrac{\operatorname{tr} (A^2)}{N} \]

其中 \(k_i\) 为节点 \(i\) 的度，\(A\) 为网络的邻接矩阵

无标度条件

有概率分布函数 \(F(x)\)，若 \(\forall a\)，\(\exists b\) 使得 \(F(ax)=bF(x)\)，则称 \(F(x)\) 满足无标度条件

幂律分布函数 \(F(x)=f(1)x^{-\gamma}\)，\(\gamma=-f(1)/F(1)\) 是唯一的离散无标度分布

度分布

\(P(k)\) 表示度为 \(k\) 的节点所占比例

累积度分布 \(P_k=\sum_{i=k}^{\infty} P(i)\)，若度分布为幂律分布，\(P_k\propto k^{-(\gamma-1)}\)

距离参数

直径 \(D\)

平均路径长度 \(L=\dbinom{2}{N}^{-1}\sum\limits_{1\le i<j\le N}d_{ij}\)

聚类系数

节点 \(v_i\) 度为 \(k_i\)，其聚类系数 \[ C_i=\dfrac{E_i}{\dbinom{2}{k_i}} \] 其中 \(E_i\) 表示邻居之间存在的边数

记 \(a_{ij}^{(p)}\) 为邻接矩阵 \(A^p\) 的元，则 \(C_i=\dfrac{a^{(3)}_{ii}}{k_i(k_i-1)}\)，亦有 \(k_i=a_{ii}^{(2)}\)

网络的聚类系数 \(C=\overline C\)

聚类系数分布 \(P(C)\) 表示聚类系数出现的概率

无向网络静态特性

联合度分布

\[ P(k_1,k_2)=\dfrac{M(k_1,k_2)}{M} \]

其中 \(M(k_1,k_2)\) 为度值 \(k_1\) 的节点与度值 \(k_2\) 的节点连接总边数

最近邻平均度

节点 \(v_i\) 的最近邻平均度（节点邻居的平均度） \[ k_{nn,i}=\dfrac{\sum_{j}a_{ij}k_j}{k_i} \] 度值为 \(k\) 节点的最近邻平均度平均值 \[ k_{nn}(k)=\dfrac{\sum_{i | k_i=k}k_{nn,i}}{N\cdot P(k)} \] 该函数增则为同配网络，否则为异配网络

同配系数

度的 Pearson 相关系数 \[ r=\dfrac{\overline{k_ik_j}-\left(\dfrac{1}{2}\overline{k_i+k_j}\right)^2} {\dfrac{1}{2}\overline{k_i^2+k_j^2}-\left(\dfrac{1}{2}\overline{k_i+k_j}\right)^2} \] 其中 \(\overline{f(k_i,kj)}\) 表示 \(M^{-1}\sum_{e_{ij}\in E}f(k_i,k_j)\)

注：\(\rho_{XY}=\dfrac{\text{Cov}(X,Y)}{\sqrt{\text{Var}X\cdot\text{Var}Y}}\)

聚-度相关性

局部聚类系数 \[ C(k)=\dfrac{2\overline {M_{nn}(k)}}{k(k-1)} \] 度为 \(k\) 的节点的邻居之间存在的平均边数与这些邻居之间存在的最大可能的边数的比值

全局聚类系数 \[ C=\dfrac{\sum_{k=0}^{\infty}k(k-1)P(k)C(k)}{\overline{k^2}-\overline k} \]

介数

节点介数 \(B_i\) 表示最短路径途径（比例）和 \[ B_{i}=\sum_{1\le l<m\le N\wedge l\neq m\neq i}\dfrac{n_{lm}(i)}{n_{lm}} \] 边介数 \(\widetilde {B_{ij}}\) 表示所有最短路径经过该边的条数（比例）和 \[ \widetilde {B_{ij}}=\sum_{1\le l<m\le N\wedge (l,m)\neq (i,j)}\dfrac{N_{lm}(e_{ij})}{N_{lm}} \]

核数

\(k\)-核是指反复去掉度值小于 \(k\) 的节点及其连线后所剩余的子图，该子图的节点数就是该核的大小

若一个节点存在于 \(k\)-核，而在 \((k+1)\)-核中被移去，那么此节点的核数为 \(k\)

中心性

度中心性 \(C_D(v_i)=\dfrac{k_i}{N-1}\)

构造同节点数量星形网络，得最大网络度中心性为 \[ H=\sum_{i=1}^{N}\left[\max_{u_{\text{star}}}\{C_D(u_{\text{star}})\}-C_D(u_{\text{star}, i})\right]=N-2 \] 网络度中心性 \(C_D=H^{-1}\sum_{i=1}^{N}\left[\max_{u}\{C_D(u)\}-C_D(u_i)\right]\)

介数中心性 \(C_B(v_i)=\dfrac{2B_i}{(N-1)(N-2)}\)

网络介数中心性 \(C_B=(N-1)^{-1}\sum_{i=1}^{N}\left[\max_{u}\{C_B(u)\}-C_B(u_i)\right]\)

PageRank

\(Ax=\lambda x\)，其中 \(x\) 是网络的特征向量，则节点的特征向量中心性分值 \[ C_E(v_i)=x_i=\dfrac{1}{\lambda_{\max}}\sum_{j=1}^{N}a_{ij}x_j \] Markov 链的状态转移概率矩阵 \(P\)（\(p_{ij}\) 表示由状态 \(i\) 至 \(j\) 的概率） \[ p_{ij}=\dfrac{1-d}{N}+d\dfrac{b_{ij}}{r_i} \] 其中 \(d\) 为模型参数（常取 \(d=0.85\)），\(r_i\) 为行和（链出数目）

正则 Markov 链（\(\exists k\)，使 \(a_{ij}^{(k)}>0\)）存在平稳分布（不动点） \(P^{T}x=x\)，即存在特征值为 \(1\) 的特征向量

赋权网络静态特性

权重

边权 \(w_{ij}\)

点权 \(S_i\)：与它相连的边权之和 \(\sum_{j\in N_i} w_{ij}\)

单位权 \(U_i\)：节点连接的平均权重 \(U_i=S_i/k_i\)

权重分布的差异性 \(Y_i\)：节点连接的边权分布的离散程度 \(\sum_{j\in N_i} (w_{ij}/S_i)^2\)

权-度相关性

基于节点的权-度相关性

\[ S_{vv}(k)=\dfrac{\sum_{i|k_i=k}S_i}{N\cdot P(k)} \]

分母：度为 \(k\) 的节点个数；分子：度为 \(k\) 的所有节点的点权之和

基于边的权-度相关性

赋权最近邻平均度 \[ k_{w_{nn},i}=\dfrac{\sum_j w_{ij}k_i}{S_i} \]

  • 若 \(k_{w_{nn},i}>k_{nn,i}\)，则边权与度正相关
  • 若 \(k_{w_{nn},i}<k_{nn,i}\)，则边权与度负相关

其中 \(k_{nn,i}\) 为最近邻平均度

赋权聚类系数

顶点 \(i\) 的 Onnela 赋权聚类系数 \[ C_{\mathrm O,i}^w=\dfrac{1}{k_i(k_i-1)}\sum_{j,k}(w_{ij}w_{jk}w_{ki})^{\dfrac{1}{3}} \] 为三角形边权几何平均值与三元组数量的比值

顶点 \(i\) 的 Holme 赋权聚类系数 \[ C_{\mathrm H,i}^w=\dfrac{\sum_{j,k}w_{ij}w_{jk}w_{ki}}{\max_{j}(w_{ij})\sum_{j,k}w_{ij}w_{ki}} \]

网络的其他静态特性

结构熵

节点的重要度 \(I_i=k_i/\sum_j k_j\)

结构熵 \(E=-\sum_{i|I_i\neq0} I_i\ln I_i\)

结构熵越大，越均匀

归一化结构熵 \(\hat E=\dfrac{E-E_{min}}{E_{max}-E_{min}}\)

其中星形网络 \(E_{min}=\dfrac{\ln (4(N-1))}{2}\)

均匀网络 \(E_{max}=\ln N\)

特征谱

Wigner 半圆定理：\(A_{n_1}\in\mathbb R^{N\times N}\) 每一个非对角线元素独立同分布且服从高斯分布 \(N(0,1)\)，对角线独立同分布于 \(N(0,2)\)，Wigner 矩阵 \(W_{n_1}=\dfrac{1}{\sqrt{N}}A_{n_1}\) 的谱分布服从半圆律 \[ f_{SC}(x)=\begin{cases} \dfrac{1}{2\pi}\sqrt{4-x^2},&|x|\le 2\\ 0, & |x|>2 \end{cases} \] 网络的 Laplacian 矩阵 \(L=D-A\)，其中 \(D\) 为各节点的度的对角矩阵

由于 \(L\)（或 \(A\)）是实对称矩阵，有 N 个实特征值 \(\lambda_j\)（有重）

谱密度 \[ \rho(\lambda)=\dfrac{1}{N}\sum_{j=1}^N\delta(\lambda-\lambda_j) \] 谱密度的 \(p\)-阶矩 \[ \begin{aligned} M_p&=\dfrac{1}{N}\int_{-\infty}^{+\infty}\lambda^p\rho(\lambda)\ \mathrm d\lambda\\ &=\dfrac{1}{N}\sum_{j=1}^N\lambda_j^p\\ &=\dfrac{1}{N}\operatorname{tr}(A^p)\\ &=\dfrac{1}{N}\sum_{i_1,i_2,\cdots,i_p}a_{i_1i_2}a_{i_2i_3}\cdots a_{i_pi_1} \end{aligned} \] 右侧即长为 \(p\) 的闭合回路总数

经典复杂网络模型分析

规则网络

  • 全局耦合网络（GCN）
  • 最近邻耦合网络（NCN）
  • 星形耦合网络（SCN）
网络类型 度 直径 \(D\) 平均路径长度 \(L\) 聚类系数 \(C_i\)，\(C\)
全局耦合网络 \(N-1\) \(1\) \(1\) \(C_i=C=1\)
最近邻耦合网络 \(K\) \(N/K\) \(\approx N/(2K)\) \(C_i=C=\dfrac{3(K-2)}{4(K-1)}\)
星形耦合网络 \(1\) 或 \(N-1\) \(2\) \(2-2/N\) \(0\)

随机网络

ER：所有可能边中选取 \(m\) 条

二项式模型：以概率 \(p\) 连接，边数期望 \(pN(N-1)/2\)

如果 \(N\to\infty\) 时产生一个具有性质 \(Q\) 的 ER 随机网络的概率为 \(1\)，那么就称几乎每一个 ER 随机网络都具有性质 \(Q\) ；如若 \(p>p_c\propto (\ln N)/N\)，几乎每一个 ER 网络都是联通的。

性质：

  • 度分布为 Poisson 分布（平均度 \(p(N-1)\)）
  • 平均距离 \(L_{ER}\propto\dfrac{\ln N}{\ln \left<k\right>}\) 短（小世界特性）
  • 聚类系数 \(C_{ER}=\dfrac{\left<k\right>}{N-1}=p\) 小
  • 特征谱半圆分布（\(p=cN^{-z}\)，\(0<z<1\)）(\(z>1\) 时不然)

小世界网络

性质

  • \(L\) 短；\(C\) 高，Poisson 分布

WS：NCN 网络按概率 \(p\) 重新随机连接

NW：NCN 网络按概率 \(p\) 随机加边

网络类型 度分布 平均路径长度 \(L\) 平均聚类系数 \(C\)
WS 近似泊松，至少 \(K/2\) \(\dfrac{2N}{K}f(NKp/2)\) \(\dfrac{3(K-2)}{4(K-1)}(1-p)^3\)
NW \(\dfrac{3(K-2)}{4(K-1)+4K(p+2)}\)

其中 \(f(u)\approx(2\sqrt{u^2+2u})\operatorname {arctanh}\sqrt{\dfrac{u}{u+2}}\)

小世界网络特征谱类似尖峰

无标度网络

Scale-Free Network

BA 网络，\(P\{k=x\}\propto x^{-\gamma}\)，\(2<\gamma <3\)

  • 增长，初始节点数 \(m_0\) 每次增加节点连接 \(m\) 条边

  • 优先连接：新节点 \(v\) 与已经存在的节点 \(v_i\) 连接的概率 \(\Pi_i\) 与度 \(k_i\) 正相关

连续场模型

\(\Pi_i=\dfrac{k_i+1}{\sum_j(k_j+1)}\)；\(t_i\) 为 \(v_i\) 加入网络的时间节点，有 \(k_i(t_i)=m\)，\(\dfrac{\mathrm dk_i}{\mathrm dt}=m\Pi_i(t)\)：

  • 解得 \(k_i(t)=m\sqrt{t/t_i}\)
  • 假设等时间间隔加入，该时间段 \(t\) 内某节点 \(v_i\) 度分布为常数 \(P\{k_i(t)<k\}=P\{t_i>\dfrac{m^2}{k^2}t\}\)

解得 BA 模型的度分布 \[ P\{k_i=k\}=\dfrac{\mathrm d P\{t_i>\dfrac{m^2}{k^2}t\}}{\mathrm d k}=\dfrac{2m^2t}{m_0+t}\cdot\dfrac{1}{k^3} \]

速率方程法

求解度分布

设 \(t\) 时刻拥有 \(k\) 条边的节点数（期望）为 \(N_k(t)\)，有 \(\sum_k kN_k(t)=2mt\) \[ \dfrac{\mathrm dN_k(t)}{\mathrm d t}=m\dfrac{(k-1)N_{k-1}(t)-kN_k(t)}{\sum_k kN_k(t)}+\delta_{km} \] 边界条件 \[ \delta_{km}=\begin{cases} 1,& k=m;\\ 0,& k\neq m. \end{cases} \] 求解，有 \(N_k(t)\approx tP\{k_i=k\}\)（大数定律 \(t\gg 1\)）

简化为 \((k+2)P\{k_i=k\}=(k-1)P\{k_i=k-1\}+2\delta_{km}\)

递推得 \(P\{k_i=k\}=\dfrac{2m(m+1)}{k(k+1)(k+2)}\propto 2m^2k^{-3}\)

求解度相关性

令 \(m=1\)，设 \(t\) 时刻连接的度分别为 \(k\) 和 \(l\) 的节点对数量为 \(N_{k,l}(t)\) \[ \dfrac{\mathrm dN_{kl}(t)}{\mathrm d t}= \dfrac{(k-1)N_{k-1,l}(t)-kN_{k,l}(t)}{2t} + \dfrac{(l-1)N_{k,l-1}(t)-lN_{k,l}(t)}{2t} +(l-1)N_{l-1}\delta_{kl} \] 化简为递归关系略；该递归关系证明了 \(n_{kl}\neq n_kn_l\)，即存在度相关性

其他参数

平均路径长度 \[ L\propto \begin{cases} \ln\ln N, &2<\gamma<3,\\ \dfrac{\ln N}{\ln\ln N}, & \gamma =3,\\ \ln N, & \gamma > 3, \end{cases} \] 平均聚类系数

高于 ER，幂律衰减

特征谱

三角形，幂律衰减

随机攻击鲁棒性（无阈值现象），故意攻击脆弱性（阈值很小）

对于随机网络，无论是故意攻击还是随机故障，只要所移除的节点比例超过一个阈值， 网络的极大连通分支中的节点比例将近似为零

层次网络

聚-度相关性

\(C_H(k)\) 表示度值为 \(k\) 的平均聚类系数

层次性：\(C_H(k)\propto k^{-a}\)，\(a\) 为层次指数

确定性网络

确定性小世界网络

从三角形开始，对每一条新加入的边构建一个新的三角形

点数 \(N_t=3\cdot 2^t\)，边数 \(M_t=3(2^{t+1}-1)\)

平均聚类系数 0.6931，度分布是指数分布

确定性无标度网络

阿波罗网络

Waxman 随机图产生器

连边概率正比于反指数距离

传播动力学

概念

  • S（Susceptible）
  • I（Infected）
  • R（Removed / Recovered）

SI 模型

\(i(t)=I(t)/N\)；\(s(t)=S(t)/N\)；\(i+s=1\)

所有个体脆弱，感染永远染病，感染率（每个 \(I\) 个体单位时间感染数量与 \(s\) 的比值）不变，个体总数不变 \[ \begin{cases} \dfrac{\mathrm d s}{\mathrm d t}=-\alpha i s\\ \dfrac{\mathrm d i}{\mathrm d t}=\alpha i s\\ \end{cases} \] 分离变量解得 \(i(t)=\dfrac{1}{1+(1/i_0-1)e^{-\alpha t}}\)

SIS 模型

加入单位时间治愈率 \(\beta\)，会反复发作 \[ \begin{cases} \dfrac{\mathrm d s}{\mathrm d t}=-\alpha i s+\beta i\\ \dfrac{\mathrm d i}{\mathrm d t}=\alpha i s-\beta i\\ \end{cases} \] 解伯努利方程

有效传播率 \(\lambda=\alpha/\beta\)，阈值为 \(\lambda_c=1\)

SIR 模型

被治愈免疫 \[ \begin{cases} \dfrac{\mathrm d s}{\mathrm d t}=-\alpha i s\\ \dfrac{\mathrm d i}{\mathrm d t}=\alpha i s-\beta i\\ \dfrac{\mathrm d r}{\mathrm d t}=\beta i\\ \end{cases} \] 无解析解，\(\lambda>1\) 则所有人最终 R，\(\lambda\le 1\) 则会剩余 S

SIRS

R 以概率 \(\gamma\) 成为 S \[ \begin{cases} \dfrac{\mathrm d s}{\mathrm d t}=\gamma r-\alpha i s\\ \dfrac{\mathrm d i}{\mathrm d t}=\alpha i s-\beta i\\ \dfrac{\mathrm d r}{\mathrm d t}=\beta i-\gamma r\\ \end{cases} \]

均匀网络传播动力学

平均场理论 MFT

基于 SIS

染病密度 \(\rho(t)\)，易感密度 \(1-\rho(t)\)

假设 \(k_i\approx \left <k\right>\)（均匀性），\(\lambda\propto \rho(t)\)（均匀混合），总数不变；不妨令 \(\beta=1\)（单位速率） \[ \dfrac{\mathrm d \rho}{\mathrm dt}=-\rho+\lambda \left<k\right>\rho(1-\rho) \] 稳态解 \(\rho=\dfrac{\lambda-\lambda_c}{\lambda}\)，\(\lambda_c=\dfrac{1}{\left<k\right>}\)

基于 SIR

\[ \begin{cases} \dfrac{\mathrm d s}{\mathrm d t}=-\lambda\left<k\right> i s\\ \dfrac{\mathrm d i}{\mathrm d t}=\lambda\left<k\right> i s- i\\ \dfrac{\mathrm d r}{\mathrm d t}=i\\ \end{cases} \]

有 \(\dfrac{\mathrm d s}{s}=-\lambda\left<k\right> \mathrm d r\)，则 \(s=e^{-\lambda\left<k\right> r}\)，得 \(r(\infty)=1-e^{-\lambda\left<k\right> r(\infty)}\)

存在非平凡解则满足 \(\left.\lambda\left<k\right>e^{-\lambda\left<k\right> r(\infty)}\right|_{r(\infty)\to0}\ge 1\)，则有 \(\lambda\ge\dfrac{1}{\left<k\right>}\)

泰勒展开得 \(r(\infty)\propto (\lambda-\lambda_c)\)

非均匀网络传播动力学

基于 SIS

度为 \(k\) 的节点染病密度 \(\rho_k(t)\) \[ \dfrac{\mathrm d \rho_k}{\mathrm dt} =-\rho_k+\lambda k(1-\rho_k)\sum_{k'}P(k' | k)\rho_{k'} \operatorname{tr}iangleq -\rho_k+\lambda k(1-\rho_k)\Theta(\rho_k) \] 求解稳态解，\(\rho_k=\dfrac{k\lambda\Theta}{1+k\lambda\Theta}\)

对于没有度度相关性的无标度网络，\(P(k' | k)=\dfrac{k'P(k')}{\left<k\right>}\)

稳态密度估算值 \(\rho=\sum_kP(k)\rho_k\)

可得 \(\Theta\) 的自治方程 \(\Theta =\dfrac{1}{\left<k\right>}\sum_{k'}\dfrac{k'^2P(k')\lambda\Theta}{1+k'\lambda\Theta}\)

若要存在非平凡解，要求 \(\dfrac{\lambda\left<k^2\right>}{\left<k\right>}\ge 1\)，即 \(\lambda_c=\dfrac{\left<k\right>}{\left<k^2\right>}\)

基于 SIR

类似地，\(\Theta(t)=\sum_{k'}P(k' | k)i_{k'}\) \[ \begin{cases} \dfrac{\mathrm d s}{\mathrm d t}=-\lambda ks_k\Theta\\ \dfrac{\mathrm d i}{\mathrm d t}=\lambda ks_k\Theta- i\\ \dfrac{\mathrm d r}{\mathrm d t}=i\\ \end{cases} \] 解得传播阈值完全一致

免疫策略

随机免疫

均匀网络 SIS 模型

免疫节点密度 \(\delta\)，随机网络下，传染率 \((1-\delta)\lambda\)，代入得免疫临界值 \(\delta_c=1-\dfrac{\lambda_c}{\lambda}\)

稳态感染密度 \(\rho_{\delta}=\dfrac{\delta_c-\delta}{1-\delta}\)，传播阈值 \(\tilde \lambda_c=\dfrac{\lambda_c}{1-\delta}\)

无标度网络 SIR 模型

\(\delta_c=1-\dfrac{\lambda_c}{\lambda}\)，\(\tilde \lambda_c=\dfrac{\lambda_c}{1-\delta}\)

目标免疫

非均匀网络 SIR 模型

\[ \delta_k= \begin{cases} 1 ,& k>\mathcal K,\\ c ,& k=\mathcal K,\\ 0 ,& k<\mathcal K.\\ \end{cases} \]

免疫平均概率 \(\overline \delta=\sum_k\delta_kP(k)\)

目标免疫后传播阈值 \(\hat \lambda_c>\dfrac{\lambda_c}{1-\overline \delta}\)

就无标度网络而言，免疫临界值 \(\delta_c\propto e^{-\dfrac{2}{m\lambda}}\)，其中 \(\delta=\sum_{k>kt}P(k)\)

复杂网络的同步动力学

Li-Yorke 混沌系统

迭代：\(f^{(n)}(x)=f(f^{(n-1)}(x))\)

周期点：对于某个 \(x_0\)，有 \(f^{(n)}(x_0)=x_0\)，但对 \(k<n\)，\(f^{(k)}(x_0)\neq x_0\)，则称 \(x_0\) 是一个 \(n\)-周期点

混沌：\(f(x)\) 在闭区间 \(X\) 上连续自映射，若

  1. 存在任意周期的周期点，且周期无上界；
  2. （不收敛不发散）\(X\) 上存在不可数子集 \(S\subset X\)，\(x_0\notin S\)，使
    • \(\forall x,y\in S\)，\(x\neq y\)，\(\lim_{n\to\infty} \inf|f^{(n)}(x)-f^{(n)}(y)|=0\)
    • \(\forall x,y\in S\)，\(x\neq y\)，\(\lim_{n\to\infty} \sup|f^{(n)}(x)-f^{(n)}(y)|>0\)
    • \(\forall x\in S\)，\(p\) 为任意周期点，\(\lim_{n\to\infty} \inf|f^{(n)}(x)-f^{(n)}(p)|=0\)

则 \(f(x)\) 在区间 \(S\) 上是混沌的

Li-York 论断：有 3-周期点则蕴涵混沌

混沌

混沌模型的特征

  • 初始值高度敏感
  • 有界（整体稳定性）：不会走出混沌吸引子
  • 随机性：任意区域概率密度不为零
  • 遍历性：可达到吸引子内任何不稳定周期轨道的任何邻域，且不会重复
  • 普适性：不依赖具体的系统方程
  • 正 Lyapunov 指数：相空间相邻两条轨道按指数速度分离或聚合的平均变化率

n-周期轨道：当 \(x_0\) 为一个 \(n\) 周期点，称 \(\{x_0,f^{(1)}(x_0),\cdots,f^{(n-1)}(x_0)\}\) 为 \(f(x)\) 的一个 n-周期轨道

例：Logistic 映射 \(f(x)=\alpha x(1-x)\)，\(0<\alpha \le 1\) 时稳定不动点 \(0\)；\(1<\alpha<3\) 稳定不动点 \(1-1/\alpha\)；\(\alpha=3\) 产生 \(2\)-周期点；\(\alpha>3.57\) 迅速产生倍周期分岔

Lyapunov 指数

一维

一维动力学系统 \(x_{n+1}=F(x_n)\)

假设每次映射迭代对 \(x_{0}\)，\(x_{0}+\varepsilon\) 引起指数分离 \[ \varepsilon e^{n\sigma(x_0)}=\left|F^{(n)}(x_0+\varepsilon)-F^{(n)}(x_0)\right| \] 取极限 \[ \sigma(x_0) =\lim_{n\to\infty}\lim_{\varepsilon\to 0}\dfrac{1}{n}\ln\left|\dfrac{F^{(n)}(x_0+\varepsilon)-F^{(n)}(x_0)}{\varepsilon}\right| =\lim_{n\to\infty} \dfrac{1}{n}\ln\left|\dfrac{\mathrm dF^{(n)}(x)}{\mathrm d x}\right| \] 将 \(F^{(n)}(x)\) 链式法则展开裂项相消得 Lyapunov 指数 \[ \sigma = \lim_{n\to\infty}\dfrac{1}{n}\sum_{i=1}^n\ln\left|\dfrac{\mathrm dF(x)}{\mathrm d x}\right|_{x=x_i} \]

高维

\(m\) 维离散动力学系统，设 \(F:\mathbb R^{m}\to\mathbb R^m\)

初始值选取无穷小的 \(m\) 维球面，将迭代后椭球的所有主轴按长度 \(p_i^{(n)}\) 排列，第 \(i\) 个 Lyapunov 指数 \[ \sigma_i = \lim_{n\to\infty}\dfrac{1}{n}\ln\dfrac{p_i^{(n)}}{p_i^{(0)}} \] 设 \(F_J(X)\) 表示 \(F\) 在 \(X\) 的 Jacobian 矩阵，\(J_k=F_J(X_0)F_{j}(X_1)\cdots F_J(X_{k-1})\)，将 \(J_k\) 的 \(m\) 个复特征值取模后排列得 \(\lambda_i^{(k)}\) \[ \sigma_i = \lim_{n\to\infty}\dfrac{1}{n}\ln\left|\lambda_i^{(k)}\right| \]

混沌同步

两个子系统构成的动力学系统 \[ \begin{cases} \dot X=F(X,Y,t)\\ \dot Y=G(X,Y,t) \end{cases} \] 若存在时间无关映射 \(H:\mathbb R^n\times\mathbb R^m\to\mathbb R^k\) 使 \[ \lim_{t\to\infty}\|H(\phi_X,\phi_Y)\|=0 \] 其中 \(\phi_X\)，\(\phi_Y\) 分别为其轨道的抽象性质，引出四种同步定义：完全同步、相位同步、滞后同步、广义同步

仅讨论完全同步 \[ \lim_{t\to\infty}\|X(t)-Y(t)\|=0 \] 沿同步流形上所有条件 Lyapunov 指数小于零

基于条件 Lyapunov 指数的稳定性判据

误差系统 \(Z=X-Y\)，动力学微分方程组 \(\dot Z=F(Z)\)，假设 \(0\) 是平衡点，\(F(Z)\) 在区域 \(G=\{Z\ | \ \|Z\|\le a, a>0\}\) 有连续偏导数

第一方法（间接法）

线性化扰动方程 \[ \dfrac{\mathrm d}{\mathrm d t}\delta Z(t)=L\delta Z(t) \] 其中 \(L\) 是 \(F(Z)\) 在 \(Z=0\) 处的 Jacobi 矩阵

条件 Lyapunov 指数 \[ \sigma_i = \lim_{n\to\infty}\dfrac{1}{n}\ln\left|\dfrac{\partial z_i{(t)}}{\partial z_i{(0)}}\right| \] 若所有指数小于零，则趋于稳定

第二方法（直接法）

构造正定标量函数 \(V(Z)\) 作为虚拟广义能量函数

Lyapunov 函数 \(V(Z)\) 为 \(\|Z\|\le a\) 内定义的一个实连续标量函数，\(V(0)=0\)，正定。假设对所有变量偏导数存在且连续，动力学方程组解条件下对时间求导得 \(V(Z)\) 关于动力学方程组的全导数 \[ \left.\dfrac{\mathrm dV(Z)}{\mathrm d t}\right|_{\dot Z=F(Z)} = \sum_{i=1}^{m}\left(\dfrac{\partial V(Z)}{\partial z_i}\cdot\dfrac{\mathrm d z_i}{\mathrm d t}\right) = \sum_{i=1}^{m}\left(\dfrac{\partial V(Z)}{\partial z_i}\cdot f_i(Z)\right) \] 判定定理

  • 若存在 \(V(Z)\)，其关于动力学方程组的全导数半负定或为零，则系统零解稳定
  • 若存在 \(V(Z)\)，其关于动力学方程组的全导数负定，则系统零解渐进稳定
  • 若存在 \(V(Z)\)，其关于动力学方程组的全导数半负定，但使全导数为零的点 \(Z\) 只有 \(Z=0\)（其他解负），则系统零解渐进稳定

同步方法

驱动-响应法（P-C 同步法）

考虑 \(n\) 维自治动力学系统 \(\dot U=F(U)\) 的两个子系统 \[ \begin{cases} \dot V=G(V,W)\\ \dot W=H(V,W) \end{cases} \] 第一个是稳定系统，第二个是混沌系统；上述系统构成驱动系统，构造响应系统 \(\dot W'=H(V,W')\)，则 \(W\) 与 \(W'\) 受相同驱动变量 \(V\) 驱动，其误差系统 \(\dot Z=\dot W-\dot W'=H(V,W)-H(V,Z-W)\)

复杂动态网络的完全同步

考虑一个以 \(N\) 个相同的动力学系统 \(\dot X_i=F(X_i)\) 作为节点所构成的连续时间耗散耦合动态网络，该网络状态方程 \[ \dot X_i=F(X_i)+c\sum_{j=1}^N l_{ij}HX_j \] 其中 \(c>0\) 为耦合强度，\(H\) 为内部耦合函数（输出函数），其为对角阵，描述进行耦合的状态变量，完全同步时 \(H=0\)

\(l_{ij}\) 构成外耦合矩阵 \(L\)，表示网络的拓扑结构，行和为零（可用拉普拉斯矩阵）；\(L\) 仅有一个重数为 \(1\) 的零特征值，对应特征向量为 \(1\) 向量，其他特征值均为负实数

网络完全同步：\(\lim_{t\to\infty} X_i(t)=S(t)\)（可达到同步状态 \(S(t)\)）

若耦合强度与外耦合矩阵每个负特征值的积都在同步化范围内 \(c\lambda_k\in U\)，则渐近稳定；根据同步化区域 \(U\) 不同类型分为

  • 类型 I 网络 \(U=(-\infty,\alpha_1)\)，则 \(c\lambda_2<\alpha_1\) 时稳定
  • 类型 II 网络 \(U=(\alpha_1,\alpha_2)\)，则 \(c\lambda_2<\alpha_1\)，\(c\lambda_N>\alpha_2\) 时稳定
  • 类型 III 网络 \(U=\emptyset\)

均匀网络

最近邻网络 \(\lim_{N\to\infty}\lambda_2=0\)，当 \(N\) 很大时 \(\lambda_N/\lambda_2\) 很大

全局耦合网络 \(\lambda_2=\lambda_3=\cdots=-N\)

星形网络 \(\lambda_2=-1\)，\(\lambda_N=-N\)

NW 小世界网络

随着 \(p\) 不断增加，第二特征值线性变小直至趋近 \(-N\)

WS 小世界网络

随着 \(p\) 不断增加，第二特征值一次变小直至趋近 \(-N\)

无标度网络

\(\lambda_2\) 随着 \(m\) 增加而下降，随 \(N\) 增加而上升，\(\lim_{N\to\infty}\lambda_2=\tilde \lambda_2<0\)（\(10^{-1}\) 数量级）

若随机删除节点，特征值很快逼近 \(0\)