感觉写的并不透彻,不过就这样吧。

网络模型

随机图模型

随机图模型,致力于在图构成的集合上构建概率测度。既然是概率,就可以用三元组 $(\mathcal{G},\mathcal{F},P)$ 表示。其中 $\mathcal{G}$ 是一些图的集合,$\mathcal{F}$ 是其上的 $\sigma$-代数,$P$ 是概率测度。通常 $\mathcal{G}$ 是有限集,此时 $\mathcal{F}=2^{\mathcal{G}}$.

经典模型

Erdos & Renyi 模型:用 $G(n,m)$ 表示所有 $n$ 个顶点,$m$ 条边的图的集合,共有 $\dbinom{\frac{n(n-1)}{2}}{m}$ 个。让每一个图等概率出现。

Gilbert 模型:记作 $G(n,p)$,它考虑所有 $n$ 个顶点的图,每个边的出现概率为 $p$,并且独立于其他边。共有 $2^{\frac{n(n-1)}{2}}$ 种不同的图。

等价性:在 Gilbert 模型中令 $np=m$,然后令 $n\to\infty$,根据大数定律,几乎所有的图边数都是 $m$,此时 E-R 模型和 Gilbert 模型行为是类似的。

度分布(degree distribution)

显然单个节点的度服从二项分布 $B(n-1,p)$.

通常我们关心边数固定时的渐近情况,即令 $p=c/n$, $c$ 是常数。当 $n\to\infty$ 时,二项分布趋近于泊松分布 $Poisson((n-1)p)\approx Poisson(c)$ [2].

现实中的图往往是非均匀网络,它的度分布更接近幂律分布,所以经典的随机图模型并不能很好地模拟现实情况。

一般模型

一般模型允许我们在图上施加任意限制,例如考虑固定顶点数 $n$ 和度序列 $(k_1,\cdots,k_n)$,然后等概率选取。

这使得我们可以针对观察到的图进行模拟:使用相同的度序列随机生成一些图,然后看一下我们观察到的特征是否显著。

此外还可以加别的限制条件。根据指定的条件随机生成图的算法是一个复杂的话题,我们这里暂且不讨论。

把图放进概率空间,手段就多了。我们可以给 $P$ 带上参数,变成分布族 $\mathcal{P}={P_\theta:\theta\in\Theta}$. 我们这就来介绍享誉全球的指数随机图模型(exponential random graph models, ERGM)

指数随机图模型

图 $g\in G$ 的概率定义为 $$ P_\theta(g)=\frac{1}{\kappa(\theta)}e^{\theta^TT(g)}. $$ 其中 $\theta$ 是 $p$ 维参数。$T(g)$ 是 $p$ 维统计量,通常是我们关注的一些图的性质,比如边数、三角形数等。$\kappa$ 是归一化因子,即 $$ \kappa=\sum_{g\in G}e^{\theta^T T(g)}. $$ 显然它是个指数族。注意这里我们是根据感兴趣的特征量来确定 $T$,然后给他配上相同维度的 $\theta$.

估计

通常我们使用极大似然估计,但对一般的模型来说并不容易。通常 $G$ 的规模异常巨大,$\kappa$ 很难求出解析形式,所以要使用 MCMC 进行模拟。

统计量

在 ERGM 中,$T$ 是钦定的。除了常见的边数、三角形数等,我们还有一些高大上的统计量。

Geometrically weighted edgewise shared partner (GWESP) 通常可以用来替代三角形数,它的定义是

$$ \mathrm{GWESP}\gamma(g)=e^\gamma\sum{k=0}^{n-2}\left(1-(1-e^{-\gamma})^k\right)\mathrm{SP}_k(g), $$

其中 $\gamma\ge 0$ 是钦定的,$\mathrm{SP}_k(g)=\sharp{(u,v)\in E:u,v\text{ 恰好有 }k\text{ 个公共邻居}}$.

Geometrically weighted degree (GWD) 则可以用来替代 $k$-star 的个数。它是

$$ \mathrm{GWD}\gamma(g)=\sum{k=0}^{n-1}e^{-k\gamma}D_k(g), $$

其中 $D_k(g)$ 是度为 $k$ 的节点个数。

Block Model

这时 ERGM 的一种。我们假设图分成了 $I$ 组,一条边的连接概率只和两个端点所在的组有关。我们有参数 $b=(b_{11},\cdots,b_{II})$,若 $u$ 在第 $i$ 组,$v$ 在第 $j$ 组,则 $P_b((u,v)\in E)=b_{ij}$.

对给定的图 $g$,我们可以计算他的概率 $$ P_b(g)=\prod_{i\le j}b_{ij}^{m_{ij}}\left(1-b_{ij}\right)^{N_{ij}-m_{ij}}, $$ 其中 $n_i$ 为第 $i$ 组的点数,$N_{ij}$ 为可能出现的边数,$i=j$ 时 $N_{ii}=\dbinom{n_i}{2}$,$i\ne j$ 时 $N_{ij}=n_i n_j$. $m_{ij}$ 是第 $i$ 组和第 $j$ 组之间的边数。

请自行验证它是指数族。

这个极大似然估计我们能算出来: $$ \hat b_{ij}=\frac{m_{ij}}{N_{ij}}. $$

Logistic model

很多时候我们不仅要考虑图的连接方式,还要考虑节点的属性,例如年龄、性别等。

我们设每个节点 $u$ 有一个属性向量 $x_u$. 我们用函数 $h(x_u,x_v)$ 表示我们感兴趣的东西。例如 $h(x,y)=(I(x_1=y_1),x_2+y_2)$ 意味着我们想看看“邻居的属性 1 是否一样,属性 2 的大小是否会影响连接概率”。考虑模型 $$ P((u,v)\in E)=p_{uv}=\frac{e^{\beta^T h(x_u,x_v)}}{1+e^{\beta^T h(x_u,x_v)}}. $$

可以算出图 $g$ 出现的概率 $$ P_\beta(g)=\frac{\exp\left(\sum_{(u,v)\in E}\beta^Th(x_u,x_v)\right)}{\prod_{u\le v}\left(1+\exp\left({\beta^Th(x_u,x_v)}\right)\right)}. $$ 哎,他还是指数族,没想到吧!

我们可以用 logistic 回归来估计参数。如果 $(u,v)\in E$,$p_{uv}$ 的观测值就是 1,否则就是 0.

带有协变量的 ERGM

推广一下 logistic model,我们把协变量和传统的 $T(g)$ 结合起来: $$ P_{\theta,\beta}(g)=\exp\left(\theta^T T(g)+\sum_{(u,v)\in E}\beta^Th(x_u,x_v)\right)\kappa_x^{-1}(\theta,\beta). $$ 其中 $\theta$ 和 $\beta$ 都是参数,他俩拼起来是完整参数。注意 $\theta=0$ 就是 logistic model 了。

odds

事件 $A$ 的 odds 定义为 $P(A)/(1-P(A))$. 对于图来说,假设所有其他边都固定,只有 $(w,y)$ 不确定,则可以设 $g_+$ 表示 $(w,y)\in E$ 的图,$g_-$ 表示 $(w,y)\notin E$ 的图,于是 $(w,y)\in E$ 的 odds 是 $$ O_1=\frac{\exp(\theta T(g_+)+\beta^T h(x_w,x_y))}{\exp(\theta T(g_-))}. $$

链接预测

给出一张图,通过已知的边来预测可能出现的潜在的其他边,就是链接预测。通常来说,链接预测给每个顶点对 $(u,v)$ 一个分数 $s_{uv}$,该分值越大,越有可能连接。

ERGM

当我们拟合了 ERGM 模型之后,可以给出边的出现概率: $$ p_{uv}=\frac{P(g_+)}{P(g_+)+P(g_-)}. $$

无 model-fitting

此外,还有许多不需要 model-fitting 的方法。我们寄 $S(u)$ 为顶点 $u$ 的邻居集合,$k_u=\sharp S(u)$。

  • Jaccard measure $$ s_{uv}=\frac{\sharp [S(u)\cap S(v)]}{\sharp [S(u)\cup S(v)]}, $$

  • Adam-Adar measure $$ s_{uv}=\sum_{w\in S(u)\cap S(v)}\frac{1}{\log k_w}, $$

  • Preferential attachment $$ s_{uv}=k_u k_v. $$

还有基于邻接矩阵的。记邻接矩阵为 $A$,我们得到 $B$ 之后,$B_{uv}$ 就是分数。

  • matrix exponential $$ B=\exp(\alpha A)=\sum_{i=0}^\infty\frac{\alpha^i}{i!}A^i, $$

  • von Neumann kernel $$ B=(I-\alpha A)^{-1}=\sum_{i=0}^\infty \alpha^i A^i. $$

其中 $\alpha$ 为参数。

pseudo-likelihood

我们可以考虑 pseudo-likelihood,它解决了传统 ERGM 无法求解的问题。Pseudo-likelihood 就是上面的 $p_{uv}$ 乘起来。具体地,在 ERGM 中可以计算出 $p_{uv}=\dfrac{P(g_+)}{P(g_+)+P(g_-)}$. 把所有边的 $p_{uv}$ 乘起来就行了。

参考文献

  1. Statistical Analysis of Network Data with R, 2nd edition. Eric D. Kolacyk and G´abor Cs´ardi, Springer (2018) [main].
  2. https://zh.wikipedia.org/wiki/%E4%BA%8C%E9%A0%85%E5%BC%8F%E5%88%86%E5%B8%83#%E6%B3%8A%E6%9D%BE%E8%BF%91%E4%BC%BC
  3. https://www.youtube.com/watch?v=Ma2Bj33Qemc