复杂网络 彭海朋

虫口方程

第零讲

$$
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
$$