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

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

背景技术：

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

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

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

技术实现要素：

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

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

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

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

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

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

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

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

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

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

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

g＝(v,e)

其中，v＝{v1,v2,…,vn}表示无权无向网络中节点的集合，vi表示无权无向网络中第i个节点，i∈[1,n]，无权无向网络共有n个节点；

e表示无权无向网络连边的集合，连边ei,j＝(vi,vj)∈e表示无权无向网络中第i个节点和第j个节点间连边，i∈[1,n]，j∈[1,n]，节点vi和vj称为边ei,j的端点；

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

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

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

其中，aij表示无权无向网络中第i个节点与无权无向网络中第j个节点相邻的次数，在无权无向网络中，aij＝1表示无权无向网络中第i个节点和无权无向网络中第j个节点间有连边，aij＝0表示第i个节点和第j个节点间无连边；

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

其中，i∈[1,n]，j∈[1,n]，n为无权无向网络节点总数，deg(vi)为无权无向网络中第j个节点的度，所述的节点的度表示与该节点相连接的边的数目；

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

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

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

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

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

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

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

步骤2.5，计算网络g1的聚集系数

步骤2.6，若输出当前参数t、r、γ为最终估计参数，若使用二分法调整参数t，转到步骤2.3，，其中为预设的误差阈值；

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

i∈[1,|v|].

其中，ri表示无权无向网络嵌入到双曲空间后的第i个节点的径坐标，r为无权无向网络双曲嵌入后扩展庞加莱圆盘的最大半径，t∈(0,1]为温度系数，控制网络聚集系数，t越大网络聚集系数越小，γ为网络度分布幂指数，|v|为网络节点总数，deg(vi)表示无权无向网络中第i个节点的度；

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

l＝d-a，其中，d为无权无向网络的度矩阵，a为无权无向网络的邻接矩阵；

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

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

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

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

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

定义n×d大小的矩阵z，矩阵的行向量zi表示无权无向网络中第i个节点在d维欧氏空间中的向量表示，优化问题为：

s.t.z^tdz＝i.

其中，ai,j为无权无向网络的邻接矩阵第i行第j列的元素，d为无权无向网络的度矩阵，i为单位矩阵；

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

由于此处欧氏空间为2维，取最小的两个非零特征值对应的特征向量z1＝(z11,z12,…,z1n),z2＝(z21,z22,…,z2n)，其中，n为无权无向网络的节点总数，则无权无向网络拉普拉斯特征映射后第i个节点的直角坐标为(z1i,z2i)，i∈[1,n]；

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

对于无权无向网络中的每个节点i∈[1,n]，在其双曲嵌入的初始角坐标附近采样个角坐标将采样得到的角坐标代入对数似然函数计算得到取对数似然值最大的角坐标为网络优化调整后双曲嵌入角坐标，即

其中，表示向下取整，φi,t表示无权无向网络中第i个节点的第t个采样角坐标，表示无权无向网络中第i个节点的第t个采样角坐标计算得到的对数似然值，n为无权无向网络的节点总数，θi为无权无向网络中第i个节点优化调整后双曲嵌入角坐标；

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

其中，aij为邻接矩阵第i行第j列元素，pij为无权无向网络中第i个节点与第j个节点间的连接概率，其表达式为：

其中，r、t为步骤2中获取的双曲随机几何图模型参数，d(vi,vj)表示无权无向网络双曲嵌入后第i个节点与第j个节点间的双曲距离，通过下式计算：

d(vi,vj)＝cosh^-1(coshricoshrj-sinhrisinhrjcosδθij),

其中，δθij＝π-|π-|θi-θj||，ri为无权无向网络双曲嵌入后第i个节点的径坐标，rj为无权无向网络双曲嵌入后第j个节点的径坐标，θi为无权无向网络双曲嵌入后第i个节点的角坐标，θj为无权无向网络双曲嵌入后第j个节点的角坐标；

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

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

{r1,r2,…,rn}

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

{θ1,θ2,…,θn}，

其中，ri为无权无向网络双曲嵌入后第i个节点的径坐标，θi为网络优化调整后第i个节点的双曲嵌入角坐标，n为网络节点总数，i∈[1,n]；

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

转化后的直角坐标为：

{(x1,y1),(x2,y2),…,(xn,yn)}

其中，xi为无权无向网络双曲嵌入后第i个节点的x轴坐标，yi为无权无向网络双曲嵌入后第i个节点的y轴坐标，n为网络节点总数，i∈[1,n]；

将转化后的直角坐标通过几何数据结构构造搜索树tree({(x1,y1),(x2,y2),…,(xn,yn)})；

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

步骤3.1：定义搜索树为tree({(x1,y1),(x2,y2),…,(xn,yn)})，{s1,s2,…,sn}＝{(x1,y1),(x2,y2),…,(xn,yn)}为搜索树tree的空间对象集合，该集合由前述无权无向网络双曲嵌入后所有节点坐标转换后的直角坐标组成，si＝(xi,yi)为搜索树tree的第i个空间对象，定义si.mbr为第i个空间对象的最小边界矩形，n为网络节点总数；

初始化搜索树的空间聚类集合q＝{q1,q2,…,qn}，其中，qi为q中的第i个空间聚类，qi仅包含一个空间对象si＝(xi,yi)，对应于无权无向网络双曲嵌入后第i个节点坐标转换后的直角坐标，令qi.mbr＝si.mbr为q中第i个空间聚类的最小边界矩形，n为网络节点总数，i∈[1,n]，设定tree的参数阈值为m，表示一个非叶子节点所包含的最大子节点数量，

步骤3.2：表示空间聚类集合q需要被划分成δ个聚类，表示向上取整，len(q)表示空间聚类集合q中空间聚类个数，如果δ＝1，则将空间聚类集合q聚类成一个根节点root，qi为root节点的子节点，搜索树tree({(x1,y1),(x2,y2),…,(xn,yn)})构建完成，如果δ>1，则执行步骤3.3，

步骤3.3：计算ε表示每个聚类在直角坐标系x方向和y方向上划分的份数，表示向上取整，对空间聚类集合q按照qi.mbr.minx在直角坐标系x方向递增排序，将其在x方向上平均地划分成ε份聚类，其中qi.mbr.minx为q中第i个空间聚类的最小边界矩形的最小x方向坐标，然后对每份聚类结果在y方向上按照qi.mbr.miny排序，将其在y方向上平均地划分成ε份聚类，两次划分产生μ份聚类，该聚类集合组成q'，其中qi.mbr.miny为q中第i个空间聚类的最小边界矩形的最小y方向坐标，δ≤μ<len(q)，len(q)表示空间聚类集合q中空间聚类个数，集合q中的聚类为集合q'中聚类的子节点，用空间聚类集合q'替换空间聚类集合q，转到步骤3.2；

作为优选，步骤4中的节点对为从无权无向网络中随机采样的个节点对，其中n为网络节点总数；

预设搜索k条路径，调整路径跳数参数τ和路径似然使得超圆周满足两个条件：

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

所述的超圆周指双曲空间中到某条测地线l距离为给定值ρ的点的集合，测地线l称为超圆周的轴，ρ>0是任意给定的正数，ρ称为超圆周的半径，具体地，设l是一条给定的双曲测地线，记d(z,l)是点z到l的双曲距离，则集合为关于l的一个超圆域，在单位庞加莱圆盘中，超圆域的边界是两条欧氏圆弧，称为超圆周，表示二维双曲空间；

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

其中，t、r为步骤2中所述的双曲随机几何图模型参数，τ为路径跳数参数和为路径似然参数，s,t为采样的节点对，表示无权无向网络的第s个节点和第t个节点，d(s,t)表示无权无向网络的第s个节点和第t个节点双曲嵌入后的双曲距离，通过下式计算：

d(s,t)＝cosh^-1(coshrscoshrt-sinhrssinhrtcosδθst),

其中，δθst＝π-|π-|θs-θt||，rs为无权无向网络双曲嵌入后第s个节点的径坐标，rt为无权无向网络双曲嵌入后第t个节点的径坐标，θs为无权无向网络第s个节点优化调整后的双曲嵌入角坐标，θt为无权无向网络第t个节点优化调整后的双曲嵌入角坐标；

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

根据超圆周与步骤3中构建的搜索树tree({(x1,y1),(x2,y2),…,(xn,yn)})查询，获得超圆周内部的节点集合v'，具体查询方法如下：

遍历搜索树tree({(x1,y1),(x2,y2),…,(xn,yn)})中的非叶子节点的最小边界矩形，找出与超圆周的最小边界矩形存在重叠的搜索树非叶子节点的最小边界矩形，收集这些非叶子节点对应叶子节点上存储的所有空间对象，取出在超圆周内部的空间对象，组成节点集合v'，根据v'和无权无向网络g＝(v,e)得到点导出子图，该点导出子图即超圆周内部子网，所述的点导出子图表示以v'为节点集合，以g中两端点均属于v'的所有边作为边集所组成的子图；

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

tree({(x1,y1),(x2,y2),…,(xn,yn)})，所述的超圆周为步骤5中计算得到的超圆周，所述的点导出子图表示以v'为节点集合，以g中两端点均属于v'的所有边作为边集所组成的子图，其中v'为超圆周内部节点集合；

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

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

附图说明

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

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

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

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

具体实施方式

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

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

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

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

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

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

g＝(v,e)

其中，v＝{v1,v2,…,vn}表示无权无向网络中节点的集合，vi表示无权无向网络中第i个节点，i∈[1,n]，无权无向网络共有n＝1000个节点；

e表示无权无向网络连边的集合，连边ei,j＝(vi,vj)∈e表示无权无向网络中第i个节点和第j个节点间连边，i∈[1,n]，j∈[1,n]，节点vi和vj称为边ei,j的端点；

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

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

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

其中，aij表示无权无向网络中第i个节点与无权无向网络中第j个节点相邻的次数，在无权无向网络中，aij＝1表示第i个节点和第j个节点间有连边，aij＝0表示第i个节点和第j个节点间无连边；

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

其中，i∈[1,n]，j∈[1,n]，n＝1000为无权无向网络节点总数，deg(vi)为无权无向网络中第j个节点的度，所述的节点的度表示与该节点相连接的边的数目；

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

其中，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，利用双曲随机几何图模型生成一个网络g1；

步骤2.5，计算网络g1的聚集系数

步骤2.6，若输出当前参数t、r、γ为最终估计参数，若使用二分法调整参数t，转到步骤2.3，，其中为预设的误差阈值，可设置为小于0.1的值；

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

其中，ri表示无权无向网络嵌入到双曲空间后的第i个节点的径坐标，r为无权无向网络双曲嵌入后扩展庞加莱圆盘的最大半径，t∈(0,1]为温度系数，控制网络聚集系数，t越大网络聚集系数越小，γ为网络度分布幂指数，|v|为网络节点总数，deg(vi)表示无权无向网络中第i个节点的度；

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

l＝d-a，其中，d为无权无向网络的度矩阵，a为无权无向网络的邻接矩阵；

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

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

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

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

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

定义n×d大小的矩阵z，矩阵的行向量zi表示无权无向网络中第i个节点在d维欧氏空间中的向量表示，优化问题为：

s.t.z^tdz＝i.

其中，ai,j为无权无向网络的邻接矩阵第i行第j列的元素，d为无权无向网络的度矩阵，i为单位矩阵；

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

由于此处欧氏空间为2维，取最小的两个非零特征值对应的特征向量z1＝z11,z12,…,z1n),z2＝(z21,z22,…,z2n)，其中，n为无权无向网络的节点总数，则无权无向网络拉普拉斯特征映射后第i个节点的直角坐标为(z1i,z2i)，i∈[1,n]；

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

对于无权无向网络中的每个节点i∈[1,n]，在其双曲嵌入的初始角坐标附近采样个角坐标将采样得到的角坐标代入对数似然函数计算得到取对数似然值最大的角坐标为网络优化调整后双曲嵌入角坐标，即

其中，表示向下取整，φi,t表示无权无向网络中第i个节点的第t个采样角坐标，表示无权无向网络中第i个节点的第t个采样角坐标计算得到的对数似然值，n为无权无向网络的节点总数，θi为无权无向网络中第i个节点优化调整后双曲嵌入角坐标；

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

其中，aij为邻接矩阵第i行第j列元素，pij为无权无向网络中第i个节点与第j个节点间的连接概率，其表达式为：

其中，r、t为步骤2中获取的双曲随机几何图模型参数，d(vi,vj)表示无权无向网络双曲嵌入后第i个节点与第j个节点间的双曲距离，通过下式计算：

d(vi,vj)＝cosh^-1(coshricoshrj-sinhrisinhrjcosδθij),

其中，δθij＝π-|π-|θi-θj||，ri为无权无向网络双曲嵌入后第i个节点的径坐标，rj为无权无向网络双曲嵌入后第j个节点的径坐标，θi为无权无向网络双曲嵌入后第i个节点的角坐标，θj为无权无向网络双曲嵌入后第j个节点的角坐标；

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

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

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

{r1,r2,…,rn}

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

{θ1,θ2,…,θn}，

其中，ri为无权无向网络双曲嵌入后第i个节点的径坐标，θi为网络优化调整后第i个节点的双曲嵌入角坐标，n为网络节点总数，i∈[1,n]；

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

转化后的直角坐标为：

{(x1,y1),(x2,y2),…,(xn,yn)}

其中，xi为无权无向网络双曲嵌入后第i个节点的x轴坐标，yi为无权无向网络双曲嵌入后第i个节点的y轴坐标，n为网络节点总数，i∈[1,n]；

将转化后的直角坐标通过几何数据结构构造搜索树tree({(x1,y1),(x2,y2),…,(xn,yn)})；

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

步骤3.1：定义搜索树为tree({(x1,y1),(x2,y2),…,(xn,yn)})，{s1,s2,…,sn}＝{(x1,y1),(x2,y2),…,(xn,yn)}为搜索树tree的空间对象集合，该集合由前述无权无向网络双曲嵌入后所有节点坐标转换后的直角坐标组成，si＝(xi,yi)为搜索树tree的第i个空间对象，定义si.mbr为第i个空间对象的最小边界矩形，n为网络节点总数；

初始化搜索树的空间聚类集合q＝{q1,q2,…,qn}，其中，qi为q中的第i个空间聚类，qi仅包含一个空间对象si＝(xi,yi)，对应于无权无向网络双曲嵌入后第i个节点坐标转换后的直角坐标，令qi.mbr＝si.mbr为q中第i个空间聚类的最小边界矩形，n为网络节点总数，i∈[1,n]，设定tree的参数阈值为m，表示一个非叶子节点所包含的最大子节点数量，

步骤3.2：表示空间聚类集合q需要被划分成δ个聚类，表示向上取整，len(q)表示空间聚类集合q中空间聚类个数，如果δ＝1，则将空间聚类集合q聚类成一个根节点root，qi为root节点的子节点，搜索树tree({(x1,y1),(x2,y2),…,(xn,yn)})构建完成，如果δ>1，则执行步骤3.3，

步骤3.3：计算ε表示每个聚类在直角坐标系x方向和y方向上划分的份数，表示向上取整，对空间聚类集合q按照qi.mbr.minx在直角坐标系x方向递增排序，将其在x方向上平均地划分成ε份聚类，其中qi.mbr.minx为q中第i个空间聚类的最小边界矩形的最小x方向坐标，然后对每份聚类结果在y方向上按照qi.mbr.miny排序，将其在y方向上平均地划分成ε份聚类，两次划分产生μ份聚类，该聚类集合组成q'，其中qi.mbr.miny为q中第i个空间聚类的最小边界矩形的最小y方向坐标，δ≤μ<len(q)，len(q)表示空间聚类集合q中空间聚类个数，集合q中的聚类为集合q'中聚类的子节点，用空间聚类集合q'替换空间聚类集合q，转到步骤3.2；

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

步骤4中的节点对为从无权无向网络中随机采样的个节点对，其中n＝1000为网络节点总数；

预设搜索k＝3条路径，调整路径跳数参数τ和路径似然使得超圆周满足两个条件：

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

所述的超圆周指双曲空间中到某条测地线l距离为给定值ρ的点的集合，测地线l称为超圆周的轴，ρ>0是任意给定的正数，ρ称为超圆周的半径，具体地，设l是一条给定的双曲测地线，记d(z,l)是点z到l的双曲距离，则集合为关于l的一个超圆域，在单位庞加莱圆盘中，超圆域的边界是两条欧氏圆弧，称为超圆周，表示二维双曲空间；

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

其中，t、r为步骤2中所述的双曲随机几何图模型参数，τ为路径跳数参数和为路径似然参数，s,t为采样的节点对，表示无权无向网络的第s个节点和第t个节点，d(s,t)表示无权无向网络的第s个节点和第t个节点双曲嵌入后的双曲距离，通过下式计算：

d(s,t)＝cosh^-1(coshrscoshrt-sinhrssinhrtcosδθst),

其中，δθst＝π-|π-|θs-θt||，rs为无权无向网络双曲嵌入后第s个节点的径坐标，rt为无权无向网络双曲嵌入后第t个节点的径坐标，θs为无权无向网络第s个节点优化调整后的双曲嵌入角坐标，θt为无权无向网络第t个节点优化调整后的双曲嵌入角坐标；

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

根据超圆周与步骤3中构建的搜索树tree({(x1,y1),(x2,y2),…,(xn,yn)})查询，获得超圆周内部的节点集合v'，具体查询方法如下：

遍历搜索树tree({(x1,y1),(x2,y2),…,(xn,yn)})中的非叶子节点的最小边界矩形，找出与超圆周的最小边界矩形存在重叠的搜索树非叶子节点的最小边界矩形，收集这些非叶子节点对应叶子节点上存储的所有空间对象，取出在超圆周内部的空间对象，组成节点集合v'，根据v'和无权无向网络g＝(v,e)得到点导出子图，该点导出子图即超圆周内部子网，所述的点导出子图表示以v'为节点集合，以g中两端点均属于v'的所有边作为边集所组成的子图；

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

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

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

tree({(x1,y1),(x2,y2),…,(xn,yn)})，所述的超圆周为步骤5中计算得到的超圆周，所述的点导出子图表示以v'为节点集合，以g中两端点均属于v'的所有边作为边集所组成的子图，其中v'为超圆周内部节点集合；

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

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

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

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

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

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

技术特征：

1.一种基于双曲嵌入的网络多路径搜索方法，其特征在于，包含以下步骤：

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

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

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

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

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

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

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

2.根据权利要求1所述的基于双曲嵌入的网络多路径搜索方法，其特征在于，

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

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

g＝(v，e)

其中，v＝{v1，v2，...，vn}表示无权无向网络中节点的集合，vi表示无权无向网络中第i个节点，i∈[1，n]，无权无向网络共有n个节点；

e表示无权无向网络连边的集合，连边ei，j＝(vi，vj)∈e表示无权无向网络中第i个节点和第j个节点间连边，i∈[1，n]，j∈[1，n]，节点vi和vj称为边ei，j的端点；

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

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

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

其中，aij表示无权无向网络中第i个节点与无权无向网络中第j个节点相邻的次数，在无权无向网络中，aij＝1表示无权无向网络中第i个节点和无权无向网络中第j个节点间有连边，aij＝0表示第i个节点和第j个节点间无连边；

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

其中，i∈[1，n]，j∈[1，n]，n为无权无向网络节点总数，deg(vi)为无权无向网络中第i个节点的度，所述的节点的度表示与该节点相连接的边的数目。

3.根据权利要求1所述的基于双曲嵌入的网络多路径搜索方法，其特征在于，

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

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

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

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

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

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

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

步骤2.5，计算网络g1的聚集系数

步骤2.6，若输出当前参数t、r、γ为最终估计参数，若使用二分法调整参数t，转到步骤2.3，，其中为预设的误差阈值；

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

其中，ri表示无权无向网络嵌入到双曲空间后的第i个节点的径坐标，r为无权无向网络双曲嵌入后扩展庞加莱圆盘的最大半径，t∈(0，1]为温度系数，控制网络聚集系数，t越大网络聚集系数越小，γ为网络度分布幂指数，|v|为网络节点总数，deg(vi)表示无权无向网络中第i个节点的度；

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

l＝d-a，其中，d为无权无向网络的度矩阵，a为无权无向网络的邻接矩阵；

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

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

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

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

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

定义n×d大小的矩阵z，矩阵的行向量zi表示无权无向网络中第i个节点在d维欧氏空间中的向量表示，优化问题为：

s.t.z^tdz＝i.

其中，ai，j为无权无向网络的邻接矩阵第i行第j列的元素，d为无权无向网络的度矩阵，i为单位矩阵；

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

由于此处欧氏空间为2维，取最小的两个非零特征值对应的特征向量z1＝(z11，z12，...，z1n)，z2＝(z21，z22，...，z2n)，其中，n为无权无向网络的节点总数，则无权无向网络拉普拉斯特征映射后第i个节点的直角坐标为(z1i，z2i)，i∈[1，n]；

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

对于无权无向网络中的每个节点i∈[1，n]，在其双曲嵌入的初始角坐标附近采样个角坐标将采样得到的角坐标代入对数似然函数计算得到取对数似然值最大的角坐标为网络优化调整后双曲嵌入角坐标，即

其中，表示向下取整，φi，t表示无权无向网络中第i个节点的第t个采样角坐标，表示无权无向网络中第i个节点的第t个采样角坐标计算得到的对数似然值，n为无权无向网络的节点总数，θi为无权无向网络中第i个节点优化调整后双曲嵌入角坐标；

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

其中，aij为邻接矩阵第i行第j列元素，pij为无权无向网络中第i个节点与第j个节点间的连接概率，其表达式为：

其中，r、t为步骤2中获取的双曲随机几何图模型参数，d(vi，vj)表示无权无向网络双曲嵌入后第i个节点与第j个节点间的双曲距离，通过下式计算：

d(vi，vj)＝cosh^-1(coshricoshrj-sinhrisinhrjcosδθij)，

其中，δθij＝π-|π-|θi-θj||，ri为无权无向网络双曲嵌入后第i个节点的径坐标，rj为无权无向网络双曲嵌入后第j个节点的径坐标，θi为无权无向网络双曲嵌入后第i个节点的角坐标，θj为无权无向网络双曲嵌入后第j个节点的角坐标。

4.根据权利要求1所述的基于双曲嵌入的网络多路径搜索方法，其特征在于，

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

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

{r1，r2，...，rn}

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

{θ1，θ2，...，θn}，

其中，ri为无权无向网络双曲嵌入后第i个节点的径坐标，θi为网络优化调整后第i个节点的双曲嵌入角坐标，n为网络节点总数，i∈[1，n]；

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

转化后的直角坐标为：

{(x1，y1)，(x2，y2)，...，(xn，yn)}

其中，xi为无权无向网络双曲嵌入后第i个节点的x轴坐标，yi为无权无向网络双曲嵌入后第i个节点的y轴坐标，n为网络节点总数，i∈[1，n]；

将转化后的直角坐标通过几何数据结构构造搜索树tree({(x1，y1)，(x2，y2)，...，(xn，yn)})；

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

步骤3.1：定义搜索树为tree({(x1，y1)，(x2，y2)，...，(xn，yn)})，{s1，s2，...，sn}＝{(x1，y1)，(x2，y2)，...，(xn，yn)}为搜索树tree的空间对象集合，该集合由前述无权无向网络双曲嵌入后所有节点坐标转换后的直角坐标组成，si＝(xi，yi)为搜索树tree的第i个空间对象，定义si.mbr为第i个空间对象的最小边界矩形，n为网络节点总数；

初始化搜索树的空间聚类集合q＝{q1，q2，...，qn}，其中，qi为q中的第i个空间聚类，qi仅包含一个空间对象si＝(xi，yi)，对应于无权无向网络双曲嵌入后第i个节点坐标转换后的直角坐标，令qi.mbr＝si.mbr为q中第i个空间聚类的最小边界矩形，n为网络节点总数，i∈[1，n]，设定tree的参数阈值为m，表示一个非叶子节点所包含的最大子节点数量，

步骤3.2：表示空间聚类集合q需要被划分成δ个聚类，表示向上取整，len(q)表示空间聚类集合q中空间聚类个数，如果δ＝1，则将空间聚类集合q聚类成一个根节点root，qi为root节点的子节点，搜索树tree({(x1，y1)，(x2，y2)，...，(xn，yn)})构建完成，如果δ＞1，则执行步骤3.3，

步骤3.3：计算ε表示每个聚类在直角坐标系x方向和y方向上划分的份数，表示向上取整，对空间聚类集合q按照qi.mbr.minx在直角坐标系x方向递增排序，将其在x方向上平均地划分成ε份聚类，其中qi.mbr.minx为q中第i个空间聚类的最小边界矩形的最小x方向坐标，然后对每份聚类结果在y方向上按照qi.mbr.miny排序，将其在y方向上平均地划分成ε份聚类，两次划分产生μ份聚类，该聚类集合组成q′，其中qi.mbr.miny为q中第i个空间聚类的最小边界矩形的最小y方向坐标，δ≤μ＜len(q)，len(q)表示空间聚类集合q中空间聚类个数，集合q中的聚类为集合q′中聚类的子节点，用空间聚类集合q′替换空间聚类集合q，转到步骤3.2。

5.根据权利要求书1所述基于双曲嵌入的网络多路径搜索方法，其特征在于，

步骤4中的节点对为从无权无向网络中随机采样的个节点对，其中n为网络节点总数；

预设搜索k条路径，调整路径跳数参数τ和路径似然使得超圆周满足两个条件：

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

所述的超圆周指双曲空间中到某条测地线l距离为给定值ρ的点的集合，测地线l称为超圆周的轴，ρ＞0是任意给定的正数，ρ称为超圆周的半径，具体地，设l是一条给定的双曲测地线，记d(z，l)是点z到l的双曲距离，则集合为关于l的一个超圆域，在单位庞加莱圆盘中，超圆域的边界是两条欧氏圆弧，称为超圆周，表示二维双曲空间；

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

其中，t、r为步骤2中所述的双曲随机几何图模型参数，τ为路径跳数参数和为路径似然参数，s，t为采样的节点对，表示无权无向网络的第s个节点和第t个节点，d(s，t)表示无权无向网络的第s个节点和第t个节点双曲嵌入后的双曲距离，通过下式计算：

d(s，t)＝cosh^-1(coshrscoshrt-sinhrssinhrtcosδθst)，

其中，δθst＝π-|π-|θs-θt||，rs为无权无向网络双曲嵌入后第s个节点的径坐标，rt为无权无向网络双曲嵌入后第t个节点的径坐标，θs为无权无向网络第s个节点优化调整后的双曲嵌入角坐标，θt为无权无向网络第t个节点优化调整后的双曲嵌入角坐标；

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

根据超圆周与步骤3中构建的搜索树tree({(x1，y1)，(x2，y2)，...，(xn，yn)})查询，获得超圆周内部的节点集合v′，具体查询方法如下：

遍历搜索树tree({(x1，y1)，(x2，y2)，...，(xn，yn)})中的非叶子节点的最小边界矩形，找出与超圆周的最小边界矩形存在重叠的搜索树非叶子节点的最小边界矩形，收集这些非叶子节点对应叶子节点上存储的所有空间对象，取出在超圆周内部的空间对象，组成节点集合v′，根据v′和无权无向网络g＝(v，e)得到点导出子图，该点导出子图即超圆周内部子网，所述的点导出子图表示以v′为节点集合，以g中两端点均属于v′的所有边作为边集所组成的子图。

6.根据权利要求书1所述基于双曲嵌入的网络多路径搜索方法，其特征在于，

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

tree({(x1，y1)，(x2，y2)，...，(xn，yn)})，所述的超圆周为步骤5中计算得到的超圆周，所述的点导出子图表示以v′为节点集合，以g中两端点均属于v′的所有边作为边集所组成的子图，其中v′为超圆周内部节点集合。

7.根据权利要求书1所述基于双曲嵌入的网络多路径搜索方法，其特征在于，

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

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

技术研发人员：江昊;王强;聂琦;羿舒文;彭姿文
受保护的技术使用者：武汉大学
技术研发日：2021.04.12
技术公布日：2021.08.03