[發明專利]一種基于局部拓撲信息和社團相關性的鏈路預測方法

在審

• 申請號: 201710260562.3
• 申請日: 2017-04-20
• 公開（公告）號: CN107248923A
• 公開（公告）日: 2017-10-13
• 發明（設計）人: 楊清海;席敏燕
• 申請（專利權）人: 西安電子科技大學;西安中電科西電科大雷達技術協同創新研究院有限公司
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 西安長和專利代理有限公司61227
• 代理人: 黃偉洪

1.一種基于局部拓撲信息和社團相關性的鏈路預測方法，其特征在于，所述基于局部拓撲信息和社團相關性的鏈路預測方法利用節點之間局部拓撲信息計算節點之間的相似性值；當兩個節點處于同一個社團時，社團相關性為最大值，當兩個節點處于不同社團時，在考慮局部拓撲信息的基礎上，將節點之間的相似性轉化為兩個社團之間的相關性，然后計算兩個社團之間的相關性值；最后綜合考慮局部拓撲信息和社團相關性的影響進行鏈路預測；

所述基于局部拓撲信息和社團相關性的鏈路預測方法在無權無向的復雜網絡中進行；用A表示鄰接矩陣，如果節點i和節點j有聯系，那么A的第i行第j列上的值為A_ij＝1，否則A_ij＝0；節點的度被定義為網絡中所有與該節點直接相連的節點的個數，節點i的度通常被記為k_i，可以用公式表示；定義：Γ(x)為x的鄰居集合，其中x可以是節點也可以是社團。

2.如權利要求1所述的基于局部拓撲信息和社團相關性的鏈路預測方法，其特征在于，所述基于局部拓撲信息和社團相關性的鏈路預測方法包括以下步驟：

步驟一，建立網絡模型G(V,E),V＝{v₁,v₂,...v_n}為網絡中的節點集合，E＝{(v_x,v_y)|v_x∈V,v_y∈V}代表邊的集合，基于網絡模型生成鄰接矩陣A，其中

步驟二，網絡被劃分成四個社團，記為C＝{c₁,c₂,c₃,c₄}，其中V(c₁)＝{1,2,3,4}，V(c₂)＝{5,6,7,8,9}，V(c₃)＝{10,11,12,13}，V(c₄)＝{14,15,16,17}；

步驟三，將網絡中所有的節點對(i,j)挑選出來作為候選節點對；

步驟四，利用候選節點對之間的局部拓撲信息計算步驟三所述的節點對之間的相似性值，因為這兩對節點都沒有共同鄰居，所以用局部拓撲信息計算出來的兩對節點的相似性值都為0；

步驟五，計算步驟三所述的節點對所在社團的社團相關性；

步驟六，綜合考慮局部拓撲信息和社團相關性對節點相似性的影響，重新計算候選節點對之間的相似性值S_u,v；采用公式因此節點5和節點10之間的相似性比節點10和節點14之間的相似性高；

步驟七，重復步驟四至步驟六，計算每個節點對的相似性值，并將相似性值按降序排列，構建相似性列表；

步驟八，根據某種相似性準則，獲取相似性列表中前N個節點對，這些排在前N個的節點對即為本鏈路預測方法得出的最有可能在未來產生連邊的節點對，其中N為正整數。

3.如權利要求2所述的基于局部拓撲信息和社團相關性的鏈路預測方法，其特征在于，所述步驟五中具體過程如下：

(1)分別找到候選節點5和10所在的社團c₂和c₃；

(2)計算V(c₂)＝{5,6,7,8,9}，Γ(c₂)＝{3,10}，因此Γ(c₂)∪V(c₂)＝{3,5,6,7,8,9,10}；

(3)同上，求出Γ(c₃)∪V(c₃)＝{4,7,10,11,12,13}；

(4)計算社團c₂和c₃的社團相關性為

(5)對(4)中的社團相關性進行歸一化，結果為

同理，可得到節點10和節點14分別屬于社團c₃和社團c₄，這兩個社團歸一化之后的社團相關性為

4.一種利用權利要求1～3任意一項所述基于局部拓撲信息和社團相關性的鏈路預測方法的預測的鏈路。