摘 要：鏈路預(yù)測(cè)是社交網(wǎng)絡(luò)中一項(xiàng)具有挑戰(zhàn)性的任務(wù)，移動(dòng)社交網(wǎng)絡(luò)中的鏈路預(yù)測(cè)是指通過(guò)已知的網(wǎng)絡(luò)節(jié)點(diǎn)以及社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)等信息預(yù)測(cè)移動(dòng)社交網(wǎng)絡(luò)中尚未產(chǎn)生連邊的兩個(gè)節(jié)點(diǎn)之間產(chǎn)生鏈接的可能性。本文主要比較了4種常用的鏈路預(yù)測(cè)方法。最終，我們使用米蘭大學(xué)數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，結(jié)果顯示基于共同鄰居的相似性指標(biāo)能夠使移動(dòng)社交網(wǎng)絡(luò)中鏈路預(yù)測(cè)有更好的效果。

關(guān)鍵詞：移動(dòng)社交網(wǎng)絡(luò)；鏈路預(yù)測(cè)；相似性；共同鄰居

中圖分類號(hào)：TP393.09

由于人們使用的各種個(gè)人無(wú)線設(shè)備的（如手機(jī)，GPS設(shè)備）迅速和廣泛普及，導(dǎo)致移動(dòng)社交網(wǎng)絡(luò)（MSNs）變得越來(lái)越有重要?？梢园袽SNs看作圖，其中節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)人或?qū)嶓w，邊對(duì)應(yīng)與人們之間的某種關(guān)聯(lián)。在移動(dòng)社交網(wǎng)絡(luò)中，聯(lián)系和實(shí)體往往隨著時(shí)間出現(xiàn)，這就導(dǎo)致了高度的動(dòng)態(tài)性和復(fù)雜的系統(tǒng)。此外，圈內(nèi)好友也經(jīng)常改變，當(dāng)人們通過(guò)社會(huì)聯(lián)系建立友誼，或當(dāng)它們?cè)谝环N社會(huì)關(guān)系的興趣結(jié)束，鏈接會(huì)被移除[1]。對(duì)于移動(dòng)社交網(wǎng)絡(luò)，我們本文中研究討論的是預(yù)測(cè)未來(lái)兩個(gè)節(jié)點(diǎn)之間相關(guān)聯(lián)的可能性。Liben-Nowel[2]提出了鏈路預(yù)測(cè)問(wèn)題：在t時(shí)刻記錄社交網(wǎng)絡(luò)，我們精確預(yù)測(cè)在t到給定的未來(lái)時(shí)間t’時(shí)間間隔內(nèi)添加到網(wǎng)絡(luò)中的邊。

在本文中，我們主要關(guān)注網(wǎng)絡(luò)的局部信息，并利用相似性指數(shù)來(lái)表征未來(lái)互動(dòng)的可能性。本文的其余部分安排如下。第2節(jié)介紹一些相關(guān)工作。第3節(jié)提出了移動(dòng)社交網(wǎng)絡(luò)預(yù)測(cè)的方法。結(jié)果和實(shí)驗(yàn)都在第4節(jié)討論，第5節(jié)總結(jié)全文。

1 相關(guān)工作

鏈路預(yù)測(cè)的現(xiàn)有方法可以分為三類。第一種基于機(jī)器學(xué)習(xí)的方法[3]。Hasan等人[4]指出監(jiān)督式學(xué)習(xí)和預(yù)測(cè)，在社交網(wǎng)絡(luò)中的兩個(gè)潛在連接的節(jié)點(diǎn)是否是一個(gè)正的或負(fù)的示例。他們嘗試了七個(gè)不同的分類算法，并使用不同的性能度量比較這些分類的性能。然而，他們的工作并沒(méi)有趕上復(fù)雜網(wǎng)絡(luò)研究目前的進(jìn)展，特別是他們?nèi)狈φJ(rèn)真考慮網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn)。

第二種方法基于最大似然估計(jì)。Clauset，Moore和Newman[5]提出了一種方法，從網(wǎng)絡(luò)數(shù)據(jù)的分層結(jié)構(gòu)推斷，并進(jìn)一步將其應(yīng)用到在部分已知的網(wǎng)絡(luò)中去預(yù)測(cè)丟失的鏈接，如草地物種食物網(wǎng)和恐怖分子關(guān)聯(lián)網(wǎng)絡(luò)。然而，該算法的一個(gè)很大的缺點(diǎn)是運(yùn)行速度非常慢。另一個(gè)值得注意的要點(diǎn)是，這種模式可能會(huì)對(duì)這些沒(méi)有明確的層次結(jié)構(gòu)的網(wǎng)絡(luò)有較差的預(yù)測(cè)結(jié)果。

第三類基于節(jié)點(diǎn)鄰居的測(cè)量方法。擁有更多的共同鄰居數(shù)的節(jié)點(diǎn)未來(lái)連邊的可能性越大。Liben-Nowell and Kleinberg[2]將一些基于結(jié)構(gòu)的節(jié)點(diǎn)相似性指標(biāo)與隨機(jī)預(yù)測(cè)方法在五種合著網(wǎng)絡(luò)中進(jìn)行比較，發(fā)現(xiàn)的確有包含在單獨(dú)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中的有用信息。這種方法對(duì)待所有的共同鄰居結(jié)果都一樣，它沒(méi)有區(qū)分不同鄰居的預(yù)測(cè)出不同的效果。

在本文中，我們將主要介紹最后一個(gè)方法。節(jié)點(diǎn)的相似性可以通過(guò)使用節(jié)點(diǎn)的本質(zhì)屬性來(lái)定義，即當(dāng)兩個(gè)節(jié)點(diǎn)具有更多共同的特征時(shí)，兩個(gè)節(jié)點(diǎn)更相似。

2 移動(dòng)社交網(wǎng)絡(luò)預(yù)測(cè)方法

我們將4個(gè)經(jīng)典的基于局部信息的相似性指標(biāo)進(jìn)行比較：共同鄰居CN（common neighbors），Jaccard指數(shù)（JC），Adamic–Adar指數(shù)（AA）和Leicht–Holme–Newman指數(shù)（LHN-I）。下面對(duì)每個(gè)方法進(jìn)行說(shuō)明：

CN方法[6]就是說(shuō)兩個(gè)節(jié)點(diǎn)如果有更多的共同鄰居，則它們更傾向于連邊。確切地講，該方法被定義為：

其中，Γ（x）為網(wǎng)絡(luò)中節(jié)點(diǎn)x的鄰居節(jié)點(diǎn)集合，x的鄰居節(jié)點(diǎn)定義為與節(jié)點(diǎn)x直接相連的節(jié)點(diǎn)。節(jié)點(diǎn)x與節(jié)點(diǎn)y的相似度就是它們共同擁有鄰居節(jié)點(diǎn)的個(gè)數(shù)。

JC方法[7]確保那些共享較高比例的共同鄰居數(shù)的節(jié)點(diǎn)對(duì)享有較高的預(yù)測(cè)值。 （2）

AA指標(biāo)思想是度小的共同鄰居節(jié)點(diǎn)的貢獻(xiàn)大于度大的共同鄰居節(jié)點(diǎn)[8]，因此根據(jù)共同鄰居節(jié)點(diǎn)的度為每個(gè)節(jié)點(diǎn)賦予一個(gè)權(quán)重值，該權(quán)重等于該節(jié)點(diǎn)的度的對(duì)數(shù)分之一，即1/lgk。其定義如下：

LHN-I指標(biāo)給部分節(jié)點(diǎn)分配較高的相似性，這些節(jié)點(diǎn)有很多共同鄰居數(shù)不是因?yàn)闈撛谧畲笾档拇嬖诙沁@些鄰居預(yù)期的數(shù)量[9]。分母被定義為kx×ky，正比于節(jié)點(diǎn)x和y的共同鄰居的預(yù)期數(shù)目[10]。

3 實(shí)驗(yàn)結(jié)果與分析

本文采用的衡量鏈路預(yù)測(cè)算法精度的指標(biāo)是AUC[11]，AUC從整體上衡量算法的精度。定義為： 。

每次隨機(jī)從測(cè)試集中選取一條邊與隨機(jī)選擇的不存在的邊進(jìn)行比較，如果測(cè)試集中的邊的分?jǐn)?shù)值大于不存在邊的分?jǐn)?shù)值，就加1分；如果兩個(gè)分?jǐn)?shù)值相等，就加0.5分。n表示獨(dú)立比較的次數(shù)。n表示測(cè)試集中的分?jǐn)?shù)值大于不存在邊的分?jǐn)?shù)值的次數(shù)，表示兩分?jǐn)?shù)值相等的次數(shù)。

我們使用的數(shù)據(jù)集是由米蘭大學(xué)（UniMi）掌上移動(dòng)跟蹤記錄設(shè)備收集的。該數(shù)據(jù)集包含米蘭大學(xué)44個(gè)移動(dòng)設(shè)備的移動(dòng)軌跡。該數(shù)據(jù)收集的是2008年11月的19天。

本文實(shí)驗(yàn)采取對(duì)比的方式進(jìn)行，將所取得的數(shù)據(jù)集分別用上述4種方法進(jìn)行實(shí)現(xiàn)并得到不同的結(jié)果。仿真工具是MATLAB。我們使用真正的跟蹤數(shù)據(jù)，確保了預(yù)測(cè)方法的準(zhǔn)確性。米蘭大學(xué)（UniMi）數(shù)據(jù)集是一個(gè)很小的移動(dòng)社交網(wǎng)絡(luò)，它的節(jié)點(diǎn)之間進(jìn)行頻繁的互動(dòng)。因此，如示于圖1中，我們可以看到，鏈路數(shù)目隨著時(shí)間的推移，顯示出周期性的變化。因此，我們選擇400000s到800000s的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。

我們的研究結(jié)果是基于100次的獨(dú)立實(shí)驗(yàn)?？梢钥闯?，CN指標(biāo)比其他指標(biāo)測(cè)量結(jié)果更好。從表4中可以看出，基于共同鄰居的方法（CN）的AUC值要高于要優(yōu)于其他算法。結(jié)果表明，CN預(yù)測(cè)效果和預(yù)測(cè)精度要更好，能更好地預(yù)測(cè)節(jié)點(diǎn)之間下一時(shí)刻的連邊。

4 結(jié)束語(yǔ)

本文對(duì)移動(dòng)社交網(wǎng)絡(luò)的一些特點(diǎn)進(jìn)行了研究，對(duì)多種鏈路預(yù)測(cè)的方法進(jìn)行研究分析，而且通過(guò)AUC指標(biāo)將4種預(yù)測(cè)方法進(jìn)行了對(duì)比分析。證明采用共同鄰居的算法能在移動(dòng)社交網(wǎng)絡(luò)中取得更好的鏈路預(yù)測(cè)效果。本文主要考慮了共同和鄰居對(duì)預(yù)測(cè)結(jié)果的影響，下一步的研究中可以通過(guò)加入時(shí)間相關(guān)的局部結(jié)構(gòu)變化.建立概率模型等方法來(lái)進(jìn)行更好的鏈路預(yù)測(cè)。

參考文獻(xiàn)：

[1]Schall D.Link prediction in directed social networks[J].Social Network Analysis and Mining，2014（01）：1-14.

[2]Liben-Nowell D，Kleinberg J.The link-prediction problem for social networks[J].Journal of the American Society for Information Science and Technology，2007（58）：1019-1031.

[3]Wang C.，Satuluri V.and Parthasarathy S.，Local Probabilistic Models for Link Prediction，in Proceedings of the 2007 seventh IEEE International Conference on Data Mining（IEEE Press，Washington DC），2007：322-331.

[4]M.A.Hasan，V.Chaoji，S.Salem，M.Zaki，Link Prediction Using Supervised Learning，in Proc.of SDM 06 workshop on Link Analysis[J].Counterterrorism and Security，2006.

[5]A.Clauset，C.Moore，M.E.J.Newman，Hierarchical structure and the prediction of missing links in networks[J].Nature，2008（98）.

[6]Newman，M.E.J.Clustering and preferential attachment in growing networks[J].Physical Review E，2001（64）.

[7]JACCARD P.Etude comparative de la distribution florale dans une portion des Alpes et des Jura[J].Bulletin de la Société Vaudoise des Science Naturelles，1901（37）：547-579.

[8]Adamic，L.A.，Adar，E.Friends and neighbors on the web[J].Social Networks，2003（25）：211-230.

[9]E.A.Leicht，P.Holme，M.E.J.Newman，Vertex similarity in networks[J].Phys.Rev.E，2006.

[10]M.Molloy，B.Reed，A critical point for random graphs with a given degree sequence，Random Structures Algorithms，1995（06）：161.

[11]HANELY J A，MCNEIL B J.The meaning and use of the area under a receiver operating characteristic（ROC） curve[J].Radiology，1982（143）：29-36.

作者簡(jiǎn)介：鄭?。?982.09-），男，江西萍鄉(xiāng)人，講師，博士，研究方向：無(wú)線傳感器網(wǎng)絡(luò)、網(wǎng)絡(luò)優(yōu)化、最優(yōu)化算法。

作者單位：南昌航空大學(xué) 軟件學(xué)院，南昌 330063

基金項(xiàng)目：江西省青年科學(xué)基金（項(xiàng)目編號(hào)：20142BAB217017）：基于節(jié)點(diǎn)運(yùn)動(dòng)特征的機(jī)會(huì)傳感網(wǎng)絡(luò)局部拓?fù)漕A(yù)測(cè)。