魏爽　高華玲

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

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

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：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òu)成的由一個或多個因素關(guān)聯(lián)起來的一種社交結(jié)構(gòu) [1]。

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

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

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

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

本文的目的是預(yù)測社交網(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ù)，包括評論、群體成員信息、朋友建議、最喜愛的照片點(diǎn)擊以及訪問的限制等。

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

2 研究方法

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

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

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

2.1 一般模型測試

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

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

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

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

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

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

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

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

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

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

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

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

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

（ii）采用讓步比計算。概率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的自然對數(shù)作為新的因變量，這樣新的因變量取值范圍就變成了-∞到+∞。這里將ln（p/（1-p））稱為logit（p）。得到的新模型就是：

（2）

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

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

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

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

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

3 實驗結(jié)果

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

4 小結(jié)

使用了各種模型方法進(jìn)行數(shù)據(jù)預(yù)測，從結(jié)果可以看出最好的方法就是綜合各個假設(shè)，使用邏輯回歸模型。從8690個數(shù)據(jù)的結(jié)果來看，使用該模型進(jìn)行預(yù)測的正確率約為90%。這可證明該模型為二值預(yù)測的最好模型。然而，這個模型還不能完全地正確預(yù)測。為了使預(yù)測結(jié)果更準(zhǔn)確，可以考慮在計算時對各個模型引入權(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ù)測問題研究[D].合肥： 中國科學(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ò)社會中個體人格特征及其行為關(guān)系[J].蘭州大學(xué)學(xué)報：社會科學(xué)版，2011（5）.

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

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