02-网络的性质和随机图模型

• 如何表示网络属性

• 用什么样的模型生成网络

网络的性质

度的分布

度分布$p(k)$：随机选择的节点具有$k$度的概率；$N_k$：度为$k$的节点； 归一化直方图：

$$p(k)=N_k/N$$

image-20210115180538404

对于有向图，有单独的入度和出度分布

图中的路径

• 路径

路径是一个结点序列，其中每个节点都链接到下一个节点：

$$P_n=\{i_0,i_1,\cdots,i_n\}；P_n = \{(i_0,i_1),(i_1,i_2),\cdots,(i_{n-1},i_n)\}$$

一个结点可以在一条路径多次交叉的穿过同一条边，例如:$ACBDCDEG$

image-20210115180557850

• 距离

路径：连通两个结点之间的边，所构成的边集合就是路径。

最短路径：连通两个结点之间的边，所构成的边数最小的集合就是最短路径。

如果两个节点不连通，距离通常定义为$inf(or\ 0)$。

$$\begin{align} &G_{BD} = 2\\ &G_{AX} = \infty \end{align}$$

image-20210115180608091

在有向图中，路径距离需要跟随箭头的方向：

$$G_{AB} \not= G_{BA}$$

image-20210115180620606

• 网络直径

直径：图中任意一对节点之间的最大(最短路径)距离。

连通图或强连通有向图的平均路径长度：

$$\bar h=\frac{1}{2E_{max}}\sum\limits_{i,j\not=i}h_{ij}$$

其中，$h_{ij}$为结点$i$到结点$j$的距离，$E_{max}$为结点$i$到$j$的最大边数，节点对总数= $\frac{n(n-1)}{2}$

1. 很多时候，只计算连接节点对的平均值

2. 注意，该度量也适用于图的(强)连接分量

聚类系数

聚类系数$(用于无向图)$：聚合系数是衡量一个节点的邻居相互之间的连接程度。

$$C_i = \frac{2e_i}{k_i(k_i-1)}$$

其中，$i$结点具有$k_i$度，$C_i \in {0,1}$。

image-20210115180637500

平均聚类系数：

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

连通性

最大连通分量：任意两个顶点被一条路径的最大集合所连接起来。

如何找到连通分量：

• 从随机节点开始，执行广度优先搜索$(BFS)$

• 标记$BFS$访问的节点

• 如果所有节点都被访问，则网络已经连通

• 否则，找到一个未访问的节点并重复$BFS$

image-20210115180713043

图模型

简单图

• $G_{np}$：$n$个节点上的无向图，每一对结点$(u,v)$都以概率$p$独立连接。

$G_{nm}$：具有$n$个节点，$m$条边的无向图。

随机图模型

随机图

随机图就是将一堆顶点随机的连接上边。

image-20210108220236693

相同的点以及边数，有着很多种构造图的方式。

事实上$G_{np}$的度分布是二项式的；设$P(k)$表示结点的度为$k$的概率。设$P(k)$表示结点的度为$k$的概率，则

$$P(k) = \left[ \begin{matrix} n-1 \\ k \end{matrix} \right]p^k(1-p)^{n-1-k}$$

二项分布的均值，方差为：

$$\begin{align} &\bar k = p(n-1) \\ &\sigma^2 = p(1-p)(n-1) \end{align}$$

假设$P(k)$服从于高斯分布，有

image-20210113112849612

根据大数定律，随着网络规模的增加，分布变得越来越窄——使得我们越来越相信一个节点的度在k附近。

$$\frac{\sigma}{k} = \left[ \begin{matrix} \frac{1-p}{n}&\frac{1}{n-1} \end{matrix} \right]^{\frac{1}{2}} = \frac{1}{(n-1)^{\frac{1}{2}}}$$

$G_{np}$的聚类系数

$$C_i = \frac{2e_i}{k_i(k_i-1)}$$

其中，$e_i$是$i$的邻居之间的边数。且边在$G_{np}$中出现的概率均为$p$，有，

$$E(e_i) = p\frac{k_i(k_i-1)}{2}$$

然后，有

$$E[C_i] = p\frac{2\cdot \frac{k_i(k_i-1)}{2}}{k_i(k_i-1)} = p = \frac{\bar k}{n-1} \approx \frac{\bar k}{n}$$

于是，

$$C = p = \frac{\bar k}{n}$$

$G_{np}$的路径

为了更好的描述路径，定义一个概念Expansion：

• 在图$G(V,E)$中，对于结点的任何子集$(if \ \forall S\subseteq \ V)$，边的数量将具有扩展$\alpha$，且有$\alpha\cdot min(|S|,|V\setminus S|)\leq S$

$$\alpha = \mathop{min}_{S\subseteq V}\frac{保留该集合S的边缘数}{min(|S|,|V\setminus S|)}$$

image-20210113115243416

假设，一个具有$n$个结点的随机图以及扩展$\alpha$，那么对于所有的成对的结点之间的路径长度为$O(\frac{\log n}{\alpha})$

image-20210113121422409

随机图的直径$(diam)$为:

$$for\ log\ c\leq np\leq n,diam(G) = \frac{\log{n}}{\log{np}}$$

随机图具有良好的扩展性，因此$BFS$访问所有节点需要对数级的步骤。

随机图与真实的网络

随机网络模型的问题:

• 度分布不同于真实网络

• 在大多数真实网络中，巨大的组件不会通过相变出现

• 任何局部结构聚类系数都不会太低

注意真实的网络不是随机的。

小世界模型

如何能同时具有高聚类和小直径?

image-20210113133830651

• 聚类意味着边缘“局部性”

• 随机性创造了“捷径”

采用小世界模型，就可以同时具有两种性质。

小世界模型$(The\ Small-World\ Model)$$[Watts-Strogatz\ '98]$

模型的两个组成部分:

$(1).$ 一个环状的规则网络开始：网络含有$N$个结点，每个节点向与它最临近的$K$个节点连出$K$条边，并满足$N>>K>>ln(N)>>1$。

$(2).$ **随机化重连：以概率$p$随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。**其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。这样就会产生$pNK/2$条长程的边把一个节点和远处的结点联系起来。改变$p$值可以实现从规则网络$(p=0)$向随机网络$(p=1)$转变。

image-20210113135842552

该模型至少能够部分解释许多网络中的“小世界”现象 "，比如电网、电影演员的社交网络。

image-20210113140459276

Kronecker图模型

kronecker 图模型

1. 用途

在基于网络属性模拟的生成模型中，有一些模型使用矩阵的乘积模拟网络的邻接矩阵的扩展和演化。其中，$Jure\ Leskovec$等研究人员发现可以用矩阵的$Kronecker$乘积操作来生成网络，并且通过实验验证了$Kronecker$图模型生成的网络可以很好地模拟静态网络的度分布、特征值分布以及动态网络的直径、密度变化的幂律分布等特性。$Kronecker$积的数学特性使得$Kronecker$图模型所生成的网络具有良好的可分析性。

1. 如何递归地思考网络结构？直觉：自相似性

物体与自身的一部分相似：整体的形状与一个或多个部分相同

1. 模拟递归图/社区增长：

image-20210113142616436

1. $Kronecker$内积是一种生成自相似矩阵的方法

2. $Kronecker$图模型

网络结构的递归模型

image-20210113142850781

1. $Kronecker$内积的定义：

$$C = A_{N\times N} \otimes B_{K\times L} = \left[ \begin{matrix} a_{11}B&a_{12}B&\cdots&a_{1m}B \\ a_{21}B&a_{22}B&\cdots&a_{2m}B \\ \vdots&\vdots&\ddots&\vdots \\ a_{n1}B&a_{n2}B&\cdots&a_{nm}B \\ \end{matrix} \right]_{N*K\times M*L}$$

1. 定义两个图的克罗内克积为其邻接矩阵的克罗内克积，$Kronecker$图是通过在初始矩阵上迭代$Kronecker$积得到的图的增长序列

$$K_1^{[m]}=K_m = \underbrace{K_1\otimes K_1\otimes\cdots\otimes K_1}_{m\ times}=K_{m-1}\otimes K_1$$

image-20210113144200068

随机Keronecker图

为了使模型能够更好地模拟真实世界网络，提出了$Kronecker$图模型的改进模型，即随机$Kronecker$图模型。

• 创建$N_1\times N_1$的概率矩阵$\Theta_1$

• 递归计算第$k$个$Kronecker$乘积$\Theta_k$

• $\Theta_k$中的值$p_{uv}$表示节点和$u$节点$v$之间生成边的概率

image-20210113145719866

当实际的运行的时候，会发现$Kronecker$图运算太费时间了，这个该怎么解决？

可以利用Kronecker图的递归结构

• 快速生成克罗内克图的方法

image-20210113150639423

• 如何在$n = 2^m$个节点的图$G$生成$kronecker$图

image-20210113150756701

利用递归的性质，进行生成。

真实网络和克罗内克图模型的比较

估计：点值$(n=76k,m=510k)$

image-20210113153547433

实验证明 $Kronecker $图在各种性质上都能较好地拟合真实的网络。但这个模型生成的图的$ degree\ distribution $并不是平滑的。直观上说，按初始定义的$ block\ structure $进行递归所得到的图可能的确存在这个问题，即某些部分连接紧密有些地方稀疏，而这种差异并不连续。

用于模拟真实世界的