复杂网络 彭海朋

虫口方程

第零讲

$$
x_{n+1}=\gamma x_n(1-x_n)
$$

在不控制的条件下，人口每25年增加一倍，即按几何级数增长。xn+1 = 𝛾xn。修正就是计入限制虫口增长的负因素。虫口数目太多时，由于争夺有限的食物和生存空间发生咬斗，由于接触传染而导致疾病蔓延，争斗使虫口数目减少的事件，这些事件的数目比例于xn^2。

Logistic映射（Logistic Map）

$$
x_{n+1}=rx_n(1-x_n)
$$

分叉与周期倍增（Bifurcation & Period Doubling）

對初始值的敏感性

混沌内部的自相似结构

第一讲

复杂网络的数学描述

网络G=（V, E），由点集V（G）和边集E（G）组成的一个图，可分为无向、有向和加权网络
令ei∈ E（G），每条边ei有V（G）中的一对点(u,v)与之对应；如果任意(u,v)与(v,u)对应同一条边，则称为无向网络，否则为有向网络；如果任意∣ei ∣ =1，则称为无权网络，否则为加权网络。

——复杂网络是对复杂系统的一种抽象

对网络拓扑结构的描述

几何量及其分布

度（Degree）：朋友的个数
集聚系数（群系数）（Clustering coefficient）：朋友的朋友还是不是朋友的情况
最短路径（Shortest path）：两个顶点之间边数最少的路径
介数（Betweenness）：经过我的最短路径的条数

网络的基本模型

  • 规则网
    (a) 完全连接; (b) 最近邻居连接; (c) 星形连接; (d) Lattice; … (z) Layers
  • 随机图
  • 小世界网络
  • Scale-Free 网络

ER 随机图模型

特征:
连通性:Poisson 分布
齐次特征:每个节点大约有相同的
连接数:节点数不增加

Untitled

小世界网络

特征:
齐次性:每个节点有大约相同的连接数
节点不增加

Scale Free网络的基本特征

Power Law Degree Distribution（幂律度分布）

$$
P(k)\propto k^{-\gamma} \ \ \ \ \ln P(k)\propto -\gamma\ln k\P(\lambda k)\propto(\lambda k)^{-\gamma}=\lambda^{-\gamma}k^{-\gamma}=\lambda^{-\gamma}P(k)
$$

1、自相似结构
2、两极分化，高度弥散

六度分隔（Six Degrees of Separation）理论。简单地说：“你和任何一个陌生人之间所间隔的人不会超六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。”

比较

E/R随机图模型 现实生活的复杂网络
平均距离 小/大 小
聚类系数 大/小 大(Small-world feature)
度分布 二项式/Poisson 幂指数(Scale-free feature)

直径：两点间最短距离的最大值

分形

分形和不规则形状的几何有关。

分形（Fractal)：局部与整体具有相似性，或者说在标度变换下具有相似性的几何形体。

曼德勃鲁集

分形音乐

分维

假设ε是小立方体一边的长度， N （ε）是用此小立方体覆盖被测形体所得的数目，维数公式意味着通过用边长为ε的小立方体覆盖被测形体来确定形体的维数。对于通常的规则物体 ，覆盖一根单位 长度的线 段所需 的数目要 N （ε）＝1／ε，覆盖一个单位边长的正方形，N(ε)＝（1／ε）2 ，覆盖单位边 长的立方体，N （ε）＝（1／ε）3。从这三个式子可见维数公式也适用于通常的维数含义。

复杂网络病毒的行为分析

恶意代码的基础知识

恶意代码是最头痛的安全问题之一，它甚至是整个软件安全的核心。虽然单独对付某台设备上的指定恶意代码并不难，但是，网上各种各样的海量恶意代码，却像癌细胞一样，危害着安全，而且，既杀之不绝，又严重消耗正常体能。

狭义上说，恶意代码是指故意编制或设置的、会产生威胁或潜在威胁的计算机代码（软件）。最常见的恶意代码有计算机病毒、特洛伊木马、计算机蠕虫、后门、逻辑炸弹等。
广义上说，恶意代码还指那些没有作用却会带来危险的代码，比如，流氓软件和广告推送等。

恶意代码的入侵手段主要有三类：利用软件漏洞、利用用户的误操作、前两者的混合。

恶意代码的主要传播方式是病毒式传播

死亡型病毒的动力学分析

设网络的用户数为N，在t时刻，已经受害的用户数为T(t)，暂未受害的用户数为S(t)，那么，有恒等式S(t)+T(t)=N。
再令f(S,T)为在“已有T人受害，S人暂未受害”条件下，受害事件发生率，于是，有下面两个微分方程
dT(t)/dt=f(S,T) 和 dS(t)/dt=-f(S,T)

在生物医学的流行病学中，有一个可借鉴的概念是传染力λ(T)，它表示在已有T台设备中毒的情况下，暂未中毒的设备与中毒者相连接的概率，所以，f(S,T)=λ(T)S；
另一个概念是传染率β，它表示一个未中毒设备在连接到中毒者后，被传染的概率；所以，λ(T)=βT。于是，f(S,T)=λ(T)S=βTS，即，它是一个双线性函数。

康复型病毒的动力学分析

与死亡型模型不同，在康复型模型中，受害用户在经过救治后，又可以康复成为暂未受害的用户，当然，该用户也可能再次受害。
其实，绝大部分恶意代码，特别是诱骗类恶意代码，都是这种康复型的。

在此，除了10.2节中的S、T、F(S,T)和N等概念外，我们再引入另一个概念，即g(T)，它表示在T个受害者中，有g(T)个用户被康复成正常健康用户，从而，变成暂未受害用户。
若用γ表示康复率（生物医学经验告诉我们：每个受害者，在下一小段时间δt内，被康复的概率为γδt+0(δt)2。并且受害者被康复的时间，服从均值为1/γ的指数分布。）那么：g(T)=γT

由此，我们可以得到微分方程组：
dT(t)/dt=f(S,T)-g(T)=βTS-γT和 dS(t)/dt=-f(S,T)+g(T)=-βTS+γT
若令u(t)=S(t)/N， v(t)=T(t)/N， t’=γt和R0=βN/γ，那么，上面的两个微分方程就变为：
du/dt=-(R0u-1)v 和dv/dt=(R0u-1)v
其定义域为：D={0≤u≤1,0≤v≤1,u+v=1}

定理10.1：针对康复型恶意代码，如果R0<1，那么，康复型恶意代码就会最终被消灭，即，无人受害；反过来，如果R0>1，那么，康复型恶意代码就会在一定范围内长期为害，具体地说，受害者人数将长期徘徊在N(1-1/R0)附近。

免疫型病毒的动力学分析

设S、T、γ、β和N等概念与10.3节相同，又记R(t)为t时刻被康复（具有了免疫力）的用户数。于是，在任何一个时刻，都恒有N=S(t)+T(t)+R(t)
为了使相关公式看起来简单一些，分别用S(t)/N、T(t)/N和R(t)/N去代替S(t)、T(t)和R(t)并且仍然采用原来的记号来表示S(t)、T(t)和R(t)，此时便有S(t)+T(t)+R(t)=1
简单来说，S(t)、T(t)和R(t)分别代表暂未受害、正受害和受害康复且具有免疫力的用户，各占总用户数的比例。

定理10.2：针对免疫型恶意代码，当F0<1时，此恶意代码不会爆发，并随着时间的推移，会自动消灭；当F0>1时，该恶意代码会在一定的时段内爆发，受害者人数达到一个最大值Tmax后，才开始递减，并最终消灭。更深入地，Tmax在总人数中所占的比例为1-ρ+ρln(ρ/S0)
在这里S0表示刚开始时，暂未受害的人数比例。

开机和关机对免疫型病毒的影响

以上所有小节的分析，都假定活跃用户数固定为N。但是，在实际情况下，当然有例外。比如，某用户主动关机后，任何恶意代码对他都不构成威胁，此时活跃用户就减少一个；当某用户终端中毒后被宕（dang）机，这里活跃用户数也减少一个；当新用户开机（或进入网络）后，他又可能成为恶意代码的攻击对象，这时，活跃用户数又增加一个等。

定理10.3：记P0=β/(γ+μ)，那么，在情况1之下，
当P0≤1时，该免疫型恶意代码一定会随着时间的推移，最终自动消灭；
当P0≥1时，该免疫型恶意代码一定会随着时间的推移，最终在$S=1/P_0、T=μ(P_0-1)/β、R=1-1/P_0-μ(P_0-1)/β$点处达到全局渐近稳定，即，最终健康终端的比例为$S=1/P_0$，受害终端的比例为$T=μ(P_0-1)/β$，获得免疫力的终端比例为$R=1-1/P_0-μ(P_0-1)/β$。

预防措施的效果分析

我们虽然不能强求全体用户都采取预防措施，但是，如果有比例为p的用户采取了预防措施（比例为q的用户偷了懒，此处，p+q=1），那么，我们发现：只要当p足够大时，仍然能够消灭该恶意代码。

定理10.5：在10.5节的情况1中，如果在暂未受害的终端中，采取了预防措施终端数的比例p≥1-1/P0，这里P0=β/(γ+μ)，那么，该免疫型恶意代码一定会随着时间的推移，最终自动消灭。
此定理告诉我们：对付恶意代码，虽然不能指望全体人员都及时采取预防措施，但是，只要有足够多的人（占总人数比例超过P0=β/(γ+μ)）重视安全，并及时采取了预防措施，那么，该恶意代码就一定是可控的，甚至会最终被消灭。

回声状态网络

人工神经网络（Artificial Neural Network）是由大量处理单元互联组成的非线性、自适应信息处理系统 。

人工神经网络按照性能分为两类：
（1）静态神经网络 Static Neural Network
（2）动态神经网络 Recurrent Neural Network
其中，动态神经网络又称为递归神经网络

两种网络对比：

静态网络数学表达式：

$$
y=\sigma(\sum^n_{i=1}\omega_1x_1+\sigma_1)
$$

静态网络数学表达式：

$$
y=\sigma(\sum^n_{i=1}\omega_1x_1(t-\tau_i)+\sigma_1)
$$

对比表达式，我们可以看出：动态网络内部存在带延迟因子的反馈连接，可以更好的反映动态系统的特性和演化行为 。而静态网络没有这种能力。

回声状态状态网络作为一种新型的递归神经网络，无论是建模还是学习算法，都已经与传统的递归神经网络差别很大。
ESN网络特点：
（1） 它的核心结构是一个随机生成、且保持不 变的储备池（Reservoir）
（2）其输出权值是唯一需要调整的部分
（3）简单的线性回归就可完成网络的训练

ESN的结构和运行机理

ESN网络的核心结构是一个“储备池”。所谓的储备池就是随机生成的、大规模的、稀疏连接（SD通常保持1%~5%连接 ）的递归结构。
注：SD是储备池中相互连接的神经元占总的神经元N的百分比

从结构上讲，ESN是一种特殊类型的递归神经网络，其基本思想:使用大规模随机连接的递归网络，取代经典神经网络中的中间层，从而简化网络的训练过程。
我们假设系统具有M个输入单元，N个内部处理单元（Processing Elements，PE），即N个内部神经元，同时具有L个输出单元。

那么输入单元u（n）内部状态x（n）以及输出单元y（n）在n时刻值分别为：

$$
u(n)=[u_1(n),u_2(n),\dots,u_M(n)]^T\ x(n)=[x_1(n),x_2(n),\dots,x_N(n)]^T\ y(n)=[y_1(n),y_2(n),\dots,y_L(n)]^T
$$

则回声状态网络状态方程为：

$$
x(n+1)=f(Wx(n)+W_{in}u(n)+W_{back})y(n)\ y(n+1)=f_{out}(W_{out}[x(n+1),u(n+1),y(n)]+W_{bias}^{out})
$$

ESN的储备池

虽然有大量的研究是关于如何获得与具体问题相关的“好”的储备池，但是并没有形成一个系统的方法，多数研究是从实验的角度进行的。这也是目前ESN方法遇到的最大的挑战。
ESN的最终性能是由储备池的各个参数决定的，下面首先简要介绍储备池的四个关键参数。

储备池内部连接权谱半径SR

储备池规模N

储备池输入单元尺度IS

储备池稀疏程度SD

关于IS的规则：
如果需要处理的任务的非线性越强，那么输人单元尺度越大。
该原则的本质是通过输入单元尺度IS，将输入变换到神经元激活函数funtion相应的范围。
注：神经元激活函数的不同输入范围，其非线性程度不同。

智能优化算法

牛顿迭代法、共轭梯度法、单纯形法、黄金分割

课上重点

求

$$
\min(x_1^2+2x_2^2)=E
$$