小世界模型

模型引入

ER随机图中的聚类系数是一个很小的值，会随着节点数量的增加而持续减小。那么如何在确定最短路径的同时获得一个比较大的距离系数呢?

实际上，聚类系数反应的是边的局部特性，而ER图的聚类系数和真实网络的差距过大，我们举一个例子

通过上面的例子可以发现，随机图计算出来的聚类系数和真实的聚类系数的数量级相差至少在 10^2 以上。

在网格网络中，我们实现了三角闭合和高聚类系数，但是平均路径长度较长。

在随机网络中，我们实现了较短的平均路径长度，但聚类系数较低。

基于以上两个图结构，似乎不能直观地得到一个具有较短的平均路径长度，同时也具有较高的聚类系数的图。但是，大多数现实世界网络具有如下表所示的属性，其中 $h$ 是平均最短路径长度，$c$ 是平均聚类系数为，了便于比较，随机图的平均度与实际网络相同。

网络类型	$h_{actual}$	$h_{random}$	$c_{actual}$	$c_{random}$
电影演员	3.65	2.99	0.79	0.00027
电力网络	18.70	12.40	0.080	0.005
C.elegans	2.65	2.25	0.28	0.05

同时满足以上标准的高聚类系数和小平均路径长度的网络（数学上定义为 $L\propto \log N$，其中 $L$ 是平均路径长度，$N$ 是网络中的节点的总数）称为小型世界网络。

小世界模型

1998年，Duncan J. Watts和Steven Strogatz提出了一个模型，该模型用于构建具有高聚类和较短平均路径长度的网络。他们将此模型称为“小世界模型”。要创建这样的模型，我们采用以下步骤：

1. 低维度的规则格
   在我们实际的情况中，我们可以将图中的环视为一个格。从低维度的常规环开始，通过将每个节点连接到右侧的 $k$ 个邻居和左侧的 $k$ 个邻居， 其中 $k\geq2$。
   

2. 重新连线，生成捷径
   添加或者删除一些边，依次来将一些“捷径”以概率 $p$ 加入到距离较远的格部分。
   

然后，我们进行以下观察：

• 在 $p=0$ 没有发生重新连接边的地方，这仍然是具有高簇集，大直径的网格网络。
• 对于 $0<p<1$ ，某些边缘已经进行了重新连线，但是大部分结构仍然保留。这意味着localoity和shortcuts。
• 对于 $p=1$，所有边缘都进行了随机重新连接，这是一个具有低聚类，低直径的ErdősRényi (ER)随机图。

小世界模型通过重新连接概率 $p \in[0,1]$ 来参数化。观察聚类系数和平均路径长度如何随 $p$ 的变化——平均路径长度随着 $p$ 增加而下降得更快，而聚类系数仍然相对较高。重新布线引入了shortcuts，这使得在结构保持相对坚固（高度聚类）的情况下，平均路径长度也可以减小。

从社交网络的角度来看，这种现象是直观的。虽然我们的大多数朋友都是本地人，但我们在不同国家/地区也有一些远距离的友谊，这足以使人类社交网络的直径崩溃，从而解释了流行的“六度分离”概念。

Watts-Strogatz小世界模型的两个局限性在于其度的分布与现实网络的幂律分布不匹配，并且由于假定了网络的大小，因此无法对网络的增长进行建模。

小结

1. 通过小世界模型，只要确定合适的概率p，我们就可以获得一个比较小的图的直径，同时获得比较大的聚类系数。也就是在聚类系数和直径之间做出来一个平衡
2. 更容易去捕捉局部特征
3. 由于更高的聚类系数，所以更好的去模拟了真实的网络

克罗内克(Kroneker) 图模型

基本结构

图生成的模型已被广泛研究。这些模型使我们能够在收集实际图困难时生成用于仿真和假设检验的图，并且还使我们可以检查生成模型应遵循的某些现实属性。

在制定图生成模型时，有两个重要的考虑因素。首先是生成现实网络的能力，其次是模型的数学易处理性，这允许对网络属性进行严格的分析。

Kronecker图模型是一个递归图生成模型，结合了数学易处理性和实际的静态和时态网络属性。Kronecker图模型的直观感受是自相似性，整体具有一个或多个部分的形状相同。

Kronecker积

Kronecker积是一种非标准的矩阵运算，是一种生成自相似矩阵的方法。

数学上，Kronecker积是两个任意大小矩阵间的运算，表示为 $\otimes$。对于两个任意矩阵 $A \in \mathbb{R}^{m \times n}$ 和 $B \in \mathbb{R}^{p \times q}$， $A\otimes B \in \mathbb{R}^{mp \times nq}$，即：

$$\textbf{A} \otimes \textbf{B} = \begin{bmatrix}a_{11}\textbf{B} & \dots & a_{1n}\textbf{B} \\ \vdots &\ddots & \vdots \\ a_{m1}\textbf{B} & \dots & a_{mn}\textbf{B} \\ \end{bmatrix}$$

例如，

$$\begin{bmatrix} 1&2\\3&4 \end{bmatrix} \otimes \begin{bmatrix} 0&5\\6&7 \end{bmatrix} = \begin{bmatrix} 1 \begin{bmatrix} 0&5\\6&7 \end{bmatrix} &2 \begin{bmatrix} 0&5\\6&7 \end{bmatrix} \\3 \begin{bmatrix} 0&5\\6&7 \end{bmatrix} &4 \begin{bmatrix} 0&5\\6&7 \end{bmatrix} \end{bmatrix} = \begin{bmatrix} 1 \times 0 & 1 \times 5 & 2 \times 0 & 2 \times 5\\ 1 \times 6 & 1 \times 7 & 2 \times 6 & 2 \times 7\\ 3 \times 0 & 3 \times 5 & 4 \times 0 & 4 \times 5\\ 3 \times 6 & 3 \times 7 & 4 \times 6 & 4 \times 7 \end{bmatrix} = \begin{bmatrix} 0 & 5 & 0 & 10\\ 6 & 7 & 12 & 14\\ 0 & 15 & 0 & 20\\ 18 & 21 & 24 & 28 \end{bmatrix}$$

为了在图生成中使用Kronecker积，我们将两个图的Kronecker积定义为两个图的邻接矩阵的Kronecker积。

从初始矩阵$K_{1}$(图的邻接矩阵)开始，我们迭代Kronecker积以生成更大的图

$$K_{2}=K_{1}\otimes K_{1},K_{3}=K_{2}\otimes K_{1} \dots$$

$m$ 阶的Kronecker图定义为

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

直观地，可以将Kronecker幂构造想象为图中的社区的递归增长，其中社区中的节点递归地扩展为社区的微型副本。Kronecker初始矩阵 $K_1$ 的选择可以改变，这会迭代影响较大图形的结构。

随机的Kronecker图

目前，我们仅考虑了具有二进制值 ${0,1}$ 的初始矩阵 $K_1$。但是，从此类初始矩阵生成的图在度数分布和其他属性中具有“阶梯”效应：由于 $K_1$ 的离散性质，个别值非常频繁地出现。

为了消除这种影响，通过放宽初始矩阵中的条目只能采用二进制值这个假设来引入随机性。取而代之的是可以采用 $[0,1]$ 范围上的值的矩阵 $\Theta_1$，并且每个值都代表该特定边出现的概率。这样矩阵（以及所有生成的较大矩阵乘积）表示该矩阵在所有可能图上的概率分布。

更具体地说，对于概率矩阵 $\Theta_1$，我们计算 $k^{th}$ Kronecker幂 $\Theta_k$ 作为大型随机邻接矩阵。每个 $\Theta_k$ 中的值 $p_{uv}$ 则代表边 $(u,v)$ 出现的概率。（请注意，概率总和不必为1，因为每个边缘出现的概率与其他边缘无关）

为了获得图的一个实例，通过以随机邻接矩阵中相应条目给出的概率对每个边进行采样，然后从该分布中进行采样。采样可以被认为是抛具有偏差的硬币的结果，其中偏差被矩阵中的每个条目参数化。

但是，这意味着简单的生成实例的时间是图形大小的平方，即 $O(N^2)$；当具有100万个节点，我们需要抛 100万$\times$100万 次硬币。

Kronecker 随机图的生成过程

存在一种快速启发式生成图形的过程，该过程所需时间随着边数量线性变化。

总体思路可以描述如下：对于每个边缘，我们以概率 $p_{uv} \in \Theta_1$递归地选择大随机矩阵的子区域，直到我们下降到大随机矩阵的单个单元为止。我们将边缘放置在那里。对于Kronecker图的 $k^{th}$ 幂 $\Theta_k$，将需要 $k$ 次下降步骤。

例如，考虑 $\Theta_1$ 是一个 $2 \times 2$ 的矩阵

$$\Theta =\begin{bmatrix} a & b \\ c & d \end{bmatrix}$$

对于具有 $n=2^k$ 个节点的图 $G$

• 创建归一化矩阵 $L_{uv}=\frac{p_{uv}}{\sum_{u,v}p_{uv}},\quad p_{uv} \in \Theta_1$

• 对于每个边缘：

  • For $i=1 \dots k:$
    • 初始 $x=0,y=0$
    • 以概率 $L_{uv}$ 选择行和列
    • 下降到 $G$ 的第 $i$ 级象限$(u,v)$
      • $x=x+u \cdot 2^{k-1}$
      • $y=y+v \cdot 2^{k-1}$
    • 将边 $(x,y)$ 添加到 $G$

如果 $k=3$，且对于每一步 $i$，选择象限 $b_{(0,1)},c_{(0,1)},d_{(0,1)}$ 分别基于 $L$ 的归一化概率，有

$$x=0\cdot 2^{3-1}+1\cdot 2^{3-2}+1\cdot 2^{3-3}=0\cdot 2^2+1\cdot 2^1+1\cdot2^{0}=3\\ y=1\cdot 2^{3-1}+0\cdot 2^{3-2}+1\cdot 2^{3-3}=1\cdot 2^2+0\cdot 2^1+1\cdot2^{0}=5$$

因此，我们将边$(3,5)$添加到图中。

按照上述启发式方法，可以逐个生成连边，直到连边数满足我们的需求为止。Kronecker Graph的度量指标与相近规模的真实网络十分接近。要阅读有关Kronecker图模型的更多信息，请参阅 J Leskovec et al., Kronecker Graphs: An Approach to Modeling Networks (2010)。