[發明專利]一種面向復雜網絡的時序鏈路預測方法

有效

• 申請號: 201710095043.6
• 申請日: 2017-02-22
• 公開（公告）號: CN106934489B
• 公開（公告）日: 2020-10-23
• 發明（設計）人: 徐小龍;胡楠
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/00
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 姜慧勤

本發明公開了一種面向復雜網絡的時序鏈路預測方法，該方法主要針對社交、郵件、科研等節點之間有交互行為的網絡，利用節點之間的交互發生的時間以及頻次預測將來可能發生的交互行為。通過網絡的演化信息，進行較高精度的鏈路預測，并基于整體同步并行計算模型設計本發明的核心步驟。本發明預測方法具有很好的普適性，可以適用于多種社會網絡中的時序鏈路預測；而且本發明預測方法具有良好的可擴展性，可以適用于分布式環境中的時序鏈路預測。

技術領域

本發明涉及一種面向復雜網絡的時序鏈路預測方法，屬于復雜網絡中時序鏈路預測技術領域。

背景技術

目前主流的鏈路預測算法是基于網絡的上一時刻的網絡拓撲結構，然后根據一些節點相似指標，例如共同鄰居指標、資源分配指標等等，計算得到節點之間的相似度，然后根據相似度閾值確定下一時刻鏈路的出現情況。不同于現有的主流預測算法，利用網絡過去一段時間內的網絡演化信息來預測未來的網絡拓撲結構是一個較新的研究方向，這類預測方法更加符合現實中的網絡具有動態特性的真實情況，往往具有較優的鏈路預測精度。此外，目前的鏈路預測算法主要基于矩陣計算的方式實現相似度計算，該方法在單機情況下計算簡便，但是不適用于分布式環境。基于整體同步并行計算(BSP)模型設計算法的計算架構可使得算法運行于主流的分布式數據處理平臺，從而提高算法的擴展性。

鏈路預測算法的性能指標包括準確率、AUC等等。其中，準確率是算法的預測精度的直觀展現，AUC是對算法預測效果的整體考量。一些僅基于上一時刻網絡拓撲結構的鏈路預測算法在網絡平穩演化的時候能夠具有良好的預測精度，不過現實中的網絡往往會因為一些原因產生大幅波動，將導致預測精度大幅下降。還有一些鏈路預測算法利用網絡中的文本語義信息來改進鏈路預測精度，但是由于不同的網絡中文本語義差別比較大，而且文本信息存在難獲取、難以保證正確性等問題，所以利用文本語義的鏈路預測算法不具有普適性且不能保證一定改進鏈路預測效果。此外大多數的鏈路預測算法僅僅考慮“有沒有關系”而忽略了節點之間的鏈路往往是有緊密和疏遠之分，忽略這一層信息也會使得鏈路預測的精度下降。

可見，網絡的動態性和承載的信息的復雜性是鏈路預測技術面臨的重大挑戰，特別是現今社交網絡的快速發展，各類社會網絡承載的信息出現爆炸性增長，且網絡的演化速度加快，對于一種適應于這類應用場景且具有良好擴展性的鏈路預測算法的需求十分迫切。

發明內容

本發明所要解決的技術問題是：提供一種面向復雜網絡的時序鏈路預測方法，該方法能夠利用大規模的、具有動態特性的復雜網絡中的動態演化信息進行時序鏈路預測，并具有良好的擴展性。

本發明為解決上述技術問題采用以下技術方案：

一種面向復雜網絡的時序鏈路預測方法，包括如下步驟：

步驟1，對網絡中所有出現過的節點進行編號，并將編號作為節點自身的id，每個節點的編號唯一；

步驟2，獲取預測時刻過去一段時間內，網絡中所有節點之間的交互行為以及每次交互行為發生的時間；

步驟3，將步驟2所述過去一段時間劃分為多個時間片，并將每個交互行為劃分到對應的時間片中，每個交互行為生成一個鏈路，鏈路的端點分別為交互的兩個節點，且鏈路為無向邊；

步驟4，統計每個時間片內相同鏈路的出現次數，作為該鏈路的權重，利用每個時間片內所有帶權重的鏈路形成一個對應于該時間片的帶權網絡，最終得到帶權網絡序列；

步驟5，對帶權網絡序列進行壓縮，壓縮過程為：從帶權網絡序列中取出所有相同鏈路以及鏈路的權重信息，根據設定的時序影響系數δ計算壓縮后鏈路的時序權重，計算公式為：