幂律形式来较好地描述。现实生活中的Internet、WWW、科研合作网络以及蛋白质交互网络等众多不同领域的网络都是是某种形式上的BA无标度网络。
BA无标度网络的工作于1999年10月发表在《Science》上[3]，由美国Notre Dame大学物理系的Barabasi教授及其博士生Albert合作完成。
BA无标度网络模型构造算法： （1）. 增长：从一个具有M个节点的连通网络开始，每次引入一个新的节点并且连接
到m个已经存在的节点上，这里m≤M。
（2）. 优先连接：一个新节点与一个已经存在的节点i连接的概率?i与节点i的度ki之间满足如下关系
?ki??i。
jkjBA算法的Matlab实现代码： %function b = ba(M,m,N)
%此函数生成一个具有N个节点的BA无标度网络
%M为初始代连通网络的节点数、m为每次引入的新节点连接到已存在的节点的个数 %其中m≤M
%返回结果b为所求BA无标度网络对应的邻接矩阵
function b = ba(M,m,N) b = zeros(N);
if M==1 M=2; end
for i = 1:M-1 %这里为简便起见，假使初始网络为完全连通网络 for j = (i+1):M b(i,j) = 1; b(j,i) = 1; end end
d = zeros(N,1); %建立一个存储每个节点度值的矩阵 for i = 1:M
d(i,1) = M-1; end
for i = M+1:N
mm = 0; %mm为当前步已经和新节点连接的旧节点个数 dd = d(1:i-1,1); Y为d的副本 while mm 6 dn = 0; %dn为节点度之和 for j = 1:i-1 dn = dn+dd(j,1); end p = zeros(i-1,1); %p为节点累积度值占总度值百分比的矩阵 p(1,1) = dd(1,1)/dn; for j = 2:i-1 p(j,1) = p(j-1,1)+dd(j,1)/dn; end r = rand; for j = 1:i-1 %进行m次轮盘赌方法选择与新节点相连的节点 if r d(i,1)=d(i,1)+1; d(j,1)=d(j,1)+1; dd(j,1) = 0; break; end end end end 示例：图-4即为M?3,m?2,N?20时的BA无标度网络的节点图 图- 4：BA无标度网络 7 2. 理论分析 从以上四种网络的构造算法出发，很容易得出其边数、度分布、平均路径长度、聚类系数的理论值，如下表： 表- 1 边数 度分布 平均度 NCN最近邻耦合网络 ER随机网络 ?M??pN(N?1)/2 WS小世界网络 BA无标度网络 (N?M)m?M(M?1)/2 NK/2 NK/2 介于规则网络与随机网络之间，近似泊松分布 Nf(NKp);K ln(NKp),NKp??1K2p?1,k?K ??0,k?KK 二项分布（N很大p很小时近似泊松分布）kkN?1?k CN?1p(1?p)幂律分布：2mk 2?3?k??p(N?1) 1N/2?[2m/K]平均(N?2)m?1路径N?长度 2K 23?CK/22CKLER?DER~InN/In?k? LlnN lnlnN聚类系数 3(K?2)?4(K?1) ?k?C?p? N?1 3(K?2)(1?p)3?O(1/N)4(K?1)C(lnN)2 N比较通过拓扑性质的表达式得出有意义的结论。例如：小世界网络的平均路径长度（记和分为L）绝不会小于同等规模的随机网络的L；无标度网络的L比同等规模的随机网析 络的L小得多。 8 3. 仿真分析 运用以上四个算法的Matlab代码生成规模为1000的4种网络模型，再用NodeXL分析其拓扑性质，通过比较得出结论。 表- 2 NCN（1000,6） ER（1000，0.006） WS（1000,6,0.5） BA(3,3,1000) 图像 边数 度分布 平均度 平均路径长度 聚类系数 3000 3015 2992 2994 6 6.030 5.984 5.998 83.667 4.029739 4.280806 3.451422 0.6 0.006 0.089 0.04 比较和分析 (1)、在同等网络规模下，小世界网络的平均路径长度介于规则网络与随机网络之间，这也是小世界网络所以为“小世界”最为显著的特征； (2)、由表中度分布图可以看出：规则网络有规则的度分布、无标度网络明显倾向于幂律分布，即网络中绝大多数节点的度集中于某一值，但始终有少数节点的度在较远的其他值，这有点类似于现实生活中的“二八法则”、而随机网络和小世界网络的度分布都倾向于二项分布、正态分布或者泊松分布； (3)、从四个网络的聚类系数可以看出，规则网络、小世界网络和无标度具有相对较大的聚类系数。从我们的直观经验出发，现实生活中的网络往往都具有较大的聚类系数，这说明规则网络、小世界网络和无标度网络更接近于我们的现实生活。而随机网络聚类系数相对较小，可以猜想其具有较强的鲁棒性。 9 现在我们再看看改变网络规模N和参数m对BA无标度网络度分布的影响。 表- 3 N M=m 1 1000 1500 2000 3 5 7 结论见后。 4. 结论 本文所列举的四种基本网络模型，各有其特点和研究价值。通过以上网络模型的构造算法、Matlab实现、理论分析和仿真分析，可以得出以下基本结论： （1）. 最近邻耦合网络具有规则的结构，是最容易被分析和理解的网络模型。它的许 多性质易于用纯数学上的解析方法来研究。现实网络的许多性质，都是介于完全规则网络与完全随机网络之间的，因此最近邻耦合网络看似简单，实则蕴含着无穷的奥妙。 （2）. ER随机网络是典型的完全随机网络。当网络规模一定时，它的各种拓扑性质 就完全由随机连边概率p决定了。当网络规模足够大时，即使p非常小（如表-2 中的ER随机图模型，p?0.002），整个网络却表现出较短的平均路径长度（4.03），即“小世界”特性；整个网络的度分布也倾向于二项分布。这些都说明随机中往往蕴含着规律性的东西，自然（或曰科学）给人的惊喜（惊奇）是无穷的。 （3）. WS小世界网络是由规则的最近邻耦合网络引入随机性得来的，所以它的许多 10 性质都介于完全规则网络与完全随机网络之间。然而它最为突出的“小世界”特性，最贴近于我们的现实生活，对它在各种形式下的拓扑性质的研究，具有极大的实用价值。 （4）. BA无标度网络引入了WS小世界网络所忽略的实际网络的另外两个重要特性， 即增长（Growth）特性和优先连接（Preferential attachment）特性。这使得BA无标度网络表现出幂律性的度分布，且该幂律性与网络规模N和参数m均无关的更为复杂的拓扑性质。对这些特性的研究，有利于人们理解并控制实际网络的演变与发展。受BA无标度网络的鲁棒性与脆弱性的启发，直接改善了人们对传染病的预防与控制机制。 5. 参考文献 [1] BOLLOBáS B. Random Graphs [M]. New York: Academic Press, 2nd ed.,2001. [2] WATTS D J,STROGATZ S H. Collective dynamics of ‘small-world’ networks [J]. Nature, 1998,393(6684):440-442. [3] BARABáSI A-L,ALBERT R. Emergence of scaling in random networks [J]. Science, 1999,286(5439):509-512. 11