时间： 分类：   字数： 1958 字 阅读： 4分钟 阅读次数：

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

网络模型

随机图模型

随机图模型，致力于在图构成的集合上构建概率测度。既然是概率，就可以用三元组 $(\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
0%