GNN基础

图的属性

1. 节点的度分布 $P(k)$
   随机选择的节点度为 $k$ 的概率
   归一化：$P(k)=\frac{N_k}{N}$，$N_k$ 是度为 $k$ 的节点的数量，$N$ 是总的节点数

1. 路径长度 $h$**距离（无向图）：一对节点之间的距离定义为沿着连接这些节点的最短路径的边数 直径：图中任意节点对之间的最大距离 平均路径长度（连接图或强连接有向图）**：$\bar{h}=\frac{\sum_{i,j\neq i}h_{ij}}{2E_{max}}$，$h_{ij}$ 是节点 $v_i$ 到节点 $v_j$ 的距离，$E_{max}=\frac{n(n-1)}{2}$ 是最大边数（全连接图的边数）
2. 聚类系数（无向图）：领居之间的联系如何？$C_i=\frac{2e_i}{K_i(K_i-1)}$，$e_i$ 是节点 $v_i$ 邻居之间的边数，$K_i$ 是节点 $v_i$ 的度数，$K_i(K_i-1)$ 是节点 $v_i$ 邻居之间的最大边数
   平均聚类系数：$C=\frac{\sum_i^NC_i}{N}$

$G_{np}$ 的属性

包含 $n$ 个节点的无向图中，每个边以概率 $p$ 出现，$n$ 和 $p$ 不能唯一确定图！该图是随机过程的结果。给定相同的n和p，我们可以有许多不同的实现。

1. $G_{np}$的度分布（一个二项式）：$P(k)=C_{n-1}^kp^k(1-p)^{n-1-k}$
   二项式分布的均值和方差：$\bar{k}=p(n-1),\sigma^2=p(1-p)(n-1)$
   根据大数定律，随着网络规模的增加，分布变得越来越狭窄-我们越来越有信心节点的度数在k附近：$\frac{\sigma}{\bar{k}}=[\frac{1-p}{p}\frac{1}{n-1}]^{\frac{1}{2}}\approx\frac{1}{(n-1)^{\frac{1}{2}}}$
2. 聚类系数：$E(e_i)=p\frac{k_i(k_i-1)}{2},E(C_i)=\frac{pk_i(k_i-1)}{k_i(k_i-1)}=p=\frac{\bar{k}}{n-1}\approx \frac{\bar{k}}{n}$
3. 路径长度：对于图 $G(V,E)$，对于任意离开节点子集 $S$ 的边 $E_{leave}\geq\alpha\cdot\min(|S|,|V/S|)$，即 $\alpha=\min_{S\subseteq V}\frac{E_{leave}}{\min(|S|,|V/S|)}$
   在n个具有扩展α的节点上的图中，对于所有成对的节点，路径的长度为：$O((\log n)/α)$
   对于 $G_{np}$：$\log n>np>c, diam(G_{np})=O(\log n/\log (np))$
   随机图具有良好的扩展性，因此BFS访问所有节点都需要对数步