社會網絡鏈接預測研究方法探析

，

“社會網絡”是指社會行動者及其之間關系的集合。一個社會網絡由多個節點和節點之間的鏈接組成，其中節點代表個人或其他實體，鏈接表示他們之間的關系。社會網絡通過網絡模型刻畫社會實體之間的關系，分析社會關系之間的模式和隱含規律，已廣泛用于社會學、政治學等多個領域。早期由于數據收集等方面的限制，僅局限于小的團體。在當今大數據時代背景下，社會網絡規模龐大，簡單的數學知識和原始的人工處理已經不可能對其進行有效的分析[1]。從數據挖掘角度，社會網絡分析也被稱為鏈接挖掘[2]。它強調實體之間的相互作用對數據挖掘結果的影響，并擴展了傳統數據挖掘中的分類、聚類等任務。

1 鏈接預測研究內容及意義

鏈接預測(Link Prediction)是鏈接挖掘領域中的重要研究方向，是指根據對象或實體的屬性以及已有的鏈接信息預測兩個對象或實體之間是否存在鏈接。它包括兩方面的含義：一方面可以理解為識別實際存在但當前網絡中并不可見的鏈接，比如蛋白質相互作用網絡、基因調控網絡等等；另一方面可理解為基于時刻t的社會網絡狀態預測t+1時刻將會在網絡中增加哪些鏈接，如在線社交網絡、推薦系統等。鏈接預測擁有廣闊的應用前景，如以新浪微博、FaceBook為代表的在線社交網絡，通過鏈接預測，可向用戶推薦好友或可能感興趣的話題。總之，鏈接預測結果可幫助我們從理論上更好地認識和解釋復雜網絡演化的機制，有助于網絡演化機制的進一步研究。

2 鏈接預測研究方法及特點

目前，鏈接預測研究越來越引起人們的關注，計算機領域、物理學領域的學者都提出了各自的方法。下面介紹幾種目前鏈接預測研究中的常用方法。

2.1 基于網絡的拓撲結構

將社會網絡表示為一個無向圖G=，其中V代表頂點集合，E為邊的集合。假設V固定不變，E隨時間推移不斷變化。時間段[t0，t1)(t0

2.1.1 基于鄰接點的方法

該方法的核心思想為兩個有著共同朋友的人比其他人更有可能成為朋友。對于節點x，用Γ(x)表示x在圖G中的近鄰。基于上述思想，如果 Γ(x)與 Γ(y)有很大的交集，那么它們在之后產生鏈接的可能性就會很大。常用的指標有以下幾種：

(1)公共近鄰(Common Neighbors)：假設兩個節點之間的公共鄰接點越多，它們就越相似。這是最為直接的想法，定義為[3]：

Sxy=|Γ(x)∩Γ(y)|

(2)Jaccard Index：用來描述節點x和y之間擁有相同鄰接點的比率，定義為：

(3)Adamic/Adar指數：公共近鄰和Jaccard系數都是簡單的計數，將所有的近鄰同等對待，而Adamic/Adar方法考慮了近鄰的性質，定義為[4]：

其中k(z)=∣Γ(z)∣，表示節點z的度。

(4)Preferential Attachment(偏好連接、偏好依附)：由Barabasi和Albert[5]提出，其核心思想是在真實網絡中，新增加的邊并不是隨機連接的，而是傾向于和具有較大度數的點連接，認為從節點x增加一條邊的概率正比于節點x當前的鄰接點的數目。定義為：

Sxy=k(x)×k(y)

Zhou T[6]等在此基礎上提出了一種新的相似性測量指標，并認為在鏈接預測中有更好的表現，即：

(5)Resource Allocation(資源配置)：定義為：

2.1.2 基于路徑的方法

最短距離(Shortest Distance)是基于路徑的方法中最簡單的方法。兩個節點之間的路徑越短(除去直接連接的邊)，則越可能鏈接。

Katz方法是Katz在研究社會網絡時提出一種基于路徑的計算節點聲望的方法。給予短路徑更高的權重，然后將所有的路徑加起來，定義為[7]：

Local Path也是由Zhou T等人提出的，定義為[8]：

S=A2+∈A3

其中∈為參數，A為鄰接矩陣，如果節點x和y直接相連，則Axy=1，否則Axy=0。

Liben-Nowell和Kleinberg[9]是最早提出社會網絡鏈接預測模型的學者之一。他們分析了多種基于網絡拓撲結構的相似性指標，如最短路徑、共同鄰居等指標在科學合著網絡中的鏈接預測效果。Zhou T[6]將11種局部算法應用于蛋白質相互作用網絡、科學家合著網、美國航空網絡等6個實際網絡的鏈接預測中，結果顯示最簡單的測量指標公共近鄰的效果最好，Adamic-Adar指數其次。他們提出的資源配置指標與Adamic-Adar 指數相類似，效果比公共近鄰的還好，尤其是對于平均度數較高的網絡。Lü[10]等人對比了公共近鄰、Katz 指數、Local Path 3個指標在鏈接預測時的準確度及其計算復雜度。實驗表明，公共近鄰的計算復雜度最低，但因信息不充足，準確度較低。另外，Katz指數為全局算法，精確度較高，同時計算復雜度也很高。而Local Path是一個很好的權衡，既可以得到相對較高的準確度又不會有很高的時間復雜度。

在利用節點相似性進行鏈接預測時，對于含權網絡的算法的研究還很少。通常我們都認為權重較大的鏈接在預測中起重要作用，但Lü[11]等人給出了公共近鄰、Adamic-Adar指數和資源配置的含權表達式，并將其應用在3個實際網絡的預測中，發現權重較小的鏈路反而起到了更關鍵的作用。Murata和Moriyasu[12]在公共近鄰、 Adamic-Adar指數和偏好連接的基礎上，提出了3種加權的相似性指標。

基于網絡拓撲結構的預測方法計算相對簡單。由于復雜網絡的稀疏性等特點，計算時要充分考慮算法的時間及空間復雜性。同時，基于網絡拓撲結構方法忽略了節點自身的一些社會屬性，導致準確性不高。

2.2 基于網絡節點的屬性

其基本思想是如果兩個節點擁有的共同特征越多，則認為它們越相似。如兩個人具有相同的年齡、學歷、職業、興趣等，則認為他們很像[13]。Getoor[14]等人認為，實體的屬性與實體之間的關系有一定的聯系，如有共同興趣或愛好的人更容易成為朋友。在目前的研究中，基于節點屬性的方法主要有分類算法和馬爾可夫鏈兩類。

2.2.1 分類算法

鏈接預測問題經常被看作是一個簡單的二元分類問題：對于可能有鏈接存在的兩個節點Vi,Vj,，預測lij是1還是0。根據當前網絡的連接關系，抽取關系特征集，利用分類算法來分析訓練數據集并構造分類器，即鏈接預測模型，訓練后的分類器即可對未知的鏈接關系進行預測[15]。Hasan[16]等人將最短路徑等拓撲學特征、關鍵詞匹配數量等屬性作為合著網中每對節點的特征集，用支持向量機、決策樹、k最近鄰分類法及樸素貝葉斯等分類算法進行了預測。Pavlov[17]從科學家合著網中抽取出公共近鄰、最短路徑、Jaccard系數等屬性作為每對節點的特征向量，通過支持向量機、決策樹等分類器進行預測。Guns[18]構建了非洲、中東和南亞3個城市瘧疾和肺結核研究領域的加權合著網絡，運用機器學習方法發現潛在合作。Naoki Shibata[19]抽取引文網絡的結構特征，共同鄰居、Jaccard系數、中間中心度以及文獻本身的語義特征和屬性特征(如被引頻次、自引)，利用支持向量機構造分類器，對引文網絡的節點之間的鏈接進行預測。

基于分類的鏈接預測引入分類器，綜合多個特征，并利用先驗知識訓練樣本進行預測，顯著提高了預測的準確率[15]。抽取一些特征向量構造分類器的難點也在于特征值的正確選取。此外，該方法只能預測網絡中已有節點之間產生鏈接的可能性，未考慮到隨時間推移而新增的節點。

2.2.2 馬爾可夫鏈預測方法

馬爾可夫預測是應用隨機過程中馬爾可夫鏈的理論和方法，研究分析有關現象的變化規律并借此對未來進行預測的一種方法，是根據事件目前的狀況預測其在將來各個時刻(或時期)的變動狀況的一種預測方法。馬爾可夫鏈模型具有隨機性、無后效性及不過分依賴歷史數據等特點。與其他統計方法(回歸分析、時間序列等)的不同之處在于它無需從各個復雜的預測因子中尋找其相互規律以滿足應用馬爾科夫鏈進行分析預測的條件，而只需考慮事件本身歷史狀況的演變特點，通過計算狀態轉移概率從而預測內部狀態的變化，故馬爾可夫鏈模型在預測中具有廣泛的實用性。

Zhu[20-21]等運用馬爾可夫鏈對自適應網站的用戶瀏覽路徑進行了預測。Bestavros[22]和Sarukkai[23]使用馬爾可夫模型預測用戶在某確定時間內可能鏈接的網頁。

利用節點屬性信息雖然可大大提高鏈接預測的準確性，但也存在很多問題。如由于隱私和其他方面的原因，信息往往很難獲取，而且對于一些在線社交網絡，用戶注冊時填寫信息的真實性和完整性不高，即便獲得相關信息也難于確定其準確性。

2.3 統計關系學習方法

統計關系學習又稱為概率邏輯學習。它是將概率推理模型和邏輯、關系模式結合起來，利用數據間的依賴關系以求得到更高的預測或分類的準確度。現已提出似然關系模型、貝葉斯邏輯程序模型、關系馬爾可夫模型等有關統計關系學習方面的模型。

Popsecul[24]利用一種結構化的邏輯回歸模型對科技文獻的引證關系進行預測，這種模型可以利用關系特征來預測鏈接的存在。關系特征的定義是由數據庫查詢引入的，作者顯示了如何搜索關系特征空間。Taskar[25-26]等在鏈接預測領域上應用關系馬爾可夫網RMN(Relational Markov Networks)框架，在整個連接圖上定義了一個聯合概率模型，關系馬爾可夫網算法在子圖結構上定義了概率模式。在大學網頁和社會網兩個關系數據集上進行試驗的結果表明，運用RMN的集體分類方法和鏈接標簽上的子圖模式比扁(Flat)數據分類在預測精度上有顯著的提高。

基于概率模型的算法利用節點、鏈接的歷史關系信息，能夠發掘網絡中潛在的各種關聯，準確性較好。但是由于多數人們感興趣的數據集是稀疏的，因此鏈接預測構造統計模型的一個難點在于鏈接的先驗概率往往很低，模型建立的復雜度往往比較高[27-28]。

2.4 協同過濾(Collaborative Filtering)算法

隨著互聯網和電子商務技術快速發展，推薦系統應運而生。協同過濾技術是目前研究最多、應用最廣也是最為成功的推薦技術之一。通過參考與用戶具有相似興趣或需求的其他用戶的選擇對當前用戶進行推薦的基本思想為“和我興趣愛好相似的人喜歡這樣東西，那我也會喜歡這樣東西”。Huang[29-30]等人以一個在線書店為例，在協同過濾算法中引入社會網絡鏈接預測研究中的6種基于網絡拓撲結構的相似性指標，并對結果進行了比較，發現Katz index的效果最好，其次是偏好鏈接、公共近鄰和Adamic/Adar指數。協同過濾算法中同樣存在網絡稀疏性問題。

3 總結

科學知識網絡的結構與演化一直都是情報學領域所關心的核心問題之一[31]。為了描繪科學知識結構，我們從文章、作者、主題、期刊等不同角度解釋某研究領域的結構及其發展狀態。但利用社會網絡分析方法對科學知識網絡的研究目前尚且處于“描述”階段，如通過聚類等方法描述某一領域研究熱點。在信息、知識大爆炸的今天，僅僅“描述”并不能夠滿足人們的需求，而是要做到如何“預測”。如果我們能夠對知識網絡進行很好的預測，就能在一定程度上把握學科未來的發展方向。鏈接預測研究作為數據挖掘領域的一個新的研究方向，主要集中在復雜網絡、計算機、物理學等研究領域。本文總結了目前鏈接預測研究的常用方法，總體來看，基于節點屬性的方法準確率相對較高，但屬性信息不容易獲取；基于網絡拓撲結構的方法相對容易些。對于實際中的網絡，都存在網絡稀疏性的問題，導致算法的復雜性大大增加。

在生物醫學領域，生物數據迅速增長，但仍有很多生物信息，如蛋白質相互作用信息等還未被發現。通過鏈接預測技術對生物信息網絡進行預測，可以避免盲目預測所有鏈接，能指導實驗，節省時間及開銷。在圖書情報學領域，有學者利用分類算法對合著網絡進行鏈接預測研究，并且近年來有成為熱點的趨勢。圖書情報學的鏈接預測研究雖然尚處于初步應用性階段，但通過對科研合著網、引文網絡等進行鏈接預測研究，可以為科研合作、管理決策等提供依據[32]。