[發明專利]基于線性規劃的有向網絡鏈路預測方法

在審

• 申請號: 202010913525.X
• 申請日: 2020-09-03
• 公開（公告）號: CN112183820A
• 公開（公告）日: 2021-01-05
• 發明（設計）人: 劉樹新;李星;李勁松;王凱;李英樂;朱宇航;何贊園;王庚潤;衛紅權;陳鴻昶;馬宏
• 申請（專利權）人: 中國人民解放軍戰略支援部隊信息工程大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06K9/62
• 代理公司: 鄭州大通專利商標代理有限公司 41111
• 代理人: 石丹丹

1.一種基于線性規劃的有向網絡鏈路預測方法，其特征在于，包含以下步驟：

步驟1，根據網絡類型與先驗信息確定可調參數的取值，引入可調參數區分不同鄰居節點的信息傳輸能力；

步驟2，利用步驟1的可調參數構建原始有向網絡的有向含權同質網絡；

步驟3，基于線性規劃計算最優的鄰居節點貢獻矩陣；

步驟4，根據步驟3得到的最優的鄰居節點貢獻矩陣，計算相似度矩陣；

步驟5，按相似度大小進行排序，取前若干條邊作為最終預測邊。

2.根據權利要求1所述的基于線性規劃的有向網絡鏈路預測方法，其特征在于，在所述步驟1之前，還包括：

對目標網絡進行預處理，包括去除連邊權重、自環、重復連邊和孤立節點，得到原始網絡的無權同質拓撲結構，作為待處理網絡。

3.根據權利要求2所述的基于線性規劃的有向網絡鏈路預測方法，其特征在于，在對目標網絡進行預處理之后，還包括：

對待處理網絡中的連邊按照比例f進行隨機劃分，其中一部分作為訓練集，另一部分作為測試集，訓練集與測試集中的連邊數量之比為f:(1-f)，其中f為數據集劃分比例。

4.根據權利要求1所述的基于線性規劃的有向網絡鏈路預測方法，其特征在于，所述步驟2中的原始有向網絡為D(V,E)，其中V和E分別為節點集合和連邊集合，用N＝|V|表示節點數，M＝|E|表示連邊數，A＝{a_ij}_N×N表示鄰接矩陣，e(x,y)表示由節點x到節點y的一條有向邊。

5.根據權利要求4所述的基于線性規劃的有向網絡鏈路預測方法，其特征在于，原始有向網絡D(V,E)中某節點x∈V具有三種類型鄰居，分別為連入鄰居、連出鄰居和互惠鄰居，其節點集合分別用Γ_in(x)、Γ_out(x)、Γ_recip(x)表示，且滿足Γ(x)＝Γ_out(x)∪Γ_in(x)∪Γ_recip(x)。

6.根據權利要求5所述的基于線性規劃的有向網絡鏈路預測方法，其特征在于，所述引入可調參數α區分三種鄰居節點的信息傳輸能力，其中出度節點的傳輸能力為1，入度節點的傳輸能力為α，互惠節點的傳輸能力為1+α。

7.根據權利要求6所述的基于線性規劃的有向網絡鏈路預測方法，其特征在于，所述構建原始有向網絡的有向含權同質網絡具體為：

構建原始有向網絡D(V,E)的有向含權同質網絡D′(V,E,W)，其中W＝{w_ij}_N×N為網絡含權鄰接矩陣，滿足：

8.根據權利要求7所述的基于線性規劃的有向網絡鏈路預測方法，其特征在于，所述計算最優的鄰居節點貢獻矩陣具體為：

首先，對于有向含權同質網絡D′(V,E,W)，e(x,y)形成的可能性正比于節點x的所有鄰居貢獻之和，即：

其中，s_xy表示節點x與節點y之間連邊概率，c_zy表示節點z對節點y的貢獻值，節點z是節點x和節點y的共同鄰居節點；

然后，相應的臨時相似度矩陣S表示為：

S＝AC+αA^TC＝WC

其中C為待求鄰居節點貢獻矩陣；

最后，利用線性規劃求解最優的鄰居節點貢獻矩陣。