[發明專利]一種基于元路徑的異構網絡鏈路預測的方法

有效

• 申請號: 201910904558.5
• 申請日: 2019-09-24
• 公開（公告）號: CN110677284B
• 公開（公告）日: 2022-06-17
• 發明（設計）人: 段大高;尹丹琪;韓忠明;楊偉杰;劉文文
• 申請（專利權）人: 北京工商大學
• 主分類號: H04L41/147
• 分類號: H04L41/147;H04L41/14;H04L41/12;G06F16/901;G06N3/04;G06N3/08
• 代理公司: 北京盛詢知識產權代理有限公司 11901
• 代理人: 張海青

1.一種基于元路徑的異構網絡鏈路預測的方法，其特征在于，包括如下步驟：

步驟一、確定是否為異構網絡，所述異構網絡為：如果一個網絡中節點對象的類型|A|1或關系類型|R|1，根據節點類型連接而成不同關系類型，不同的關系類型加節點組建成的即為異構網絡，所述節點類型為不同類型的節點，所述關系類型為不同類型的邊；

構建異構網絡具體方法為：將同一類節點排成一列，有幾種類型的節點就排幾列，在節點列與節點列之間實現連邊，構建出異構網絡G＝(V,E)，在異構網絡中，不同類型節點間組建成一條元路徑P_i，

定義為元路徑，其中V_i∈V,i∈{1,2,…,k},R_i∈R,i∈{1,2,…,k-1},R是節點間關系的集合,即R＝(R₁,R₂,…,R_k-1)；從異構網絡中提取出包含不同關系類型的元路徑，所述元路徑將異構網絡的多種類型的節點和邊建立起聯系，表達出節點的網絡拓撲結構特征；

步驟二、從網絡中提取元路徑：元路徑有不同長度，一條元路徑包含幾個節點即長度為幾，利用棧這種數據結構，枚舉生成所有路徑長度小于5的元路徑；

具體方法為：輸入異構網絡的節點數列V＝(v₁,v₂,…,v_n)和鄰接矩陣A，設定合理的元路徑長度為限制條件，給定起始節點類型，初始化棧，在棧里存放元路徑，若兩個類型節點之間存在連邊，將后者壓入棧，不斷向里壓入合理節點，最長到元路徑長度l5，即每條元路徑包含不超過四個節點對象時結束，棧滿時將站內節點元素組成的元路徑添加到元路徑集合P中，最后輸出給定起始節點的所有的元路徑集合P，則，給定兩類起始節點，兩次棧運算輸出每一類起始節點引導的所有的元路徑集合P＝(P₁,P₂,…,P_n)，生成的元路徑是在有效長度范圍內所有的元路徑，即理論上合理的元路徑；

步驟三、元路徑處理：對獲取到的元路徑做進一步處理，將獲取到的長度小于5的元路徑按長度分類，分為長度為2、3、4的三類元路徑；然后從真實網絡G＝(V,E)中獲取符合元路徑的網絡元路徑實例I＝(I₁,I₂,…,I_n)；一類元路徑包含多個元路徑實例，一個網絡的元路徑實例包含這個網絡的語義信息；起始節點類型已給定，對于長度為2的所有元路徑實例，提取起始節點的一階鄰居；對于長度為3的所有元路徑實例，提取起始節點的二階及以下鄰居；對于長度為4的所有元路徑實例，提取起始節點的三階及以下鄰居；

步驟四、統一節點特征空間：對于網絡中的所有節點做嵌入，向向量轉換，從語義空間到向量空間做映射，同時在向量空間保持原樣本在語義空間的關系；

步驟五、計算節點權重：針對不同長度的元路徑計算路徑上鄰居節點的權重，判斷鄰居節點對起始節點的影響力，用節點度數計算出權重α，鄰居節點的向量表示乘對應的權重α，元路徑上所有鄰居節點表示再聚合起來成為這條元路徑起始節點的向量表示；最后，同一個起始節點的不同長度的元路徑實例有多條，起始節點向量表示來自于每一條元路徑，將所有元路徑的聚合起來就得到最后的起始節點的向量表示；

步驟六、聚合鄰居節點嵌入：同一個起始節點有多條元路徑，考慮鄰居節點的權重，一層層聚合鄰居節點嵌入，得到一條元路徑的起始節點的嵌入，得到每一條元路徑的起始節點嵌入后，再聚合所有起始節點嵌入，得到這一起始節點的最終嵌入；具體來說，同樣長度的同一個起始節點的元路徑實例有多條，每一條都得到一個起始節點的向量表示，聚合所有來自不同元路徑實例的同一個起始節點嵌入，得到這種長度的元路徑的一個起始節點嵌入，最后將不同長度元路徑得到的起始節點嵌入再聚合，就得到最終這一起始節點的嵌入；

步驟七：計算基于元路徑的特征值：基于元路徑的異構信息網絡拓撲特征，主要提取網絡中的結構特征信息；

步驟八：構建鏈路預測模型，計算鏈接概率：預測節點x，y之間可能鏈接的概率公式如下：

其中，Z_x，Z_y是通過聚合獲得的起始節點x，y的最終嵌入，H_xy是包含四種基于元路徑的異構網絡拓撲特征的元路徑綜合特征值，f(·)是只有一個輸出的MLP層，sigmoid(·)是sigmoid層神經網絡的激活函數，將變量映射到0-1之間，是嵌入連接操作；

將節點x的最終嵌入，節點y的最終嵌入和節點間元路徑網絡拓撲特征值的嵌入連接起來融合；最后，將融合嵌入輸入到MLP神經網絡中獲得預測分數

步驟九、預測分數范圍在0-1之間，越高則越有可能連接，則通過分數值大小準確地為用戶提供出感興趣的內容。