基于XGBoost算法的社交網(wǎng)絡(luò)鏈路預(yù)測(cè)

陳耀飛 王友國(guó) 朱亮

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

關(guān)鍵詞：鏈路預(yù)測(cè); XGBoost;機(jī)器學(xué)習(xí);社交網(wǎng)絡(luò)

0 引言

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

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[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] 呂琳媛. 復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)[J]. 電子科技大學(xué)學(xué)報(bào)，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ù)測(cè)優(yōu)化算法[J]. 通信學(xué)報(bào)，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.

（責(zé)任編輯：黃 健）