复杂网络模型比较研究

阿布力米提·艾西丁

摘要：复杂网络属于大型网络系统，拥有相对复杂的拓扑结构，由诸多节点通过相互连接构成，其动力行为具备动态性和多样性，比如神经网络、食物链接网络、社会网络等自然形成的复杂网络；与此同时，人类还不断地建造了互联网、电力网、万维网、交通网络等复杂网络。该文论述复杂网络基本概念与复杂网络模型，同时对复杂网络模型进行比较。

关键词：复杂网络；网络模型；网络特性

中图分类号：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模型。

[模型＼&节点度分布＼&平均路径长度＼&聚类系数＼&真实网络＼&幂率分布＼&小＼&大＼&小世界网络＼&泊松分布＼&小＼&大＼&无标度网络＼&幂率分布＼&小＼&大＼&]

4 结束语

复杂网络搜索过程的复杂性给搜索过程建模工作带来一定程度的难度，在了解基本概念与复杂网络结构的特性的基础上，主要目的就是为了更好地描述复杂网络动力学行为相关的问题（比如：网络搜索、渗流、传播、相变等）的在个体层和群体层之间的复杂性。本首先综述了复杂网络基本概念与复杂网络模型，同时对复杂网络模型进行比较。

参考文献：

[1] 汪小帆， 李翔， 陈关荣. 复杂网络理论及其应用[M]. 北京： 清华大学出版社， 2006.

[2] 刘兴堂， 刘力， 宋坤. 复杂系统建模与仿真的几点重要思考[J]. 系统仿真学报， 2007， 19（13）.