Stanford图机器学习公开课CS224W(二)笔记

Lecture 2 -Properties of Networks & Random Graph Models

Posted by Yunlongs on November 16, 2020

Properties of Networks & Random Graph Models

1. 网络的属性:如何来度量一个网络

For 无向图,对于有向图很容易泛化

1.1 度分布(Degree Distribution)

Degree distribution $P(k)$: 一个随机选取的节点,其度为k的概率。

$N_k$为度为k的节点个数,$P(k) = N_k/N$.

1.2 路径长度(Path Length)

路径长度 两个点之间的最短距离。

图的直径(Diameter):图中的最大路径长度。

平均路径长度:对于强连通图来说: \(\bar{h}=\frac{1}{2 E_{\max }} \sum_{i, j \neq i} h_{i j}\) 其中$h_{ij}$为节点i和节点j之间的距离,$E_{max}=n(n-1)/2$为图可能存在的最多边数。

1.3 聚类系数(Clustring Coefficient)

用来评估节点的邻居们之间的连通性。 当节点i的度表示为$k_i$时,此节点的聚类系数为: \(C_i = \frac{2e_i}{k_i(k_i-1)}\)

其中,$e_i$为节点i的邻居中存在的边数。

平均聚类系数: \(C = \frac{1}{N} \sum^N_i C_i\)

1.4 连通成分大小(Connected components)

为最大连通子图中节点的个数。

2.真实网络的属性度量

对MSN中的网络进行了统计。

3.Erdös-Renyi Random Graphs

为了回答上面的问题,因此,我们需要为图进行建模。

3.1 随机图模型

有两种变体:

  1. $G_{np}$: 有n个节点,且每条边都以概率$p$出现的无向图
  2. $G_{nm}$: 有n个节点,随机采样m条边的无向图。

后面我们主要使用第一种形式。需要注意的是相同的n和p值可以具有多种的图表现形式。

3.2 随机图模型的属性度量

3.2.1 随机图的度分布

随机图的度分布是二项式的,如下图: 原因很简单:从N-1个节点中随机选择k个节点,选中的概率为p,没选中的概率为(1-p)

3.2.2 随机图的聚类系数

3.2.3 随机图的属性总结

路径长度和最大连通图大小的证明省略。 从图中可以看出来,随机图模型与真实世界网络之间存在较大的差距,因此随机图模型并不能很好的反映出真实网络。

4. The Small-World Model

4.1 聚类系数意味着边的局部性

从上面的例子可以看出来,MSN真实网络的聚类系数比随机图模型大了7阶,并且老师还举了其他几个例子,都发现真实网络的聚类系数要大的多。

为此,还发现当将一个低聚类系数的网络变成高聚类系数的网络,网络中将会出现局部结构,聚类意味着边的局部性,而随机性则会在不同节点之间增加短接边。

Small-World model

当不断的增加p的概率,就可以得到一个合适的参数区间,同时具有高聚类系数和低路径长度,来模拟真实世界。

总结

  • 提供small-world的思想,和聚类之间的短接
  • 捕捉了一些真实网络的结构特性
  • 为真实网络的高聚类系数做出了解释
  • 但没有提供正确的度分布

5.Kronecker graphs:

提出了一种自相似性的观点,认为目标的各部分之间具有相似性。

而利用Kronecker积可以生成具有这种自相似性的矩阵。

5.1 Kronecker graphs模型

定义:两个图之间的Kronecker 乘积为其邻接矩阵之间的乘积

而Kronecker graphs则是通过对一个初始矩阵迭代进行Kronecker 乘积生成。

5.2 Stochastic Kronecker graphs

  1. 创建一个$N_1\times N_1$的概率矩阵$\theta_1$
  2. 对其计算k次Kronecker乘积得到$\theta_k$
  3. 对于$\theta_k$中的每条边$(u,v)$具有概率$p_{uv}$

实验结果显示,此模型与真实网络非常相似