一种基于双曲嵌入的网络多路径搜索方法

摘要

本发明提供了一种基于双曲嵌入的网络多路径搜索方法。本发明输入无权无向网络；借助于双曲随机几何图模型完成双曲嵌入，获得网络节点表征向量；通过网络节点表征向量构造几何搜索树并借助于双曲空间超圆周获取网络中每对节点间的主干通信子网；最终在该子网中完成完全不相交或部分不相交的多路径搜索。本发明通过将网络嵌入到双曲空间中，利用双曲空间的负常数曲率，高效表征近似树状的网络结构，本发明的方法避免了多路径的全局拓扑搜索，该方法在保证搜索成功率的同时，显著降低传统算法的搜索空间，提高了搜索效率。

说明书

技术领域

本发明属于复杂网络分析和通信技术领域，具体涉及一种基于双曲嵌入的网络多路径搜索方法。

背景技术

网络是一种描述实体与实体之间关系的有效方法。许多天然的和人工的复杂网络都是多路径信息路由的范例，例如，互联网、社会网络、脑神经网络和流行病传播网络等等。特别是多路径路由已经成为Internet上一种无处不在的技术，它被用来促进网络的生存性，支撑多路径传输，保证服务质量，平衡流量负载，采用流量工程方法来优化网络资源利用率。这些应用的一个基本问题是如何找到多条不相交路径，包括完全不相交的最短路径和部分不相交的最短路径。

目前，求解多条完全不相交的最短路径问题主要通过网络最大流方法，部分不相交的最短路径问题主要借助于增广路径和残留网络技术。

现有技术存在以下问题：传统的基于图的算法需要全局拓扑结构，才能充分利用路径多样性。因此，这类算法在大规模网络中可能会导致很高的开销。为了有效地利用局部拓扑并减少不必要的开销，最近的部分研究从经典图论转向了基于几何的模型，如双曲随机几何图。现有的研究已经表明，仅使用双曲随机几何图上的局部信息就可高效搜索两个节点之间的单一路径。然而，由于这些方法大多只获得一条无约束的近似最短路径，因此并不能直接将它们应用于多条路径的搜索任务。

发明内容

本发明针对现有技术的不足，提供一种基于双曲嵌入的网络多路径搜索方法，以解决现有技术需要搜索网络全局拓扑获取多路径而存在开销大的问题。

本发明的技术方案提供了一种基于双曲嵌入的网络多路径搜索方法，包含以下步骤：

步骤1，构建无权无向网络；

步骤2，估计双曲随机几何图模型参数，根据无权无向网络中节点度结合双曲随机几何图模型参数获取无权无向网络嵌入到双曲空间后的径坐标，构建网络的拉普拉斯矩阵，利用拉普拉斯特征映射方式获取无权无向网络嵌入到双曲空间后的初始角坐标，进一步采用最大似然估计方法调整无权无向网络嵌入到双曲空间后的初始角坐标，获得网络优化调整后双曲嵌入角坐标；

步骤3，基于无权无向网络嵌入到双曲空间后的径坐标和网络优化调整后双曲嵌入角坐标结合几何数据结构构建搜索树；

步骤4，采样网络中部分节点对，调整路径跳数参数和路径似然参数，使得计算得到的超圆周内子网尽可能小同时覆盖尽可能多节点对间的路径；

步骤5，根据路径跳数参数、路径似然参数和待计算的源目的节点对求取超圆周；

步骤6，利用超圆周查询搜索树，获取超圆周内部的点导出子图；

步骤7，最终在该点导出子图上搜索节点间多路径，多路径可为完全不相交路径或部分不相交路径；

作为优选，步骤1中所述的无权无向网络为无权无向简单图，且符合幂律度分布；

步骤1中所述的无权无向网络的定义为：

G＝(V,E)

其中，V＝{v

E表示无权无向网络连边的集合，连边e

|V|为集合V的势，表示无权无向网络节点总数，其值等于N；

|E|为集合E的势，表示无权无向网络连边总数；

步骤1中所述的无权无向网络的邻接矩阵定义为：

其中，a

步骤1中所述的无权无向网络的度矩阵为N×N的对角矩阵，其定义为：

其中，i∈[1,N]，j∈[1,N]，N为无权无向网络节点总数，deg(v

作为优选，步骤2所述的双曲随机几何图模型参数包括：双曲嵌入后扩展庞加莱圆盘的最大半径R，温度系数T，网络度分布幂指数γ；

所述双曲随机几何图模型参数的具体估计方法如下：

步骤2.1，获取无权无向网络所有节点的度，将所有节点的度与幂律分布拟合得到幂指数γ，计算无权无向网络的聚集系数

步骤2.2，从(0,1]中生成随机数T；

步骤2.3，更新双曲随机几何图模型参数R为：

其中，|V|为无权无向网络节点总数，|E|表示无权无向网络连边总数，π为圆周率；

步骤2.4，利用双曲随机几何图模型生成一个网络G

步骤2.5，计算网络G

步骤2.6，若

步骤2所述无权无向网络嵌入到双曲空间后的径坐标结合双曲随机几何图模型参数获取为：

i∈[1,|V|].

其中，r

步骤2所述构建网络拉普拉斯矩阵的具体方法为：

L＝D-A，其中，D为无权无向网络的度矩阵，A为无权无向网络的邻接矩阵；

步骤2所述利用拉普拉斯特征映射方式获取无权无向网络嵌入到双曲空间后的初始角坐标的具体步骤如下：

步骤2中所述的无权无向网络嵌入到双曲空间后的初始角坐标与拉普拉斯特征映射的角坐标一致；

利用拉普拉斯特征映射将无权无向网络嵌入到二维欧氏空间中，获取嵌入后无权无向网络中节点的直角坐标，将该直角坐标转化为极坐标，其中，极坐标包含径坐标与角坐标；

步骤2所述的拉普拉斯特征映射为：

最小化无权无向网络中有连接的节点在降维后的欧式空间中的距离；

定义N×d大小的矩阵Z，矩阵的行向量z

s.t.Z

其中，a

通过拉格朗日乘子法将优化问题转化为求解Lz＝λDz的广义特征值问题，其中，L无权无向网络的拉普拉斯矩阵，λ为拉格朗日乘子；

由于此处欧氏空间为2维，取最小的两个非零特征值对应的特征向量Z

步骤2所述的采用最大似然估计方法调整无权无向网络嵌入到双曲空间后的初始角坐标，获得网络优化调整后双曲嵌入角坐标步骤如下：

对于无权无向网络中的每个节点i∈[1,N]，在其双曲嵌入的初始角坐标附近采样

其中，

所述的最大似然估计采用的对数似然函数为：

其中，a

其中，R、T为步骤2中获取的双曲随机几何图模型参数，d(v

d(v

其中，Δθ

作为优选，步骤3所述的基于无权无向网络嵌入到双曲空间后的径坐标和网络优化调整后双曲嵌入角坐标结合几何数据结构构建搜索树步骤如下：

前述步骤2已获得无权无向网络双曲嵌入后的径坐标为：

{r

网络优化调整后双曲嵌入角坐标为：

{θ

其中，r

将无权无向网络嵌入到双曲空间后的径坐标和网络优化调整后双曲嵌入角坐标通过下式转化为直角坐标：

转化后的直角坐标为：

{(x

其中，x

将转化后的直角坐标通过几何数据结构构造搜索树Tree({(x

所述的几何数据结构可采用Rtree，具体可通过排序拼贴递归树STRtree实现，Rtree为多叉树，上述无权无向网络双曲嵌入后坐标转换得到的直角坐标为树的空间对象，一个空间对象仅属于Rtree上的一个叶子节点，该树的索引构建步骤如下：

步骤3.1：定义搜索树为Tree({(x

初始化搜索树的空间聚类集合Q＝{q

步骤3.2：

步骤3.3：计算

作为优选，步骤4中的节点对为从无权无向网络中随机采样的

预设搜索k条路径，调整路径跳数参数τ和路径似然

对于采样节点对，内部子网可搜索到k条路径；且满足使超圆周半径最小；

所述的超圆周指双曲空间中到某条测地线l距离为给定值ρ的点的集合，测地线l称为超圆周的轴，ρ>0是任意给定的正数，ρ称为超圆周的半径，具体地，设l是一条给定的双曲测地线，记d(z,l)是点z到l的双曲距离，则集合

所述的超圆周的轴为通过采样节点对的测地线，超圆周半径结合双曲随机几何图模型参数和采样节点对的双曲嵌入后的径坐标、优化调整后的角坐标计算如下：

其中，T、R为步骤2中所述的双曲随机几何图模型参数，τ为路径跳数参数和

d(s,t)＝cosh

其中，Δθ

所述的超圆周内部子网通过如下步骤获得：

根据超圆周与步骤3中构建的搜索树Tree({(x

遍历搜索树Tree({(x

作为优选，步骤6中所述的搜索树为步骤3中构建的搜索树

Tree({(x

作为优选，步骤7所述的点导出子图为步骤6中导出的子图，所述的完全不相交路径指除源目的节点外无重复节点和连边的多条路径，所述的部分不相交路径指路径是彼此连边不相交的，但节点可部分相交，相交节点的数目满足预设的最大数目且相交节点仅可被两条路径共享。

本方法将网络嵌入到双曲空间中，通过几何数据结构实现高效节点索引，进一步通过超圆周提取包含网络中任意两点间主要路径的局部拓扑，以此来减小路径搜索空间，提高多路径搜索效率。

附图说明

为了更清楚地说明本发明实施例或现有技术方案，下面对实施例或现有技术进行简单地介绍，下面描述中的附图是本发明的一些实施例：

图1：是本发明实施例的基于双曲嵌入的网络多路径搜索方法的流程图。

图2：是本发明实施例的双曲嵌入的流程图。

图3：是本发明实施例的双曲嵌入模型参数估计的流程图。

具体实施方式

本发明主要基于复杂网络的双曲随机几何图模型，在双曲随机几何图模型中，节点由有界双曲圆盘中的点表示，连边存在的概率取决于相应两个节点之间的双曲距离。双曲坐标有利于节点索引，可以使用几何数据结构快速检索给定范围内的节点。网络中的多条路径靠近通过源目的节点对的双曲测地线。本发明根据源目的节点在双曲随机几何图中的位置，估计节点间主要通信骨干子网所在范围。通过超圆周结合几何数据结构完成节点快速筛选，获得局部子网，最终在子网上执行多路径搜索。本发明使用局部拓扑路径搜索替代全局拓扑路径搜索，在大规模网络中可明显提升搜索效率。

本发明提供的方法能够用计算机软件技术实现流程。为使本发明实施例的目的、技术方案和优点更加清楚，下面结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述。

本发明实施例提供了一种基于双曲嵌入的网络多路径搜索方法，一种基于双曲嵌入的网络多路径搜索方法，包含以下步骤：

步骤1，输入无权无向网络；

步骤1中的无权无向网络为无权无向简单图，所述的网络符合幂律度分布；

步骤1中所述的无权无向网络的定义为：

G＝(V,E)

其中，V＝{v

E表示无权无向网络连边的集合，连边e

|V|为集合V的势，表示无权无向网络节点总数，其值等于N＝1000；

|E|为集合E的势，表示无权无向网络连边总数；

步骤1中所述的无权无向网络的邻接矩阵定义为：

其中，a

步骤1中所述的无权无向网络的度矩阵为N×N的对角矩阵，其定义为：

其中，i∈[1,N]，j∈[1,N]，N＝1000为无权无向网络节点总数，deg(v

所述的双曲随机几何图模型是一种双曲空间中的网络生成模型。该模型对许多真实网络中观察到的常见属性进行了几何解释，包括节点度的异质分布、强聚集性以及社区结构。首先在半径为R＝2log(N)+C的扩展庞加莱圆盘中根据概率密度函数

其中，N＝1000为网络节点总数，C为控制平均度的模型参数，α≥0.5为是控制度分布幂指数的参数，度分布幂指数γ＝2α+1，T∈(0,1]为温度系数，控制网络聚集系数，T越大网络聚集系数越小；

步骤2，估计双曲随机几何图模型参数，根据无权无向网络中节点度结合双曲随机几何图模型参数获取无权无向网络嵌入到双曲空间后的径坐标，构建网络的拉普拉斯矩阵，利用拉普拉斯特征映射方式获取无权无向网络嵌入到双曲空间后的初始角坐标，进一步采用最大似然估计方法调整无权无向网络嵌入到双曲空间后的初始角坐标，获得网络优化调整后双曲嵌入角坐标；

所述的模型参数包含圆盘半径R、温度系数T，度分布幂指数γ；

所述双曲随机几何图模型参数的具体估计方法参见图3，具体步骤如下：

步骤2.1，获取无权无向网络所有节点的度，将所有节点的度与幂律分布拟合得到幂指数γ，计算无权无向网络的聚集系数

步骤2.2，从(0,1]中生成随机数T；

步骤2.3，更新双曲随机几何图模型参数R为：

其中，|V|为无权无向网络节点总数，|E|表示无权无向网络连边总数，π为圆周率；

步骤2.4，利用双曲随机几何图模型生成一个网络G

步骤2.5，计算网络G

步骤2.6，若

步骤2所述无权无向网络嵌入到双曲空间后的径坐标结合双曲随机几何图模型参数获取为：

其中，r

步骤2所述构建网络拉普拉斯矩阵的具体方法为：

L＝D-A，其中，D为无权无向网络的度矩阵，A为无权无向网络的邻接矩阵；

步骤2所述利用拉普拉斯特征映射方式获取无权无向网络嵌入到双曲空间后的初始角坐标的具体步骤如下：

步骤2中所述的无权无向网络嵌入到双曲空间后的初始角坐标与拉普拉斯特征映射的角坐标一致；

利用拉普拉斯特征映射将无权无向网络嵌入到二维欧氏空间中，获取嵌入后无权无向网络中节点的直角坐标，将该直角坐标转化为极坐标，其中，极坐标包含径坐标与角坐标；

步骤2所述的拉普拉斯特征映射为：

最小化无权无向网络中有连接的节点在降维后的欧式空间中的距离；

定义N×d大小的矩阵Z，矩阵的行向量z

s.t.Z

其中，a

通过拉格朗日乘子法将优化问题转化为求解Lz＝λDz的广义特征值问题，其中，L无权无向网络的拉普拉斯矩阵，λ为拉格朗日乘子；

由于此处欧氏空间为2维，取最小的两个非零特征值对应的特征向量Z

步骤2所述的采用最大似然估计方法调整无权无向网络嵌入到双曲空间后的初始角坐标，获得网络优化调整后双曲嵌入角坐标步骤如下：

对于无权无向网络中的每个节点i∈[1,N]，在其双曲嵌入的初始角坐标附近采样

其中，

所述的最大似然估计采用的对数似然函数为：

其中，a

其中，R、T为步骤2中获取的双曲随机几何图模型参数，d(v

d(v

其中，Δθ

步骤3，基于无权无向网络嵌入到双曲空间后的径坐标和网络优化调整后双曲嵌入角坐标结合几何数据结构构建搜索树；

步骤3所述的基于无权无向网络嵌入到双曲空间后的径坐标和网络优化调整后双曲嵌入角坐标结合几何数据结构构建搜索树步骤如下：

前述步骤2已获得无权无向网络双曲嵌入后的径坐标为：

{r

网络优化调整后双曲嵌入角坐标为：

{θ

其中，r

将无权无向网络嵌入到双曲空间后的径坐标和网络优化调整后双曲嵌入角坐标通过下式转化为直角坐标：

转化后的直角坐标为：

{(x

其中，x

将转化后的直角坐标通过几何数据结构构造搜索树Tree({(x

所述的几何数据结构可采用Rtree，具体可通过排序拼贴递归树STRtree实现，Rtree为多叉树，上述无权无向网络双曲嵌入后坐标转换得到的直角坐标为树的空间对象，一个空间对象仅属于Rtree上的一个叶子节点，该树的索引构建步骤如下：

步骤3.1：定义搜索树为Tree({(x

初始化搜索树的空间聚类集合Q＝{q

步骤3.2：

步骤3.3：计算

步骤4，采样网络中部分节点对，调整路径跳数参数和路径似然参数，使得计算得到的超圆周内子网尽可能小同时覆盖尽可能多节点对间的路径；

步骤4中的节点对为从无权无向网络中随机采样的

预设搜索k＝3条路径，调整路径跳数参数τ和路径似然

对于采样节点对，内部子网可搜索到k＝3条路径；且满足使超圆周半径最小；

所述的超圆周指双曲空间中到某条测地线l距离为给定值ρ的点的集合，测地线l称为超圆周的轴，ρ>0是任意给定的正数，ρ称为超圆周的半径，具体地，设l是一条给定的双曲测地线，记d(z,l)是点z到l的双曲距离，则集合

所述的超圆周的轴为通过采样节点对的测地线，超圆周半径结合双曲随机几何图模型参数和采样节点对的双曲嵌入后的径坐标、优化调整后的角坐标计算如下：

其中，T、R为步骤2中所述的双曲随机几何图模型参数，τ为路径跳数参数和

d(s,t)＝cosh

其中，Δθ

所述的超圆周内部子网通过如下步骤获得：

根据超圆周与步骤3中构建的搜索树Tree({(x

遍历搜索树Tree({(x

步骤5，根据路径跳数参数、路径似然参数和待计算的源目的节点对求取超圆周；

步骤6，利用超圆周查询搜索树，获取超圆周内部的点导出子图；

步骤6中所述的搜索树为步骤3中构建的搜索树

Tree({(x

步骤7，最终在该点导出子图上搜索节点间多路径，多路径可为完全不相交路径或部分不相交路径；

步骤7所述的点导出子图为步骤6中导出的子图，所述的完全不相交路径指除源目的节点外无重复节点和连边的多条路径，所述的部分不相交路径指路径是彼此连边不相交的，但节点可部分相交，相交节点的数目满足预设的最大数目且相交节点仅可被两条路径共享。

本发明提供的方法具有如下优点或者有益技术效果：

本发明提出了一种基于双曲嵌入的多路径搜索方法。利用双曲空间的负常数曲率，高效表征近似树状的网络结构。通过对双曲随机几何图模型中的多路径进行分析，确定源目的节点间的多路径以高概率分布在对应的测地线附近。进一步通过超圆周结合几何数据结构快速定位两点间的网络导航骨干子网，设计了一种在该局部拓扑子网上搜索多路径的算法。该算法在保证搜索成功率的同时，显著降低传统算法的搜索空间，提高了搜索效率。

尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例做出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本发明范围的所有变更和修改。

显然，本领域的技术人员可以对本发明实施例进行各种改动和变型而不脱离本发明实施例的精神和范围。这样，倘若本发明实施例的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。