论文部分内容阅读
摘要：复杂网络属于大型网络系统，拥有相对复杂的拓扑结构，由诸多节点通过相互连接构成，其动力行为具备动态性和多样性，比如神经网络、食物链接网络、社会网络等自然形成的复杂网络；与此同时，人类还不断地建造了互联网、电力网、万维网、交通网络等复杂网络。该文论述复杂网络基本概念与复杂网络模型，同时对复杂网络模型进行比较。
关键词：复杂网络；网络模型；网络特性
中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2017）03-0023-02
1 基本概念
所谓“网络”（networks），实际上就是节点（node）和连边（edge）的集合。若节点相对（i，j）和（j，i）的边是相同的，则它就是无向网络；如果不是相同的边，那么就是有向型的。当将权值赋给各边时，就得到了加权网络，若不赋值，就是无权型的，具体如下图：
如果根据特定规律将各节点连边到一起，那么就能获得图2所示规则网络。若根据任意形式将节点各边连到一起，那么就能获得随机网络。
通常可以用介数、度分布、平均路径长度等参数来阐述复杂网络的各种特性，下文将描述各参数。
1）平均路径长度（Average path length）
将网络内的任意两节点[i]与[j]的间距[lij]定義为假定两节点分别为起点与终点，中间过程最小的连边量。将网络直径定义成网络内部任何两节点之间的最大值。则：
[D=maxi，jlij] （1-1）
平均路径长度定义[L]为网络中所有节点对之间距离的平均值，用公式表示为：
2）簇系数（Clustering efficient）
网络中存在一节点[i]，它和另外的节点通过[ki]条边连到一起，这i[ki]个节点称为节点[i]的邻居节点，最多会有[KiKi-12]条边。[i]的簇系数用[ki]个邻居节点中含有的边数[2Ni]比上最大边数[KiKi-12]的数值来计算，用[Ci]来表示。公式为：
[Ci=2NiKiKi-1i] （1-3）
3）度分布（Degree distribution）
若将节点[i]的度[ki]定义成和它连接的另外节点的个数，就可用[i]的邻居数来称呼它。一般每个节点会有单独的度，网络平均度就是全部节点度的均值，用[k]表示。公式为：
[K=1Ni=1NKi] （1-4）
通常可以用度分布函数[Pk]来显示节点的分布状态。[Pk]含义为选择任何的一个节点，它的度正好是[k]的概率。则：
[Pk=1Ni=1Nδk-ki] （1-5）
2复杂网络模型
1）规则网络（Regular network）
图3显示了普遍的网络模型，分别是全局耦合、最近邻耦合及星型模型。
上图（a）显示的全局模型中存在[N]个节点，边数为[NN-12]条边，它的[L=1]（最小），[C=1]（最大）。
2） ER随机网络（random network）
20世纪50年代匈牙利的两位科学家设计出了此模型，如图4所示：
（a）[p=0]时，存在10个孤立节点；（b）～（c）[p=0.1，0.15]时，得到的随机效果图
3）小世界网络（small-world network）
1998年美国的Watts等人提出了一个小世界模型，它的特点是聚类参数大、路径长度短，功能是使完全规则的网络向完全随机的形式转变，通常称作WS模型。如图5所示：
4） NW小世界模型
因为网络的连通性或许会被WS模型的随机重连过程损坏，所以想要防止孤立子网产生，在1999年美国的Newman等人设计了一个新的小世界模型，它将随机重连用随机加边代替，通常称作NW模型。如图6所示：
5）无标度网络（scale-free network）
1999年Albert等人设计了一种无标度模型，来解释此类网络的幂律特性，通常被称作BA模型，如图7所示。
3 网络模型比较
下面比较WS小世界网络模型、BA无标度网络模型与真实网络的主要性质的异同。根据表1.5所示，现实网络三大特性中的两点能被BA与WS模型捕捉到。研究人员为了使现实网络的全部特性都能被显示，又设计了很多模型，然而BA与WS模型的结构简单，规则明确，且对复杂网络的基本特性准确把握，所以现阶段应用频率最高的还是BA与WS模型。
[模型＼
关键词：复杂网络；网络模型；网络特性
中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2017）03-0023-02
1 基本概念
所谓“网络”（networks），实际上就是节点（node）和连边（edge）的集合。若节点相对（i，j）和（j，i）的边是相同的，则它就是无向网络；如果不是相同的边，那么就是有向型的。当将权值赋给各边时，就得到了加权网络，若不赋值，就是无权型的，具体如下图：
如果根据特定规律将各节点连边到一起，那么就能获得图2所示规则网络。若根据任意形式将节点各边连到一起，那么就能获得随机网络。
通常可以用介数、度分布、平均路径长度等参数来阐述复杂网络的各种特性，下文将描述各参数。
1）平均路径长度（Average path length）
将网络内的任意两节点[i]与[j]的间距[lij]定義为假定两节点分别为起点与终点，中间过程最小的连边量。将网络直径定义成网络内部任何两节点之间的最大值。则：
[D=maxi，jlij] （1-1）
平均路径长度定义[L]为网络中所有节点对之间距离的平均值，用公式表示为：
2）簇系数（Clustering efficient）
网络中存在一节点[i]，它和另外的节点通过[ki]条边连到一起，这i[ki]个节点称为节点[i]的邻居节点，最多会有[KiKi-12]条边。[i]的簇系数用[ki]个邻居节点中含有的边数[2Ni]比上最大边数[KiKi-12]的数值来计算，用[Ci]来表示。公式为：
[Ci=2NiKiKi-1i] （1-3）
3）度分布（Degree distribution）
若将节点[i]的度[ki]定义成和它连接的另外节点的个数，就可用[i]的邻居数来称呼它。一般每个节点会有单独的度，网络平均度就是全部节点度的均值，用[k]表示。公式为：
[K=1Ni=1NKi] （1-4）
通常可以用度分布函数[Pk]来显示节点的分布状态。[Pk]含义为选择任何的一个节点，它的度正好是[k]的概率。则：
[Pk=1Ni=1Nδk-ki] （1-5）
2复杂网络模型
1）规则网络（Regular network）
图3显示了普遍的网络模型，分别是全局耦合、最近邻耦合及星型模型。
上图（a）显示的全局模型中存在[N]个节点，边数为[NN-12]条边，它的[L=1]（最小），[C=1]（最大）。
2） ER随机网络（random network）
20世纪50年代匈牙利的两位科学家设计出了此模型，如图4所示：
（a）[p=0]时，存在10个孤立节点；（b）～（c）[p=0.1，0.15]时，得到的随机效果图
3）小世界网络（small-world network）
1998年美国的Watts等人提出了一个小世界模型，它的特点是聚类参数大、路径长度短，功能是使完全规则的网络向完全随机的形式转变，通常称作WS模型。如图5所示：
4） NW小世界模型
因为网络的连通性或许会被WS模型的随机重连过程损坏，所以想要防止孤立子网产生，在1999年美国的Newman等人设计了一个新的小世界模型，它将随机重连用随机加边代替，通常称作NW模型。如图6所示：
5）无标度网络（scale-free network）
1999年Albert等人设计了一种无标度模型，来解释此类网络的幂律特性，通常被称作BA模型，如图7所示。
3 网络模型比较
下面比较WS小世界网络模型、BA无标度网络模型与真实网络的主要性质的异同。根据表1.5所示，现实网络三大特性中的两点能被BA与WS模型捕捉到。研究人员为了使现实网络的全部特性都能被显示，又设计了很多模型，然而BA与WS模型的结构简单，规则明确，且对复杂网络的基本特性准确把握，所以现阶段应用频率最高的还是BA与WS模型。
[模型＼