[發明專利]一種鏈路預測方法及裝置

有效

• 申請號: 201711481642.8
• 申請日: 2017-12-29
• 公開（公告）號: CN109993338B
• 公開（公告）日: 2021-08-06
• 發明（設計）人: 李宙洲
• 申請（專利權）人: 中移（蘇州）軟件技術有限公司;中國移動通信集團公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/00
• 代理公司: 北京同達信恒知識產權代理有限公司 11291
• 代理人: 郭潤湘

1.一種鏈路預測方法，其特征在于，包括：

將待預測的網絡劃分成多個社團，其中，任一個社團包含多個網絡節點；

通過以下步驟，確定任一個社團中的第一網絡節點和第二網絡節點之間的連接概率，其中所述第一網絡節點和所述第二網絡節點為所述社團中任一對未連接的網絡節點：

確定所述第一網絡節點與至少一個第三網絡節點中每個第三網絡節點之間的第一結構相似度，以及確定所述第二網絡節點與至少一個第四網絡節點中每個第四網絡節點之間的第二結構相似度；其中，所述至少一個第三網絡節點為所述第二網絡節點的鄰居節點，所述至少一個第四網絡節點為所述第一網絡節點的鄰居節點；

根據確定的至少一個第一結構相似度和至少一個第二結構相似度確定所述第一網絡節點和所述第二網絡節點之間的連接概率；

其中，確定所述第一網絡節點與任一個第三網絡節點之間的第一結構相似度，以及確定所述第二網絡節點與任一個第四網絡節點之間的第二結構相似度，包括：根據所述第一網絡節點與該第三網絡節點之間的第一共同鄰居節點個數、所述第一網絡節點的第一鄰居節點個數和該第三網絡節點的第二鄰居節點個數，確定所述第一網絡節點和該第三網絡節點之間的第一結構相似度；以及，根據所述第二網絡節點與該第四網絡節點之間的第二共同鄰居節點個數、所述第二網絡節點的第三鄰居節點個數和該第四網絡節點的第四鄰居節點個數，確定所述第二網絡節點和該第四網絡節點之間的第二結構相似度。

2.如權利要求1所述的方法，其特征在于，所述方法還包括：

根據所述社團中的多個網絡節點之間的連接關系，確定鄰接矩陣；

將所述鄰接矩陣自相乘，得到第一中間矩陣，所述第一中間矩陣指示所述社團中的多個網絡節點中每兩個網絡節點之間的共同鄰居節點個數；

將所述鄰接矩陣的每行中的值相加，得到第二中間矩陣，所述第二中間矩陣指示所述社團中的每個網絡節點的鄰居節點個數；

根據所述第一中間矩陣確定所述第一網絡節點與該第三網絡節點之間的所述第一共同鄰居節點個數，根據所述第二中間矩陣確定所述第一網絡節點的所述第一鄰居節點個數和該第三網絡節點的所述第二鄰居節點個數；以及

根據所述第一中間矩陣確定所述第二網絡節點與該第四網絡節點之間的所述第二共同鄰居節點個數，根據所述第二中間矩陣確定所述第二網絡節點的所述第三鄰居節點個數和該第四網絡節點的所述第四鄰居節點個數。

3.如權利要求1或2所述的方法，其特征在于，確定任兩個網絡節點之間的結構相似度Sim_x,y，符合以下公式：

其中，A為網絡節點x和網絡節點y之間的共同鄰居節點個數；D(x)為網絡節點x的鄰居節點個數；D(y)為網絡節點y的鄰居節點個數。

4.如權利要求1或2所述的方法，其特征在于，確定所述第一網絡節點和所述第二網絡節點之間的連接概率S_a,b，符合以下公式：

其中，Γ(a)為第一網絡節點a的鄰居節點集合；Γ(b)為第二網絡節點b的鄰居節點集合；c為Γ(a)中任一個網絡節點；d為Γ(b)中任一個網絡節點；Sim_a,c為所述第一網絡節點a與網絡節點c之間的結構相似度；Sim_b,d為所述第二網絡節點b與網絡節點d之間的結構相似度。

5.如權利要求1或2所述的方法，其特征在于，在確定所述第一網絡節點和所述第二網絡節點之間的連接概率之后，還包括：

確定所述連接概率的準確度。