《无标度网络模型构造实践报告》由会员分享，可在线阅读，更多相关《无标度网络模型构造实践报告（11页珍藏版）》请在金锄头文库上搜索。
1、轡讹H工芳女毎课题：无标度网络模型构造姓名 赵训学号 201026811130班级 实验班1001源起无标度网络（或称无尺度网络）的概念是随着对复杂网络的研究而出现的。 “网络”其实就是数学中图论研究的图，由一群顶点以及它们之间所连的 边构成。在网络理论中则换一套说法，用“节点”代替“顶点”，用“连 结”代替“边”。复杂网络的概念，是用来描述由大量节点以及这些节点 之间错综复杂的联系所构成的网络。这样的网络会出现在简单网络中没有 的特殊拓扑特性。自二十世纪60年代开始，对复杂网络的研究主要集中在随机网络上。随机 网络，又称随机图，是指通过随机过程制造出的复杂网络。最典型的随机 网络是保罗埃尔德
2、什和阿尔弗雷德雷尼提出的ER模型。ER模型是基于 一种“自然”的构造方法：假设有:个节点，并假设每对节点之间相连的 可能性都是常数门厂。这样构造出的网络就是ER模型网络。科学家 们最初使用这种模型来解释现实生活中的网络。ER模型随机网络有一个重要特性，就是虽然节点之间的连接是随机形成的, 但最后产生的网络的度分布是高度平等的。度分布是指节点的度的分布情 况。在网络中，每个节点都与另外某些节点相连，这种连接的数目叫做这 个节点的度。在网络中随机抽取一个节点，它的度是多少呢？这个概率分 布就称为节点的度分布。在一般的随机网络（如ER模型）中，大部分的节点的度都集中在某个特殊 值附近，成钟形的泊松分
3、布规律（见下图）。偏离这个特定值的概率呈指 数性下降，远大于或远小于这个值的可能都是微乎其微的，就如一座城市 中成年居民的身高大致的分布一样。然而在1998年，Albert-Laszlo Barab dsi、Reka Albert等人合作进行一项描绘万维网的研究时，发现通过超链 接与网页、文件所构成的万维网网络并不是如一般的随机网络一样，有着 均匀的度分布。他们发现，万维网是由少数高连接性的页面串联起来的。 绝大多数（超过80%）的网页只有不超过4个超链接，但极少数页面（不到 总页面数的万分之一）却拥有极多的链接，超过1000个，有一份文件甚至 与超过200万个其他页面相连。与居民身高的例子作
4、类比的话，就是说大多 数的节点都是“矮个子”，而却又有极少数的身高百丈的“巨人”。Barab asi等人将其称为“无标度”网络。二、 描述与定义无标度网络的特性，在于其度分布没有一个特定的平均值指标，即大多数节点的 度在此附近。在研究这个网络的度分布时,Barabdsi等人发现其遵守幂律分布（也 称为帕累托分布），也就是说，随机抽取一个节点，它的度汀是自然数卜的概率：也就是说的概率正比于上的某个幂次（一般是负的，记为：）。因此人越大，的概率就越低。然而这个概率随卜增大而下降的“速度”是比较缓慢的：在一般的随机网络中，下降的速度是指数性的，而在无尺度网络中只是以多 项式类的速度下降。在现实中许多
5、大规模的无尺度网络中，度分布：的值介于2与3之间。在对数坐标 系中，度分布将会是一条斜率介于-2至-3之间的直线。如下图中，横坐标为节点 的度，从川：一直到二几 纵坐标为找到这样的节点的概率从一直到川：。最高度数的节点有882条连接。所有的蓝点大致成一条直线分布（绿色的直线）。200,000个节点的无标度网络的度分布(对数坐标)仅仅是将度分布的幂律分布作为无标度网络的定义有其不够完善之处。由于幂律 分布是方差可能无穷的高可变分布，对于度分布是同一个幂律分布的不同网络， 其拓扑结构和特性可能存在巨大的差异。2005年，Lun Li和大卫阿尔德森(David Alderson)等人在论文迈向无标度
6、图的理论(Towards a Theory of Scale Free Graphs)中提出了一种补充性的标度性测度。擾；为所有具有(依照幂律分 布的)度分布D二的网络口的集合，对于其中每一个网络定义度-度相关数：5二 E d-d3-其中八表示丿中所有连接的集合。根据排序原理，如果度数大的点之间相互连接的话，那么山会比较大。设为最大的，那么定义度-度相关系数：s（s）=度-度相关系数R介于0与1之间。越靠近1,则称此网络“无尺度”的，Bi；靠近0,则称是“富尺度”的。在此定义下，无尺度网络中的节点度数分布 特征体现了自相似的性质，而凸显了“无尺度”的特征，与富尺度网络之间有相 当的差异。三、例
7、子不少现实中的网络结构都属于无标度网络，或者有无标度的特性。以下是一些无 标度网络的例子：网络节点连接电影演员网络演员出演同一部电影万维网网页超链接因特网路由器物理连接蛋白质相互作用网络蛋白质蛋白质之间的相互作用关系金融网络金融机构借贷关系美国飞机航班网络机场飞机航线BA模型及其构造算法Alber t-Ldszl6 Barabdsi与RQka Alber t在1999年的论文中提出了一个模型来解 释复杂网络的无标度特性，称为BA模型。这个模型基于两个假设：增长模式：不少现实网络是不断扩大不断增长而来的，例如互联网中新网页的 诞生，人际网络中新朋友的加入，新的论文的发表，航空网络中新机场的建造等
8、 等。优先连接模式：新的节点在加入时会倾向于与有更多连接的节点相连，例如新 网页一般会有到知名的网络站点的连接，新加入社群的人会想与社群中的知名人 士结识，新的论文倾向于引用已被广泛引用的著名文献，新机场会优先考虑建立 与大机场之间的航线等等。在这种假设下，BA模型的具体构造为：1增长：从一个较小的网络心开始（这个网络有匕:个节点，条边），逐步加入新的节点，每次加入一个。2连接：假设原来的网络已经有打个节点（）。在某次新加入一个节点，时，从这个新节点向原有的;个节点连出个连结。3优先连接：连接方式为优先考虑高度数的节点。对于某个原有节点二为：；0，将其在原网络中的度数记作&,那么新节点与之相连
9、的概率二此JEJ=i 冷这样，在经过F次之后，得到的新网络有： - 个节点，一共有尺：小条边。分析BA模型网络的渐近度分布（当节点数量很大时的度分布）主要有连续场理论、 主方程法和速率方程法。这三种方法得到的渐近结果都是相同的。2001年，Bela Bollobds证明了在节点数量很大时，BA模型网络的度分布遵从；二的幂律分布。 之后，其它的无标度网络模型也开始被提出。有 1000 个节点的 BA 模型网络制造BA模型的过程：每次增加一个节点，两个连接相应程序代码(使用Matlab实现)FreeScale.mfunction matrix = FreeScale(X)N= X; m0= 3;
10、m= 3;%初始化网络数据 adjacent_matrix = sparse( m0, m0);% 初始化邻接矩阵 for i = 1: m0for j = 1:m0if j = i%去除每个点自身形成的环adjacent_matrix(i,j) = %建立初始邻接矩阵， 3点同均同其他的点相连 endendendadjacent_matrix =sparse(adjacent_matrix); %邻接矩阵稀疏化 node_degree = zeros(1,m0+1);%初始化点的度node_degree(2: m0+1) = sum(adjacent_matrix); %对度维数进行扩展 f
11、or iter= 4:Niter% 加点total_degree = 2*m*(iter- 4)+6% 计算网络中此点的度之和 cum_degree = cumsum(node_degree) % 求出网络中点的度矩阵 choose= zeros(1,m) % 初始化选择矩阵% 选出第一个和新点相连接的顶点r1= rand(1)*total_degree % 算出与旧点相连的概率for i= 1:iter-1if (r1=cum_degree(i)&( r1=cum_degree(i)&(r2=cum_degree(i)&(r2=cum_degree(i)&(r3=cum_degree(i)&
12、(r3cum_degree(i+1) choose(3) = i;breakendendend %新点加入网络后, 对邻接矩阵进行更新 for k = 1:madjacent_matrix(iter,choose(k) = 1; adjacent_matrix(choose(k),iter) = 1;endnode_degree=zeros(1,iter+1);node_degree(2:iter+1) = sum(adjacent_matrix);endmatrix = adjacent_matrix;tu_plot.mfunction tu_plot(rel,control)%由邻接矩阵画
13、连接图，输入为邻接矩阵rel,必须为方阵；%control 为控制量， 0 表示画出的图为无向图， 1 表示有向图。默认值为 0 r_size=size(rel); %a=size(x)返回的是一个行向量，该行向量第一个元素是%x的行数，第2个元素是x的列数if nargin2%nargin 是用来判断输入变量个数的函数con trol=0; %输入变量小于2 ,即只有一个，就默认con trol为0endif r_size(1)=r_size(2) %行数和列数不相等，不是方阵，不予处理 disp(Wrong Input! The input must be a square matrix!); return;endlen=r_size(1);rho=10;% 限制图尺寸的大小 r=2/1.05Alen; %点的半径 theta=0:(2*pi/len):2*pi*(1-1/len);pointx,pointy=pol2cart(theta,rho); theta=0:pi/36:2*pi;tempx,tempy=pol2cart(theta,r); point=pointx,pointy;hold onfor i=1:lentemp=tempx,tempy+p
