Chapter 1 网络模型

随机图

图论的基本概念

在开始介绍有关网络的概念之前，首先需要介绍的是有关图论的相关内容。

• 顶点度(Degrees of a Vertex)
  一个图由\(N\)个顶点相互连接构成，其中每个顶点的度数定义为与某个这个顶点连接的边的个数。
  
• 配位数(Corrdination Number)
  配位数指的是整张图的平均顶点度。

在这里，我们引入随机图（random graph）的概念：一个随机图指的是图中的两个顶点以概率\(p\)连接的图称为随机图。\(p\)称为随机图的连接概率(Connection Probability).

Erdos-Renyi图是一种特殊的随机图，它由\(N\)个顶点和\(\frac{Nz}{2}\)条边随机连接，因此其连接概率为：
\[ p=\frac{Nz}{2}\frac{2}{N(N-1)}=\frac{z}{N-1} \]

当构成图的元素数量趋近于无穷大的时候，此时的极限称为热力学极限。对于Erdos-Renyi图，\(N\rightarrow 0\)时候连接概率的热力学极限为\(p\rightarrow 0\).

小世界效应

定义随机图的直径\(D\)为所有可能的顶点配对组合之间的最大分离度。如果一个具有对于给定的平均度数\(z\)和顶点数\(N\)的图，\(D\)可以近似为：
\[ z^D\approx N \] 也就是说，\(D\)正比于\(logN\)。称这样的图/网络具有小世界效应，具有小世界效应的网络往往可以通过几个顶点就能够遍历绝大部分的其他结点。

• 网络中的聚类
  在网络中，称聚类系数（Clustering Coefficient） 为相邻结点之间有边的概率，对于随机图而言，其中的一个结点通常具有\(z(z-1)/2\)对相邻的结点，根据之前的推导，那么随机图聚类系数同等于Erdos-Renyi图的连接概率，即为：
  \[ C_{rand}=\frac{z}{N-1}\approx \frac{z}{N} \] ​ 聚类系数越大表明网络的连通性越强。

• 团
  在网络中，定义团(Cliques)为一组满足如下条件的顶点：

  • 每个顶点都通过一条边与其他所有顶点相连
    
  • 团外的任何顶点都不会和团内的所有顶点相连

  如果把团在社交网络中类比，那么团的意思是在这个社群中所有的人都知道对方。
  在有\(N\)结点和连接概率为\(p\)的Erdos-Renyi图中，存在大小为\(K\)的团的数量为：
  \[ C_N^Kp^{K(K-1)/2}(1-P^K)^{N-K} \] 即从\(N\)个顶点中选择\(K\)个顶点，这些顶点两两连接，并和其他结点不连接。

一些研究统计了真实的网络中的聚类系数，列表如下，其中\(C_{rand}\)表示同等情况下的随机图的聚类系数：

	\(N\)	\(C\)	\(C_{rand}\)
Movie Actors	225226	0.79	0.00027
Neural Network	282	0.28	0.05
Power Grid	4941	0.08	0.0005
Internet Domains	6242195	0.20	0.000006

可以发现，相比于随机图，真实的网络具有相当大的聚类系数，连通性要比随机图好得多，这意味着真实的网络中存在小世界效应。这是因为：

• 真实的网络中可能存在相当多的环路，然而许多随机图在达到热力学极限之后倾向于形成树图而非环路
• 现实中的网络中存在二部图（Bipartite），即一种包含两组顶点，且顶点仅在组之间存在连接。二部图的出现会增加聚类系数。

度分布

度分布函数

定义有数量为\(X_k\)的顶点中存在度数为\(k\)，那么\(p_k=X_k/N\)表示在所有的顶点中有多少个结点的度数为\(k\)。有\(\sum_kp_k=1\)。

在Erdos-Renyi图中，\(p_k\)服从二项分布：
\[ p_k=C_{N-1}^kp^k(1-p)^{N-1-k} \] 当\(N>>k\)时，这个分布退化为泊松分布，有：
\[ p_k=e^{-z}\frac{z^k}{k!} \] 根据泊松分布的性质可以求得\(p_k\)的均值和方差都为\(z\).

幂律分布和无尺度图

存在一种特殊情况是当\(k\)非常大的时候，\(p_k\)与\(k^{-\alpha}\)成正比关系，其中\(\alpha\)为一个系数，因此\(p_k\)的变化符合幂律。在这种情况下，\(p_k\)的平均值为： \[ \overline{p_k}=\frac{\alpha-1}{2-\alpha}(1+k)^{2-\alpha}|^K_0-1 \] 当\(\alpha\leq2\)的时候该式子不成立，当\(\alpha>2\)时\(\overline{p}=\frac{1}{\alpha-2}\), \(\alpha >3\)时方差为无穷大。

从上面的式子中可以推出，无论\(k\)再增加多少倍，增加的倍数\(a\)都可以被归一化吸收，其性质仍然保持不变。称\(p_k\)符合幂律分布的随机图为无尺度图。