更改

复杂网络的双曲几何模型 (查看源代码)

2020年8月16日 (日) 01:28的版本

添加64字节、 2020年8月16日 (日) 01:28

无编辑摘要

第4行：第4行：

}}

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

−

==背景==

第74行：第73行：

ds^2=4 \zeta \frac{dr^2+r^2d\theta^2}{(1-r^2)^2}

</math>

+

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

第90行：第90行：

其中，<math>\Delta \theta=\pi-|\pi-|\theta-\theta'||</math>

+

=====近似表达式=====

第100行：第101行：

<math>x\approx r+r'+\frac{2}{\zeta}\log{\Delta\theta/2}</math>

+

====圆====

第110行：第112行：

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

+

[[File:hyperbolicextendedpoincaredisk.png|500px]]

−

~~[[File:hyperbolicextendedpoincaredisk.png|500px]]~~

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

+

在一般的曲率下<math>K=-\zeta^2</math>，圆的周长计算公式为：

第120行：第123行：

L(r)=2\pi\sinh \zeta r

</math>

+

面积为：

第126行：第130行：

A(r)=2\pi(\cosh \zeta r -1)

</math>

+

===双曲空间与树形网络===

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

+

[[File:hyperbolictreethreebranches.png|500px]]

−

~~[[File:hyperbolictreethreebranches.png|500px]]~~

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

第141行：第146行：

* 所有点随机撒的区域是一个半径为R的双曲圆。其中R为一个给定的参数。双曲圆的圆心原则上讲可以是双曲平面上的任意一个区域，但是不失一般性，我们可以选择坐标原点；

* r=R，也就是连通性的邻域半径r刚好与撒点的空间大小R相等

+

[[File:randomgeometricgraphinhyperbolicspace.png|500px]]

−

~~[[File:randomgeometricgraphinhyperbolicspace.png|500px]]~~

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

+

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

+

===连接异质性===

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

+

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

+

[[File:illustrationofscalingfreeinhyperbolic.png|300px]]

−

~~[[File:illustrationofscalingfreeinhyperbolic.png|300px]]~~

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

+

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

第163行：第172行：

A_1=2\pi\left(\cosh(R-r)-1\right)

</math>

+

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

第169行：第179行：

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

第175行：第186行：

\cosh R=\cosh r \cosh y - \sinh r\sinh y\cos \theta_y

</math>

+

最后计算得到，总面积：

第185行：第197行：

\end{align}

</math>

+

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

第191行：第204行：

\langle k(r)\rangle = \frac{N}{2\pi (\sinh(R)-1)}A(r)

</math>

+

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

第197行：第211行：

\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>\langle k(r)\rangle</math>为r处节点的平均度，而这一圈节点的度分布是一个泊松分布，因此

第203行：第218行：

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

</math>

+

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

第209行：第225行：

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

+

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

+

====一般曲率情形<math>K=-\zeta^2</math>====

第221行：第240行：

\rho(r)=\alpha\frac{\sinh \alpha r}{\cosh \alpha R -1 }\approx \alpha R^{\alpha (r - R)}\sim e^{\alpha r}

</math>

+

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

+

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

第232行：第253行：

P(k)\sim k^{-\gamma}

</math>

+

这里，

第238行：第260行：

\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>

+

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

第244行：第267行：

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

</math>

+

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

第250行：第274行：

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

</math>

+

===软化连接模型===

第258行：第283行：

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

</math>

+

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

+

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

第270行：第297行：

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

+

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

+

[[File:hyperbolicspaceclusteringwithtemperature.png|500px]]

−

~~[[File:hyperbolicspaceclusteringwithtemperature.png|500px]]~~

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

==体－边界对偶关系==

+

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

第288行：第317行：

\Pi=f(\frac{\theta_{XY}}{\mu\kappa\kappa'})

</math>

+

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

+

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

第296行：第327行：

\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>\xi=\frac{\theta_{XY}}{\mu\kappa\kappa'}</math>，则<math>\theta=\frac{\xi}{\mu\kappa\kappa'}</math>，于是<math>d\theta=\frac{d\xi}{\mu\kappa\kappa'}</math>。这样，上面的积分就变为：

第302行：第334行：

\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>I=\int f(\xi)d\xi, \langle\kappa\rangle=\int_{\kappa_0}^{\infty}\kappa'\rho(\kappa')d\kappa'</math>是<math>\kappa</math>的平均值。于是，我们可以得到

第308行：第341行：

\frac{k(\kappa)}{\langle k\rangle}=\frac{\kappa}{\langle \kappa\rangle}

</math>

+

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

−

第318行：第351行：

P(k)=(\gamma-1)\kappa_0^{\gamma-1}\frac{\Gamma(k+1-\gamma,\kappa_0)}{k!}

</math>

+

对于较大的k，这近似是一个幂指数为的<math>\gamma</math>的幂律分布，即：

第324行：第358行：

P(k)\sim k^{-\gamma}

</math>

+

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

+

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

+

===对偶===

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

+

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

第338行：第376行：

\kappa=\kappa_0e^{\zeta (R-r)/2}

</math>

+

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

第347行：第386行：

f(x)=\Theta(1-x)

</math>

+

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

+

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

<math>\theta_{XY}<\mu\kappa\kappa'\propto e^{\zeta (R-(r+r')/2)}</math>

+

也就是：

第359行：第401行：

r+r'+\frac{2}{\zeta}\log\frac{\theta_{XY}}{2}<R

</math>

+

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

+

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

第367行：第411行：

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

+

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

第376行：第421行：

* 节点一旦生成就永久存在

* 反复执行上述过程就可以构造起网络

+

下图展示了这套规则：

+

[[File:hyperbolicspacegrowthnetworkmodel.png|500px]]

−

~~[[File:hyperbolicspacegrowthnetworkmodel.png|500px]]~~

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

第386行：第432行：

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

+

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

+

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

第396行：第444行：

<math>s^{a}\Delta\theta_{st}^{1-a}</math>

+

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

+

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

第404行：第454行：

r_s(t)=\beta r_s+(1-\beta)r_t

</math>

+

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

+

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

第412行：第464行：

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>s^{\beta}\Delta\theta_{st}</math>，或者最小化<math>s^{a}\theta_{st}^{1-a}</math>，其中<math>a=\beta/(1+\beta)</math>。这样，流行性和相似性之间就构成了竞争的关系。

第422行：第475行：

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

</math>

+

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

+

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

第436行：第491行：

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

</math>

+

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

第442行：第498行：

\Pi(k)\propto k+m(\frac{1}{\beta}-1)

</math>

+

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

+

[[File:preferentialattachmentinhyperbolicspace.png|600px]]

−

~~[[File:preferentialattachmentinhyperbolicspace.png|600px]]~~

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

+

[[File:probabilityvshyperbolicdistanceinempiricalnetworks.png|600px]]

−

~~[[File:probabilityvshyperbolicdistanceinempiricalnetworks.png|600px]]~~

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

+

====无标度网络====

第460行：第518行：

P(k)\sim k^{-\gamma}

</math>

+

其中，<math>\gamma=1+1/\beta</math>

+

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

+

===与静态模型的比较===

第493行：第554行：

*[http://wiki.swarma.net/index.php/%E5%8F%8C%E6%9B%B2%E7%A9%BA%E9%97%B4%E6%A8%A1%E5%9E%8B 复杂的网络与优雅的几何]

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

+

*[http://arxiv.org/abs/1812.03002 Scale-free network clustering in hyperbolic and other random graphs 双曲和其他随机图的无标度网络聚类]

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

+

*[https://hazyresearch.github.io/hyperE/ HyperE: Hyperbolic Embeddings for Entities 双曲空间中的网络、单词及其知识图谱]

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

+

----

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

乐多多

763

个编辑

更改

复杂网络的双曲几何模型 (查看源代码)

2020年8月16日 (日) 01:28的版本

导航菜单

搜索