[發(fā)明專利]一種基于雙曲嵌入的網絡多路徑搜索方法

在審

• 申請?zhí)枺?/td>: 202110388656.5
• 申請日: 2021-04-12
• 公開（公告）號: CN113204677A
• 公開（公告）日: 2021-08-03
• 發(fā)明（設計）人: 江昊;王強;聶琦;羿舒文;彭姿文
• 申請（專利權）人: 武漢大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/906;G06F17/16;G06Q10/04
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 許蓮英

本發(fā)明提供了一種基于雙曲嵌入的網絡多路徑搜索方法。本發(fā)明輸入無權無向網絡；借助于雙曲隨機幾何圖模型完成雙曲嵌入，獲得網絡節(jié)點表征向量；通過網絡節(jié)點表征向量構造幾何搜索樹并借助于雙曲空間超圓周獲取網絡中每對節(jié)點間的主干通信子網；最終在該子網中完成完全不相交或部分不相交的多路徑搜索。本發(fā)明通過將網絡嵌入到雙曲空間中，利用雙曲空間的負常數(shù)曲率，高效表征近似樹狀的網絡結構，本發(fā)明的方法避免了多路徑的全局拓撲搜索，該方法在保證搜索成功率的同時，顯著降低傳統(tǒng)算法的搜索空間，提高了搜索效率。

技術領域

本發(fā)明屬于復雜網絡分析和通信技術領域，具體涉及一種基于雙曲嵌入的網絡多路徑搜索方法。

背景技術

網絡是一種描述實體與實體之間關系的有效方法。許多天然的和人工的復雜網絡都是多路徑信息路由的范例，例如，互聯(lián)網、社會網絡、腦神經網絡和流行病傳播網絡等等。特別是多路徑路由已經成為Internet上一種無處不在的技術，它被用來促進網絡的生存性，支撐多路徑傳輸，保證服務質量，平衡流量負載，采用流量工程方法來優(yōu)化網絡資源利用率。這些應用的一個基本問題是如何找到多條不相交路徑，包括完全不相交的最短路徑和部分不相交的最短路徑。

目前，求解多條完全不相交的最短路徑問題主要通過網絡最大流方法，部分不相交的最短路徑問題主要借助于增廣路徑和殘留網絡技術。

現(xiàn)有技術存在以下問題：傳統(tǒng)的基于圖的算法需要全局拓撲結構，才能充分利用路徑多樣性。因此，這類算法在大規(guī)模網絡中可能會導致很高的開銷。為了有效地利用局部拓撲并減少不必要的開銷，最近的部分研究從經典圖論轉向了基于幾何的模型，如雙曲隨機幾何圖。現(xiàn)有的研究已經表明，僅使用雙曲隨機幾何圖上的局部信息就可高效搜索兩個節(jié)點之間的單一路徑。然而，由于這些方法大多只獲得一條無約束的近似最短路徑，因此并不能直接將它們應用于多條路徑的搜索任務。

發(fā)明內容

本發(fā)明針對現(xiàn)有技術的不足，提供一種基于雙曲嵌入的網絡多路徑搜索方法，以解決現(xiàn)有技術需要搜索網絡全局拓撲獲取多路徑而存在開銷大的問題。

本發(fā)明的技術方案提供了一種基于雙曲嵌入的網絡多路徑搜索方法，包含以下步驟：

步驟1，構建無權無向網絡；

步驟2，估計雙曲隨機幾何圖模型參數(shù)，根據(jù)無權無向網絡中節(jié)點度結合雙曲隨機幾何圖模型參數(shù)獲取無權無向網絡嵌入到雙曲空間后的徑坐標，構建網絡的拉普拉斯矩陣，利用拉普拉斯特征映射方式獲取無權無向網絡嵌入到雙曲空間后的初始角坐標，進一步采用最大似然估計方法調整無權無向網絡嵌入到雙曲空間后的初始角坐標，獲得網絡優(yōu)化調整后雙曲嵌入角坐標；

步驟3，基于無權無向網絡嵌入到雙曲空間后的徑坐標和網絡優(yōu)化調整后雙曲嵌入角坐標結合幾何數(shù)據(jù)結構構建搜索樹；

步驟4，采樣網絡中部分節(jié)點對，調整路徑跳數(shù)參數(shù)和路徑似然參數(shù)，使得計算得到的超圓周內子網盡可能小同時覆蓋盡可能多節(jié)點對間的路徑；

步驟5，根據(jù)路徑跳數(shù)參數(shù)、路徑似然參數(shù)和待計算的源目的節(jié)點對求取超圓周；

步驟6，利用超圓周查詢搜索樹，獲取超圓周內部的點導出子圖；

步驟7，最終在該點導出子圖上搜索節(jié)點間多路徑，多路徑可為完全不相交路徑或部分不相交路徑；

作為優(yōu)選，步驟1中所述的無權無向網絡為無權無向簡單圖，且符合冪律度分布；

步驟1中所述的無權無向網絡的定義為：

G＝(V,E)

其中，V＝{v₁,v₂,…,v_N}表示無權無向網絡中節(jié)點的集合，v_i表示無權無向網絡中第i個節(jié)點，i∈[1,N]，無權無向網絡共有N個節(jié)點；