matlab课程论文—无尺度网络的实现与可视化

1、课程论文：无尺度网络的实现与可视化摘要随着对复杂网络的深入研究，越来越多的系统，如神经网络和万维网，都被描述为有着复杂拓扑结构的网络。而很多的网络中节点的度分布都满足与图的大小无关的幂率分布，这被称为无尺度网络。幂率分布被发现是由增长和优先连接导致的。在这里我用matlab实现了网络动态生长的过程并把最终生成的无尺度网络进行了可视化。1引言1.1无尺度网络的提出在网络理论的研究中，复杂网络是由数量巨大的节点和节点之间错综复杂的关系共同构成的网络结构。用数学的语言来说，就是一个有着足够复杂的拓扑结构特征的图。复杂网络的研究是现今科学研究中的一个热点，与现实中各类高复杂性系统，如的互联网网络、神经

2、网络和社会网络的研究有密切关系。无论在社会科学、生命科学还是信息科学中，都存在着拥有十分复杂的拓扑结构特征的网络结构。这种网络结构的形式既不是完全规则，也不是完全随机的，例如在度分布中出现重尾现象。在一般的随机网络（如ER模型）中，大部分的节点的度都集中在某个特殊值（平均值）附近，成钟形的泊松分布规律。偏离这个特定值的概率呈指数性下降，远大于或远小于这个值的可能都是微乎其微的，就如一座城市中成年居民的身高大致的分布一样。然而现实世界的网络大部分都不是随机网络，少数的节点往往拥有大量的连接，而大部分节点却很少，一般而言他们符合二八定律，(也就是80/20 Pareto principle)。在1

3、998年，Barabasi、Albert等人合作进行一项描绘万维网的研究时，发现通过超链接与网页、文件所构成的万维网网络并不是如一般的随机网络一样，有着均匀的度分布4。他们发现，万维网是由少数高连接性的页面串联起来的。绝大多数（超过80%）的网页只有不超过4个超链接，但极少数页面（不到总页面数的万分之一）却拥有极多的链接，超过1000个，有一份文件甚至与超过200万个其他页面相连。与居民身高的例子作类比的话，就是说大多数的节点都是“矮个子”，而却又有极少数的身高百丈的“巨人”。Barabasi等人将其称为无尺度网络1。1.2无尺度网络的性质人们给具有这种性质的网络起了一个特别的名字无尺度网络。

4、这里的无标度是指网络缺乏一个特征度值（或平均度值），即节点度值的波动范围相当大，典型的特性则是度分布的幂定律(Power law)递减。所谓一个网络的度分布，是指随机地从网络中挑出一个节点时，这个节点的度为d的概率。无尺度网络的度分布满足幂律分布，也就是说d=k的概率正比于k的某个次幂：Pd=kk-。幂律分布这一特性，正说明了无尺度网络的度分布与一般随机网络的不同。随机网络的度分布属于正态分布，因此有一个特征度数，即大部分节点的度数都接近它。无尺度网络的度分布是呈集散分布：大部分的节点只有比较少的连接，而少数节点有大量的连接。由于不存在特征度数，因此得名“无尺度”。现实生活中，无尺度网络的例子

5、有很多。因特网、美国演员网络、细胞中蛋白质的交互网络都是无尺度网络。无尺度网络的特性是：当节点意外失效或改变时，对网络的影响一般很小，只有很小的概率会发生大的影响，但当有Hub节点受到影响时，网络受到的影响会比随机网络大得多。1.3无尺度网络的形成无尺度网络是怎么产生的呢？幂率分布又是如何形成的Barabasi在1999年的论文中提出了一个BA模型来解释复杂网络的无尺度特性2。这个模型基于两个假设：l 增长模式(Growth)：不少现实网络是不断扩大不断增长而来的，例如互联网中新网页的诞生，人际网络中新朋友的加入，新的论文的发表，航空网络中新机场的建造等等。l 优先连接模式(Preferent

6、ial attachment)：新的节点在加入时会倾向于与有更多连接的节点相连，例如新网页一般会有到知名的网络站点的连接，新加入社群的人会想与社群中的知名人士结识，新的论文倾向于引用已被广泛引用的著名文献，新机场会优先考虑建立与大机场之间的航线等等。在这种假设之下，BA模型的具体构造为：1. 增长：从一个较小的网络开始（这个网络是有m0个节点的完全图），逐步加入新的节点，每次加入一个新节点。新节点与m个(m小于等于m0)不同的已经存在于网络中的旧点相连产生m条新边。2. 优先连接：连接方式为优先考虑高度数的节点。对于某个原有节点i，将其在原网络中的度数记作di，那么新节点与之相连的概率为：Pi

7、=diidi论文中证明了这种方式产生的网络度分度为幂率分布，是无尺度网络。2无尺度网络的实现基于增长和优先选择机制，这里用matlab程序生成无尺度网络。定义函数scale_free，输入变量为网络中节点的个数，输出为网络对应图的邻接矩阵。Matlab代码如下：function matrix = scale_free(X) %初始化网络数据N = X; %网络结点个数m0 = 3; %初始结点个数m = 3; %后来每个新加每个节点发出的边的个数adjacent_matrix = zeros(N); % 初始化邻接矩?for i = 1: m0 for j = 1:m0 if (j = i)

8、%去除每个点自身形成的? adjacent_matrix(i,j) =1; %建立初始邻接矩阵，3个节点构成完全图 end endend node_degree = zeros(1,m0+1); %初始化点的度temp = sum(adjacent_matrix);node_degree(2: m0+1) = temp(1:m0); %求每个节点的度%node_degree(i+1)为第i个节点的度，方便后面总度数的计算 for iter= 4:N %循环加新节点 total_degree = 2*m*(iter - 4) + 6; %计算网络中此点的度之和 cum_degree = cums

9、um(node_degree); %求出网络中节点的度的累加和 choose = zeros(1,m); %初始化选择矩阵 %选出第一个和新点相连接的顶点 r1= rand(1)*total_degree; %算出与旧点相连的概率 for i= 1:iter-1 if ( (r1>=cum_degree(i)&&( r1<cum_degree(i+1) ) %优先选取度大的点 choose(1) = i; break end end %选出第二个和新点相连接的顶点 choose(2) = choose(1); while ( choose(2) = choose(1

10、) ) %第一个点和第二个点相同的话，重新选择 r2 = rand(1)*total_degree; for i = 1:iter-1 if (r2>=cum_degree(i)&&(r2<cum_degree(i+1) choose(2) = i; break end end end %选出第三个和新点相连接的顶? choose(3) = choose(1); while ( (choose(3)=choose(1)|(choose(3)=choose(2) ) r3 = rand(1)*total_degree; for i =1:iter-1 if (r3&g

11、t;=cum_degree(i)&&(r3<cum_degree(i+1) choose(3) = i; break end end end %新点加入网络后, 对邻接矩阵进行更新 for k = 1:m adjacent_matrix(iter,choose(k) = 1; adjacent_matrix(choose(k),iter) = 1; end %调整节点度的值 node_degree=zeros(1,iter+1); temp = sum(adjacent_matrix); node_degree(2:iter+1) = temp(1:iter);endma

12、trix = adjacent_matrix;输入scale_free(50)，可以得到一个50*50的临界矩阵，对应的网络就是随机生成的无尺度网络。但是这只是一个矩阵，用C语言，Java都可以生成。而且举着过于抽象，难以理解，无法把握住无尺度网络的特性，于是用matlab把这个网络可视化。3无尺度网络的可视化对于生成的无尺度网络，用matlab绘图工具可视化。定义函数graph_plot，输入变量为一个图的邻接矩阵，且为方针，否则会输出错误信息。输出为邻接矩阵对应的图。整体思路为首先绘制出每个节点，这里把节点放置在一个以原点为圆心的圆上，排列比较整齐。然后根据临界矩阵绘制出节点之间的边，用连

13、线代表。同时再在每个节点附近标注出节点的度，便于观察幂率分布。Matlab代码如下：function graph_plot(Adjacent)row,col = size(Adjacent);if(row=col) %不是方阵，报错 disp('Wrong Input! The input must be a square matrix!'); return;endN = row; %取得节点个数node_degree = sum(Adjacent); %计算每个节点的度angle=0:2*pi/N:2*pi*(1-1/N); %计算每个节点的偏角x=100*cos(angle

14、); %计算每个节点的坐标y=100*sin(angle);for i=1:N for j=i+1:N if Adjacent(i,j)=1 %绘制节点之间的连线 plot(x(i),x(j),y(i),y(j),'linewidth',1); hold on; end end %绘制节点的度 text(x(i)+3*cos(angle(i),y(i)+3*sin(angle(i),num2str(node_degree(i) );endhold offaxis off可以用graph_plot函数可视化scale_free函数生成的邻接矩阵。例如在matlab输入：graph

15、_plot(scale_free(50)，可以得到一个可视化的有50个节点的无尺度网络。这个图上从0°到360°按照逆时针排列着50个节点，每个节点上的数字代表着节点的度，这些连线代表着节点之间的边。从图上可以大致看出比较靠前的节点的度比较大，而后来新加入的节点度稍微小一些，而且图上大部分的节点度都比较小，而很少数的节点则拥有很大的度，复合二八定律。下面这张图是100个节点的无尺度网络可视化结果。由于节点比较多，看起来没有那么舒适，但是还是可以看到度分布的二八定律。4分析与思考无尺度网络还有一个特点就是“富者越富”，因为新节点发出的边的选择是优先选择度比较大的点。从可视化结

16、果就可看出，度比较大的点基本都分布在第一象限，也就是最初选定的初始节点和比较早加进去的点。这也是因为网络中最开始出现的节点在最初几步新加入节点时有较大的概率被新加的节点选中作为邻居。而由于比较早的节点有较大的几率在每一步被选中，因而他们的度相比于后加入的节点会比较大，在后续节点加入过程中更容易被选中。有如滚雪球般，最初的节点度比较大，容易被选中。容易被选中就导致度更大，最后导致了度分布为幂率分布。当然还有一些值得思考的问题，例如后加入的节点有没有可能因为某个关系而突然取得领先优势，在网络中成为度最大的节点？或者在最开始每个节点的度都一样的时候，度最大的节点时如何逐渐脱颖而出的？参考文献1 Al

17、bert, Réka, Hawoong Jeong, and Albert-László Barabási. "Internet: Diameter of the world-wide web." Nature 401.6749 (1999): 130-131.2 Barabási, Albert-László, and Réka Albert. "Emergence of scaling in random networks." science 286.5439 (1999): 509-512.5课程收获和建议这学期我选修了matlab课程，收获不小。不得不说matlab是一款功能很强大的软件，上至矩阵运算，下至方程组求解，样样精通。真是连比较难的二次三次多元方程组都可以给出带参数的精确解。这让我对matlab有些相见恨晚的感觉，甚至在想，当初学线性代数的时候怎么没有去学习matlab，不然矩阵的求逆，矩阵的特征多项式的求解会方便很多的。我是计算机专业的学生，在大四上的时候接触了matlab，那时候我在学习社交网络相关的知识，需要做蒙特卡洛模拟，也需要绘图。当时我是把matlab代码嵌入到