CS244W: Machine Learning with Graphs (2) ——图的性质和随机图模型_网络的largest components

网络的四种性质

• 度分布（Degree distribution）
• 路径长度（Path length）
• 聚类系数（Clustering coefficient）
• 连通分量（Connected components）

一、度分布（Degree distribution）
定义：度分布P(k)为随机选择一个节点，该节点度数为k的概率。

 
二、路径长度（Path length）
图中的路径（Path in a Graph）
定义：一个路径是指一串彼此之间相连的节点。
一条路径可以相交并多次通过同一条边。

例：ACBDCDEG是例图中的一条路径

图中的距离（Distance in a Graph）
定义：两个节点之间最短路径的边数。如果两个节点不连通，则距离为正无穷。

在有向图中路径需要遵从边的方向。

网络的直径（Network diameter）
定义：最大的两节点之间的距离。

平均路径长度（Average path length）
定义：对于连通图和强连通图而言，平均路径长度为

• h_ij是节点 i 到节点 j 的距离。
• E_max是该图可能存在的最大边数，即不同节点对的数量，即n (n- 1) / 2。

也可以忽略距离为正无穷的节点对，只计算连通的部分。
 
 
三、聚类系数（Clustering coefficient）
无向图的聚类系数
定义：聚类系数C衡量一个节点的邻居之间的连通程度，C∈[0, 1]。对于度数为k_i的节点 i ，聚类系数为：

• e_i为节点 i 的邻居之间的边数。
• k_i (k_i - 1)为节点 i 的邻居之间边数的最大值。
• 对于度数为0或1的节点，聚类系数为0或未定义。
  
  平均聚类系数为
  
  

 
四、连通分量（Connected components）
定义：最大的连通分量的大小，即任意两个节点都由路径相连的最大集合。
最大连通分支Largest component也被成为Giant component。
可使用广度优先搜索找到一个图的连通分支。
 
 
五、MSN通信网络的性质

• 度分布：当度数指数上升时比例呈指数下降。平均度数为14.4。
• 路径长度：平均路径长度为6.6，90%节点之间的距离小于8。
• 聚类系数：平均聚类系数为0.11。
• 连通分量：存在Giant component包含99.9%的节点。

如何平均网络这些性质？那些性质只是一般情况，那些性质比较不寻常？
我们需要一个模型与该网络进行对比。
 
 
六、随机图模型（Random Graph Model）
Erdös-Renyi Random Graphs
无向随机图G_np的两个参数：

• 节点数 n
• 任意一组节点之间边存在与否是独立同分布的，且概率为 p

无向随机图G_nm的两个参数：

• 节点数 n
• 随机存在 m 条边

同样的 n 和 p 能够产生很多不同的图。

 
七、随机图G_np的性质

1. G_np的度分布
   G_np的度分布是二项分布的：
   
   G_np中度数为k的节点比例＝G_np中任意节点 i 的度数为 k 的概率
   平均值与方差：
   
   对比标准差和平均值的变化：
   
   当节点数 n 极大时，标准差相比平均值极小，故任意节点的度数越接近平均度数。

2. G_np的聚类系数
   节点 i 的邻居之间存在的边数的期望值为
   
   故节点 i 聚类系数的期望值为
   

3. 路径长度
   在这引入扩展性（expansion）：
   
   或
   
   扩展性a描述了图的任意节点集与剩余节点之间边的数量，即任意节点集S都有至少a · min(|S|, |V / S|)条边与V / S相连。
   Fact：对于一个有 n 个节点，扩展性为 a 的图，任意一对节点之间存在路径长O( ( logn ) / a )。由于随机图G_np的扩展性很好，我们可以像树一样不断扩展到全部节点。扩展性a反映了扩展过程中边的数量，边的数量越多，就能越快扩展完所有节点。
   
   
   其中c为常数。log(np)表示 p 对随机图G_np直径的影响，即p越大遍历全图所需的步数越小。
   
   但平均度数不变，节点数增加时，平均距离的增长十分缓慢。

4. 连通分量
   
   当平均度数小于1时随机图基本不连通，当平均度数为3时基本完全连通。

5. 对比MSN网络和随机图G_np
   
   

 
八、小世界模型（The Small-World Model）
一个图能够同时具有较高的聚类系数和较短的路径长度吗？
Small-World Model [Watts-Strogatz ‘98]
首先，从一个低维常规网络开始，该网络具有高聚类系数。
第二步，重新连接边（Rewire）。对于任意边，以一定概率将目标节点改为一个随机的节点，以产生“捷径”。


该模型表现了集群和小世界之间的关系；捕捉到了许多真实网络的结构；说明了真实网络的高聚集性；但度分布并不正确。

九、生成大型真实图——克罗内克图模型（Kronecker Graph Model）

主要思想：递归的生成图。网络的整体的形状与它的一部分相似。克罗内克图模型是一种生成自我相似的矩阵的模型。

矩阵A和B的克罗内克內积C为

克罗内克图（Kronecker graph）就是对初始邻接矩阵K_1不断与自己进行克罗内克內积得到的图。

随机克罗内克图（Stochastic Kronecker Graph）
第一步：创建N_1 x N_1的可能性矩阵O_1
第二步：计算O_1进行k次克罗内克內积的结果O_k
第三步：对于O中任意的任意元素p_uv，以可能性p_uv决定矩阵K_k中是否存在该条边

获得图的邻接矩阵K_k需要进行n^2次随机。

快速克罗内克图生成算法（Fast Kronecker Generator Algorithm）

按照初始矩阵的概率选取一个子矩阵，重复随机选取知道确定一条边，将该边插入图中。如果重复则重新插入。

真实的网络与使用克罗内克图模型生成的网络性质十分相似。