更改

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

2020年8月16日 (日) 10:50的版本

添加106字节、 2020年8月16日 (日) 10:50

无编辑摘要

第27行：第27行：

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

−

<math>

+

:<math>

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>

第43行：第43行：

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

−

<math>

+

:<math>

r'=2\tanh^{-1}{r},\theta'=\theta

</math>

第84行：第84行：

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

−

<math>

+

:<math>

\cosh{\zeta x}=\cosh(\zeta r)\cosh(\zeta r')-\sinh(\zeta r)\sinh(\zeta r')\cos(\Delta \theta)

</math>

第95行：第95行：

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

−

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

+

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

当<math>\Delta\theta/2)</math>很小的时候，

−

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

+

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

第106行：第106行：

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

−

<math>

+

:<math>

r=\tanh(r'/2)

</math>

第120行：第120行：

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

−

<math>

+

:<math>

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

</math>

第127行：第127行：

面积为：

−

<math>

+

:<math>

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

</math>

第172行：第172行：

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

−

<math>

+

:<math>

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

</math>

第179行：第179行：

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

−

<math>

+

:<math>

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>

第186行：第186行：

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

−

<math>

+

:<math>

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

</math>

第193行：第193行：

最后计算得到，总面积：

−

<math>

+

:<math>

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

第204行：第204行：

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

−

<math>

+

:<math>

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

</math>

第211行：第211行：

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

−

<math>

+

:<math>

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

第218行：第218行：

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

−

<math>

+

:<math>

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

</math>

第225行：第225行：

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

−

<math>

+

:<math>

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>

第240行：第240行：

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

−

<math>

+

:<math>

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

</math>

第253行：第253行：

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

−

<math>

+

:<math>

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

</math>

第260行：第260行：

这里，

−

<math>

+

:<math>

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

第267行：第267行：

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

−

<math>

+

:<math>

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

</math>

第274行：第274行：

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

−

<math>

+

:<math>

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

</math>

第283行：第283行：

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

−

<math>

+

:<math>

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

</math>

第293行：第293行：

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

−

<math>

+

:<math>

\gamma=2\frac{\alpha}{\zeta\beta}+1

</math>

+

===聚集系数===

第313行：第314行：

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

+

===圆环模型===

第318行：第320行：

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

−

<math>

+

:<math>

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

</math>

第328行：第330行：

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

−

<math>

+

:<math>

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

</math>

第335行：第337行：

为了求这个积分，我们做变量替换，令<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>。这样，上面的积分就变为：

−

<math>

+

:<math>

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

第342行：第344行：

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

−

<math>

+

:<math>

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

</math>

第352行：第354行：

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

−

<math>

+

:<math>

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

</math>

第359行：第361行：

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

−

<math>

+

:<math>

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

</math>

第377行：第379行：

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

−

<math>

+

:<math>

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

</math>

第387行：第389行：

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

−

<math>

+

:<math>

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

</math>

第397行：第399行：

近一步，当我们把<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>

+

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

也就是：

−

<math>

+

:<math>

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

</math>

第411行：第413行：

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

+

==生长模型==

第448行：第451行：

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

−

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

+

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

第456行：第459行：

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

−

<math>

+

:<math>

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

</math>

第466行：第469行：

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

−

<math>

+

:<math>

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>

第472行：第475行：

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

+

===改进模型2：软化链接===

第477行：第481行：

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

−

<math>

+

:<math>

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

</math>

第486行：第490行：

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

+

===网络的性质===

第493行：第498行：

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

−

<math>

+

:<math>

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

</math>

第500行：第505行：

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

−

<math>

+

:<math>

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

</math>

第522行：第527行：

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

−

<math>

+

:<math>

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

</math>

第558行：第563行：

[[File:双面.gif|300px|缩略图|右|双曲空间的可视化]]

−

+

===集智相关课程===

−

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

+

====[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随机网、小世界网络、无标度网络，网络的分形特征等。之后，重点讲述如何利用真实的网络数据来重构系统的空间几何特征。

+

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

−

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

+

===相关文章===

−

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

+

====[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 双曲空间中的网络、单词及其知识图谱]

+

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

−

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

+

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

----

薄荷

7,129

个编辑