复杂网络(3)

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

1、节点的度和度分布

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

$$ \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、平均路径长度

网络中两个节点vi和vj之间的距离dij定义为连接这两个节点的最短路径上的边数,它的倒数1/dij称为节点vi和vj之间的效率,记为εij。通常效率用来度量节点间信息传递速度。当vi和vj之间没有路径连通时,dij=∞,而ε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、聚类系数

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

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

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

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

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

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

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

0%