1. (Traditional) Generative Models for Graphs
- 图生成模型问题的研究动机：
我们此前的学习过程中，都假设图是已知的；但我们也会想通过graph generative model人工生成与真实图类似的synthetic graph，这可以让我们：
①了解图的形成过程。
②预测图的演化。
③生成新的图实例。
④异常检测：检测一个图是否异常。
- 本课程对图生成模型的介绍流程：
在本章介绍真实图的属性（生成图需要符合的特性）和传统图生成模型（每种模型都源自对图形成过程的不同假设）。
在下一章介绍深度图生成模型，从原始数据直接学习到图生成过程。
2. Properties of Real-world Graphs
- 衡量真实图数据的属性有：
degree distribution
clustering coefficient
connected components
path length
对这些属性的介绍可参考
- connectivity是largest connected component（任意两个节点都有路径相连的最大子图2）的大小。
largest component=giant component
找到connected components（连通分量）的方法：随机选取节点跑BFS3，标记所有被访问到的节点；如果所有节点都能访问到，说明整个网络都是连通的；否则就选一个没有访问过的节点重复BFS过程。
- path length：一条路径的长度。
节点对之间最短路径长度称为距离。
diameter：图中最大的节点对间最短路径。
- 案例研究：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
- G n p 的图属性值：
这种平均度数在1上下会突然出现largest connected component的转变被称为phase transition9 behavior，如图所示，平均度数达到3的时候已经几乎所有节点都属于largest connected component了：
- G n p 的degree distribution，clustering coefficient和connectivity：
- 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
- 发明小世界模型的动机：我们有高聚集系数、高diameter的regular lattice graph，也有低聚集系数、低diameter的 G n p 随机图，但真实图是低diameter、高聚集系数的，我们希望找到一个能生成这种图的模型。
- 在同节点数、同平均度数的随机图的对比下，各种真实图都展示出了类似的特质：
- 在随机图和regular lattice graph中，这两个属性间却存在着矛盾：
由于expansion的缘故，在固定平均度数时，随机图中的short paths为 O ( log n ) 长但聚集系数也很低。
而有局部结构的网络regular lattice graph有很多社交网络中常有的triadic closure（我朋友的朋友还是我的朋友），即高聚集系数，但diameter也很高。
- 我们希望在两种图间进行插值，得到结合二者特性，高聚集系数、低diameter的small-world graph：
- small-world model13 的方法：
- 从一个低维regular lattice（这里表示成ring）开始，这个图有很高的聚集系数和diameter。
- rewire：新增随机捷径，将本来较远的部分连接起来
对每个边，以 p 的概率将一端移到一个随机节点上
（但这些公式是怎么得到的，我并不知道）
- 在下图中绿色箭头指向的区域，就是小世界模型适宜的参数区域：（能够得到这个合适区域的直觉理解：需要很多随机性才能破坏聚集系数，但仅需一点随机性就能产生捷径，所以就能得到高聚集系数、低diameter的中间的图）
- 总结：
小世界模型提供了一个在clustering和small-world（指diameter小）之间交互的视角，捕获到了真实图的结构，解释了真实图中的高聚集系数，但其度数分布仍然并不符合真实图的情况。
5. Kronecker Graph Model
- Kronecker Graph Model的idea：迭代式的图生成
self-similarity：物体自身总是与其部分相似。我们模仿图/社区的迭代式增长，如图所示不断重复同样的图的生成过程。
Kronecker product克罗内积就是一种生成self-similar矩阵的方式。
2.
（这个东西看起来有点分形的感觉噢……但是这个self-similar的是邻接矩阵，其实也不是图本身）
- 克罗内积定义：
矩阵 A 和 B 的克罗内积
图的克罗内积是对两个图的邻接矩阵求克罗内积，以其值作为新图的邻接矩阵。
- Kronecker graph就通过对initiator matrix K 1 连续迭代做克罗内积，逐渐增长式得到最终结果（也可以用多个尺寸、元素都可以不同的initiator matrics）：
- Kronecker initiator matrices示例：
- stochastic Kronecker graphs
步骤如图所示：
- Generation of Kronecker Graphs
根据上面提到的方法，如果想要生成一个有向的stochastic Kronecker graph，需要计算 n 2 次概率，太慢。
利用Kronecker graphs的递归特性，我们还有一种更快的方法ball dropping / edge dropping：
- Fast Kronecker generator algorithm中插入一条有向边的算法：
- 对矩阵进行归一化（就让它的元素总和为1，也就是变成概率矩阵）。
- 逐层根据概率选择象限并挪动对应的坐标。在选到最后一层时就把这条边添上。
6. 本章总结
介绍了传统的图生成模型，每种模型都对图生成过程提出了不同的先验假设。
下一章将介绍直接从原始数据学习图生成过程的深度图生成模型。
