复杂网络的无标度特性

1、复杂网络的无标度特性复杂网络的无标度特性第1页目录概率统计预备知识网络(图)基础概念规则图和随机网Scale-free网络常见软件参考文件复杂网络的无标度特性第2页一、概率统计预备知识复杂网络的无标度特性第3页目录随机变量与分布函数（离散、连续）随机变量数字特征（数学期望、方差）泊松分布幂函数指数函数复杂网络的无标度特性第4页随机变量与分布函数对某个随机试验 ，假如每次试验结果能够用一个数X来表示，而且对任何实数k，Xx有着确定概率，则称X是随机变量。随机变量X值小于实数k概率P(Xx)是x函数，记作 F(k)=P(X0是常数，则称变量X服从参数为 泊松分布，记为 复杂网络的无标度特性第14页

2、复杂网络的无标度特性第15页于是，x数学期望为：即复杂网络的无标度特性第16页复杂网络的无标度特性第17页所以，X方差和均方差分别为： 复杂网络的无标度特性第18页指数函数对公式线性化，两边取对数得令则复杂网络的无标度特性第19页指数函数复杂网络的无标度特性第20页幂函数式中 为实数。对公式线性化，两边取对数，得令 ， ， 得函数形式为：复杂网络的无标度特性第21页幂函数变量代换可在双对数坐标上得直线， 复杂网络的无标度特性第22页二、网络(图)基础概念复杂网络的无标度特性第23页中国教科网复杂网络的无标度特性第24页网络(图)基础概念节点通常见来表示系统中部件；边通常见来表示系统中部件之间关

3、系。网络(图)就是由节点与节点之间关系组成一张图。复杂网络的无标度特性第25页中国教科网拓扑结构复杂网络的无标度特性第26页网络（图）基础概念关联与邻接度、平均度节点度分布最短路径与平均路径长度群系数复杂网络的无标度特性第27页网络(图)基础概念aedcb复杂网络的无标度特性第28页有向图、无向图、不连通图复杂网络的无标度特性第29页网络(图)基础概念节点度分布是指网络（图）中度为 节点概率 随节点度 改变规律。复杂网络的无标度特性第30页网络(图)基础概念最短路径就是从指定始点到指定终点全部路径中总权最小一条路经。平均路径长度是指全部点对之间最短路径算术平均值。复杂网络的无标度特性第31页网

4、络(图)基础概念集群系数(Clustering coefficient)反应网络群集程度，定义为网络平均度与网络规模之比。复杂网络的无标度特性第32页22 77 55553311网络(图)基础概念复杂网络的无标度特性第33页节点1到7之间最短路13，平均路径长度5.47，平均度为3.4，集群系数为0.48。网络(图)基础概念复杂网络的无标度特性第34页三、规则图和随机图规则图特征假如系统中节点及其与边关系是固定，每个节点都有相同度数，就能够用规则图来表示这个系统。随机图特征假如系统中节点及其与边关系不确定，就只能用随机图来表示这个系统。复杂网络的无标度特性第35页规则图特征平均度为3。复杂网络

5、的无标度特性第36页随机图特征节点确定，但边以概率 任意连接。节点不确定，点边关系也不确定。复杂网络的无标度特性第37页随机图节点19，边43平均度为2.42，集群系数为0.13。复杂网络的无标度特性第38页随机图节点42，边118平均度为5.62，集群系数为0.133。复杂网络的无标度特性第39页四、Scale-free网络复杂网络的无标度特性第40页目录早期网络模型无标度Scale-free网络BA模型复杂网络的无标度特性第41页早期网络模型ER模型小世界模型复杂网络的无标度特性第42页ER模型Erds和Rnyi （ER）最早提出随机网络模型并对模型进行了深入研究，他们是用概率统计方法研究

6、随机图统计特征创始人。在模型开始阶段给定N个节点，没有边，以概率p用边连接任意一对节点，用这么方法产生一随机网络。复杂网络的无标度特性第43页复杂网络的无标度特性第44页ER模型Erds和Rnyi（1959）首先研究了在随机网络中最大和最小度分布，Bollobs(1981)随即得到了全部度分布形式，推导出度数为k节点数遵从平均值为 泊松分布，即 复杂网络的无标度特性第45页Connect with probability pp=1/6 N=10 k 1.5Poisson distribution复杂网络的无标度特性第46页小世界模型为了描述从一个局部有序系统到一个随机网络转移过程，Watts和

7、 Strogatz（WS）提出了一个新模型，通常称为小世界网络模型。WS模型始于一含有N个节点一维网络，网络节点与其最近邻接点和次邻接点相连接，然后每条边以概率p重新连接。约束条件为节点间无重边，无自环。复杂网络的无标度特性第47页C(p) : clustering coeff. L(p) : average path lengthP(k)=0.1 p(k)=0.3复杂网络的无标度特性第48页小世界模型当p等于0时，对应网络规则图。两个节点间平均距离线性地随N增加而增加，集群系数大。当p等于1时，系统变为随机图。 对数地随N增加而增加，且集群系数随N降低而降低。在p等于（0，1）区间任意值时，

8、模型显示出小世界特征，约等于随机图值，网络含有高度集群性。复杂网络的无标度特性第49页复杂网络都含有分布于平均值两边度分布曲线吗？复杂网络的无标度特性第50页无标度(Scale-free)网络Scale-free网络发觉Scale-free网络特征复杂网络的无标度特性第51页Scale-free)网络发觉信息交换网（万维网、国际互联网、电话网、电力网）社会网络（电影演员合作网、科研合作图、引文网、人类性接触网、语言学网）生物网络（细胞网络、生态网络、蛋白质折叠）复杂网络的无标度特性第52页复杂网络的无标度特性第53页复杂网络的无标度特性第54页Scale-free网络特征度分布呈幂率分布中枢节

9、点出现稳健性脆弱性复杂网络的无标度特性第55页复杂网络的无标度特性第56页复杂网络的无标度特性第57页无标度网络与随机图特征比较复杂网络的无标度特性第58页无标度（Scale-free）网络无标度模型由Albert-Lszl Barabsi和Rka Albert在1999年首先提出，现实网络无标度特征源于众多网络所共有两种生成机制： （）网络经过增添新节点而连续扩张； （）新节点择优连接到含有大量连接节点上。复杂网络的无标度特性第59页BA模型增加和择优连接这两种要素激励了BarabsiAlbert模型提出，该模型首次导出度分布按幂函数规律改变网络。模型算法以下：（1）增加：开始于较少节点数量

10、（m0），在每个时间间隔增添一个含有m（m0）条边新节点，连接这个新节点到m个不一样已经存在于系统中节点上。（2）择优连接：在选择新节点连接点时，假设新节点连接到节点i概率取决于节点i度数即复杂网络的无标度特性第60页经过t时间间隔后，该算法程序产生一含有N=t+m0个节点，mt条边网络。数量模拟表明含有k条边节点概率服从指数为r=3幂指数分布。复杂网络的无标度特性第61页P(k) k-3A.-L.Barabsi, R. Albert, Science 286, 509 (1999)复杂网络的无标度特性第62页BA模型（a)Barabsi-Albert模拟度分布。（b）不一样系统规模下 。 复

11、杂网络的无标度特性第63页BA模型设节点 i 度 满足动态方程：分母求和是对系统中除新进入系统节点外全部节点进行 ，则复杂网络的无标度特性第64页BA模型当t足够大时，有解微分方程，有复杂网络的无标度特性第65页由初始条件得解为 式中可给出度小于k节点概率 复杂网络的无标度特性第66页设在相同时间间隔，添加节点到网络 中， 值含有常数概率密度 代入前式t趋于无穷时度分布 式中复杂网络的无标度特性第67页模型度分布是与时间无关渐进分布且与系统规模无关。 幂律度分布系数与 成正比 。无标度模型动态特征能够用各种分析方法给出 ： 连续域理论 主方程法 改变率方程法 复杂网络的无标度特性第68页Bar

12、alsi-Albert模型限制条件 保持了网络增加特征，不考虑择优连接，网络度分布呈指数衰减。 消除了增加过程，只考虑择优连接，络度分布围绕其均值为一高斯分布。复杂网络的无标度特性第69页Baralsi-Albert模型扩展研究初始吸引度非线性择优连接择优连接更迭机理 增加制约条件及增加方式局部相互作用适应度模型复杂网络的无标度特性第70页五、常见软件SasMatlabPajekOriginNetdrawWaxmanGt-itmTiers BriteInetPlarg复杂网络的无标度特性第71页六、主要参考文件Albert, R., H. Jeong, and A.-L. Barabsi, Diameter of the World-Wide-Web,1999, Nature (London)401, 130. Barabsi, A.-L., and R. Albert, Emergence of scaling in random networks, 1999, Science 286, 509 .Barabsi, A.-L., R. Albert, and H. Jeong, Me