分类:指数随机图

来自Big Physics


问题

给定一个网络的记录[math]\displaystyle{ D }[/math]——这个记录可能是不准确的有观测误差的（记实际网络为[math]\displaystyle{ A }[/math]，观测记为[math]\displaystyle{ A }[/math]，于是，[math]\displaystyle{ P\left(D\right)=P\left(D\left|\right. A,O\right) }[/math]），还有可能是所有的可能得到的样本——一个系综——之中的一个（也就是背后有一个分布函数[math]\displaystyle{ \mathcal{P}\left(D\right) }[/math]），还有可能是两者的结合——它是所有可能的样本中的一个并且通过有误差的测量得到的，也就是背后有一个分布函数[math]\displaystyle{ \mathcal{P}\left(A\right) }[/math]然后这个[math]\displaystyle{ A }[/math]经过观测成了[math]\displaystyle{ D }[/math]——记做[math]\displaystyle{ \mathcal{P}\left(D\right)=\sum_{A}P\left(D\left|\right. A,O\right)\mathcal{P}\left(A\right) }[/math]，我们想知道两件事情：

  1. 从单个的数据记录中，我们是否可以得到几何量的分布函数，也就是[math]\displaystyle{ P\left(x\left(A\right)\left|\right.D\right) }[/math]？
  2. 背后的分布函数（[math]\displaystyle{ \mathcal{P}\left(D\right) }[/math]， [math]\displaystyle{ \mathcal{P}\left(A\right) }[/math]）长什么样？有没有一些结构上的偏好，例如双向边、三角形的出现具有一定优势等。

当然，原则上，只要解决第二个问题，第一个问题只要从系综分布函数开始求平均就可以解决了。

统计物理学背景知识

在统计物理学[1]里面，[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]时候的子空间上的均匀分布函数。

有了分布函数，还可以这样来讨论问题：两个数据来源于同一个分布函数的可能性是多大。例如，我们可以从第一套样本估计出来参数值，然后用这个参数值再得到第二套样本出现的概率，或者把两套样本反过来用。当然，这个时候得到的两个概率是不是一样，还得讨论。但是，这样确实就有了比较两套样本的一种方式。顺便，看看统计学的书，如何来得到两套样本是否来源于同一个分布函数（KS检验的背后理据）？

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


指数随机图模型相当于统计物理学中的正则系综（[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]是归一化系数。在统计物理学中，这个系数被称为配分函数。

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

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

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

在一般的统计学中，例如对身高的统计，我们实际上是通过取大量的样本来给出来这个用于比较的区间的。例如，对于一个样本的身高，[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]，然后再加上之前的正则系综的能量函数。

这些研究都是在假设观测到的网络就是实际网络的基础上做的，或者至少，也是符合某个分布的实际网络样本集合当中的一个。Newman问了这样一个问题[2][3]：如果有观测误差，则，这个观测误差是不是也需要放到网络统计量的计算里面去呢？也就是说，假设，我们得到的矩阵[math]\displaystyle{ A }[/math]实际上应该是从观测数据[math]\displaystyle{ D }[/math]当中推断得来的。也就是观测数据应该看做是[math]\displaystyle{ D }[/math]，然后从这个观测数据估计出来真实的[math]\displaystyle{ A }[/math]，通过[math]\displaystyle{ P\left(A\left|\right.D) }[/math]。怎么才能得到这个概率呢？假设我们的测量数据是通过某个有误差的测量过程[math]\displaystyle{ O }[/math]产生的，则，我们就可以通过[math]\displaystyle{ P\left(D\left|\right.A,O) }[/math]把[math]\displaystyle{ P\left(A\left|\right.D) }[/math]计算出来。具体计算见[2][3]。这个计算主要依靠两样东西一个是对观测过程[math]\displaystyle{ O }[/math]的模型化假设，一个是对网络构建过程中每一条边的生成机制的假设。

我们发现，如果这些方法都能够统一起来，则实际上，我们对测量误差、分布函数误差、和一般模型的对比、网络演化过程中的特质，都有了一个描述，也就是解决了一开始提出的两个问题，[math]\displaystyle{ P\left(x\left(A\right)\left|\right.D\right) }[/math]以及分布函数[math]\displaystyle{ P\left(A\right) }[/math]的特征。

浅层结合

首先，把零模型（微正则分布）和指数随机图（正则分布）统一，然后推广到巨正则分布，也就是顶点数也可变的分布函数。 其次，把观测数据的准确度问题，也就是Newman的分析，放在前面，根据观测记录[math]\displaystyle{ D }[/math]得到实际网络[math]\displaystyle{ P\left(A\left|\right.D) }[/math]，接着把这样的实际网络的每一个样本[math]\displaystyle{ A }[/math]看做是上面的系综理论计算的起点，来得到系统分布函数[math]\displaystyle{ \mathcal{P}\left(A\left|\right.D\right) }[/math]最终的几何量的分布[math]\displaystyle{ \mathcal{P}\left(x\left(A\right)\left|\right.D\right) }[/math]。

深层结合

实际上，在Newman的方法中，网络模型的部分也可以考虑用随机图模型。

更深层结合

按照上面的框架，一起来解决测量误差和系综样本问题，也就是把测量得到的样本看作是从系综抽样然后做了有误差的测量的结果，也就是[math]\displaystyle{ \mathcal{P}\left(D\right)=\sum_{A}P\left(D\left|\right. A,O\right)\mathcal{P}\left(A\right) }[/math]，接着，我们问，从这里能不能得到[math]\displaystyle{ \mathcal{P}\left(A\right) }[/math]？

关于深层结合和更深层结合，参考参数估计问题中测量和系综的结合。

下一步工作

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

当前研究

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

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

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

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

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

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


参考文献

  1. ↑ 吴金闪，《系统科学导引》，科学出版社，http://www.systemsci.org/jinshanw/books/
  2. ↑ 2.0 2.1 M. E. J. Newman, Network structure from rich but noisy data, Nature Physics 14, 542–545 (2018). https://www.nature.com/articles/s41567-018-0076-1
  3. ↑ 3.0 3.1 M. E. J. Newman, Network reconstruction and error estimation with noisy network data, https://arxiv.org/abs/1803.02427
  4. ↑ 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). https://doi.org/10.1016/j.socnet.2006.08.002
  5. ↑ Garry Robins, Tom Snijders, Peng Wang, Mark Handcock, Philippa Pattison Recent developments in exponential random graph (p*) models for social networks, Social Networks, Volume 29, 192-215(2007). https://doi.org/10.1016/j.socnet.2006.08.003
  6. ↑ Steven M.Goodreau, Advances in exponential random graph (p*) models applied to a large social network, Social Networks, 29, 231-248(2007). https://doi.org/10.1016/j.socnet.2006.08.001
  7. ↑ Peng Wang, Garry Robins, Philippa Pattison, Emmanuel Lazega, Exponential random graph models for multilevel networks, Social Networks, 35, 96-115(2013). https://doi.org/10.1016/j.socnet.2013.01.004
  8. ↑ M.A.J. Van Duijn, T.A.B. Snijders, B.J.H. Zijlstra， p2: a random effects model with covariates for directed graphs， Statistica Neerlandica, 58 (2004), pp. 234-254. https://onlinelibrary.wiley.com/doi/abs/10.1046/j.0039-0402.2003.00258.x
  9. ↑ Agata Fronczak, Exponential random graph models, Chapter in Encyclopedia of Social Network Analysis and Mining, R. Alhajj, J. Rokne (Eds.), Springer-Verlag, 2014, https://arxiv.org/abs/1210.7828
  10. ↑ Sergei Maslov, Kim Sneppen, Specificity and Stability in Topology of Protein Networks, Science, 296, 910-913(2002). https://doi.org/10.1126/science.1065103
  11. ↑ 尚可可, 许小可, 基于置乱算法的复杂网络零模型构造及其应用, 电子科技大学学报, 43, 7-20(2014) https://doi.org/10.3969/j.issn.1001-0548.2014.01.002

子分类

本分类只有以下子分类。

A

取自“https://www.bigphysics.org/index.php?title=分类:指数随机图&oldid=1549”