分类:An introduction to exponential random graph (p*) models for social networks

Garry Robins, Pip Pattison, Yuval Kalish, Dean Lusher, An introduction to exponential random graph (p*) models for social networks, Social Networks, 29(2), 173-191(2007).

Abstract

This article provides an introductory summary to the formulation and application of exponential random graph models for social networks. The possible ties among nodes of a network are regarded as random variables, and assumptions about dependencies among these random tie variables determine the general form of the exponential random graph model for the network. Examples of different dependence assumptions and their associated models are given, including Bernoulli, dyad-independent and Markov random graph models. The incorporation of actor attributes in social selection models is also reviewed. Newer, more complex dependence assumptions are briefly outlined. Estimation procedures are discussed, including new methods for Monte Carlo maximum likelihood estimation. We foreshadow the discussion taken up in other papers in this special edition: that the homogeneous Markov random graph models of Frank and Strauss [Frank, O., Strauss, D., 1986. Markov graphs. Journal of the American Statistical Association 81, 832–842] are not appropriate for many observed networks, whereas the new model specifications of Snijders et al. [Snijders, T.A.B., Pattison, P., Robins, G.L., Handock, M. New specifications for exponential random graph models. Sociological Methodology, in press] offer substantial improvement.

总结和评论

文章^[1]介绍了exponential random graph models，指数分布随机图模型的概念，用来解决哪些问题。文章^[2]介绍了最新进展以及参数估计的方法和工具包。文章^[3]提供了一个计算的例子。 文章^[4]把指数随机图模型发展到了多层次网络上。这里的多层次网络可以看做是多层网络的一种：例如上一个层次看作是下一个层次的集团结构的标记。文章^[5]把模型拓展到能够加上顶点的属性，而不仅仅是网络结构。^[6]给了一个用统计物理学语言做的指数随机图模型的描述，非常好。

在一般随机样本的统计性质的研究中，我们获得了统计量之后，一般要做一个统计量的显著性，或者是统计量的方差的估计，或者是把这个统计量和某个大样本的均值和方差来比较。一个实现这个显著性分析或者方差估计的方法就是Bootstrap方法。通过重抽样来产生样本，然后计算这些新样本的同一个统计量，来看实际观测到的数据的统计量的显著性。

在网络科学的研究中，我们可以从网路数据得到统计量。我们也需要给这样的统计量一个显著性描述，或者说方差，或者说大样本当背景来比较。

为了解决这个问题，人们提出来了零模型^[7][8] ，以及这个指数随机图模型。

零模型的意思就是通过Bootstrap来产生样本。而指数随机图模型就是在所有的网络（例如顶点数量相同）中，给出来每一个网络的几率，然后通过这个几率再来计算同一个统计量的大样本的均值和方差。同时，在指数随机图模型中，这个几率的生成也是基于观测到的网络的。因此，这就有了某种更加适合这个网络的保持某种属性的随机样本。

可以考虑把指数随机图模型和网络零模型相结合，来分析网络统计量的统计显著性，在某种随机意义下的大样本对比看来。

下一步工作

指数随机图模型相当于统计物理学中的正则系综（[math]\displaystyle{ \rho=\frac{1}{Z}e^{-\beta H} }[/math]），零模型相当于统计物理学中的微正则系综（[math]\displaystyle{ \rho=\frac{1}{\Sigma} }[/math]），也就是把正则系综局限在一个等能面上的情形（仅仅考虑[math]\displaystyle{ H=E }[/math]常数的状态集合）。

在指数随机图模型里面，[math]\displaystyle{ H }[/math]可以是大量的网络统计量[math]\displaystyle{ x_{i}\left(A\right) }[/math]，例如总边数[math]\displaystyle{ x_{1}=E=\sum_{ij}A_{ij} }[/math]，可以是度序列[math]\displaystyle{ x_{2}=\vec{d}, d_{i} =\sum_{j}A_{ij} }[/math]，可以是平均距离、集聚系数等等等等。也就是说，一般的分布函数形式是[math]\displaystyle{ \rho=\frac{1}{Z}e^{\sum_{i}\theta_{i}x_{i}\left(A\right)} }[/math]，其中[math]\displaystyle{ Z=\sum_{\left\{A\right\}}e^{\sum_{i}\theta_{i}x_{i}\left(A\right)} }[/math]是归一化系数。在统计物理学中，这个系数被称为配分函数。

一点点统计物理学

在统计物理学^[9]里面，[math]\displaystyle{ H }[/math]一般是系统的能量函数——这个时候，称为正则系综[math]\displaystyle{ \rho=\frac{1}{Z}e^{-\beta H} }[/math]。对于正则系综，一般来说，我们可以从给定的温度[math]\displaystyle{ \beta }[/math]出发来计算出来各个物理量在这个温度下的数值。反过来，在一个温度下物理量的取值只有一个的条件下，我们也可以通过物理量的数值把温度求出来，然后，再来计算相同条件下的其他物理量。不仅如此，我们还可以计算出来字啊同样条件下这些个物理量的方差。这样我们就有了一个对这个物理量的比较好的认识。当然，如果同一个温度对应着的某个物理量的值超过一个，则这个反解的过程就不能用了。这时候在物理学上通常是存在相变的情况——同一个温度下系统可以处于两个不同的宏观状态。

实际上，这个能量函数还可以包含其他物理量。例如当它包含粒子数[math]\displaystyle{ N }[/math]的时候，叫做巨正则系综。当它什么都不包含的时候，相当于把整个状态空间看作是微正则系综的均匀分布函数。微正则系综也可以看作是正则系综在[math]\displaystyle{ H=E }[/math]时候的子空间上的均匀分布函数。

大量的物理量的计算都可以归结到对配分函数[math]\displaystyle{ Z }[/math]的计算。但是，直接计算配分函数由于状态数太多了是非常困难的。所以，物理学家们发明了一个叫做Metropolis方法的Monte Carlo模拟方法来求解。大概来说，就是从一个状态出发，每次改变整个系统中的一个小小的状态——例如一个粒子的状态，然后看这个状态转变是否能够发生，如果能够则产生一个新的状态样本点。不断地重复这样的状态转移，就能够得到一大堆状体样本点。只要翻转的规则合适，则这样的样本点合起来就符合分布函数[math]\displaystyle{ \rho }[/math]。

统一、推广和应用指数随机图模型和网络零模型

有了这一点点统计物理学的铺垫之后，我们来统一、推广和应用指数随机图模型和网络零模型。

网络零模型解决的问题是：给定一个网络的一个实际样本，以及从这个给定的实际样本里面算出来的统计量，如何能够给这个统计量一个比较的区间，这样可以知道这个计算出来的网络性质到底是不是非常的特殊。

在一般的统计学中，例如对身高的统计，我们实际上是通过取大量的样本来给出来这个用于比较的区间的。例如，对于一个样本的身高，[math]\displaystyle{ h_{i} }[/math]我们找出来和这一个样本条件类似的集合，例如同样民族同样国家的一群人的身高，然后计算这个群体的平均身高和方差，给出来一个区间。接着把这个个体身高，放到这个区间的背景下来考虑。如果这个身高远远大于这个区间的高值，则我们说这个身高是出众的，甚至可以估计出来一个出众的程度。

但是，在网络科学中，我们不可能获得这样的一个大样本。一般来说，每个网络都是独特的。例如，internet只有一个，人际关系网络也可能相互之间不能相比较。那怎么办？能不能在只有一个样本，注意这个样本本身通常包涵大量的元素，的条件下，来给出来一个这个样本的取值的参考区间？在零模型中，大家采用Bootstrap方法来从单个样本来获取多个样本。例如，让每一条边都随机，仅仅保持总顶点数不变。例如，让每一条边都随机，但是保持总顶点数和总边数不变。例如，保持总顶点数和总边数，以及每个顶点的度不变。这样，我们就可以在每个不同条件下得到一个样本的集合。有了这个集合，我们就可以计算这个集合的样本的几何量的均值和方差，来提供一个衡量实际网络性质是否突出的区间。

指数随机图模型解决的问题是：给定一个网络，我们如何通过把这个网络和其他网络相比来了解这个网络是不是有某些结构上的偏好，例如更喜欢形成互指的连接（[math]\displaystyle{ A_{ij}=A_{ji} }[/math]）、三角形连接（[math]\displaystyle{ A_{ij}A_{jk}A_{ki}=1 }[/math]）、星型连接（[math]\displaystyle{ A_{ij}A_{ik}A_{il}=1 }[/math]）等等。对于社会网络分析这样的典型结构是非常有意义的信息。同时，指数随机图模型也可以用来解决连接和属性的关联，例如是否年轻的学者更喜欢和年老的学者合作，还是在年轻人之间合作。

指数随机图模型解决这个问题的方法是，把每一条连边看做是随机事件，然后，把典型结构看作统计量，连边这个随机事件看作是统计量的函数。当然，通过这些连边随机事件构成的整个网络也就成了随机事件，其整体概率也依赖于这些典型结构对应的统计量。接着按照最大熵原理，人们猜测这样的随机事件和统计量的关系，符合指数分布，也就是[math]\displaystyle{ \rho=\frac{1}{Z}e^{\sum_{l}\theta_{l}x_{l}\left(A\right)} }[/math]。具体的[math]\displaystyle{ x_{l}\left(A\right) }[/math]可以是，[math]\displaystyle{ x_{1}\left(A\right)=\sum_{ij}A_{ij} }[/math], [math]\displaystyle{ x_{2}\left(A\right)=\sum_{ij}A_{ij}A_{ji} }[/math]等等。然后，通过把实际网络和给定参数[math]\displaystyle{ \theta_{l} }[/math]的情况下生成的网络来做对比，就可以得到参数的取值。所得到的参数取值的大小就反映了网络是否存在对相应的结构的偏好。例如，绝对值很大的正（负）的[math]\displaystyle{ \theta }[/math]表示存在比较大的偏好（厌恶）。

现在，我们注意到，实际上，指数随机图模型也可以用来给出来统计量的区间：在得到相应的分布函数的参数值[math]\displaystyle{ \theta }[/math]之后，求出来这个参数值情况下的几何量的均值和方差，甚至分布函数，就能够得到一个这个几何量的区间。这个区间就可以用来当作实际观测到的几何量的背景。也就是说，实际上指数随机图模型可以用来解决网络零模型所要解决的问题。

实际上，两者之间的联系还不仅仅是这样。实际上网络零模型是指数随机图模型之间的关系，就像统计物理学中的正则系综和微正则系综的关系一样。零模型可以看作是指数随机图模型在给定分布函数之后的等能面上的情况。也就是说，可以把零模型的样本集合当作是满足[math]\displaystyle{ \sum_{l}\theta_{l}x_{l}\left(A\right)=C }[/math]为常数的样本集合。当然，实际上，在目前的零模型中，往往取的是满足一系列[math]\displaystyle{ x_{l}\left(A\right)=x^{*}_{l} }[/math]等于观测到的实际网络上的取值的集合，也就是比等能面的一个子集。或者，这样来看，零模型是在所选择的集合的范围内，给所有的样本相同的概率的一种分布函数，而不去管这个集合里面的样本哪一些可能和实际观测到的网络更像一些。于是，指数随机图理论在这一点上，自然就可以对零模型做一个改进：考虑所有的样本，而不需要认为来选择合适的样本集合，接着给每一个样本一个概率，满足对于和实际网络更像的网络给出来更大的概率值。至于为什么指数分布通常能够给和实际观测样本相似的样本更大的概率这一点，在统计物理学里面，被称为最可几构形——指的是分布函数的极值和均值比较接近的意思。通过实际网络的观测量[math]\displaystyle{ \vec{x^{*}_{l}} }[/math]来反推参数[math]\displaystyle{ \theta^{*} }[/math]，然后再计算这个参数情况下的观测量的取值区间，这样的过程，一般来说，确实能够保证和实际网络更像的网络给出来更大的概率值这一点。

有了这样的统一的视角之后，就有了一个自然的推广，是不是其实还可以考虑巨正则系综，也就是让网络的顶点数也成为分布函数的随即变量，也就是[math]\displaystyle{ \rho=\frac{1}{Z}e^{\sum_{l}\theta_{l}x_{l}\left(A\right)} }[/math]，其中[math]\displaystyle{ x_{0}\left(A\right)=dim\left(A\right) }[/math]，然后再加上之前的正则系综的能量函数。

计算实现

1. 看一看没有加上网络顶点数的能量函数给出来的观测量取值区间和零模型给出来的取值区间有什么区别和联系。
2. 看一看加上网络顶点数之后，又会如何。
3. 提供一个分析工具包，并且保证在原始的社会网络分析的任务上，这个新的工具包，仍然能够给出来类似的信息，也就是网络的形成过程中对某些局部结构是否确实有偏好，对网络顶点的属性是否确实有偏好。
4. 这个工作和科学家选择研究主题的关联，在三层网络的框架下。

参考文献