图的基础知识

课程知识复习使用。

1.基本概念

• 图：一系列的点和对应的连接边。
• 度数：顶点v的连接边数目。有向图中, 节点度数分为入度和出度。一个节点度数是其入度和出度的和。
• 连通图：对于一个无向图，任意两个顶点之间都存在一条路径，则称之为连通图，否则为非连通图。
• 最大连通区域：一个非连图由多个部分组成，其中规模最大的被称为最大连通区域。
• 强连通图：对于一个有向图，对于任意一对节点A和B，存在从A到B的有向路径，同时也存在从B到A的一条有向路径，则称为强连通图。
• 弱连通图：对于一个有向图，忽略边的方向，这个图在无向图的概念中是连通的，则这个有向图被称为弱连通图。
• 完全图（团）：任意两个节点间都连接有边。
• 二部图：节点分为两个不相交的集合𝑈和𝑉，每条边都分别连接集合𝑈和𝑉中的一个点。
• 多重图：含有平行边或者自环边的图，即图中某两个顶点之间的边数不止一条，又允许顶点通过一条边与本身关联，则该图被称为多重图。
• 自环图：无平行边而只存在自环边的图又被称为自环图。
• 图的表示：邻接矩阵，邻接表，压缩稀疏表达$（CSR）$。
  

2.图的度量

对一张图进行度量的四种方式：度数分布，路径长度，聚集系数，连通分量。

• 度数分布：图中度数的概率分布。对于有向图，需要考虑入度分布和出度分布。真实图的度数分布通常近似满足幂律分布，即度数大的节点非常少，度数小的节点占了绝大多数。
• 路径长度：路径中所包含的边的数目。节点间的距离为它们的最短路径长度。

引申概念：小世界图：任意两个节点之间均存在较短路径，且节点间的最短路径⻓度与总节点数目不是线性关系，而是对数关系。

• 聚集系数：衡量节点$v_i$ 的$k_i$ 个邻居间的连接紧密程度。计算如下：

$$C_{local}(v_{i}) = \frac{2E_i}{k_i(k_i-1)}$$

其中$E_i$ 是$v_i$ 的邻居之间两两连边的数目。度数较大的节点，其聚集系数一般是较小的，而度数较小的节点，其聚集系数一般是较大的。

• 连通分量：无向图的极大连通子图。

3.静态图生成模型

给定待生成图的节点数 𝑁 和边数 𝑀，静态图生成模型一次性生成整张图。

3.1Erdos-Renyi 模型,E-R 模型

• 定义：𝐺(𝑁, 𝑝)，𝑁为图中节点总数，$p$为任意两个节点之间连边的概率。
• 生成算法：首先生成$N$ 个节点，对每个节点的除它以外的$N-1$ 个节点，都以概率$p$ 连边。
  
  

3.2Watts–Strogatz 小世界模型

• $k$-正则图：每个节点都有$k$个邻居的图。
• 生成算法：首先生成$k$ 正则图，接着对每一条边以概率$p$ 将这条边的其中一个端点移到平均随机选取的节点上。
• 当$p=0$时，生成图为$k$ 正则图；当$p=1$时，生成图为$E-R$ 图，此时边是随机生成的。

3.3Kronecker 模型

递归的图生成模型，其基本思想是自相似性(self-similarity)，即通过在图的部分结构中模仿其整体结构的特征递归地生成图。递归地将图的整体结构代入到子结构中，在某种程度上模仿了真实社交网络图中社区的生⻓规律。

4.动态图生成模型

给定待生成图的节点数$n$或边数$m$，模型建模节点和边逐步加入的过程。

4.1Barabási–Albert (BA)模型

• 基本思想：假设图是以节点为中心不断增⻓的，通过不断增加节点来生成图。并且存在优先连接的现象，即一个节点当前 具有的度数越大，新增加的节点就越有可能与它连边。
• 生成算法：首先生成有$m_0$ 个节点的随机图，接下来每一步生成一个新的节点，由它延伸出$m$ 条边，与之前已有的节点相连。每次连接都按照已有节点当前的度数来分配连边的概率。

4.2以边为中心的优先连接模型

通过加入新边来实现图规模的增⻓。注意的是，每次边插入可能引入0 个、1 个或 2 个新节点。

5.参考资料

中国科学院大学邹磊老师，图数据管理与应用课程课件