1. (Traditional) Generative Models for Graphs

1. 图生成模型问题的研究动机：

我们此前的学习过程中，都假设图是已知的；但我们也会想通过graph generative model人工生成与真实图类似的synthetic graph，这可以让我们：

①了解图的形成过程。

②预测图的演化。

③生成新的图实例。

④异常检测：检测一个图是否异常。

2. 本课程对图生成模型的介绍流程：

在本章介绍真实图的属性（生成图需要符合的特性）和传统图生成模型（每种模型都源自对图形成过程的不同假设）。

在下一章介绍深度图生成模型，从原始数据直接学习到图生成过程。

2. Properties of Real-world Graphs

1. 衡量真实图数据的属性有：

degree distribution

clustering coefficient

connected components

path length

对这些属性的介绍可参考

4. connectivity是largest connected component（任意两个节点都有路径相连的最大子图2）的大小。

largest component=giant component

找到connected components（连通分量）的方法：随机选取节点跑BFS3，标记所有被访问到的节点；如果所有节点都能访问到，说明整个网络都是连通的；否则就选一个没有访问过的节点重复BFS过程。

5. path length：一条路径的长度。

节点对之间最短路径长度称为距离。

diameter：图中最大的节点对间最短路径。

6. 案例研究：MSN Graph（社交网络）

（这个本来有个地图，但是它好像有点问题，在B站视频里直接码掉了，我也不敢放。总之就是一个地图，并说图数据中有180M用户节点、1.3B条边）

• degree distribution

用线性坐标轴绘制就基本啥都看不清：

用log-log双对数坐标绘制（数据不变，但是坐标轴换成对数的）：

• clustering coefficient按度数分布：

• weakly connected component4大小的分布：

• path length的分布：

small word phenomenon：虽然图很大但是平均最短路径很小（6.6）。

随机选择一个节点，90%节点都可以在8跳BFS内达到。

• 这些核心属性在图上的最终结果：这些值是否超乎预料，需要通过图生成模型来检验。

3. Erdös-Renyi Random Graphs6

3. G _{n p} 的图属性值：

这种平均度数在1上下会突然出现largest connected component的转变被称为phase transition9 behavior，如图所示，平均度数达到3的时候已经几乎所有节点都属于largest connected component了：

4. G _{n p} 的degree distribution，clustering coefficient和connectivity：

6. expansion是用来衡量鲁棒性的：为了disconnect l 个节点（让一个CC中 l 个节点不再属于这个CC），需要割断至少 α ⋅ l条边。

（为什么是 l  而不是 min ⁡ ( l , n − l ) 呢，因为 n − l 要是比 l 还小这就不太对劲了，就不是这 l  个节点被disconnect了而是对面被disconnect了对吧……在上文也说了一般这部分是小部分，所以可以直接用 l 的）

如图所示，expansion越低的图越容易被disconnect。而社交网络就是在社区内部expansion高，在社区之间expansion低：

4. The Small-World Model

1. 发明小世界模型的动机：我们有高聚集系数、高diameter的regular lattice graph，也有低聚集系数、低diameter的 G _{n p}  随机图，但真实图是低diameter、高聚集系数的，我们希望找到一个能生成这种图的模型。

2. 在同节点数、同平均度数的随机图的对比下，各种真实图都展示出了类似的特质：

3. 在随机图和regular lattice graph中，这两个属性间却存在着矛盾：

由于expansion的缘故，在固定平均度数时，随机图中的short paths为 O ( log ⁡ n ) 长但聚集系数也很低。

而有局部结构的网络regular lattice graph有很多社交网络中常有的triadic closure（我朋友的朋友还是我的朋友），即高聚集系数，但diameter也很高。

4. 我们希望在两种图间进行插值，得到结合二者特性，高聚集系数、低diameter的small-world graph：

5. small-world model13 的方法：

• 从一个低维regular lattice（这里表示成ring）开始，这个图有很高的聚集系数和diameter。

• rewire：新增随机捷径，将本来较远的部分连接起来

对每个边，以 p 的概率将一端移到一个随机节点上

（但这些公式是怎么得到的，我并不知道）

6. 在下图中绿色箭头指向的区域，就是小世界模型适宜的参数区域：（能够得到这个合适区域的直觉理解：需要很多随机性才能破坏聚集系数，但仅需一点随机性就能产生捷径，所以就能得到高聚集系数、低diameter的中间的图）

7. 总结：

小世界模型提供了一个在clustering和small-world（指diameter小）之间交互的视角，捕获到了真实图的结构，解释了真实图中的高聚集系数，但其度数分布仍然并不符合真实图的情况。

5. Kronecker Graph Model

1. Kronecker Graph Model的idea：迭代式的图生成

self-similarity：物体自身总是与其部分相似。我们模仿图/社区的迭代式增长，如图所示不断重复同样的图的生成过程。

Kronecker product克罗内积就是一种生成self-similar矩阵的方式。

2. （这个东西看起来有点分形的感觉噢……但是这个self-similar的是邻接矩阵，其实也不是图本身）

3. 克罗内积定义：

矩阵 A  和 B 的克罗内积

图的克罗内积是对两个图的邻接矩阵求克罗内积，以其值作为新图的邻接矩阵。

4. Kronecker graph就通过对initiator matrix K 1 连续迭代做克罗内积，逐渐增长式得到最终结果（也可以用多个尺寸、元素都可以不同的initiator matrics）：

5. Kronecker initiator matrices示例：

6. stochastic Kronecker graphs

步骤如图所示：

7. Generation of Kronecker Graphs

根据上面提到的方法，如果想要生成一个有向的stochastic Kronecker graph，需要计算 n ² 次概率，太慢。

利用Kronecker graphs的递归特性，我们还有一种更快的方法ball dropping / edge dropping：

10. Fast Kronecker generator algorithm中插入一条有向边的算法：

• 对矩阵进行归一化（就让它的元素总和为1，也就是变成概率矩阵）。
• 逐层根据概率选择象限并挪动对应的坐标。在选到最后一层时就把这条边添上。

6. 本章总结

介绍了传统的图生成模型，每种模型都对图生成过程提出了不同的先验假设。

下一章将介绍直接从原始数据学习图生成过程的深度图生成模型。