英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
通过拉普拉斯算子将复杂网络有效嵌入双曲空间
摘要：复杂网络增长过程中涉及的不同因素在可观察的拓扑中留下有价值的信息。如何利用这些信息准确地预测结构网络变化是一个很好的研究课题。最近的网络增长模型表明节点出现时间与相似度的权衡结果产生了大部分复杂系统所共有的属性。在双曲空间中，这个模型有一个几何解释，即节点之间的距离抽象了这个优化过程。目前在网络双曲映射研究中产生节点坐标的方法能最大限度的提高上述模型产生网络的可能性。在这里，基于拉普拉斯的网络嵌入的方式采用了不同的策略，这是一种简单而准确，高效和数据驱动的流形学习方法，可以对大型网络进行快速几何分析。它与现有的嵌入和预测技术进行比较，突出了其对网络演进和链接预测的适用性。
复杂系统各部分之间关系的通用表示，是网络中节点和边的逐渐增加，它在拓扑结构中是有价值的信息。因此，挖掘网络结构技术的发展对于理解网络结构形成所遵守的要素是十分重要的。
大部分复杂网络常见的性质是强大的聚类和无标度节点度分布，这为建立链路预测【1】、社区发现【2】、突出节点的识别【3】等工具奠定了基础。此外，还有几个模型旨在模仿具有上述所提到的特点的网络的演变与形成【4】。我们特别感兴趣的是一系列假定网络结构隐含几何并塑造它的拓扑结构【5-12】的模型。（读者可以在文献13中见到详细的讨论）。这种假设是有道理的，因为复杂网络具有几何对象中常见的特征，如尺度不变性和自相似性【7，14-16】。
其中一个模型就是所谓的普及（PS）模型，它支持集群和层次结构是基于节点受欢迎程度和节点间的相似性两个特征所优化的结果【12】。受欢迎程度反映了节点吸引其他节点连接的属性，因此与系统中节点的资历状态相关联。另一方面，相似的节点具有很高的连接可能性，而不考虑它们的秩。
PS模型在双曲空间具有几何解释【9,12】，即节点之间的双曲距离受节点受欢迎程度以及节点相似性两方面综合的影响。短的双曲距离意味着它们之间有较大的可能形成链路【12】。这意味着将一个网络映射到双曲空间实际上是了解复杂构造网络拓扑的变量的值（在这里是节点受欢迎程度和节点间的相似度），以便能更好的理解系统增长的动态性。
目前，人们探索采用最大似然估计的方法（MLE）来努力推断复杂网络中的双曲几何，在该方法中，我们探索了与感兴趣的网络具有相同结构特性的PS模型的空间，从而寻找更符合网络拓扑的模型【12,17,18】。这种研究在计算上有很高的要求，这意味着这些方法需要纠正步骤或者启发式，从而适合于大型网络【18】。
在本文中，我们采取了一种不同的策略。受到机器学习中非线性降维的拉普拉斯特征映射算法【19】适应性的影响，该算法由Belkin和Niyogi提出，用来表示复杂数据的低维，我们提出了将复杂网络嵌入到二维双曲平面的方法。该方法是基于网络拉普拉斯矩阵的近似特征分解，这使得它相当简单，但准确和有效，允许在几秒钟内分析大网络。此外，它是数据驱动的，这意味着对构建感兴趣网络的模型没有任何假设。最后，针对现有的嵌入和预测技术，突出说明了它用于预测节点间新链路和研究网络演进的优点。
结果
预备知识和方法
在本篇文章中，我们只考虑无向、无加权的单组网络，因为所提出的嵌入方法只适用于具有这些属性的网络【20】。此外，这些网络假定是无标度的（标度指数）并且聚类系数c显要大于预期偶然。这些网络可以用图来表示，个节点，条与之相连的边。一个无向、无加权图可以由的邻接矩阵来表示，如果节点i,j之间有边，则数值为1，否则为0。图的拉普拉斯是通过对矩阵A的转型，其中D是对角线上为节点的度，其它地方为0的矩阵。
现在，让我们考虑一个实值函数对网络节点的集合，，它将实数分配给了每个图节点。如果拉普拉斯作为该函数，，人们可以看到它提供了每个节点i和它的邻居节点j比较的f值【21】。这是拉普拉斯算子在矢量计算和微分集合概括的离散模拟，Laplace-Beltrami算子【20】，代表了在一个给定的点上，一个曲面的曲率有多少变化。如果把一个函数作为近似的图就更明显了，这样的节点在拉普拉斯值更大的地方具有更多的边（见图1）。
图1 图的拉普拉斯
一个三维表面被描绘成热地图上的等高线图，表面被近似为一个网络，当拉普拉斯算子的值更大时（热地图的红色区域），节点具有更多的边。让一个函数作用于N个节点中的每一个节点并产生它的度。网络的拉普拉斯，这一作用在表面的离散版本，可以用做f(i)的一个操作数，提供每个节点i和它的邻居节点j之间的度的信息，换言之。 节点大小与节点度成正比。标记每个节点的数字表示其在拉普拉斯矩阵中的行/列。
特别是将网络嵌入到二维双曲平面，它由一个欧氏圆【9】的内部来表示，可以写成的矩阵，其中i代表第i行，提供节点嵌入坐标。使用拉普拉斯算子（见上文），这相当于简化，将其简化到，D上文有过定义，I是单位矩阵，MT是M的转置矩阵，tr(M)是M的跟踪矩阵。最终是最小化该目标函数所代表的矩阵，由两个特征向量的最小非零特征值组成用于求解广义特征值问题（见补充资料的第1节，详细说明这种嵌入方法的理由）。
在流行学习的背景下，大多数算法依赖于包含感兴趣样本的高维流行网格的建设【19,22】。当计算样本两两之间的距离时，它们会得到符合构建网络的最短路径，从而当数据被嵌入到低维中时，能够得到更好的一个数据保存关系【19,20,22,23】。如果在一个复杂的网络中确实存在一个双曲几何，那么它应该位于双曲面上，节点从空间原点向外发散。如果网络本身被看做是彼此之间非常接近的连接样本（这里是指节点）的网格【21】，它可以用作流形学习来恢复节点的双曲线坐标。网络中的连接对节点在目标、低维空间中应该非常接近（因此上文提出了最小化问题），所以它们的角度分离（PS模型提出，由节点相似性引导）应该也很小。图2a展现了嵌入应用方法的实例，用PS模型生成了一个人工神经网络（详情参见方法）。
图2 基于拉普拉斯的网络嵌入
- 通过PS模型产生一个750节点的网络，目标平均节点度，标度指数，网络温度T=0。通过LaBNE描述节点在网络蕴含的双曲圆盘上的角度位置，将网络嵌入到双曲平面。（b）最后，分配节点的径向坐标，以便每个节点能根据它们的度来排序。由突出角度坐标的节点颜色，我们可以注意到，由LaBNE嵌入到双曲空间与实际由PS模型得到的节点角度坐标只是位置旋转了一定的角度，这不会影响双曲下的与距离相关的连接概率，因为距离在旋转下是不变的。由LaBNE嵌入的原边不是很清晰。
因此，为了完成对双曲平面的嵌入，节点的角度坐标可以通过来得到，径向坐标（由PS模型中的受欢迎程度或资历维度提取）则根据每个节点的度来排序。这通过来实现，其中节点是网络节点按照度逐渐减少进行了排序，（看如2b，更多细节在方法中讨论）。
这种策略是有效的。因为在的本地表示中，双曲空间包含在欧氏圆盘中，从原点开始，欧氏距离和双曲距离是等价的，是保形的模型。这意味着节点间欧几里德角分离也相当于双曲的角分离【9】。另一方面，节点的径向排列对应于圆盘【9】中径向坐标的准均匀分布。同样，由于距离旋转的不变性，由双曲坐标描述的、网络中观察到的边的集合不是唯一的（见图2b）。因此，所提出的技术的目标不是找到一组特定的坐标，而是找到一个与双曲距离相关的连接概率更好的连接，从而产生感兴趣的网络。
在这一节中，我们将描述网络嵌入的方法，表一描述的以下简称为LaBNE的基于拉普拉斯的网络嵌入。
表一 基于拉普拉斯的网络嵌入（LaBNE）
注意将网络G嵌入到利用了L的截断谱分解。通过秩为k 1的矩阵，给出了最接近的本征分解，确保了LaBNE计算的时间复杂度为。
学习LaBNE的基准
为了测试LaBNE推断复杂网络双曲几何的能力，由PS模型产生人工神经网络。该模型允许构造n个节点和目标平均节点度2m、标度指数gamma;和聚类系数c的已知双曲坐标网络。聚类系数随着网络温度T的减小而线性减小，并且在T=0【9】时具有最大值（详情参见方法）。将参数，和任意组合可以生成100个合成网络，节点n的数目固定为500。采用LaBNE的方法将这些网络嵌入到双曲空间，然后计算推测的双曲距离与采用实际节点坐标所测量的双曲距离的Pearson关系，在每个参数配置的一百个网络中取平均。这个过程采用最新和最快的HyperMap算法，它是一种极大似然估计方法，通过最大化网络产生的可能性来找到通过PS模型【17,18】产生的网络节点坐标，从而将网络嵌入到双曲空间中（详情参见方法）。
图3a展现了由LaBNE方法产生的各参数组合的平均相关性比HyperMap方法产生的要高，这种现象在密集的、强聚集的网络中尤为明显（例如较大的2m,,从而获得较高的聚集系数）。这些结果推断出，比起HyperMap方法来说，LaBNE方法所推断的角度坐标要更接近于由PS模型产生的角度坐标（看图S1）。
图3 LaBNE的基本准则
- 对于所描述的参数N=500，的任一组合，采用PS模型生成100个人工网络。每个网络采用LaBNE方法和最新最快的HyperMap算法嵌入到双曲空间中，计算实际节点距离与推测节点距离的Pearson关系。100个网络的平均pearson相关性显示了每个参数的组合。（b）HyperMap和LaBNE为每个参数配置嵌入100个仿真网络所需的平均时间通过从后者到前者的倍数进行比较。在这种情况下，T被固定为0，N在250到1000中取值。
为了深入分析两种算法在时间性能上的差异，我们提出了一个类似图3a所进行的实验，不过在这个实验中，T固定为0，网络得大小在中改变，图3b描述了HyperMap和LaBNE为每个参数配置嵌入100个仿真网络所需的平均时间的倍数变化。可以看出，对于最小的网络而言，后者比LaBNE慢了500倍。这些结果强调了LaBNE的最大优点之一，它的时间性能，这源于其计算复杂度为且k=3。在一个单连通分支的网络中，L的最小特征值总是0【21】，并且它相应的特征向量不再使用。接下来的两个对应于最小非零特征值，形成结果节点坐标。由于K是永远不变的，LaBNE可以考虑是算法。
尽管我们考虑的HyperMap算法【18】同样也是的计算复杂度（详情见方法），但是图3b显示，它比LaBNE要慢。这是因为用来加速该算法的启发式算法实际上并不使用于感兴趣网络的所有N个节点，而只适用于那些度小于参数【18】（详情见方法）。该参数值越大，算法的速度越快，对其精度的影响也越大。在本文中，它被设置为10，这样可以在合理的时间内产生良好的结果。另一方面，LaBNE利用了R包igraph的效率和可移植性【24】，它的高性能子程序接口被设计解决大规模特征值问题【25】。
真实网络中链路预测的双曲嵌入
考虑到LaBNE所能实现的准确性和时间性能，并且考虑到双曲距离越短，节点之间的连接概率越高【12】，LaBNE被用来推断三个真实网络节点的双曲线坐标（见表2和方法），然后进行链路预测。正如前一节所表明的那样，图3表明对于具有更多拓扑信息的网络来说，LaBNE的准确性更高，即在节点间具有更多的边，这发生在高平均节点度（2m）和低温度（这意味着高聚类系数c）。因此，选择这里分析的三个真实网络是为了研究LaBNE在低，中，高聚类系数场景中的性能（见表2）。另外，这些网络数据集表示来自不同领域的复杂系统：高质量的人类蛋白质相互作用网络（PIN）模拟人类细胞内蛋白质之间的关系（低c），在相当好的隐私网络（PGP）中，用户与他们信任的人共享加密密钥（中c），与自治系统互联网（ASI）与路由器组之间相对应的通信网络（高c，详见方法）。
对于可观察网络中预测链路的任务，仅基于结构来进行拓扑链接预测是不存在的。评估链路预测器性能的标准方法是从研究中的网络中随机删除一定数量的链路，使用预测器将可能性分数指定给缩减拓扑中所有非相邻节点对。根据分数对候选链接进行排序。最后用一个移动的阈值来扫描这个排序的候选列表以计算精确性（通过当前分数阈值的候选链接的分数和在删除链接中的一部分）和回忆（未通过分数阈值的候选链接的分数，而是在已删除链接的集合中）统计数据【1,26】。
然而，上面提到的评估框架带有重要的附加说明。随机修剪边缘可以以不可预知的方式从可观察到的网络拓扑中删除重要信息，这无疑对链接预测器有不同的影响【26】。为了避免这个问题，必须使用网络演化的历史数据来测试一个链路预测器在网络Gt 1中评估边缘可能性的能力，这个网络还没有出现在应用的快照Gt中。对于ASI【27】和PGP，其拓扑结构的时空快照是存在的并且使用了该评价方法（见表2中下标为T 1的网络）。对于PIN【28】，有必要求助于所谓的关联原理【29】，即两种蛋白质在同一生物过程中很可能发生相互作用，在这种情况下，链接预测被应用到可观察到的蛋白质网络中，而好的和坏的候选交互之间的区别是基于对非相邻蛋白质的生物学过程之间的相似
全文共17522字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[16643]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
