陳耀飛 王友國 朱亮

摘 要：提升鏈路預測精度是復雜網(wǎng)路研究的基礎(chǔ)問題之一。傳統(tǒng)基于局部信息相似性、基于全局信息相似性與基于隨機游走相似性的鏈路預測都是基于單個相似性指標進行預測的，而沒有充分利用這些相似性指標的綜合信息。將鏈路預測問題看作機器學習中的二分類問題，將有連接的樣本標簽記為1，無連接的樣本標簽記為0，將基于局部信息、基于全局信息與基于隨機游走相似性等15個指標作為樣本特征。綜合考慮以上信息，使用XGBoost算法，選取AUC作為模型評價準則，在facebook真實數(shù)據(jù)集上進行實驗。結(jié)果表明，該算法在測試集上的AUC高于基于單個相似性指標鏈路預測的AUC。

關(guān)鍵詞：鏈路預測; XGBoost;機器學習;社交網(wǎng)絡

0 引言

隨著網(wǎng)絡時代的到來，社交網(wǎng)絡已逐漸成為學者們研究的熱點。作為網(wǎng)絡科學領(lǐng)域的研究方向之一，鏈路預測是指通過已知與已觀察到網(wǎng)絡中的鏈接，預測給定網(wǎng)絡中尚不存在的兩個節(jié)點之間鏈接的可能性。鏈路預測既包含了對未知鏈接的預測，也包含了對未來鏈接的預測[1]。在計算機領(lǐng)域，已有不少學者針對鏈路預測進行深入研究，當前主要的鏈路預測方法是基于網(wǎng)絡拓撲結(jié)構(gòu)的鏈路預測方法，其可分為基于節(jié)點鄰居相似性、基于最大似然估計及基于概率模型3種類型。在基于節(jié)點鄰居相似性的鏈路預測中，具有代表性的算法有基于局部信息相似性的共同鄰居算法、基于路徑相似性的Katz算法與基于游走相似性的RWR算法。

Getoor等[1]把文檔與單詞之間的關(guān)系看作鏈路預測問題，通過觀察到的鏈接與節(jié)點屬性可以估計一個鏈接存在的最大可能性。之后，David & Kleinberg[2]首次定義了社交網(wǎng)絡中的鏈路預測問題，并且在大規(guī)模共同作者網(wǎng)絡數(shù)據(jù)集上進行實驗，結(jié)果表明，關(guān)于未來交互的信息可以單獨從網(wǎng)絡拓撲中提取出來。社交網(wǎng)絡中由于存在不準確信息，導致網(wǎng)絡中存在虛假鏈接[3-4]，鏈路預測算法可用于發(fā)現(xiàn)網(wǎng)絡中的虛假鏈接，還原真實網(wǎng)絡[5]。鏈路預測不僅可以幫助分析網(wǎng)絡中的缺失數(shù)據(jù)，還可用來發(fā)現(xiàn)網(wǎng)絡演化過程中將來可能出現(xiàn)的鏈接[6-7]。O'Madahain等[8]提出局部條件概率模型，在進行預測時充分利用網(wǎng)絡拓撲結(jié)構(gòu)和節(jié)點屬性等信息;Lin等[9]根據(jù)節(jié)點屬性定義節(jié)點相似性，從而利用節(jié)點相似性進行預測。利用節(jié)點屬性可以很好地進行預測，但節(jié)點屬性信息很難獲取，即使能獲取到，也不能保證信息的真實性，如社交網(wǎng)絡中很多用戶的注冊信息則不夠真實。Linben等[10]基于網(wǎng)絡拓撲結(jié)構(gòu)分析了幾種指標對社會網(wǎng)絡中鏈路預測產(chǎn)生的效果;Clauset等[11]發(fā)現(xiàn)在具有明顯層次結(jié)構(gòu)的網(wǎng)絡中，利用網(wǎng)絡層次結(jié)構(gòu)進行鏈路預測可取得不錯的效果?；谙嗨菩缘姆椒ㄊ亲罨厩易罹邌l(fā)式的方法，通過利用相似性指標進行鏈路預測，如Adamic等[12]通過分配給較少的相連鄰居更高權(quán)重，重新定義CN（Common Neighbor）為Adamic-Adar（AA）得分;Katz[13]基于所有路徑集合，直接對所有路徑求和，對于更長路徑，通過指數(shù)衰減賦予更少權(quán)重得到Katz得分。還有一些其它相似性指標，包括資源分配指標（RA）[14]、Jaccard指標[15]、Sorensen指標[16]等?；陔S機游走的相似性指標包括重啟的隨機游走（RWR）與余弦相似性（Cos+）。Mohammad等[17]通過使用有監(jiān)督學習方法，分別在BIOBASE和DBLP兩個數(shù)據(jù)集上進行測試，都取得了不錯的效果;Backstrom等[18]提出有監(jiān)督的隨機游走算法，可以自然地將網(wǎng)絡結(jié)構(gòu)中邊與節(jié)點級別的信息結(jié)合起來;吳祖峰等[19]使用有監(jiān)督學習方法，使用Adaboost算法對arXiv 論文合作網(wǎng)絡與電子郵件網(wǎng)絡兩個真實數(shù)據(jù)集進行測試，準確率和召回率都顯著高于當時的主流算法。

基于相似性的鏈路預測是目前運用最多的鏈路預測算法，進行預測前首先需要計算兩個節(jié)點之間的相似性，包括CN等基于局部信息的相似性指標、Katz等提出的基于全局信息的相似性指標、Cos+等基于隨機游走的相似性指標。基于相似性的方法憑借其計算簡單、速度快等優(yōu)點吸引了很多學者關(guān)注，但該方法的缺點是只考慮單一相似性指標，而未綜合考慮這3類基于不同信息的相似性指標。

本文在基于相似性的鏈路預測算法基礎(chǔ)上，將鏈路預測問題看作機器學習中的二分類問題，使用有監(jiān)督學習中的XGBoost算法[20]進行鏈路預測，從而綜合考慮所有相似性指標信息，提高鏈路預測精度。

3 結(jié)語

本文基于XGBoost算法進行鏈路預測，與基于單相似性指標算法的鏈路預測不同，基于XGBoost算法的鏈路預測將鏈路預測問題看作機器學習中的二分類問題，模型訓練時選取基于局部信息、基于全局信息與基于隨機游走的相似性指標作為機器學習中的特征，考慮多個指標進行鏈路預測，并且使用AUC作為模型評價準則。經(jīng)過實驗發(fā)現(xiàn)，基于XGBoost的多個指標鏈路預測優(yōu)于基于單個相似性指標的鏈路預測，而且綜合考慮所有信息相似性指標后進行鏈路預測效果最好。鏈路預測可用于社交網(wǎng)絡中的好友推薦，推薦準確度的提升可提高社交網(wǎng)站用戶的忠誠度。

參考文獻：

[1] GETOOR L， DIEHL C P. Link mining：a survey[J]. ACM Sigkdd Explorations Newsletter， 2005， 7（2）：3-12.

[2] LIBEN-NOWELL D， KLEINBERG J. The link-prediction problem for social networks[M]. New York：John Wiley & Sons， Inc. 2007.

[3] VON MERING C， KRAUSE R， SNEL B， et al. Comparative assessment of large-scale data sets of protein-protein interactions[J]. Nature， 2002， 417：399-403.

[4] BUTTS C T. Network inference， error， and informant （in）accuracy： a Bayesian approach[J]. Social Networks， 2003， 25（2）：103-140.

[5] GUIMERA R， SALES-PARDO M. Missing and spurious interactions and the reconstruction of complex networks[C]. Proceedings of the National Academy of Sciences， 2009， 106（52）：22073-22078.

[6] Lü L， ZHOU T. Link prediction in complex networks： a survey[J]. Physica A：statistical mechanics and its applications， 2011， 390（6）： 1150-1170.

[7] 呂琳媛. 復雜網(wǎng)絡鏈路預測[J]. 電子科技大學學報，2010，39（5）：651-661.

[8] OMADADHAIN J，HUTCHINS J， SMYTH P. Prediction and ranking algorithms for event-based network data[C]. Proceedings of the ACM SIGKDD 2005. New York： ACM Press， 2005： 23-30.

[9] LIN D. An information-theoretic definition of similarity[C]. Proceedings of the 15th International Conference of Machine Learning，1998： 296-304.

[10] LIBEN N D，KLEINBERG J. The link-prediction problem for social networks[J]. Journal of American Soci Information Science Technology，2007，58（7）： 1019-1031.

[11] CLAUSET A，MOOR C，NEWMAN M E J. Hierarchical structure and the prediction of missing links in networks[J]. Nature，2008， 453： 98-101.

[12] ADAMIC L A，ADAR E. Friends and neighbors on the Web[J].? Social Networks，2003， 25（3）：211-230.

[13] KATZ L. A new status index derived from sociometric analysis[J].? Psychometrika，1953，18（1）：39-43.

[14] ZHOU T，LINYUAN Lü， ZHANG Y C. Predicting missing links via local information[J]. The European Physical Journal B，2009，71（4）：623-630.

[15] JACCARD P. étude comparative de la distribution ？orale dans une portion des Alpes et des jura[J]. Bull Soc Vaudoise Sci Nat， 1901， 37：547-579.

[16] S？RENSEN T. A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on danish commons[J]. Biol. Skr， 1948， 5： 1-34.

[17] HASAN M A，CHAOJI V，SALEM S， et al. Link prediction using supervised learning[C]. The Proceedings of the Fourth Workshop on Link Analysis， Counterterrorism and Security， 2006.

[18] BACKSTROM L，LESKOVEC J. Supervised random walks： predicting and recommending links in social networks[C]. WSDM，2011.

[19] 吳祖峰，梁棋，劉嶠，等. 基于AdaBoost的鏈路預測優(yōu)化算法[J]. 通信學報，2014，35（3）：116-123.

[20] CHEN T，GUESTRIN C. XGBoost：a scalable tree boosting system[J]. KDD '16 Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2016：785-794.

（責任編輯：黃 ?。?/p>