魏爽　高華玲

摘要：如今，社交網(wǎng)絡(luò)服務(wù)的使用越來越多，像Facebook這樣的社交網(wǎng)站成了繼雅虎、MSN等大型門戶網(wǎng)站和谷歌等搜索引擎之后最受歡迎的網(wǎng)站。預(yù)測(cè)社交網(wǎng)絡(luò)中人與人之間的關(guān)聯(lián)成了分析社交網(wǎng)絡(luò)的一大難題。論文目的是通過對(duì)現(xiàn)有的網(wǎng)站數(shù)據(jù)準(zhǔn)確地預(yù)測(cè)朋友關(guān)系。通過使用數(shù)據(jù)挖掘的方法，預(yù)測(cè)的準(zhǔn)確度達(dá)到約90%。

關(guān)鍵詞：社交網(wǎng)絡(luò)；數(shù)據(jù)挖掘；關(guān)聯(lián)預(yù)測(cè)；回歸；ROC

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）12-0046-03

Link Prediction in Social Network Using Data Mining Method

WEI Shuang， GAO Hua-ling

（Sanya University， Sanya 572022，China）

Abstract： Using social network services is becoming more and more popular. Websites of social network like Facebook currently are among the most popular internet services just after giant portals such as Yahoo and MSN and search engines like Google. One of the main problem in analyzing these networks is the prediction of relationships between people in the network. The purpose of this paper is to forecast the relationship using existing data accurately. About 90% correct prediction is achieved with regards to the results obtained by using data mining method.

Key words： social network；data mining；link prediction；regression；ROC

社交網(wǎng)絡(luò)是由個(gè)人以及群體構(gòu)成的由一個(gè)或多個(gè)因素關(guān)聯(lián)起來的一種社交結(jié)構(gòu) [1]。

互聯(lián)網(wǎng)空間為用戶產(chǎn)生新的社交方式提供了極大的可行性。1960年，社交網(wǎng)絡(luò)的概念第一次在美國(guó)伊利諾斯大學(xué)提出。之后，成立了第一個(gè)社交網(wǎng)站，即“Six Degrees.com”。2002年之后，各種諸如LinkIn之類的社交網(wǎng)站遍地開花，給該領(lǐng)域帶來了一次重大的革命，極大地豐富了社交網(wǎng)絡(luò)。今天，社交網(wǎng)絡(luò)受到極大的歡迎，它給用戶提供了大量的交流工具。無論時(shí)新成員的加入，還是成員之間建立新的聯(lián)系，整個(gè)社交網(wǎng)絡(luò)都會(huì)得到增長(zhǎng)。在分析這些社交網(wǎng)絡(luò)的時(shí)候，預(yù)測(cè)成員之間的關(guān)系成了最主要的一個(gè)問題是。

社交網(wǎng)絡(luò)分析包含一個(gè)子領(lǐng)域，即關(guān)聯(lián)預(yù)測(cè)。做關(guān)聯(lián)預(yù)測(cè)的時(shí)候，需要對(duì)一系列的關(guān)聯(lián)進(jìn)行推理和評(píng)估。而這些關(guān)聯(lián)相對(duì)于那些已經(jīng)存在的觀測(cè)和關(guān)聯(lián)來說，可能不是十分的明顯，有的相甚至還不存在。

一般來說，關(guān)聯(lián)預(yù)測(cè)包括了以下幾個(gè)領(lǐng)域：1）關(guān)聯(lián)存在預(yù)測(cè)，即預(yù)測(cè)任意兩個(gè)節(jié)點(diǎn)之間是否存在聯(lián)系。2）對(duì)節(jié)點(diǎn)之間的關(guān)系進(jìn)行分類。3）關(guān)系回歸。

1 研究目的和數(shù)據(jù)

本文的目的是預(yù)測(cè)社交網(wǎng)絡(luò)中高可能性的朋友關(guān)系。這可以為社交網(wǎng)站在發(fā)現(xiàn)成員之間的關(guān)系上提供很大的幫助。使用的數(shù)據(jù)采集自Flickr社交網(wǎng)站。Flickr擁有龐大的社交網(wǎng)絡(luò)，包括了數(shù)百萬的用戶和大量的圖片。該網(wǎng)站有大量的朋友關(guān)系數(shù)據(jù)，包括評(píng)論、群體成員信息、朋友建議、最喜愛的照片點(diǎn)擊以及訪問的限制等。

數(shù)據(jù)包括一個(gè)訓(xùn)練文件和一個(gè)測(cè)試文件。訓(xùn)練文件包含了7，237，983條記錄。這些記錄由兩列數(shù)據(jù)組成，分別表示第一個(gè)人和第二個(gè)人的唯一ID。每條記錄的意思是第一個(gè)人是第二個(gè)人的朋友。測(cè)試文件由3列數(shù)據(jù)組成，包含了8960條記錄。前兩列數(shù)據(jù)和訓(xùn)練文件的一樣，分別表示第一個(gè)人和第二個(gè)人。第三列表示對(duì)第一個(gè)人是否是第二個(gè)人的朋友的預(yù)測(cè)，其值為0或者1：0表示第一個(gè)人和第二個(gè)人不是朋友關(guān)系，1表示兩者是朋友關(guān)系。

2 研究方法

本文采用ROC曲線來計(jì)算預(yù)測(cè)至的正確性。ROC是一個(gè)強(qiáng)大的模擬工具，廣泛用于醫(yī)學(xué)決策、心理學(xué)、通信等領(lǐng)域[2]。

首先，為了了解ROC評(píng)估情況以及數(shù)據(jù)類型，先產(chǎn)生一系列的數(shù)據(jù)并計(jì)算結(jié)果。第一步，將預(yù)測(cè)列的值設(shè)為0到1之間的一個(gè)隨機(jī)數(shù)，用這些數(shù)得到的ROC值約為0.435。第二步，將測(cè)試文件的預(yù)測(cè)列一半設(shè)為0，另一半設(shè)為1，得到的ROC值約為0.46。第三步，將預(yù)測(cè)列所有的值都設(shè)為0，得到ROC值為0.5。第四步，將預(yù)測(cè)列的所有值設(shè)為1，得到ROC值為0.5。根據(jù)最后兩步的結(jié)果可以看出，測(cè)試文件的結(jié)果為0和1的記錄的數(shù)量是一樣的。

研究表明，將那些ROC值不佳的預(yù)測(cè)列的值進(jìn)行交換，即0設(shè)為1、1設(shè)為0，可以獲得較好的ROC值。在此提出假設(shè)，將ROC值為0.468的預(yù)測(cè)列的數(shù)值進(jìn)行顛倒后應(yīng)該可以得到較好的ROC值。通過計(jì)算，ROC的值為0.532。這證明了假設(shè)的正確性。這個(gè)結(jié)果表明兩個(gè)預(yù)測(cè)列的值是互補(bǔ)的，其和為1。在前面提到的測(cè)試文件中的8690個(gè)記錄中，4345個(gè)的值為1，另外4345個(gè)的值為0。

2.1 一般模型測(cè)試

接下來，利用幾個(gè)模型來幫助發(fā)現(xiàn)成員之間的朋友關(guān)系[3-6]。用A表示第一列，B表示第二列，A和B的朋友關(guān)系預(yù)測(cè)值為第三列。訓(xùn)練文件的第一列和第二列是存在朋友關(guān)系的。A是B的朋友，那么據(jù)此可預(yù)測(cè)B是A的朋友，如圖1所示。通過研究測(cè)試文件，發(fā)現(xiàn)四百多成員滿足這個(gè)條件。

另外一個(gè)用來預(yù)測(cè)關(guān)聯(lián)的方法基于以下準(zhǔn)則：如果節(jié)點(diǎn)對(duì)（A，C）和（A，B）存在朋友關(guān)系，那么節(jié)點(diǎn)對(duì)（B，C）之間存在關(guān)聯(lián)的可能性就很高，如圖2所示。據(jù)此計(jì)算得到的ROC值為0.43

下面這個(gè)模型中包含三個(gè)節(jié)點(diǎn)，存在一個(gè)路徑。猜測(cè)路徑的起始點(diǎn)和終點(diǎn)存在著朋友關(guān)系，如圖3所示。即如果A和B存在朋友關(guān)系，且B和C存在朋友關(guān)系，那么很有可能A和C存在朋友關(guān)系。通過這個(gè)模型計(jì)算的ROC值為0.495。

如圖4所示模型，假設(shè)節(jié)點(diǎn)對(duì)（A，B），（B，C），（C，D）存在著朋友關(guān)系，那么節(jié)點(diǎn)對(duì)（A，C）和（A，D）也很有可能存在朋友關(guān)系。利用這個(gè)模型計(jì)算得到的ROC值為0.524。

接下來，利用所有這些方法預(yù)測(cè)所有的關(guān)系。最終得到的ROC值為0.78。

2.2 利用回歸進(jìn)行預(yù)測(cè)

很多的研究都是在用幾個(gè)因素來產(chǎn)生最佳值來達(dá)到特定的目的。利用統(tǒng)計(jì)學(xué)，可以通過幾個(gè)回歸算法來實(shí)現(xiàn)。在回歸計(jì)算中，通過一些獨(dú)立的自變量來推算因變量的值。此即是大多數(shù)研究的主要目標(biāo)。

回歸方法取決于研究因素的類型。邏輯回歸是一個(gè)特殊的回歸類型，它用于因變量值為二選一或多選一的情況[7，8]。

需要確定一個(gè)X的集合和一個(gè)獨(dú)立變量的關(guān)系的問題即是多變量問題。在分析這類問題上，有很多的數(shù)學(xué)方法。邏輯回歸就是一個(gè)可以用來描述X集合和一個(gè)雙態(tài)變量或多態(tài)變量Y關(guān)系的數(shù)學(xué)模型。雙態(tài)變量只有兩種值，一般用二進(jìn)制數(shù)來表示，其值要么是1，要么是0。

回歸最重要的就是找到因變量Y和預(yù)測(cè)值集X1，X2，……Xk的關(guān)系。事實(shí)上，回歸技術(shù)就是要設(shè)法確定Y和觀測(cè)變量X集合的一個(gè)關(guān)系Y=f（X1，X2，……Xk）。最簡(jiǎn)單的一種解就是一個(gè)線性關(guān)系：

在評(píng)估方法的幫助下，通常用一個(gè)實(shí)例就可以將系數(shù)α確定下來。當(dāng)然了，這對(duì)因變量和觀測(cè)變量有一些條件限制，例如：假定模型的線性特性，觀測(cè)的獨(dú)立性，因變量分布的規(guī)則性以及因變量變化的穩(wěn)定性等?？上攵?，由于線性模型對(duì)條件的限制，它并非能總是有效地應(yīng)用與各種情況下。對(duì)于不同情況，需要選擇合適的數(shù)據(jù)模型。

有時(shí)因變量是一個(gè)雙態(tài)變量，而影響因變量的預(yù)測(cè)變量卻是數(shù)值型的。在這種情況下，用等式（1）表示的線性模型就不合適了。因?yàn)椋?）的左邊只能是0或者1，而在理論上來講，右邊的取值范圍為-∞到+∞。邏輯回歸就是解決這類問題的一個(gè)方法。此方法中，等式左邊被轉(zhuǎn)化為一個(gè)數(shù)值變量，分三步進(jìn)行：

（i）將（1）中的Y替換為Pr[Y=1]。顯然，概率的值可以為0至1之間的任意數(shù)。

（ii）采用讓步比計(jì)算。概率p=0.9可以表示為9：1，或者OR=p/（1-p）=0.9/0.1=9。顯然，如果p=0，OR=0，如果p=0.5，OR=1。

（iii）取OR的自然對(duì)數(shù)作為新的因變量，這樣新的因變量取值范圍就變成了-∞到+∞。這里將ln（p/（1-p））稱為logit（p）。得到的新模型就是：

（2）

為了推算出（2）中的系數(shù)，要用到長(zhǎng)度為n的隨機(jī)樣品，包括因變量和預(yù)測(cè)變量的值。故而，對(duì)于觀測(cè)變量的n個(gè)觀測(cè)結(jié)果之和，就有J個(gè)不同的樣品（j=1，2，……，J），這樣對(duì)于預(yù)測(cè)變量的第j個(gè)樣品，就有mj個(gè)觀測(cè)結(jié)果，其對(duì)應(yīng)的Y=1的概率為：

系數(shù)的似然函數(shù)對(duì)數(shù)β=（β0，β1，……βk）為

這里yj表示第j個(gè)樣品的觀測(cè)結(jié)果之和。為了找到通過最大化（4）中關(guān)于β最大值得到的最大似然值，需要下面含有k+1個(gè)變量的關(guān)于β的k+1個(gè)方程：

關(guān)于β0，β1，……βk的方程（5）是非線性的。需要用數(shù)字迭代的方法來求解。

在前面，通過所有的預(yù)測(cè)模型得到了ROC的值為0.78。對(duì)不可預(yù)測(cè)的狀態(tài)和不能加以假設(shè)的部分采用二進(jìn)制邏輯回歸的方法，得到的ROC為0.89。

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

實(shí)驗(yàn)結(jié)果如表1所示。從表中可以看出，邏輯回歸是對(duì)于前面的假設(shè)中的數(shù)據(jù)進(jìn)行0值和1值預(yù)測(cè)的合適模型。

4 小結(jié)

使用了各種模型方法進(jìn)行數(shù)據(jù)預(yù)測(cè)，從結(jié)果可以看出最好的方法就是綜合各個(gè)假設(shè)，使用邏輯回歸模型。從8690個(gè)數(shù)據(jù)的結(jié)果來看，使用該模型進(jìn)行預(yù)測(cè)的正確率約為90%。這可證明該模型為二值預(yù)測(cè)的最好模型。然而，這個(gè)模型還不能完全地正確預(yù)測(cè)。為了使預(yù)測(cè)結(jié)果更準(zhǔn)確，可以考慮在計(jì)算時(shí)對(duì)各個(gè)模型引入權(quán)重系數(shù)。

參考文獻(xiàn)：

[1] Danah M Boyd，Nicole B Ellison.Social Network Sites： Definition， History， and Scholarship[J]. Journal of Computer‐Mediated Communication，2007（1）.

[2] 萬柏坤，薛召軍，李佳，等.應(yīng)用ROC曲線優(yōu)選模式分類算法[J].自然科學(xué)進(jìn)展，2006（11）.

[3] 靳婷.在線社交網(wǎng)絡(luò)中的鏈路預(yù)測(cè)問題研究[D].合肥： 中國(guó)科學(xué)技術(shù)大學(xué)，2014.

[4] 王昭.社交網(wǎng)絡(luò)形式中基于人所形成的點(diǎn)、線、面的關(guān)系與應(yīng)用[D].北京： 中央美術(shù)學(xué)院，2014.

[5] Bruce Hoppe，Claire Reinelt.Social Network Analysis and the Evaluation of Leadership Networks[J].The Leadership Quarterly，2010，21（4）：600-619.

[6] 朱廷劭，李昂，寧悅，等.網(wǎng)絡(luò)社會(huì)中個(gè)體人格特征及其行為關(guān)系[J].蘭州大學(xué)學(xué)報(bào)：社會(huì)科學(xué)版，2011（5）.

[7] 鄭明川.幾種結(jié)合預(yù)測(cè)法的比較和研究[J].管理工程學(xué)報(bào)，1989（Z1）.

[8] 吉國(guó)力，郭志紅.改進(jìn)關(guān)聯(lián)預(yù)測(cè)法[J].廈門大學(xué)學(xué)報(bào)：自然科學(xué)版，1991（3）.