复杂网络（3）

实际网络都兼有确定和随机两大特征，确定性的法则或特征通常隐藏在统计性质中。人们在刻画复杂网络结构的统计特性上提出了许多概念和方法，其中包含：节点的度和度分布、平均路径长度、聚集系数。

1、节点的度和度分布

节点v_i的度k_i定义为该节点连接的边数。直观上看，一个节点的度越大就越意味着这个节点在某种意义上越”重要”。
网络中所有节点v_i和度k_i的平均值称为网络的平均度。

$$ \langle k \rangle = \frac{1}{N}\sum\limits_{i=1}^{N}k_{i} $$

网络中节点的度分布情况可用分布函数P(k)来描述，P(k)表示的是网络中度为k的节点在整个网络中所占的比率，也就是说，在网络中随机抽取到度为k的节点的概率为P(k)。一般地，可以用一个直方图来描述网络的度分布（degree distribution）性质。
对于规则的网络来说，由于所有的节点具有相同的度，所以其度分布集中在一个单一尖峰上，是一种Delta分布。网络中的任何随机化倾向都将使这个尖峰的形状变宽。完全随机网络（completely stochastic network）的度分布近似为泊松分布，其形状在远离峰值处呈指数下降。
大量的研究表明，许多实际网络的度分布明显地不同于泊松分布。特别地，许多网络的度分布可以用幂律形式k^-λ来更好地描述。

2、平均路径长度

网络中两个节点v_i和v_j之间的距离d_ij定义为连接这两个节点的最短路径上的边数，它的倒数1/d_ij称为节点v_i和v_j之间的效率，记为ε_ij。通常效率用来度量节点间信息传递速度。当v_i和v_j之间没有路径连通时，d_ij=∞，而ε_ij=0。
网络中任意两个节点之间的距离的最大值称为网络的直径，记为D。

$$ D = \max\limits_{1 \leq i < j \leq N}d_{ij} $$

网络中任意两个节点之间的距离的平均值称为网络的平均路径长度，记为L。

$$ L = \frac{1}{C_{N}^{2}}\sum\limits_{1 \leq i < j \leq N}d_{ij} $$

3、聚类系数

在你的朋友关系网络中，你的两个朋友很可能彼此也是朋友，这种属性在复杂网络理论中称为网络的聚集特性。一般地，假设网络中的一个节点v_i有k_i条边将它和其他节点相连，这k_i个节点就称为节点v_i的邻居。显然，在这k_i个节点之间最多可能有C_ki²条边。
节点v_i的k_i个邻居节点之间实际存在的边数E_i和总的可能的边数C_ki²之比就定义为节点v_i的聚类系数C_i，即

$$ C_{i} = \frac{E_{i}}{C_{k_{i}}^{2}} $$

从几何特点看，上式的一个等价定义为

$$ C_{i} = \frac{与节点v_{i}想连的三角形的数量}{与节点v_{i}想连的三元组的数量} =\frac{n1}{n2}$$

其中，与节点v_i相连的三元组是指包括节点v_i的三个节点，并且至少存在从节点v_i到其他两个节点的两条边。
整个网络的聚类系数C就是所有节点v_i的聚类系数C_i的平均值，即

$$ C = \frac{1}{N}\sum\limits_{i=1}^{N}C_{i} $$

显然，0 &le; C &le; 1。当所有节点均为孤立节点，即没有任何连接边时，C = 0；当且仅当网络是全局耦合的（即网络中任何两节点都直接相连）时，C = 1。对于一个具有N个节点的完全随机网络，当N很大时，C = O(N^-1)。
许多大规模的实际网络都具有明显的聚类效应，它们的聚类系数尽管远小于1但却比O(N^-1)大得多。事实上，在很多类型的网络中，随着网络规模的增加，聚类系数趋向于某个非零常数，即当N &rarr; ∞ 时，C = O(1)。这意味着这些实际的复杂网络不是完全随机的，而是在某种程度上具有类似于社会关系网络中”物以类聚，人以群分”的特性。