复杂网络基本概念

典型的网络是由节点与连接两节点的边组成，现实生活存在大量复杂系统可通过网络加以描述，比如社交网络、电力网络、交通网络等。

基本概念

【距离】网络两点间距离(Distance)定义为连接两点的最短路包含的边的数目

【直径】网络的直径(Diameter)定义为网络中所有节点对的距离的最大值

【平均路径长度】把所有节点对的距离求平均就是平均距离(Mean Distance)，即平均路径长度。平均距离表示两节点间最有可能的典型距离，决定网络的有效“尺寸”。研究表明现实生活中的网络的平均距离一般是相对较小的值，即使在边比同等节点数时完全连接网络的边数小很多的情况下。这种小的平均距离特性被称为“小世界效应”。

【聚类系数】节点A和B相连，B和C相连，A又和C相连，这是网络的聚集性。聚类系数(Clustering Coefficient)即簇系数是衡量节点集聚程度的参数。单个节点的簇系数是它所有相邻节点之间连边的数目占可能的最大连边数目的比例。网络的簇系数C是所有节点簇系数的平均值，显然C<=1，C=1当且仅当网络为完全连接的规则网络（任一节点都连接到其他全部节点）。在随机网络中C～1/N，比真实网络的簇系数小很多。

【度分布】节点的度(Degree)k_i是第i个节点拥有相邻节点的数目，是节点最简单但最重要的特性。度越大则某种程度上说明该节点越重要。平均度是所有节点的度的平均值。度分布表示有某个特定度的节点数目与该特定度之间的关系可用分布函数P(k)近似表示，P(k)表示网络中度为k的节点占总节点的比例。规则网络，每个节点的度相同，则分布函数为一尖峰，即冲击函数。随机网络的度分布函数为泊松分布(Poisson Dostribution)，泊松分布的波形在离开峰值<k>两侧以指数形式下降。现实生活的复杂网络一般服从幂律分布(Power-law Distribution)，幂律分布衰减慢很多，所以会有部分节点有较大的度。因为幂律分布与特定的标度无关，所以这样的网络也称之为无标度网络。

网络类型

【规则网络Regular Coupled Networks】规则网络有大的簇系数和平均距离。完全连接网络、邻接网络、星型互连网络都是规则网络。全连接网络有最小的平均距离和最大簇系数（前述三种网络中相比），有小世界特性，边数目与N^2同阶。邻接网络是被广泛研究的稀疏规则网络模型，每个节点只与其少数邻接节点相连，在节点数较大时，其簇系数C~=3/4。但邻接网络不是小世界网络，因为节点趋于无穷大时，平均距离也趋于无穷大，此时网路要达到某种同步是几乎不可能的。星型互连网络是具有高聚集性和小的平均距离的规则网络，中心节点与其他节点相连而其他节点间没有连接，节点N趋于无穷大时，簇系数趋于1，平均距离趋于2。

【随机网络 Random Graphs】20世纪中叶，Erdos和Renyi建立随机网络的基本模型—ER随机图。随机网络具有小的簇系数和小的平均距离。在ER随机图中，N节点中任意亮点间以概率p连接，则在整个网络中共有pN(N-1)/2条边。若概率p大于一定的门限概率，则网络中没有孤立的节点或子网。随意图的平均度为p(N-1)~=pN，簇系数C=p<<1。对于N比较大的随机网络，ER随机图的度分布函数近似服从泊松分布。

【小世界网络Small-World Models】小世界效应指的是大的簇系数和小的平均距离两个统计特征，具有这种效应的网络就是小世界网络。小世界网络的鲁棒性、传播动力学特性、同步性等都是复杂网络的研究热点。此外，大量真实网络的节点服从幂律分布，幂函数是下降相对缓慢的曲线，使得度很大的节点在真实网络中存在。幂函数有标度不变性，因为节点服从幂律分布的网络叫无标度网路(BA模型)。

-【WS模型】一种小世界网络模型，调整参数从规则网络向随机网络过渡。构造算法：环状的规则网络，有N节点，每个点向最近邻的K节点连出K条边。每条边以概率p改变节点重新连接且保证没有重复边出现，这样就会出现pNK/2条长程的边把该点和远处的节点联系起来，改变p值可实现从规则网络(p=0)向随机网络(p=1)的转变。

-【NW模型】是WS模型引入新变量构成的，不同的是，不断开原来与邻近节点的连接，而是以概率p增加与其他节点之间的连接，同样保证没有重复边和自连接的边。当p=0时，NW模型为邻接网络，p=1时变为全局互连网络。当p足够小且N充分大时，NW模型和WS模型本质是等价的，都称之为小世界模型。