劉峰　劉秉權(quán)　王曉龍

摘 要：隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，社會網(wǎng)絡(luò)成為了許多人生活日常中的一部分。這些不同興趣的社會網(wǎng)絡(luò)，大都會提供種類各異的用戶交互服務(wù)。這些種類豐富的社會成員之間的交互行為大部分都可以用鏈接的形式來表示。鏈接預(yù)測問題主要以分析鏈接網(wǎng)絡(luò)結(jié)構(gòu)為主要方法，從而預(yù)測一對節(jié)點(diǎn)是否會在未來產(chǎn)生鏈接，或是預(yù)測一對節(jié)點(diǎn)之間已經(jīng)存在鏈接的類型。本文詳細(xì)介紹了鏈接預(yù)測的任務(wù)，并給出了相應(yīng)的求解方法。

關(guān)鍵詞：鏈接預(yù)測；社會計(jì)算；用戶相似度度量；極性值分類

中圖分類號：TP391.41 文獻(xiàn)標(biāo)識號：A 文章編號：2095-2163（2015）05-

Link Prediction Task in Social Network Service

LIU Feng1， LIU Bingquan1， WANG Xiaolong1，2

（1 School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China；

2 Graduate School of Shenzhen， Harbin Institute of Technology， Shenzhen Guangdong， 518055， China）

Abstract： With the rapid development of internet techniques， SNS（Social Network Service） becomes many peoples daily life. Most of these different focus SNSs provide many kinds of functions for member interactions. Most of the interaction among members could be represented as link. By analyzing the structure of link network， the link prediction problem aims to estimate the existence or value of the links. In this paper， the details of link prediction task and certain solutions are respectively introduced.

Keywords： Link Prediction； Social Computing； User Similarity Metric； Signed Value Classification

0 引 言

伴隨著互聯(lián)網(wǎng)技術(shù)的高速發(fā)展，社會網(wǎng)絡(luò)（SNS，Social Networks Services）也隨之興起并呈現(xiàn)出快速普及態(tài)勢。目前，各類在線SNS中的注冊用戶數(shù)目已經(jīng)十分龐大，越來越多的研究者和服務(wù)商也開始關(guān)注如何為這些用戶提供更好的服務(wù)。其中為社區(qū)內(nèi)用戶之間提供豐富的交互功能（user interaction）就是SNS的一個重要功能，這些用戶交互可以利用鏈接（link）來實(shí)現(xiàn)其確立并加以表示。對鏈接預(yù)測相關(guān)問題進(jìn)行深入系統(tǒng)的研究，必將會對社會網(wǎng)絡(luò)的研究發(fā)展有著毋庸置疑的基礎(chǔ)性重要意義。

例如Wikipedia、Epinion、Slashdot等網(wǎng)站，即為用戶提供了用戶生成內(nèi)容（UGC，User Generated Content）的發(fā)布服務(wù)，也允許用戶之間對彼此發(fā)布的內(nèi)容進(jìn)行評論、修正與補(bǔ)充。一些網(wǎng)站還采取用戶自己選舉管理員的方式來進(jìn)行管理，例如Wikipedia的管理員選舉（admin role promotion）。如果使用圖來對社會網(wǎng)絡(luò)進(jìn)行建模，圖中的節(jié)點(diǎn)表示用戶，以上這些用戶行為都可以用節(jié)點(diǎn)之間的鏈接來表示，用戶交互的具體內(nèi)容則可以用鏈接類型和鏈接邊上的值來表示。包含這種用戶或是實(shí)體之間鏈接的數(shù)據(jù)集，一般稱為鏈接數(shù)據(jù)或是關(guān)系數(shù)據(jù)。對這些鏈接數(shù)據(jù)集進(jìn)行分析和預(yù)測的數(shù)據(jù)挖掘研究，統(tǒng)稱為鏈接挖掘（link mining）。其中用來處理對象間是否存在鏈接的預(yù)測，以及預(yù)測鏈接類型的研究將可稱為鏈接預(yù)測（link prediction）。通過對鏈接預(yù)測相關(guān)問題的研究，研究者可以更為精準(zhǔn)、全面地對SNS中的用戶交互進(jìn)行建模和分析，從而為其社會成員提供更好的用戶體驗(yàn)。

本文首先分析了社會網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn)，以及網(wǎng)絡(luò)中的數(shù)據(jù)分布情況。在此基礎(chǔ)上，進(jìn)一步介紹了對于鏈接存在的預(yù)測和鏈接值的預(yù)測這兩種常見的鏈接預(yù)測任務(wù)，而后又提出了相應(yīng)的解決方法。

1 社會網(wǎng)絡(luò)的結(jié)構(gòu)與特點(diǎn)

社會網(wǎng)絡(luò)是一種“復(fù)雜網(wǎng)絡(luò)（complex network）”[1]，這種網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)表現(xiàn)出不同于一般網(wǎng)絡(luò)結(jié)構(gòu)的特性。復(fù)雜網(wǎng)絡(luò)中各個元素之間相連接的模式既不是完全有規(guī)律可循，也不是完全隨機(jī)的產(chǎn)生。大部分社會網(wǎng)絡(luò)還有另外一個特點(diǎn)，就是“無標(biāo)度（scale-free）”。即任意從網(wǎng)絡(luò)中選擇一個節(jié)點(diǎn)，與其有連接的節(jié)點(diǎn)數(shù)目的統(tǒng)計(jì)描述將符合指數(shù)法則分布（power-law distribution）。

以Wikipedia的管理員選舉的數(shù)據(jù)為例，用圖來表示鏈接網(wǎng)絡(luò)，把會員表示為圖中的節(jié)點(diǎn)，會員之間的管理員選舉投票行為用圖中的有向鏈接邊來表示，投票的具體內(nèi)容用鏈接值表示?；诖?，本文隨機(jī)選擇了一個全連通網(wǎng)絡(luò)，其中包含46個用戶以及各用戶之間的205條邊，利用工具包NodeXL[2]畫出網(wǎng)絡(luò)結(jié)構(gòu)圖。如圖1所示，圖中平均每個節(jié)點(diǎn)擁有4.45條邊，節(jié)點(diǎn)之間的平均距離為1.77。節(jié)點(diǎn)的最大度數(shù)為11，最小度數(shù)為1，除了中間少數(shù)節(jié)點(diǎn)擁有很高的出入度，大部分節(jié)點(diǎn)的度數(shù)都較低。

由圖1可知，該圖中實(shí)線表示“支持投票”，虛線表示“反對投票”，該網(wǎng)絡(luò)中大部分都是正例（支持投票）。這種正負(fù)樣本不均衡的現(xiàn)象也普遍存在于社會網(wǎng)絡(luò)中，比如某些商品評價(jià)網(wǎng)站中大部分都是相信某人提供的評價(jià)，又如某些能標(biāo)注“朋友”和“敵人”的網(wǎng)絡(luò)中，大部分的標(biāo)注都是關(guān)于自己的朋友。而在另外的某些網(wǎng)絡(luò)中，比如共同創(chuàng)作網(wǎng)絡(luò)，卻只存在正例，但其中沒有連接邊的用戶并非一定不會共同創(chuàng)作一篇文章，只是目前還沒有共同創(chuàng)作過一篇文章。

為了進(jìn)一步分析社會網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn)，本文對整個管理員選舉數(shù)據(jù)集中擁有不同度數(shù)節(jié)點(diǎn)出現(xiàn)的頻率進(jìn)行了統(tǒng)計(jì)，如圖2所示。從圖2中可以明顯看出，出現(xiàn)頻率高（Y值較大）的節(jié)點(diǎn)的度數(shù)較?。╔值較小），由此可知大部分節(jié)點(diǎn)擁有較小的度數(shù)，而擁有高度數(shù)的節(jié)點(diǎn)出現(xiàn)頻率則很低。特別是度數(shù)達(dá)到一定數(shù)量的節(jié)點(diǎn)出現(xiàn)頻率極低，圖中幾乎平行于X軸且貼近Y=0的點(diǎn)線也反映了這一點(diǎn)。為了方便觀察，將圖2的X，Y都設(shè)定為取10的對數(shù)，得到圖3?？梢钥闯?，圖3中的節(jié)點(diǎn)度數(shù)分布更趨近于線性，說明了在該網(wǎng)絡(luò)中，節(jié)點(diǎn)度數(shù)符合指數(shù)法則分布。

通過如上分析，可以大致總結(jié)社會網(wǎng)絡(luò)擁有正負(fù)例樣本分布不均勻，節(jié)點(diǎn)度數(shù)呈現(xiàn)指數(shù)分布等特點(diǎn)。而且在不同的實(shí)際環(huán)境中，不同應(yīng)用重點(diǎn)的社會網(wǎng)絡(luò)都還具有自身的特點(diǎn)。對各類網(wǎng)絡(luò)進(jìn)行處理時應(yīng)該提取相應(yīng)的特征，并采用合適的方法。這些多樣性使得社會計(jì)算的各個問題充滿了樂趣和挑戰(zhàn)。

2 鏈接存在的預(yù)測

2.1 問題描述

預(yù)測兩個節(jié)點(diǎn)是否存在一條鏈接，是鏈接預(yù)測研究中較早就開始涉及的問題，鏈接預(yù)測（link prediction）的命名也是由此項(xiàng)任務(wù)產(chǎn)生。Getoor和Diehl[3]給出的經(jīng)典鏈接預(yù)測定義為：“通過兩個節(jié)點(diǎn)的屬性和觀測到的鏈接，來預(yù)測這兩個節(jié)點(diǎn)之間是否會存在一條鏈接”。例如預(yù)測社交圈內(nèi)誰和誰可能會成為朋友，或者預(yù)測誰和誰會參與某些事件，例如打電話，發(fā)郵件，或是會共同創(chuàng)作一篇文章或是其它一些活動；這類問題的共同特點(diǎn)是，對象屬性和部分鏈接可見，目的是嘗試去預(yù)測那些不可見的鏈接存在的可能性，如圖4所示。

2.2 常用方法

在研究共同創(chuàng)作（co-author）問題時，Nowell和Kleinberg[4]嘗試了多種用戶相似度計(jì)算方法，并根據(jù)相似度的高低來預(yù)測兩位作者是否會在未來共同創(chuàng)作一篇文章。研究中采用圖來表示作者間的創(chuàng)作關(guān)系，如圖5所示。之后通過節(jié)點(diǎn)的自身狀態(tài)信息和鏈接分布情況來計(jì)算任意兩個節(jié)點(diǎn)之間的相似度，并排序，相似度高的兩個節(jié)點(diǎn)則會認(rèn)定為創(chuàng)作過一篇文章，或是有可能在將來共同創(chuàng)作一篇文章。Dong等[5]列出了多種可用于鏈接預(yù)測的用戶相似度計(jì)算方法，并進(jìn)行了比較。

以上的方法主要是基于對用戶相似度的度量（user similarity metric）的計(jì)算，隨著對共同創(chuàng)作問題的深入研究，各種其它特征和基于機(jī)器學(xué)習(xí)（machine learning）方法相繼獲得采用。Hasan等[6]把這一問題當(dāng)做一個二分類問題來求解，即假設(shè)兩個作者間存在一條鏈接，如果分類器給這條鏈接的分類值為1的話，就認(rèn)為這兩位作者會在未來共同寫一遍文章，0則不會。進(jìn)一步地，研究者們嘗試了多種常用的有監(jiān)督學(xué)習(xí)分類模型，包括決策樹、K近鄰、多層感知器、支持向量機(jī)和徑向基函數(shù)網(wǎng)絡(luò)。

3 鏈接值的預(yù)測

3.1 問題描述

隨著在線社會網(wǎng)絡(luò)服務(wù)的進(jìn)步，用戶可以使用越來越復(fù)雜的功能，例如從原來的只能表達(dá)“粉，贊”這類正極性鏈接（positive links），增加到可以表達(dá)“黑，踩”等負(fù)極性鏈接。隨著這些功能的出現(xiàn)，研究者們也開始研究對負(fù)極性鏈接（negative links）的預(yù)測[7，8]。主要研究對象為能提供正、負(fù)兩種或多種評價(jià)、標(biāo)簽等服務(wù)的社會網(wǎng)絡(luò)。例如Slashdot Zoo中的用戶直接可以標(biāo)明對方是朋友（Friend）或是敵人（Foe），又例如Wikipedia等網(wǎng)站允許用戶自身選舉時的投票預(yù)測。以上這些關(guān)系，同樣可以用圖來表示，如圖6所示。其中，節(jié)點(diǎn)表示用戶，每個鏈接表示用戶之間發(fā)生過的某種交互、評價(jià)或態(tài)度，鏈接邊上的值用來表示具體的交互內(nèi)容。

3.2 常用方法

因?yàn)橐肓税?fù)極性值的鏈接，以及用戶行為的有向性，使得鏈接網(wǎng)絡(luò)結(jié)構(gòu)變得更加復(fù)雜，能提取出的特征也增加了?；谶@些數(shù)據(jù)，研究者們設(shè)計(jì)了很多方法對用戶之間的鏈接值進(jìn)行預(yù)測。其中一種為將負(fù)極性邊引入用戶相似度度量，Symeonidis和Tiakas[9]將節(jié)點(diǎn)負(fù)極性度數(shù)引入相似度計(jì)算，并利用最短路徑來計(jì)算不直接相連節(jié)點(diǎn)之間的相似度。另外一種比較常用的方法是將對鏈接值的預(yù)測轉(zhuǎn)化為分類問題，使用訓(xùn)練集樣本的特征訓(xùn)練相應(yīng)的分類器，再用該分類器來對測試集中兩個節(jié)點(diǎn)之間的鏈接值進(jìn)行預(yù)測。Leskovec等[10]使用邏輯斯蒂回歸模型來預(yù)測兩個節(jié)點(diǎn)的鏈接值的極性，具體就是隱去網(wǎng)絡(luò)中的一條鏈接邊，從其余邊提取特稱，包括節(jié)點(diǎn)的度數(shù)和邊的鏈接值。之后使用這些特征訓(xùn)練分類器并進(jìn)行預(yù)測。

隨著社會網(wǎng)絡(luò)服務(wù)的功能更加豐富，越來越多的網(wǎng)絡(luò)可以用包含正、負(fù)兩種鏈接的鏈接網(wǎng)絡(luò)來建模，Leskovec等[11]將這種網(wǎng)絡(luò)統(tǒng)稱為“極性網(wǎng)絡(luò)（signed network）”，Agrawal等[12]將正、負(fù)極性的鏈接值稱為“鏈接標(biāo)簽（link label）”。這些研究都使用了邏輯斯蒂回歸來預(yù)測Epinions（用戶信用）、Slasdot（敵友關(guān)系）和Wikipedia RfA（管理員選舉）的鏈接網(wǎng)絡(luò)中的鏈接值。在分析學(xué)習(xí)到的模型的同時，研究者們發(fā)現(xiàn)發(fā)現(xiàn)不少有趣的社會網(wǎng)絡(luò)現(xiàn)象。最近的研究中，Liu等[13]使用基于深度置信網(wǎng)絡(luò)的深度學(xué)習(xí)方法，進(jìn)一步提升了對極性網(wǎng)絡(luò)中鏈接極性值的預(yù)測性能。

4 結(jié)束語

社會網(wǎng)絡(luò)中鏈接預(yù)測的方法和應(yīng)用研究，由最原始的對鏈接存在預(yù)測為開端發(fā)展至今，其研究框架日趨清晰，各關(guān)鍵問題的研究逐步深入，研究方向和應(yīng)用領(lǐng)域也越發(fā)廣泛。鏈接預(yù)測主要任務(wù)包括對鏈接存在的預(yù)測和鏈接值的預(yù)測，而且對鏈接存在的預(yù)測也可以看成一種預(yù)測鏈接值是否為正極性的情況，所以某種程度上可以說鏈接預(yù)測最根本的研究還是對鏈接值的預(yù)測。解決鏈接預(yù)測任務(wù)的方法可以歸結(jié)為基于用戶相似度度量，以及基于分類器的鏈接極性值分類兩大種類。前者在需要較少的計(jì)算開銷前提下能提供可以接受的結(jié)果，后者借助于機(jī)器學(xué)習(xí)方法提供較高的準(zhǔn)確率。

參考文獻(xiàn)：

[1] BOCCALETTI S， LATORA V， MORENO Y， et al. Complex networks： Structure and dynamics[J]. Physics reports， 2006， 424（4）：175–308.

[2] SMITH M A， SHNEIDERMAN B， MILIC-FRAYLING N， et al. Analyzing （social media） networks with NodeXL[C]//Proceedings of the fourth international conference on Communities and technologies. New York， NY， USA： ACM， 2009：255–264.

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

[4] 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（7）：1019–1031.

[5] DONG L， LI Y， YIN H， et al. The algorithm of link prediction on Social Network[J]. Mathematical Problems in Engineering， 2013（1）：1-7.

[6] AL HASAN M， CHAOJI V， SALEM S， et al. Link prediction using supervised learning[C]//SDM06： Workshop on Link Analysis， Counter-terrorism and Security. Philadelphia， PA， USA： SIAM， 2006：1––10.

[7] HSIEH C J， CHIANG K Y， DHILLON I S. Low rank modeling of signed networks[C]//Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. New York， NY， USA： ACM， 2012：507–515.

[8] TANG J， CHANG S， AGGARWAL C， et al. Negative link prediction in social media[C]//Proceedings of the Eighth ACM International Conference on Web Search and Data Mining. New York， NY， USA： ACM， 2015：87–96.

[9] SYMEONIDIS P， TIAKAS E. Transitive node similarity： predicting and recommending links in signed social networks [J]. World Wide Web， 2014， 17（4）：743–776.

[10] LESKOVEC J， HUTTENLOCHER D， KLEINBERG J. Predicting positive and negative links in online social networks[C]//Proceedings of the 19th international conference on World wide web. New York， NY， USA： ACM， 2010：641–650.

[11] LESKOVEC J， HUTTENLOCHER D， KLEINBERG J. Signed networks in social media[C]//Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. New York， NY， USA： ACM， 2010：1361–1370.

[12] AGRAWAL P， GARG V K， NARAYANAM R. Link label prediction in signed social networks[C]//Proceedings of the Twenty-Third international joint conference on Artificial Intelligence. Palo Alto， CA， USA： AAAI Press， 2013：2591–2597.

[13] LIU F， LIU B， SUN C， et al. Deep belief network-based approaches for link prediction in signed social networks[J]. Entropy， 2015， 17（4）：2140–2169.