鏈路預測(計算機科學領域術語)

網路中的鏈路預測(Link Prediction)是指如何通過已知的網路節點以及網路結構等信息預測網路中尚未產生連邊的兩個節點之間產生連結的可能性。這種預測既包含了對未知連結（exist yet unknown links）的預測也包含了對未來連結（future links）的預測。該問題的研究在理論和套用兩個方面都具有重要的意義和價值。

基本介紹

• 中文名：鏈路預測
• 外文名：Link Prediction
• 定義：如何通過已知的網路節點以及網路結構等信息預測網路中尚未產生連邊的兩個節點之間產生連結的可能性

理論價值

近年來，隨著網路科學的快速發展，其理論上的成果為鏈路預測搭建了一個研究的平台，使得鏈路預測的研究與網路的結構與演化緊密聯繫起來。因此，對於預測的結果更能夠從理論的角度進行解釋。這也是我們相比計算機專業的人研究鏈路預測的優勢所在。與此同時，鏈路預測的研究也可以從理論上幫助我們認識複雜網路演化的機制。針對同一個或者同一類網路，很多模型都提供了可能的網路演化機制。由於刻畫網路結構特徵的統計量非常多，很難比較不同的機制孰優孰劣。鏈路預測機制有望為演化網路提供一個簡單統一且較為公平的比較平台，從而大大推動複雜網路演化模型的理論研究。另外，如何刻畫網路中節點的相似性也是一個重大的理論問題，這個問題和網路聚類等套用息息相關。類似地，相似性的度量指標數不勝數，只有能夠快速準確地評估某種相似性定義是否能夠很好刻畫一個給定網路節點間的關係，才能進一步研究網路特徵對相似性指標選擇的影響。在這個方面，鏈路預測可以起到核心技術的作用。鏈路預測問題本身也帶來了有趣且有重要價值的理論問題，也就是通過構造網路系綜並藉此利用最大似然估計的方法進行鏈路預測的可能性和可行性研究。這方面的研究對於鏈路預測本身以及複雜網路研究的理論基礎的建立和完善，可以起到推動和借鑑的作用。

基本原理

基於相似性的鏈路預測算法尤其是局部相似性指標可套用領域最為廣泛。因為它設計簡潔、可解釋性強、運算時間低、靈活可擴展，同時其預測準確度有時甚至優於相對複雜的機率模型、最大似然模型和網路嵌入模型。該類算法的基本思路利用節點的局部拓撲結構信息為每一條候選連邊分配一個相似性得分，得分越高的連邊被認為有更大可能是缺失邊，因此在預測列表中排序更靠前。

文獻首次明確提出了基於網路拓撲結構的相似性定義框架，同時一個非常簡單且符合直覺的相似指標——共同鄰居指標 (common neighbors, CN) 也是在該文中被明確強調，即兩個節點如果擁有越多的共同鄰居，則越相似。定義P為節點X的鄰居集合，則網路中節點X和節點Y的共同鄰居指標可定義為：

實際套用

鏈路預測研究不僅具有如上所述的理論價值，其更重要的意義還是體現套用方面。很多生物網路，例如蛋白質相互作用網路和新陳代謝網路，節點之間是否存在連結，或者說是否存在相互作用關係，是需要通過大量實驗結果進行推斷的。我們已知的實驗結果僅僅揭示了巨大網路的冰山一角。僅以蛋白質相互作用網路為例，酵母菌蛋白質之間80%的相互作用不為我們所知，而對於人類自身，我們知道的僅有可憐的0.3%。由於揭示這類網路中隱而未現的連結需要耗費高額的實驗成本。那么如果能夠事先在已知網路結構的基礎上設計出足夠精確的鏈路預測算法，再利用預測的結果指導試驗，就有可能提高實驗的成功率從而降低試驗成本並加快揭開這類網路真實面目的步伐！實際上，社會網路分析中也會遇到數據不全的問題，這時候鏈路預測同樣可以作為準確分析社會網路結構的有力的輔助工具。除了幫助分析數據缺失的網路，鏈路預測算法還可以用於分析演化網路，即對未來的預測。舉例來說，近幾年線上社交網路發展非常迅速，鏈路預測可以基於當前的網路結構去預測哪些尚未結交的用戶“應該是朋友”，並將此結果作為“朋友推薦”傳送給用戶：如果預測足夠準確，顯然有助於提高相關網站在用戶心目中的地位，從而提高用戶對該網站的忠誠度。另外，鏈路預測的思想和方法，還可以用於在已知部分節點類型的網路(partially labeled networks)中預測未標籤節點的類型——這可以用於判斷一篇學術論文的類型或者判斷一個手機用戶是否產生了切換運營商(例如從移動到聯通)的念頭。最近在一篇關於鏈路預測的工作中提到了不僅可以預測所謂的缺失連結還可以預測網路中的錯誤連結，這對於網路重組和結構功能最佳化有重要的套用價值。例如在很多構建生物網路的實驗中存在曖昧不清甚至自相矛盾的數據，我們就有可能套用鏈路預測的方法對其進行糾正。