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

在審

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

1.一種基于雙曲嵌入的網絡多路徑搜索方法，其特征在于，包含以下步驟：

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

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

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

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

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

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

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

2.根據權利要求1所述的基于雙曲嵌入的網絡多路徑搜索方法，其特征在于，

步驟1中所述的無權無向網絡為無權無向簡單圖，且符合冪律度分布；

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

G＝(V，E)

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

E表示無權無向網絡連邊的集合，連邊e_i，j＝(v_i，v_j)∈E表示無權無向網絡中第i個節點和第j個節點間連邊，i∈[1，N]，j∈[1，N]，節點v_i和v_j稱為邊e_i，j的端點；

|V|為集合V的勢，表示無權無向網絡節點總數，其值等于N；

|E|為集合E的勢，表示無權無向網絡連邊總數；

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

其中，a_ij表示無權無向網絡中第i個節點與無權無向網絡中第j個節點相鄰的次數，在無權無向網絡中，a_ij＝1表示無權無向網絡中第i個節點和無權無向網絡中第j個節點間有連邊，a_ij＝0表示第i個節點和第j個節點間無連邊；

步驟1中所述的無權無向網絡的度矩陣為N×N的對角矩陣，其定義為：

其中，i∈[1，N]，j∈[1，N]，N為無權無向網絡節點總數，deg(v_i)為無權無向網絡中第i個節點的度，所述的節點的度表示與該節點相連接的邊的數目。