[發明專利]一種基于雙曲幾何的有向網絡空間嵌入方法

在審

• 申請號: 202010016003.X
• 申請日: 2020-01-08
• 公開（公告）號: CN111209611A
• 公開（公告）日: 2020-05-29
• 發明（設計）人: 吳宗檸;狄增如;樊瑛
• 申請（專利權）人: 北京師范大學
• 主分類號: G06F30/10
• 分類號: G06F30/10
• 代理公司: 江蘇海越律師事務所 32402
• 代理人: 唐小紅

1.一種基于雙曲幾何的有向網絡空間嵌入方法，其特征在于，步驟如下：

步驟1.根據有向網絡的二分結構檢驗雙曲空間嵌入基礎：

1-1)依據雙曲幾何理論，一個復雜網絡用矩陣表示為A＝{a_ij}_n×n，其幾何描述其度分布的冪率指數需要滿足條件，即p(k)～k^-γ，γ＞2.1，其中，k表示網絡中節點的度節點度概率分布函數為p(k)，度分布的冪指數γ；

1-2)若網絡度分布不滿足冪律分布，則需要采用網絡骨架提取的方法，識別網絡中的關鍵連接關系；根據連邊權重大小進行降序排序，從后往前依次刪去權重小的連邊且保證網絡沒有孤立點的存在；重復上述結果，并每一步記錄下當前邊數(L_B)與原始邊數(L₀)的比值：(L_B/L₀)和當前節點數(L_B)與原始節點數L₀的比值：N_B/N₀，并將其為坐標軸繪制散點圖；

步驟2.根據有向網絡的二分結構構建模型

2-1)構建網絡模型：在雙曲空間中，節點有四個坐標r_ai,r_bj,θ_ai,θ_bj分別表示出方向和入方向的流行性r和相似性θ，基于有向網絡形成機制，出方向和入方向的相似性和流行性越大，有向邊越容易形成連邊；由此，模型由公式(1)給出：

f(x_ai,bj)＝(1+x_ai,bj^β)^-1 (1)

有向邊的相異權重：x_ai,bj＝r_ai+r_bj+2d_ai,bj (2)

有向邊的角相似性：d_ai,bj＝min(|π-|θ_ai-θ_bj||) (3)

其中，β是控制網絡集聚性的參數，公式中的下標ai表示的是點集A的i節點，在具體系統中，有向邊的相異權重表示的是節點間的空間拓撲距離，而角相似性則反映了節點間相似性的一種度量方式；

2-1)根據隱藏空間和雙曲空間的同構性質，節點的流行性坐標r有節點期望度κ_ai和κ_bi表征，即：

r_ai＝R-ln(κ_ai/κ_a0) (4)

最小的期望度：

其中，R為雙曲龐加萊圓盤半徑，和γ_i分別表示i節點的平均出度或平均入度，出度或入度分布的冪律關系指數，即p(k)～k^-γ,結果在雙對數坐標下擬合；

步驟3.使用最大期望算法進行參數估計：

3-1)隱藏度量空間和雙曲空間的同構性質，將求解流行性和相似性坐標的任務轉化為對隱藏變量和角度坐標的推斷，參數估計是通過給定鄰接矩陣拓撲信息，從而找到與最匹配的雙曲空間坐標，該過程服從貝葉斯公式：

將上式，對數線性化得到模型的似然函數：

3-2)根據似然函數求解節點空間流行性徑向坐標，通過求偏導，極大化條件概率期望函數ln L:

其中，下標*指的是集合*中節點的統計性質，如平均度，β是與控制網絡集聚系數的參數，采用節點共同鄰居數的分布指數作為的估計，即p(m)～m^-β；

3-3)由于求偏導而極大化條件概率似然函數無法得到角坐標的解析解，采用近似最大化方法求解節點空間相似性角坐標：

定義節點的*i的似然函數則整個雙曲網絡的似然值為：

節點角坐標在0,2π隨機選取，依次訪問節點；當節點*i被訪問時，將移動到使其似然值最大的角坐標上，并在訪問其他節點時仍固定在角坐標上；節點移動會導致其他節點的似然值發生變化，但是節點的似然值受節點鄰居的坐標影響；

步驟4.基于節點空間坐標定義節點距離和有向網絡可視化：

4-1)對稱雙曲距離，具有高r_ai的節點傾向于生成與具有高r_bj的節點的鏈路，混合x_ai,bj和x_bj,ai定義了對稱雙曲距離，即

x_ij＝x_ai,bj+x_bj,ai (13)

4-2)基于雙曲空間坐標的有向網絡可視化方法，節點在空間中的分布由于模型定義具有如下特點：

4-2-1)節點距離中心的距離表示節點的流行性r；

4-2-2)節點的相對位置表示節點間的相似性，即節點間空間位置越近，則表示節點越相似且具有更高的鏈接可能性。

2.如權利要求1所述的方法，其特征在于，在步驟1-1)中，國家貿易網絡的出度與入度分布的冪指數分別為3.5和2.5；生物神經網絡的出度和入度的冪指數分別為3.42和3。