社會網(wǎng)絡中的鏈接預測任務

劉峰　劉秉權　王曉龍

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

關鍵詞：鏈接預測；社會計算；用戶相似度度量；極性值分類

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

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

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

1 社會網(wǎng)絡的結構與特點

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

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

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

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

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

2 鏈接存在的預測

2.1 問題描述

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

2.2 常用方法

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

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

3 鏈接值的預測

3.1 問題描述

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

3.2 常用方法

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

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

4 結束語

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

參考文獻：

[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.