复杂网络的双曲几何模型

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索

复杂网络的双曲模型是一种解释复杂网络拓普特征和生长机制的新型模型。它假设复杂网络是一种镶嵌到双曲空间中的一种随机几何图，从而利用双曲空间的內禀特性揭示复杂网络的特征。

背景

复杂网络模型可以研究、模拟没有几何信息的非局域性关联结构。但是，这种非局域性结构通常无法我们一种美妙的秩序性，而且更关键的是几何中发展出来的一大套工具和方法论没办法应用到复杂网络中。这将会是一种很大的损失。于是，人们希望通过某种手段能够把复杂网络几何化，同时又不损失复杂网络中例如无标度、小世界等特性。

另一方面，双曲几何是非欧几何中的一个非常重要的分支，而且它也有很多实际工程技术中的应用。例如，人们发现，如果将互联网上的路由器节点都镶嵌在一个双曲空间中，那么网络总体的导航效率就会显著提高。

于是Dmitri Krioukov和Fragkiskos Papadopoulos等人于2010年提出了一种双曲空间中的随机几何图模型[1]，从而非常容易地解释了网络的异质性（无标度分布现象）和高聚集性。更有趣的是，他们还发现了双曲随机几何图模型与他们之前提出的一种“隐变量”模型[2]存在着一种对偶关系，这种对偶与物理学中的体－边界 Bulk boundary对偶存在着一直的。进一步，2012年，他们又提出了一个双曲空间中的网络生长模型，该模型与物理学中Anti de Sitter空间非常类似，并给出了各个坐标明确的含义[3]。该模型能够更好地模拟网络的生长，而且能够涵盖复杂网络中经典的BA网络模型的动态过程。

经典随机几何图

为了更容易理解双曲空间中的网络模型，我们先来看看经典欧氏空间的随机几何图模型。

这个模型非常简单。考虑一块[math]\displaystyle{ L^d }[/math]大小的矩形区域，其中d为空间维度。然后，我们往这片区域随机撒入N个点。接下来，我们以每个点P为中心，以r为半径（注意r<<L）画圆，落入该圆内的所有点都会与P点进行连边。用这种方式构造出的网络就被称为随机几何图模型。

一个二维平面中的随机几何图，其中L=1, r=0.1

这个模型有很多有趣的性质。例如模型的连通性具备相变特征：如果给定节点的密度（[math]\displaystyle{ N/L^2 }[/math]），那么不同的r就会导致相互连通的节点形成团块，有大有小。存在着一个r的阈值[math]\displaystyle{ r_c }[/math]，r超过它整个网络就会联通成一个庞大的集团。否则，网络仅仅是一系列孤立的小集团。

其次，随机几何图也是一种随机图，因此具有泊松度分布。

另外，随机几何图具有高聚集性，即相互临近的节点会连接形成大量的局域三角形。我们可以解析地给出d维欧氏空间中的随机几何图的聚集系数为：

[math]\displaystyle{ C_d=\frac{3}{\sqrt{\pi}}\frac{\Gamma\left(\frac{d+2}{2}\right)}{\Gamma\left(\frac{d+1}{2}\right)}\int_0^{\pi/3}\sin^d\theta d\theta }[/math]

相对于随机网络和无标度网络，随机几何图的度系数要高很多。

双曲空间中的随机几何图

双曲空间的扩展彭加莱圆盘模型

在数学中，所谓的双曲空间，就是指那种曲率为负数，而且恒定不变的空间。然而，由于要表示一个双曲空间，需要用更高维度的欧氏空间，很不方便，所以人们发明了各式各样的双曲空间模型。

其中，一种最常用的双曲空间模型就是彭加莱圆盘。参考双曲空间模型。

而在网络的双曲空间模型中，作者采用了一种扩展的彭加莱圆盘模型。与彭加莱圆盘最大的不同就在于每个点到原点的距离为双曲距离而不是欧氏距离。如果设彭加莱圆盘中某点的极坐标是[math]\displaystyle{ (r,\theta) }[/math]，而新扩展彭加莱圆盘模型下该点的极坐标为[math]\displaystyle{ (r',\theta') }[/math]，则根据双曲空间的特性，存在关系：

[math]\displaystyle{ r'=2\tanh^{-1}{r},\theta'=\theta }[/math]

则这个新的空间[math]\displaystyle{ (r',\theta) }[/math]即是扩展的彭加莱圆盘。

我们知道由于[math]\displaystyle{ \tanh(x) }[/math]函数是一个S型函数，在x趋近于无穷大的时候，该函数值趋于1。所以，彭加莱圆盘具有1单位大小的半径。而在扩展的彭加莱圆盘中，该空间的圆半径为无穷大。因而，在彭加莱圆盘表示中，靠近边缘的点被极度地压缩了。而在扩展的模型中，就不会存在这种被极度压缩的现象。

度规

我们知道，在彭加莱圆盘模型中，一小段微元可以写成极坐标形式的度规为：

[math]\displaystyle{ ds^2=4\frac{dr^2+r^2d\theta^2}{(1-r^2)^2}=4(dr,d\theta)\begin{pmatrix}\frac{1}{(1-r^2)^2} & 0 \\ 0 & \frac{r^2}{(1-r^2)^2}\end{pmatrix} \begin{pmatrix} dr\\ d\theta\end{pmatrix} }[/math]

我们将坐标变换[math]\displaystyle{ r=\tanh(r'/2),\theta=\theta' }[/math]代入上式，并注意到：[math]\displaystyle{ dr^2=\frac{1}{4\cosh^2(r'/2)} }[/math]，则得到：

[math]\displaystyle{ ds^2=4\frac{\frac{1}{4\cosh(r'/2)} dr'^2+\tanh^2(r'/2)d\theta'^2}{(1-\tanh^2(r'/2))^2}=dr'^2+\sinh^2(r')d\theta'^2 }[/math]


如果曲面的曲率为[math]\displaystyle{ K=-\zeta^2 }[/math]，则彭加莱圆盘的度规为：

[math]\displaystyle{ ds^2=4 \zeta \frac{dr^2+r^2d\theta^2}{(1-r^2)^2} }[/math]


而扩展的彭加莱圆盘度规为：

[math]\displaystyle{ ds^2=\zeta (dr'^2+\sinh^2(r')d\theta'^2) }[/math]

任意两点距离公式

设双曲空间曲率为[math]\displaystyle{ K=-\zeta^2 }[/math]，任意两点P、Q，它们在扩展彭加莱圆盘中的极坐标为：[math]\displaystyle{ (r,\theta) }[/math]， [math]\displaystyle{ (r',\theta') }[/math]，设它们之间的双曲距离为x，则：

[math]\displaystyle{ \cosh{\zeta x}=\cosh(\zeta r)\cosh(\zeta r')-\sinh(\zeta r)\sinh(\zeta r')\cos(\Delta \theta) }[/math]

其中，[math]\displaystyle{ \Delta \theta=\pi-|\pi-|\theta-\theta'|| }[/math]


近似表达式

当r和r'都很大，而且x也较大的时候，我们有近似公式：

[math]\displaystyle{ x\approx r+r'+\frac{2}{\zeta}\log{\sin(\Delta\theta/2)} }[/math]

当[math]\displaystyle{ \Delta\theta/2) }[/math]很小的时候，

[math]\displaystyle{ x\approx r+r'+\frac{2}{\zeta}\log{\Delta\theta/2} }[/math]


圆

根据彭加莱圆模型与扩展模型中极坐标之间的关系：

[math]\displaystyle{ r=\tanh(r'/2) }[/math]

又知道彭加莱圆模型中以某点为中心的圆方程，代入上述坐标变换公式，就能得到扩展模型中的圆。不难从图形上看出，这个圆被严重扭曲、拉伸了。

Hyperbolicextendedpoincaredisk.png


这些圆中心的坐标分别为：(0,0) 蓝色, (5,10) 紫色,(-3,3) 黄色,(1,10) 绿色。我们看到，越远离坐标中心，圆的扭曲也越厉害。


在一般的曲率下[math]\displaystyle{ K=-\zeta^2 }[/math]，圆的周长计算公式为：

[math]\displaystyle{ L(r)=2\pi\sinh \zeta r }[/math]


面积为：

[math]\displaystyle{ A(r)=2\pi(\cosh \zeta r -1) }[/math]


双曲空间与树形网络

实际上，之所以双曲空间能够比较好地描述现实中的网络，是因为大多数现实网络都具有树状的层次结构。而双曲空间就是树网络的连续版本。为什么这么说呢？我们知道如果树的一个节点有两个分叉的话，那么从树根往外放射出去，第一层有2个节点，第二层就有4个，第三层8个，……，第n层就有[math]\displaystyle{ 2^n=\exp(n \ln2) }[/math]个，因此这是一个指数增长。如果将双曲空间中的坐标原点看作是树根，到原点的距离为层数n，那么双曲空间的半径n处圆的周长就相当于树第n层的节点数，也是近似exp(n)的增长关系，所以这二者其实是等价的。

Hyperbolictreethreebranches.png


可以证明，如果一个树的分叉数为p，那么它就相当于一个曲率为[math]\displaystyle{ \ln^2p }[/math]。

双曲空间的随机几何图模型

与经典的随机几何图非常相似，双曲空间的随机几何图也是需要先在一个双曲空间上撒下N个点，然后以每个点P为圆心，以r为半径，画双曲圆（见上图）。落在圆内的那些点就都与P点相连接形成网络。但是，在Dmitri Krioukov和Fragkiskos Papadopoulos等人的模型中，还有两点主要不同：

  • 所有点随机撒的区域是一个半径为R的双曲圆。其中R为一个给定的参数。双曲圆的圆心原则上讲可以是双曲平面上的任意一个区域，但是不失一般性，我们可以选择坐标原点；
  • r=R，也就是连通性的邻域半径r刚好与撒点的空间大小R相等

Randomgeometricgraphinhyperbolicspace.png


上图展示的就是一个包含了740个节点，半径R=15.5，曲率K=-1的双曲空间中的随机几何图。我们展示了红色和绿色区域是两个点（黑色圆圈，它们的极径分别是10.6和5.0）以R为半径的双曲圆。


那么，用这个模型构造出来的网络就同时具备异质性（无标度）和高聚集性这两种特征


连接异质性

为什么双曲空间中的随机几何图模型就具备无标度网络的特性呢？直观地说，根据模型设置，越外围的的点拥有越少的链接（这是一个指数衰减的过程），而这些点却越来越多（这是一个指数增长的过程）。这两个过程合并起来的效果就会导致无标度网络，即度分布为幂律分布的。下面，给出严格的分析。


首先，我们可以证明，按照这种方式构造出的复杂网络具备无标度度分布的特性。不失一般性，我们考虑的双曲空间曲率为K＝－1.

Illustrationofscalingfreeinhyperbolic.png


如图所示，O是坐标原点，X是随机几何图中的任意一个点，坐标为[math]\displaystyle{ (r,\alpha) }[/math]，其中[math]\displaystyle{ \alpha }[/math]为任意的角度，r<R。下面我们要计算X这个节点的度，也就是它的邻居数。由于所有的节点都是在以O为圆心，R为半径的双曲圆内均匀分布，故而X的邻居数必然正比于图中深灰色区域的阴影面积。


这部分面积可以按照如下的方式计算：首先，我们以O为中心，以R-r为半径画一个圆，我们计算这个圆的面积。按照双曲圆面积的计算公式，这部分面积为：

[math]\displaystyle{ A_1=2\pi\left(\cosh(R-r)-1\right) }[/math]


然后，我们再计算剩下一半的面积：

[math]\displaystyle{ A_2=2\int_{R-r}^{R}\sinh{y}dy\int_0^{\theta_y}d\theta=2\int_{R-r}^r\theta_y\sinh{y}dy }[/math]


其中[math]\displaystyle{ \theta_y\in[0,\pi] }[/math]是如图所示的三角形OXY中OX和OY的夹角（保证|XY|=R），这个角度可以通过解下面的方程而得出：

[math]\displaystyle{ \cosh R=\cosh r \cosh y - \sinh r\sinh y\cos \theta_y }[/math]


最后计算得到，总面积：

[math]\displaystyle{ \begin{align} A(r)=A_1+A_2=&2\pi\left(\cosh(R-r)-1\right)-2\cosh R\left(\arcsin\frac{\tanh(r/2)}{\tanh R}+\arctan\frac{\cosh R \sinh(r/2)}{\sqrt{\sinh(R+r/2)\sinh(R-r/2)}}\right)\\ &+\arctan\frac{\left(\cosh R+\cosh r\right)\sqrt{\cosh 2R-\cosh r}}{\sqrt{2}\left(\sinh^2R-\cosh R-\cosh r\right)\sinh(r/2)}\\ &-\arctan\frac{\left(\cosh R-\cosh r\right)\sqrt{\cosh 2R-\cosh r}}{\sqrt{2}\left( \sinh^2 R+\cosh R-\cosh r\right)\sinh(r/2)} \end{align} }[/math]


这样，位于r半径处所有节点的平均度就是：

[math]\displaystyle{ \langle k(r)\rangle = \frac{N}{2\pi (\sinh(R)-1)}A(r) }[/math]


当R非常大的时候，这个表达式可以近似为：

[math]\displaystyle{ \langle k(r)\rangle = N\left\{\frac{4}{\pi}e^{-r/2}-\left(\frac{4}{\pi}-1\right)e^{-r}\right\}\approx \frac{4}{\pi}Ne^{-r/2} }[/math]


也就是说r处节点的平均度随着半径r而以指数衰减。近一步，我们知道了[math]\displaystyle{ \langle k(r)\rangle }[/math]为r处节点的平均度，而这一圈节点的度分布是一个泊松分布，因此

[math]\displaystyle{ g(k|r)=e^{-\langle k(r)\rangle}\langle k(r)\rangle ^k/k! }[/math]


这里，g(k|r)表示节点的极径为r位置处，度为k的概率。这样，整个网络的度分布就是：

[math]\displaystyle{ P(k)=\int_0^R g(k|r)\rho(r)dr=2\langle k\rangle^2\frac{\Gamma (k-2,\langle k\rangle /2)}{k!}\sim k^{-3} }[/math]


这里的[math]\displaystyle{ \rho(r)=\frac{\sinh r}{\cosh R-1}\approx e^{r-R}\sim e^r }[/math]为位于半径r处的圆的节点数，它随着半径r而指数生长。[math]\displaystyle{ \langle k\rangle=\int_0^R\rho(r)\langle k(r)\rangle dr\approx \frac{8}{\pi}Ne^{-R/2} }[/math]为整个网络的平均度。


由此可见，网络的度分布为一个幂指数为3的无标度分布。


一般曲率情形[math]\displaystyle{ K=-\zeta^2 }[/math]

接下来，我们考虑更一般的情况。首先，我们假设节点的密度分布为准均匀的，也就是说位于半径为r处的节点密度为：

[math]\displaystyle{ \rho(r)=\alpha\frac{\sinh \alpha r}{\cosh \alpha R -1 }\approx \alpha R^{\alpha (r - R)}\sim e^{\alpha r} }[/math]


由此可知，当[math]\displaystyle{ \alpha=1 }[/math]的时候，就恢复了上面的均匀分布模型。


第二个，我们假设双曲空间的曲率并不是－1，而是一个常数[math]\displaystyle{ K=-\zeta^2 }[/math]，其中[math]\displaystyle{ \zeta\gt 0 }[/math]。这样，当[math]\displaystyle{ \alpha=\zeta }[/math]的时候，点的分布就是均匀的。


在这种情况下，节点的度分布为：

[math]\displaystyle{ P(k)\sim k^{-\gamma} }[/math]


这里，

[math]\displaystyle{ \gamma=\left\{\begin{array}{ll}\frac{2\alpha}{\zeta}+1&\text{if } \frac{\alpha}{\zeta} \geq \frac{1}{2}\\2&\text{if } \frac{\alpha}{\zeta} \leq \frac{1}{2} \end{array}\right. }[/math]


同时，我们可以计算出平均度为：

[math]\displaystyle{ \langle k\rangle=\frac{2}{\pi}\xi^2Ne^{-\zeta R/2} }[/math]


这里[math]\displaystyle{ \xi=(\alpha/\zeta)/(\alpha/\zeta-1/2) }[/math]。因此，如果我们希望网络的平均度刚好是[math]\displaystyle{ k_0 }[/math]，那么我们需要撒入的节点数就必须为：

[math]\displaystyle{ N(k_0)=\pi \frac{k_0}{2 \xi^2} e^{\zeta R/2} }[/math]


软化连接模型

在刚刚介绍的随机几何图模型中，只有在半径小于r的时候才发生联系。而且，这个链接条件是硬性的，也就是说只要小于r才连接，不小于就一定不会连接。这在实际情况中条件过于苛刻。于是，作者提出了一种软化的模型，也就是说，任意两点发生连接的概率按照下式计算：

[math]\displaystyle{ p(x)=\frac{1}{e^{\beta(\zeta/2)(x-R)}+1} }[/math]


这里[math]\displaystyle{ \beta }[/math]为一个引入的新参数。当[math]\displaystyle{ \beta }[/math]趋近于无穷大的时候，这个模型就退化成标准的双曲空间随机几何图模型了。在一般的情形，两个节点发生连边的概率会随着它们彼此之间的双曲距离增大而减小。而且R是一个阈值，当距离超过R以后，概率减小的就会很快了。我们知道，这个概率表达式刚好是费米－狄拉克统计下的概率分布表达式。其中[math]\displaystyle{ \beta }[/math]为温度的倒数。


在这个模型中，度分布仍然为幂律分布，而且幂指数为

[math]\displaystyle{ \gamma=2\frac{\alpha}{\zeta\beta}+1 }[/math]

聚集系数

我们很难解析地计算出网络的聚集系数分布以及平均聚集系数。但是，不难看出双曲空间中的随机几何图模型具有很高的聚集系数。这是因为，在度规空间中，距离的三角不等式成立，于是如果A与B节点临近，B与C节点临近，那么A与C节点也临近。


在软化链接模型中，我们可以做出聚集系数随温度变化的曲线，如下图：

Hyperbolicspaceclusteringwithtemperature.png


这是在不同的度分布指数情况下，集聚系数随温度([math]\displaystyle{ \frac{1}{\beta} }[/math])变化的情况。我们看到，大部分的聚集系数都很大。

体－边界对偶关系

复杂网络的双曲模型中有一个很有趣的方面是，它是和一个圆环上的网络模型具有对偶关系的。在介绍这种对偶关系之前，让我们先来看看圆环上的网络模型

圆环模型

在这个模型中，我们假设所有的节点都有一个隐变量（[math]\displaystyle{ \kappa }[/math]），表示该节点预期能够达到的度。另外，我们还假设所有的节点都分配在一个圆环上（我们不妨用区间[math]\displaystyle{ [0,2\pi] }[/math]来表示）。这样，任意两个节点X（坐标为[math]\displaystyle{ \theta_x }[/math]，隐变量为[math]\displaystyle{ \kappa }[/math]）和Y（坐标为[math]\displaystyle{ \theta_y }[/math]，隐变量为[math]\displaystyle{ \kappa' }[/math]）之间具有距离[math]\displaystyle{ \theta_{XY}=\pi-|\pi-|\theta_x-\theta_y|) }[/math]。那么这两点依下面的概率发生联系（即建立连边）：

[math]\displaystyle{ \Pi=f(\frac{\theta_{XY}}{\mu\kappa\kappa'}) }[/math]


其中[math]\displaystyle{ \mu }[/math]是一个能够控制整个网络的平均度的参数，[math]\displaystyle{ f(x) }[/math]为任意的可积函数。


我们可以验证，首先，我们假设所有节点的[math]\displaystyle{ \kappa }[/math]是一个随机变量，随机变量的概率密度函数为：[math]\displaystyle{ \rho(\kappa) }[/math]，则：

[math]\displaystyle{ \langle k(\kappa)\rangle=\frac{N}{2\pi}\int\int\rho(\kappa')f(\frac{\theta_{XY}}{\mu\kappa\kappa'})d\kappa'd\theta }[/math]


为了求这个积分，我们做变量替换，令[math]\displaystyle{ \xi=\frac{\theta_{XY}}{\mu\kappa\kappa'} }[/math]，则[math]\displaystyle{ \theta=\frac{\xi}{\mu\kappa\kappa'} }[/math]，于是[math]\displaystyle{ d\theta=\frac{d\xi}{\mu\kappa\kappa'} }[/math]。这样，上面的积分就变为：

[math]\displaystyle{ \langle k(\kappa)\rangle=2\mu\kappa\int_{\kappa_0}^{\infty}\kappa'\rho(\kappa)d\kappa'\int_0^{N/(2\mu \kappa\kappa')}f(\xi)d\xi=2\mu\langle\kappa\rangle\kappa I }[/math]


这里[math]\displaystyle{ I=\int f(\xi)d\xi, \langle\kappa\rangle=\int_{\kappa_0}^{\infty}\kappa'\rho(\kappa')d\kappa' }[/math]是[math]\displaystyle{ \kappa }[/math]的平均值。于是，我们可以得到

[math]\displaystyle{ \frac{k(\kappa)}{\langle k\rangle}=\frac{\kappa}{\langle \kappa\rangle} }[/math]


也就是说，这里的隐变量[math]\displaystyle{ \kappa }[/math]实际上是正比于最后该节点的平均度的。并且，这个结论与函数f的具体形式没有关系。


这样，如果节点满足幂律分布[math]\displaystyle{ \rho(\kappa)\sim \kappa^{-\gamma} }[/math]，那么：最后的网络度分布也满足幂律分布。首先，我们可以得到网络的度分布概率密度函数为：

[math]\displaystyle{ P(k)=(\gamma-1)\kappa_0^{\gamma-1}\frac{\Gamma(k+1-\gamma,\kappa_0)}{k!} }[/math]


对于较大的k，这近似是一个幂指数为的[math]\displaystyle{ \gamma }[/math]的幂律分布，即：

[math]\displaystyle{ P(k)\sim k^{-\gamma} }[/math]


于是，该模型能够模拟出真实网络中的度分布的异质性。


除此之外，这个模型还能够复现出高集聚系数，以及尺度变化无关性等特征。


对偶

在理论物理中，体－边界对偶是一种猜想，说的是体中的物理理论可以一一映射到表面上的另一套物理理论。而在复杂网络模型中，圆环刚好构成了双曲空间彭加莱圆盘的外边界。而圆环上的网络模型则也与双曲空间中的随机几何图模型构成了对偶关系。


我们设圆环模型中任意一个节点的隐变量为[math]\displaystyle{ (\kappa,\theta) }[/math]。其中[math]\displaystyle{ \kappa }[/math]为预期的度，[math]\displaystyle{ \theta }[/math]为该节点在圆环上的位置。我们只要定义如下映射：

[math]\displaystyle{ \kappa=\kappa_0e^{\zeta (R-r)/2} }[/math]


就能将圆环上的节点映射到双曲空间中，其中任意点的极坐标为：[math]\displaystyle{ (r,\theta) }[/math]，于是，网络模型映射到双曲空间中。这里[math]\displaystyle{ \kappa }[/math]为节点的隐变量：该节点预期的度。[math]\displaystyle{ \zeta=2\alpha/(\gamma-1) }[/math]，其中[math]\displaystyle{ \alpha }[/math]为双曲空间中节点密度的参数，[math]\displaystyle{ \gamma }[/math]为圆环模型中隐变量[math]\displaystyle{ \kappa }[/math]满足的幂律分布的幂指数。


接下来，我们不难验证，只要让圆环模型中的函数f(x)取为特定的形式，则圆环网络模型就与双曲空间的随机几何图模型完全对应一个网络了。即，如果在圆环模型中X和Y存在着链接，那么经过变换后的双曲空间中的两个对应点X',Y'也会按照双曲随机几何图模型发生链接，否则就不链接。这种特殊的函数形式是：

[math]\displaystyle{ f(x)=\Theta(1-x) }[/math]


其中，[math]\displaystyle{ \Theta(x) }[/math]为Heaviside阶梯函数，即当x>0的时候，函数值为1，否则都为0。这样的话，只有当任意两点X和Y满足[math]\displaystyle{ \frac{\theta_{XY}}{\mu\kappa\kappa'}\lt 1 }[/math]的时候，这两个点才确定性地发生链接，否则二者不连。


近一步，当我们把[math]\displaystyle{ \kappa,\kappa' }[/math]按照关系式：[math]\displaystyle{ \kappa\propto e^{\zeta (R-r)/2} }[/math]代入，就不难得到，当

[math]\displaystyle{ \theta_{XY}\lt \mu\kappa\kappa'\propto e^{\zeta (R-(r+r')/2)} }[/math]


也就是：

[math]\displaystyle{ r+r'+\frac{2}{\zeta}\log\frac{\theta_{XY}}{2}\lt R }[/math]


而不等号的左边刚好就是X、Y两点间的双曲距离的近似表达式。所以，圆环网络模型的链接条件刚好就是只有当两节点之间的双曲距离小于给定常数R这个条件。


因此，我们看到环状的模型刚好与双曲空间中的随机几何图模型形成边界－体对偶。

生长模型

之前给出的各种模型都是静态模型，也就是说网络的节点和链接都是一下子建立的，不会随着时间而变化。然而，现实中的网络都是生长的。因此，为了更好地建模网络的生长，Fragkiskos Papadopoulos等人又建立了一个在双曲几何空间下的生长模型[3]。


在这个模型中，节点是一个一个地加入网络的。

  • 网络一加入就会自动映射到一个双曲空间的扩展彭加莱圆盘模型之中。
  • 其中节点的极径为[math]\displaystyle{ \log t }[/math]，其中t为时间步，而因为每个时间只加入一个节点，所以t也是从老到新的节点编号。
  • 节点的极角就从[math]\displaystyle{ [0,2\pi) }[/math]之中均匀地随机取值。
  • 然后，每个节点就链接到它双曲距离最近的m个节点，其中m为固定的参数。双曲距离是按照近似式 [math]\displaystyle{ d\approx \log t + \log s + \log\Delta\theta/2=\log (t\cdot s\cdot \Delta\theta/2) }[/math]，其中[math]\displaystyle{ \Delta\theta=\pi-|\pi-|\theta_X-\theta_Y|| }[/math]
  • 节点一旦生成就永久存在
  • 反复执行上述过程就可以构造起网络


下图展示了这套规则：

Hyperbolicspacegrowthnetworkmodel.png


该图展示了一个网络的生长过程，其中有20个节点，每个节点都对应一个数字编号。绿色的圆代表的是当前的时间坐标（[math]\displaystyle{ \log t }[/math]），粉红色的区域为新节点20所连接的m＝3的链接邻域。2、7、8都是它的邻居。黄色区域表示的是节点年龄非常相近的节点集合区域。每个节点向往指向的箭头表示的是节点的衰减运动方向（见后文）。

模型解读

在《Popularity versus similarity》这篇nature的文章中，作者指出很多网络在生长的过程中都体现为两种力量的竞争。也就是当新加入一个节点的时候，它究竟应该和谁发生联系呢？作者认为有两个主要的因素，一个是popularity，也就是一个老节点的流行性。因为流行性越大，这个节点的知名度越高，因此新节点链接它的概率也就越大。另一个主要因素就是similarity，也就是相似性。即新链入的节点会以较大的概率链接到和自己相似的节点上去。


而双曲空间中的网络生长模型正反映了这两种力量的竞争。每个节点的极径ln s，其中s是该节点的诞生时间，所以s越小，节点诞生越早，存活的时间越长，新节点链接它的概率也就越大。另一方面，节点的[math]\displaystyle{ \theta }[/math]建模了它的特征，这样让[math]\displaystyle{ \Delta \theta }[/math]越小的那些节点，也就是与新节点越相似的节点。


于是，每个新节点选择m个让[math]\displaystyle{ st \Delta \theta_{st} }[/math]最小的节点（t是新节点的诞生时间，也就是当前时刻），也就是要同时最小化流行性（s）和相似性（ [math]\displaystyle{ \Delta \theta_{st} }[/math]）。而且，在这个模型中，相似性和流行性实际上是平权的。

改进模型1：流行性的衰减

在上述模型中，我们看到新节点的链接相当于优化目标是[math]\displaystyle{ s\Delta \theta_{st} }[/math]，而s和[math]\displaystyle{ \Delta \theta_{st} }[/math]是同等重要的。那么，我们能不能加上一个权重呢？也就是我们可以引入一个调节参数[math]\displaystyle{ a\in [0,1] }[/math]使得新节点优化：

[math]\displaystyle{ s^{a}\Delta\theta_{st}^{1-a} }[/math]


所以a越大新节点越看重流行性s，否则越看重相似性。当a为1/2的时候，就恢复到了原始的模型。但是，我们这样改造的意义又是什么呢？作者给出了巧妙的回答。它们将a解释成了流行性衰减的一种大小。


也就是说，每个已经存在的节点的流行性都有一种所谓的衰减效应，即在t时刻，原本在极径s处的节点将向外移动（参见上图），于是t时刻它的极径将变为：

[math]\displaystyle{ r_s(t)=\beta r_s+(1-\beta)r_t }[/math]


这里，[math]\displaystyle{ r_s=\log s, r_t=\log t }[/math]，[math]\displaystyle{ 1-\beta\in [0,1] }[/math]控制了移动的快慢。


这样，新引入节点与该老节点的距离就变为：

[math]\displaystyle{ d\approx r_t(t)+r_s(t)+\log\Delta\theta_{st}=(2-\beta)r_t+\beta r_s+\log\Delta\theta_{st}=\log(t^{2-\beta}s^{\beta}\Delta\theta_{st}) }[/math]


于是，这就相当于新节点要最小化[math]\displaystyle{ s^{\beta}\Delta\theta_{st} }[/math]，或者最小化[math]\displaystyle{ s^{a}\theta_{st}^{1-a} }[/math]，其中[math]\displaystyle{ a=\beta/(1+\beta) }[/math]。这样，流行性和相似性之间就构成了竞争的关系。

改进模型2：软化链接

同样地，在这个生长模型中，链接也是硬性的每次新建m个链接，而且严格按照最近邻原则。作者同样考虑了软化链接的情况。即假设s与t两个节点以以下的概率发生链接：

[math]\displaystyle{ p(x_{st})=\frac{1}{1+\exp(x_{st}-R_t)/T} }[/math]


其中[math]\displaystyle{ x_{st} }[/math]为s和t之间的距离，[math]\displaystyle{ R_{t} }[/math]为t时刻的链接半径值，通常它取常数，也可能随时间而变。T为“温度”参数，可以调节网络的簇系数大小。


当T=0的时候，就变成了经典的双曲空间上的随机几何图。而当T趋于无穷大的时候，该模型就变为欧氏空间的经典随机几何图生长模型。通过改变不同的参数，该模型还能转化为经典的随机网络、BA网络模型、适应度模型等等。

网络的性质

偏好依附

下面，我们可以计算这个网络生长模型是否也具有偏好依附效应，也就是计算新加点与任意的s点相连接的概率：

[math]\displaystyle{ \Pi(r_s(t))=m\frac{(s/t)^{-\beta}}{\int_1^t(i/t)^{-\beta}di} }[/math]


它表达的是一个在s时刻建立的节点吸引新节点的概率是正比于(s/t)的β方的。近一步，将这个结论与偏好依附模型比较就会发现，它们在数学形式上是一样的。这就促使我们近一步推想后续的推导过程也类似于偏好依附模型。其中度为k的节点吸引到新点的概率为：

[math]\displaystyle{ \Pi(k)\propto k+m(\frac{1}{\beta}-1) }[/math]


但是，与BA网络模型不一样的地方是，双曲模型的链接概率还依赖于双曲距离，如下图所示：

Preferentialattachmentinhyperbolicspace.png


这两张图都是模拟结果。我们看到上图是偏好依附概率随度增长的情况，下图为链接概率与双曲距离的关系，BA网络模型与距离无关。

Probabilityvshyperbolicdistanceinempiricalnetworks.png


上两张图则展示了两个实际网络（互联网和线虫代谢网络）中链接概率与节点之间的双曲距离之间的关系。其中对于真是网络来说，每个节点的双曲空间中的位置是根据极大似然估计原理计算出来的。具体思路是，采用软化链接模型，写出生成一个网络构型（每个节点给一个双曲空间中的位置坐标）的概率，然后以这个概率为目标函数最大化，估算出所有节点的位置。具体思路见文献[3]。


无标度网络

近一步推导可以得出结论，无论是原始模型、流行度衰退模型，还是软化链接模型，它们的偏好依附形式都一样。而由偏好依附概率，我们就可以推出网络最后的的度分布形式为：

[math]\displaystyle{ P(k)\sim k^{-\gamma} }[/math]


其中，[math]\displaystyle{ \gamma=1+1/\beta }[/math]


因此，网路也是一个无标度网络。

与静态模型的比较

与静态模型相比，这个动态生长模型有了很多的有点：

  1. 首先，动态模型可以模拟动态生长情况
  2. 其次，在静态模型中，所有节点要撒到一个以原点为圆心R为半径的圆内，而且R本身也是发生连接的距离阈值，这两点要求都很苛刻而且没有实际物理意义。而在动态模型中，每个节点都只需要按照时间顺序一个个地生长下来就可以了，链接仅发生在最近邻，而且链接数目固定。这种要求自然的多。
  3. 第三，动态模型将双曲坐标赋予了实际含义，极径表示的是log t，极角则表示相似空间中的特征。这样，优化双曲距离就变为对流行性和相似度的一种综合竞争。所有参数的物理意义都很清晰。
  4. 第四，动态模型给出了一种将实际网络嵌入双曲空间的算法，从而可以针对实际网络计算双曲空间中的坐标。
  5. 最后，动态模型可以通过简单变形而重现包括偏好依附网络模型、适应度网络模型在内的经典模型。

参考文献

  1. ↑ Krioukov, D.; Kitsak, M.; Vahdat, A.; Boguñá., M (2010). "Hyperbolic geometry of complex networks". Physical Review E. 82: 036106. {{cite journal}}: Missing |author2= (help); More than one of |first1= and |first= specified (help); More than one of |last1= and |last= specified (help)
  2. ↑ Serrano, M. Ángeles; Boguñá, Marián (2008). "Self-Similarity of Complex Networks and Hidden Metric Spaces". Physical Review Letters. 100: 078701. {{cite journal}}: Missing |author2= (help); More than one of |first1= and |first= specified (help); More than one of |last1= and |last= specified (help)
  3. ↑ 3.0 3.1 3.2 Papadopoulos, F.; A ́ngeles Serrano, A.; Boguñá.first5=D., M; Krioukov (2012). "Popularity versus similarity in growing networks". Nature. 489: 537-540. {{cite journal}}: Cite has empty unknown parameter: |1= (help); Missing |author3= (help); More than one of |first1= and |first= specified (help); More than one of |last1= and |last= specified (help)

相关WIKI


编者推荐

双曲空间的可视化
本课程沿着几何的线路重新梳理复杂网络，包括ER随机网、小世界网络、无标度网络，网络的分形特征等。之后，重点讲述如何利用真实的网络数据来重构系统的空间几何特征。


具有幂律度的随机图可以将无标度网络建模为具有强度异质性的稀疏拓扑。对这种随机图的数学分析证明成功地解释了无弹性网络属性，如弹性，导航性和小距离。引入一个变分原理来解释顶点如何倾向于在三角形中聚类作为其度数的函数。将变分原理应用于双曲线模型，该模型很快成为具有潜在几何和聚类的无标度网络的模型。本文证明了双曲线模型中的聚类是非消失和自平均的，因此单个随机图样本在大网络限制中是一个很好的表示。


康奈尔大学计算机科学系教授Chris De Sa 与斯坦福大学计算机科学系博士生Albert Gu 携手构建出高效的嵌入算法——使用双曲线组合结构嵌入算法，以更低的维度更好地嵌入文本、知识图谱等非结构化的数据。

本中文词条由Jake用户参与编译，乐多多编辑，欢迎在讨论页面留言。


本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。

取自“https://wiki.swarma.org/index.php?title=复杂网络的双曲几何模型&oldid=12609”