复杂网络知识点讲解以及代码实现_复杂网络分析代码

最全复杂网络知识点讲解以及代码实现

1. 引言

自从 1998 年 Watts 和 Strogatz 提出小世界网络模型以来，复杂网络的研究在过去几年得到了迅速发展。原因有以下几个方面：
（1）计算机技术的迅猛发展使我们有可能获得各种大规模网络的统计性质。
（2）实证分析表明，从万维网到新陈代谢网，许多领域的各种复杂网络展现了某些共同的统计性质，如幂律度分布，表明其中可能存在一些普适性的概念和规律。
（3）理论研究也有了突破。Watts 和 Strogatz 给出了小世界网络的构造方式，Barabási和 Albert 则指出，增长和偏好连接是形成无标度网络的根本原因，统计物理学的研究方法在复杂网络研究中得到广泛应用。理论研究和实证分析的相互促进在复杂网络的研究中得到了充分体现。

目前，复杂网络的研究工作集中在以下几个方面：
（1）复杂网络拓扑结构的静态统计分析，包括更广泛的实证研究和更深入的理论刻画，如给定度分布基础之上的匹配模式、各种相关关系、加权网络的统计性质和描述方式以及网络的聚类等。
（2）复杂网络的演化和机制模型，实证上可以研究实际网络演化的统计规律，检验 BA模型的偏好连接假设，理论上则可以发展更完善的具有形成特定几何性质的网络机制模型。
（3）复杂网络上的动力学研究，包括网络容错性和攻击鲁棒性，以及网络上的传播、同步与共振等各种动力学过程。
总的来说，网络的结构与功能及其相互关系是网络研究的主要内容，结构与功能的相互作用特别是其对网络演化的影响是复杂网络研究需要解决的重要问题。

复杂网络是对复杂系统非常一般的抽象和描述方式，它突出强调了系统结构的拓扑特征。原则上说，任何包含大量组成单元（或子系统）的复杂系统，当我们把构成单元抽象成节点，单元之间的相互作用抽象为边时，都可以当作复杂网络来研究。复杂网络可以用来描述物种之间的捕食关系、人与人之间的社会关系、词与词之间的语义联系、计算机之间的网络链接、神经元之间的通讯反馈作用、蛋白质之间的相互关系等等。复杂网络为研究复杂系统提供了一种新的描述方式，可以加深我们对系统结构的深入了解，反过来，复杂网络的研究成果对探索复杂性又具有一定的启发和借鉴意义。

2 复杂网络的结构

2.1 复杂网络的拓扑性质

网络是由一个点集$V$和边集$E$组成的一个图$G=(V,E)$ 。$E$中的每条边$e$有$V$中的一对点$(u,v)$与之对应。复杂网络是指具有一些特殊性质的网络。
复杂网络的拓扑性质主要有度与度分布，平均路径长度，聚类系数，度相关性，介数和核数等。下面以社会关系网中的朋友网为例，对相关概念作一简略说明。
在朋友关系网中，每一个人都是一个顶点，两个人若是朋友则它们之间就连一条边。一个顶点的度是指与此顶点连接的边数，也就是一个人的朋友数。顶点聚类系数用来描述网络局部集团化的程度，对于每一个人（顶点$v$ ),考察他的所有朋友，这些朋友相互之间还是不是朋友的情况由聚类系数来度量。若这些朋友互相之间都不再熟识，则顶点$v$的聚类系数为0；反之，若这些朋友互相之间都有边相连，即它们互相之间都有朋友关系，则顶点$v$的聚类系数为1。所有顶点的聚类系数的平均值称为平均聚类系数。

2.1.1 平均路径长度

网络中两个节点$v_i$和$v_j$,之间的距离$d_{ij}$,定义为连接这两个节点的最短路径上的边数。网络中任意两个节点之间的距离的最大值称为网络的直径，记为$D$，即
$D={\max }_{i,j}{d}_{ij}$
网络的平均路径长度L(网络的特征路径长度)则定义为任意两个节点之间的距离的平均值.即
$L=\frac{1}{C_N^2}{\sum }_{1\le i<j\le N}{d}_{ij}$
其中，$N$ 为网络节点数。一个含有 $V$ 个节点和$M$ 条边的网络的平均路径长度可以用时间量级 O(MN) 的广度优先搜索算法来确定。

例1 对于图1所示的一个包含 5 个节点和5条边的网络,求网络直径D和平均路径长度L。
解:首先构造图 1对应的图 $G=(V,E)$的邻接矩阵.

W = [ 0 1 1 0 1 1 0 1 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 ] , W=

$$\begin{bmatrix}0&1&1&0&1\\1&0&1&1&0\\1&1&0&0&0\\0&1&0&0&0\\1&0&0&0&0\end{bmatrix}$$ , W= ​01101​10110​11000​01000​10000​ ​,
然后应用 Floyd 算法求出任意节点之间的最短距离，其中最大的为网络直径，网络直径$D=d_{4,5}$=3，把所有节点对之间的距离求和，除以对应完全图的边数 ${C_5}^2$，求得网络的平均路径长度工=1.6。

计算的 Matlab 程序如下 
clc, clear 
a=zeros(5); %邻接矩阵初始化 
a(1,2)=1; a(1,3)=1; a(1,5)=1; 
a(2,3)=1; a(2,4)=1;  
a=a';  %输入邻接矩阵的下三角部分 
a=sparse(a) %转换成稀疏矩阵,Matlab 工具箱的要求 
dist=graphallshortestpaths(a,'directed',false) 
D=max(max(dist))  %计算网络直径 
Ldist=tril(dist)  %提取最短距离矩阵的下三角部分 
he=sum(nonzeros(Ldist));  %求所有节点对之间最短距离的和 
n=length(a);  %求节点个数 
L=he/nchoosek(n,2)  %求平均路径长度，这里使用 Matlab 求组合数的命令 hchoosek 
1
2
3
4
5
6
7
8
9
10
11
12
13

为了便于以后求网络的直径和平均路径长度,我们编写的计算网络的最大直径及平均路径长度的 Matlab 函数如下

function [D,L]=myAPL(a);  
%计算网络直径 D，和平均路径长度 L，输入参数 a 为网络的邻接矩阵 
a=tril(a);  %截取邻接矩阵的下三角部分，满足 Matlab 工具箱的要求 
a=sparse(a); %转换成稀疏矩阵,Matlab 工具箱的要求 
dist=graphallshortestpaths(a,'directed',false); 
D=max(max(dist));  %计算网络直径 
Ldist=tril(dist);  %提取最短距离矩阵的下三角部分 
he=sum(nonzeros(Ldist));  %求所有边的和 
n=length(a);  %求节点个数 
L=he/nchoosek(n,2);  %求平均路径长度，这里使用 Matlab 求组合数的命令 hchoosek 
1
2
3
4
5
6
7
8
9
10

在朋友关系网络中，L是连接网络内两个人之间最短关系链中的朋友的平均个数。近期的研究发现，尽管许多实际的复杂网络的节点数巨大，网络的平均路径长度却惊人的小。具体地说，对于一个网络而言，如果对于固定的网络节点平均度，平均路径长度L的增加速度至多与网络规模N的对数成正比，则称此网络是具有小世界效应的。

2.1.2 聚类系数

在你的朋友关系网络中，你的两个朋友很可能彼此也是朋友，这种属性在复杂网络理论里称为网络的聚类特性。一般地，假设网络中的一个节点$v_i$有$k_i$,条边将它和其他节点相连,这$k_i$个节点就称为节点$v_i$的邻居。显然，在这$k_i$个节点之间最多可能有 $C_{k_i}^2$条边。而这$k_i$个节点之间实际存在的边数$E_i$和总的可能的边数 $C_{k_i}^2$之比就定义为节点$v_i$的聚类系数 $C_i$，即
$C_i=\frac{E_i}{C_{k_i}^2}.$
规定: 如果一个节点只有一个邻居节点，那么该节点聚类系数定义为 1
整个网络的聚类系数C就是所有节点$v_i$ 的聚类系数 $C_i$的平均值。显然，0≤ C≤1。当且仅当所有的节点均为孤立节点，即没有任何连接边时，C=0; C=1当且仅当网络是全局耦合的，即网络中任意两个节点都直接相连时，C =1。
对于一个含有N 个节点的完全随机的网络，当V很大时，$C=O(N^{-1})$。而许多大规模的实际网络都具有明显的聚类效应，它们的聚类系数尽管远小于 1 但却比 $O(N^{-1})$大得多。事实上，在很多类型的网络中，随着网络规模的增加，聚类系数趋向于某个非零常数,即当$N->+inf$时，$C=O(1)$。这意味着这些实际的复杂网络并不是完全随机的，而是在某种程度上具有类似于社会关系网络中“物以类聚，人以群分”的特性。
例 2 计算例 1 简单网络的聚类系数。
解 依次求得节点v，(i=l,.··,5) 的聚类系数分别为 13,13,1,1,1; 整个网络的聚类系数为 11/15。

计算的 Matlab 程序如下 
clc, clear 
format  rat  %有理分数的数据格式 a=zeros(5); %邻接矩阵初始化 
a(1,2)=1; a(1,3)=1; a(1,5)=1; 
a(2,3)=1; a(2,4)=1;  
a=a+a';  %输入邻接矩阵的全部元素 
[TC,c]=mycluster(a)  %TC 是整个网络的聚类系数，c 为各个节点的聚类系数 
1
2
3
4
5
6
7

function [TC,c]=mycluster(a); 
%输出参数 TC 是整个网络的聚类系数，c 为各个节点的聚类系数，输入参数是邻接矩阵 
n=length(a); 
for i=1:n 
    m=find(a(i,:));  %找第 i 行非零元的地址 
    ta=a(m,m); %提取节点 vi 的所有邻居节点所构成的邻接矩阵     
    Lta=tril(ta); %提取邻居节点所构成邻接矩阵的下三角元素     
   if  length(m)==0 
   c(i)=0;  %孤立节点的聚类系数定义为 0 
   elseif  length(m)==1 
      c(i)=1;  %只有 1 个邻居节点的聚类系数定义为 1 
   else 
      c(i)=sum(sum(Lta))/nchoosek(length(m),2);  %求节点 vi 的聚类系数 
   end 
end 
TC=sum(c)/n;  %求整个网络的聚类系数 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

不认识的两个人可以通过依次的朋友关系连接起来。复杂网络两点间的最短路径定义为所有连通的通路中，所经过的其它顶点最少的一条或几条路径。最短路径长度的平均值称为平均最短路径。在社会学的研究中，有一个有趣的结论叫做“六度分离”,通过一些通信试验人们发现，平均来说，世界上任何两个人之间可以仅仅通过6对朋友关系连接起来，这就是我们俗称的“小世界”。

2.2 网络结构

2.2.1 随机网络

随机网络就具有上面提到的“小世界”特点，即顶点之间的平均最短路径比较短。经典的随机网络是这样构造的：给定 个顶点，任意两点之间都尝试以某个概率 连接，所构成的网络就叫随机网络。数学家在上个世纪50年代对随机网络进行了深入细致的研究，得到了网络性质突现的临界连接概率等一系列结果，发现对于同样规模的网络，随机网络具有短的平均最短路径，这一点和许多实证研究结果相符。但另一方面，许多实际网络都具有很高的平均聚类系数，而随机网络却是一个局部集团化很差的网络，平均聚类系数很低。所以，随机网络不是实际网络的一个很好的刻画。
和随机网络相对应的是完全规则网络，规则网络的性质恰与随机网络相反，一般情况下具有大的聚类系数和长的平均最短路径。所以，无论是规则网络还是随机网络都无法作为描述真实网络的合适的研究基础。或者说，把规则网络和随机网络作为复杂系统的抽象都过于简单化了，离真实的复杂性太远。
代码

function [a1,N]=initial_ER()

N=500;  
p=4/499;
a1=zeros(N);

for i=1:N 
    for j=i+1:N 
        p1=rand(1,1); 
        if p>p1 
            a1(i,j)=1;a1(j,i)=1;   
        end 
    end 
     
end 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.2.2小世界网络

Watts 和 Strogatz 结合规则网络和随机网络的特点，给出了小世界网络的生成机制模型。 WS 小世界网络是在规则网络的基础上加入随机性产生的，即对规则网络的每一个顶点的所有边，以概率$p$断开一个端点，并重新连接，连接的新端点从网络中的其它顶点里随机选择。WS 小世界模型的构造算法如下
(1) 从规则图开始:考虑个含有$N$个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各$K/2$ 节点相连，$K$是偶数。
(2) 随机化重连：将上面规则图中的每条边以概率$P$随机地重新连接，即将边的一个端点保持不变，而另一个端点以概率$P$变为网络中其余 $N-K-1$个节点中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，即若重连的两个节点之间有边，则该边就不进行重连。
代码：

function [a1,N]=initial_WS()
N=500;
K=4;
p=0.1;
a1=zeros(N); 
for i=1:N 
for j=i+1:i+K/2 
jj=j; 
if j>N 
jj=mod(j,N); 
end 
a1(i,jj)=1; 
a1(jj,i)=1; 
end 
end 
for i=1:N 
    for j=i+1:i+K/2 
        jj=j; 
        if j>N 
            jj=mod(j,N); 
        end 
        p1=rand(1,1); 
        if p1<p 
            a1(i,jj)=0;a1(jj,i)=0;a1(i,i)=inf;a=find(a1(i,:)==0); 
            rand_data=randi([1,length(a)],1,1); 
            jjj=a(rand_data);a1(i,jjj)=1;a1(jjj,i)=1;a1(i,i)=0; 
        end 
    end 
end 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

在上述模型中，$P=0$对应于完全规则网络，$p=1$则对应于完全随机网络,通过调节$P$的值就可以控制从完全规则网络到完全随机网络的过渡。p 值存在一个很大的区域，网络同时拥有大聚类系数和小最短路径，在复杂网络研究中，网络同时具备这两个性质时我们就称其具有小世界特性。
WS 小世界模型构造算法中的随机化过程有可能破坏网络的连通性。另一个研究较多的小世界模型是由 Newman 和 Watts 稍后提出的，称为 NW 小世界模型。该模型是通过用“随机化加边”取代 WS 小世界模型构造中的“随机化重连”而得到的。
NW 小世界模型构造算法如下:
(1) 从规则图开始:考虑一个含有$N$个点的最近邻耦合网络，它们围成一个环，其中
每个节点都与它左右相邻的$K/2$节点相连，$k$ 是偶数。
(2)随机化加边:以概率$P$在随机选取的一对节点之间加上一条边。其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。
在 NW 小世界模型中，p=0对应于原来的最近邻耦合网络，p=1则对应于全局耦合网络。在理论分析上，NW 小世界模型要比 WS 小世界模型简单一些。当$p $足够小和$N$足够大时，NW 小世界模型本质上等同于 WS 小世界模型。
代码：

N=input('请输入最近邻耦合网络中节点的总数N:');

K=input('请输入最近邻耦合网络中每个节点的邻居数K:');

if K>floor(N-1)|mod(K,2)~=0;
disp('参数输入错误：K值必须是小于网络节点总数且为偶数的整数');
return ;
end

angle=0:2*pi./N:2*pi-2*pi/N;
angle=0:2*pi/N:2*pi-2*pi/N;
x=100*sin(angle);
y=100*cos(angle);
plot(x,y,'ro','MarkerEdgeColor','g','MarkerFaceColor','r','MarkerSize',8);      % MarkerEdgeColor 标记轮廓颜色        MarkerFaceColor 标记填充颜色  MarkerSize  标记大小    

hold on;
A=zeros(N);  %想做初始化的邻接矩阵
for i=1:N
for j=i+1:i+K/2
jj=j;
if j>N
jj=mod(j,N);
end
A(i,jj)=1;
A(jj,i)=1;
end
end

%NW小世界网络的代码
p=input('请输入随机化重连的概率p:');
[m,n]=find(A==0);
for i=1:length(m)
    if m(i)~=n(i)
        p1=rand(1,1);
        if p>p1
            A(m(i),n(i))=1;A(n(i),m(i))=1;
        end
    end
end

for i=1:N
for j=i+1:N
if A(i,j)~=0
plot([x(i),x(j)],[y(i),y(j)],'linewidth',1.2);
hold on;
end
end
end
axis equal;
hold off


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

2.2.3无标度网络

大量实际网络还存在着另一个突出的结构特征—幂律度分布，我们称其为无标度网络。网络中的大部分节点度值都很低，但存在着度数非常高的中枢节点。幂律度分布使网络在小世界特征的基础上又具有了许多新的性质。如不存在传染病传播的临界阈值等。对网络攻击的研究结果表明，随机攻击基本上不会破坏无标度网络的连通性，但在有目的的最大度攻击下，很小比例的顶点移除就会对网络的连通性造成根本性的破坏。鲁棒性和脆弱性奇妙地结合在了一起，人们戏称其为“阿基利斯的足踝”。这与现实世界中许多复杂系统的表现完全类似。
为了解释幂率分布的产生机理，Barabási 和 Albert 提出了一个无标度网络模型，现被称
为 BA 模型。他们认为以前的许多网络模型都没有考虑到实际网络的如下两个重要特性：
（1）增长(growth)特性：即网络的规模是不断扩大的。例如每个月都会有大量的新的科研文章发表，而 WWW 上则每天都有大量新的网页产生。
（2）优先连接(preferential attachment)特性：即新的节点更倾向于那些具有较高连接度的“大”节点相连接。这种现象也称为“富者更富(rich get richer)”或“马太效应(Matthew effect)”。例如，新发表的文章更倾向于引用一些已被广泛应用的重要文献。

代码

function [a1,N]=initial_BA()
% K为相依冗余度
% 从已有的m0个节点的网络开始，采用增长机制与优先连接的机制生成BA无标度网络 
% a1,a2,a3,a4——————返回生成网络的邻接矩阵 
m0 = 3;                     %未增长前的网络节点个数m0; 
m = 3;                      %每次引入的新节点时新生成的边数m; 
N = 500;                   %增长后的网络规模N 
a1=zeros(N,N);
pp = 3;                       %input('初始网络情况1，2或3： '); 

% 安全检查，要求m<=m0  
if m>m0 
    disp('输入参数m不合法'); 
    return; 
end 

switch  pp
    case 1
        a1=zeros(m0);
%         a2=zeros(m0);
    case 2
        a1=ones(m0);
%         a2=ones(m0);
        for i=1:m0
            a1(i,i)=0;%对角线元素置0
%             a2(i,i)=0;%对角线元素置0
        end
    case 3
        for i=1:m0
            for j=i+1:m0
                p1=rand(1,1);
                if p1>0.5
                    a1(i,j)=1;a1(j,i)=1;
%                     a2(i,j)=1;a2(j,i)=1;
                end
            end
        end
    otherwise
        disp('输入参数pp不合法');
        return;          
end 
%% 基于网络增长和优先连接特性的BA网络模型
for k=m0+1:N
    m1=size(a1,1);p1=zeros(1,m1);
    if isempty(find(a1==1,1))%判断网络a1的邻接矩阵A是否是零矩阵
        p1(:)=1/m1; %初始网络a1是孤立，则连接概率相等
    else
        for i=1:m1
            p1(i)=length(find(a1(i,:)==1))/length(find(a1==1));%计算网络a1所有节点的连接概率
        end
    end

    pp1=cumsum(p1);   %求网络a1累计概率分布

    for i=1:m %利用赌轮法从已有的节点中随机选择m个节点与新加入的节点相连
        random_data1=rand(1,1);

        aa1=find(pp1>=random_data1);jj1=aa1(1); % 节点jj即为用赌轮法选择的节点

        a1(k,jj1)=1; % 网络a1邻接矩阵的节点间的连接边
        a1(jj1,k)=1;
    end
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

3.复杂网络的可视化

复杂网络中的顶点数和边数一般较多，使用通常的画图软件如 Matlab 软件等，很难看清网络之间的拓扑结构。需要一些专用的可视化软件来画复杂网络。
Pajek软件是网络分析软件工具的一种，它有出色的大型网络处理能力和强大的可视化功能。Pajek可以处理拥有多达几百万节点的大型网络，突破了很多网络分析软件只能处理较小规模数据的瓶颈。它可以从大规模网络中提取出若干小网络，以便于使用经典算法实现更加细致的研究，并通过强大的可视化功能将网络及分析结果展示出来。
Pajek的输入方式比较灵活，可以直接定义一个小网络，也可以从外面导入数据生成网络，除了本身的数据格式之外，它还支持很多其他软件数据格式的导入。软件的结构是建立在网络、分类、向量、排序、群和层级6种数据结构之上的。
用 Pajek 软件画网络图，必须先构造适合 Pajek 的数据，构造 Pajek 数据的 Matlab 函数如下
代码：

function Matlab_to_Pajek(A,k)   
%Matlab 邻接矩阵 A 转换成 Pajek 数据的函数 
%k 是第 k 次转换，生成的文件命名成 Pajek_datak.net, %如果不输入第 2 个参数 k,默认文件名为 Pajek_data1.net 
if nargin==1 
    str='Pajek_data1.net'; 
    else 
    str=['Pajek_data',int2str(k),'.net']; 
end 
n=length(A); v=1:n; 
fid=fopen(str,'w');  %创建纯文本文件 Pajek_data.net 
fprintf(fid,'%s%d\n','*Vertices  ',n); %写入字符串并换行 
for i=1:n 
   fprintf(fid,' %d  ',v(i));   %写入节点编号 
   fprintf(fid,'"%d"\n',v(i));  %写入双引号节点字符串并换行 
end 
fprintf(fid,'%s\n%s\n','*Arcs','*Edges'); %写入两个字符串并各自换行 A=tril(A);  %截取邻接矩阵的下三角元素
[u,v]=find(A); n=length(u); %找非零元素，并计算个数 
for i=1:n 
    fprintf(fid,'  %d  %d  1\n',u(i),v(i));  %逐条边写入信息并换行 
end
fclose(fid)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

使用 Pajek 软件，调入上述函数生成的数据文件 Pajek_datak.net，就可以画出网络图。 注：必须使用较高版本的 Pajek 软件，否则的话，Matlab 构造的纯文本文件 Pajek 软件不识别。

按 NW 小世界模型的构造算法，得到原始的小世界网络见图 1（a），由于节点众多且节点间距离太短，不便于认识网络中各节点的联系，采用 Pajek 软件提供的 Kamada-Kawai算法，对网络空间进行重新布局，得到图 1（b）。对网络重新布局的操作步骤为，在 Pajek图形窗口，依次选择 Layout 菜单中的 Energy→Kamada-Kawai→Separate Components。

4.各种类型复杂网络的构造算法

4.1 Waxman模型及仿真

20 世纪 80 年代 Internet 的网络规模比较小，处于发展的初级阶段。1988 年，Waxman提出了随机图产生器，它较好地再现了 ARPANET 网络。其建模步骤如下[5]

由于节点众多且节点间距离太短，使用 Matlab 软件画图不便于认识网络中各节点的联系，我们使用 Pajek 软件对上述 Waxman 模型构造的网络进行可视化，并采用 Pajek 软件提供的 Kamada-Kawai 算法，对网络空间进行重新布局，得到图 4。从图 4 可以看出网络中存在一些孤立点。

代码：

Waxman 随机图仿真的 Matlab 程序如下 
clc, clear 
alpha=0.15; beta=0.1; 
m=20; n=20; %水平方向和垂直方向的点数 
h=10; %水平方向和垂直方向的间隔步长 
u=h:h:m*h; v=h:h:n*h;  %水平方向 
[u,v]=meshgrid(u,v); %生成网格节点的横坐标和纵坐标 u=u(:); v=v(:);  %转换成列向量 
hold on, plot(u,v,'*')  %画 mn 个点 
uv=[u';v'];  %构造 mn 个点的坐标 
d=dist(uv);  %求 mn 个点之间的两两距离矩阵 
L=max(max(d)); %求最大距离 
gailv=alpha*exp(-d/(beta*L)); %计算概率矩阵 
gailv=tril(gailv);  %提取概率矩阵的下三角元素 
gailv(1:m*n+1:end)=0; %概率矩阵的对角线元素置 0 
randnum=rand(m*n); %生成服从[0,1]上均匀分布随机数的 mn×mn 矩阵 [i,j]=find((randnum<=gailv));  %节点 i 和 j 之间连边 
a=zeros(m*n); %邻接矩阵初始化 
for k=1:length(i) 
    a(i(k),j(k))=1; a(j(k),i(k))=1;  %构造邻接矩阵 
    plot([u(i(k)),u(j(k))],[v(i(k)),v(j(k))]); %节点 i 和 j 之间画线 
end 
deg=sum(a); %计算所有节点的度 
dminmax=minmax(deg)  %求度的最小值和最大值 
pinshu=hist(deg,[dminmax(1):dminmax(2)]); %计算度取值的频数 
hold off,figure,loglog([dminmax(1):dminmax(2)],pinshu,'-s') %对数坐标系画图 xlabel('the degree'), ylabel('the frequency of degree') 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5. 复杂网络的抗毁性

定义1 -割点
在一个无向连通图$G$中，当且仅当删去$G$中的节点$v$及所有依附于$v$的边后，可将图分割成两个以上的连通子图，则称$v$为图$G$的割点。
定义2 -割边
在一个无向连通图 中，当且仅当删除 中的边 后，可将图分割成两个连通子图，则称边$e$为图$G$的割边.
没有割点的连通图称为重连通图（Biconnected Graph）。一个通信网络图的连通度越
高，其系统越可靠，无论是哪一个站点单独出现或遭到外界破坏，都不影响系统的正常工作。
网络安全比较低级的要求就是重连通图。在重连通图上，任何一对节点之间至少存在两条路径，在删除某个节点及与该节点相关联的边时，也不破坏图的连通性。
连通图中割点的判别方法如下
（1）从图的某一个节点开始深度优先遍历图，得到深度优先生成树。 （2）用开始遍历的节点作为生成树的根，则
i）根节点是图的割点的充要条件是，根至少有两个相邻节点。
ii）其余节点u是图的割点的充要条件是，该节点 u至少有一个相邻节点w ，从该相邻节点w出发不可能通过它的子孙节点，以及一条回边所组成的路径到达u 的祖先
iii）特别的，叶子节点不是割点。