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

最后更新于3年前

这有帮助吗？

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

如何表示网络属性
用什么样的模型生成网络

网络的性质

度的分布

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

p(k)=N_k/N

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

图中的路径

路径

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

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$

距离

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

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

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

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

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

G_{AB} \not= G_{BA}

网络直径

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

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

\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}$

很多时候，只计算连接节点对的平均值
注意，该度量也适用于图的(强)连接分量

聚类系数

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

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

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

平均聚类系数：

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

连通性

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

如何找到连通分量：

从随机节点开始，执行广度优先搜索$(BFS)$
标记$BFS$访问的节点
如果所有节点都被访问，则网络已经连通
否则，找到一个未访问的节点并重复$BFS$

图模型

简单图

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

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

随机图模型

随机图

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

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

事实上$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)$服从于高斯分布，有

根据大数定律，随着网络规模的增加，分布变得越来越窄——使得我们越来越相信一个节点的度在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|)}

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

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

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

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

随机图与真实的网络

随机网络模型的问题:

度分布不同于真实网络
在大多数真实网络中，巨大的组件不会通过相变出现
任何局部结构聚类系数都不会太低

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

小世界模型

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

聚类意味着边缘“局部性”
随机性创造了“捷径”

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

小世界模型$(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)$转变。

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

kronecker 图模型

用途

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

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

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

模拟递归图/社区增长：

$Kronecker$内积是一种生成自相似矩阵的方法
$Kronecker$图模型

网络结构的递归模型

$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}

定义两个图的克罗内克积为其邻接矩阵的克罗内克积，$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

随机Keronecker图

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

创建$N_1\times N_1$的概率矩阵$\Theta_1$
递归计算第$k$个$Kronecker$乘积$\Theta_k$
$\Theta_k$中的值$p_{uv}$表示节点和$u$节点$v$之间生成边的概率

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

可以利用Kronecker图的递归结构

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

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

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

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

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

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