鏈路預測

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

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

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

^[5] 

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