[發明專利]一種基于KNN的有效鏈路預測方法

在審

• 申請號: 202010132439.5
• 申請日: 2020-02-27
• 公開（公告）號: CN111310849A
• 公開（公告）日: 2020-06-19
• 發明（設計）人: 李龍杰;王輝;單娜;陳曉云
• 申請（專利權）人: 蘭州大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06Q10/04;G06Q50/00
• 代理公司: 成都弘毅天承知識產權代理有限公司 51230
• 代理人: 楊保剛

1.一種基于KNN的有效鏈路預測方法，其特征在于：主要包括依次進行的以下步驟，

步驟1：在網絡中選取測試集和訓練集，其中訓練集分為有邊訓練集和無邊訓練集，選取網絡中至少一個重要特征，對訓練集中的節點對分別構造特征向量；

步驟2：每給出一個測試節點對時，對測試節點對構造相同的特征向量，并分別計算與兩個訓練集中節點對的向量距離，取距離最小的前K組節點對，生成中心特征向量；

步驟3：分別計算測試節點對與有邊節點對中心特征向量及無邊節點對中心特征向量的距離；

步驟4：運用TOPSIS方法，得到測試節點對有邊可能性分數。

2.根據權利要求1所述的一種基于KNN的有效鏈路預測方法，其特征在于：所述步驟1中選取的重要特征為五個，分別是兩個節點的共同鄰居的數量CN、基于資源分配的思想而提出的鏈路預測相似性指標RA、一條邊連接到一個節點的概率正比于該節點的度PA、共同鄰居CN的基礎上考慮兩端節點度的影響JC、兩節點路徑長度為3的路徑個數3-hop。

3.根據權利要求2所述的一種基于KNN的有效鏈路預測方法，其特征在于：假設網絡中的兩個節點為v_i和v_j，v_i通過它們的共同鄰居向v_j傳遞資源，k_i、K_j分別是節點v_i、v_j的度，k_z是節點v_i、v_j的共同鄰居節點z的度，則所述CN、RA、PA、JC和3-hop分別表示為：

Sim_CN(v_i,v_j)＝|Γ(v_i)∩Γ(v_j)| (1)

4.根據權利要求2或3所述的一種基于KNN的有效鏈路預測方法，其特征在于：基于CN、RA、PA、JC和3-hop五個重要特征，所述的一種基于KNN的有效鏈路預測方法主要包括依次進行的以下步驟，

步驟1-1：將復雜網絡選取測試集E_p、有邊訓練集E_t和無邊訓練集對測試集E_p和訓練集E_t、中的每一個節點對求由CN、RA、PA,JC和3-hop五種局部指標構成的特征向量；

步驟2-1：對測試集E_p中的每一條邊，分別與訓練集E_t、的每一條邊計算特征向量的歐氏距離，分別取出距離最小的前K個節點對作為K近鄰節點對；

步驟3-1：對2組K近鄰節點對的特征向量分別計算其K近鄰中心節點對特征向量，而后分別計算當前測試節點對與2個中心節點對特征向量的歐式距離，分別記為d⁺,d^-。

步驟4-1：由TOPSIS方法的啟發，將最終的相似性分數定義為Sim(u.v)＝d⁺/(d⁺+d^-)，對測試集E_p中每一個節點對分別計算其相似性分數，得到最終的分數排名，分數越大，該測試節點對有邊的可能性就越高。