社會網(wǎng)絡(luò)鏈接預(yù)測研究方法探析

，

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

1 鏈接預(yù)測研究內(nèi)容及意義

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

2 鏈接預(yù)測研究方法及特點(diǎn)

目前，鏈接預(yù)測研究越來越引起人們的關(guān)注，計(jì)算機(jī)領(lǐng)域、物理學(xué)領(lǐng)域的學(xué)者都提出了各自的方法。下面介紹幾種目前鏈接預(yù)測研究中的常用方法。

2.1 基于網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)

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

2.1.1 基于鄰接點(diǎn)的方法

該方法的核心思想為兩個(gè)有著共同朋友的人比其他人更有可能成為朋友。對于節(jié)點(diǎn)x，用Γ(x)表示x在圖G中的近鄰?；谏鲜鏊枷?，如果 Γ(x)與 Γ(y)有很大的交集，那么它們在之后產(chǎn)生鏈接的可能性就會很大。常用的指標(biāo)有以下幾種：

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

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

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

(3)Adamic/Adar指數(shù)：公共近鄰和Jaccard系數(shù)都是簡單的計(jì)數(shù)，將所有的近鄰?fù)葘Υ?，而Adamic/Adar方法考慮了近鄰的性質(zhì)，定義為[4]：

其中k(z)=∣Γ(z)∣，表示節(jié)點(diǎn)z的度。

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

Sxy=k(x)×k(y)

Zhou T[6]等在此基礎(chǔ)上提出了一種新的相似性測量指標(biāo)，并認(rèn)為在鏈接預(yù)測中有更好的表現(xiàn)，即：

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

2.1.2 基于路徑的方法

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

Katz方法是Katz在研究社會網(wǎng)絡(luò)時(shí)提出一種基于路徑的計(jì)算節(jié)點(diǎn)聲望的方法。給予短路徑更高的權(quán)重，然后將所有的路徑加起來，定義為[7]：

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

S=A2+∈A3

其中∈為參數(shù)，A為鄰接矩陣，如果節(jié)點(diǎn)x和y直接相連，則Axy=1，否則Axy=0。

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

在利用節(jié)點(diǎn)相似性進(jìn)行鏈接預(yù)測時(shí)，對于含權(quán)網(wǎng)絡(luò)的算法的研究還很少。通常我們都認(rèn)為權(quán)重較大的鏈接在預(yù)測中起重要作用，但Lü[11]等人給出了公共近鄰、Adamic-Adar指數(shù)和資源配置的含權(quán)表達(dá)式，并將其應(yīng)用在3個(gè)實(shí)際網(wǎng)絡(luò)的預(yù)測中，發(fā)現(xiàn)權(quán)重較小的鏈路反而起到了更關(guān)鍵的作用。Murata和Moriyasu[12]在公共近鄰、 Adamic-Adar指數(shù)和偏好連接的基礎(chǔ)上，提出了3種加權(quán)的相似性指標(biāo)。

基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的預(yù)測方法計(jì)算相對簡單。由于復(fù)雜網(wǎng)絡(luò)的稀疏性等特點(diǎn)，計(jì)算時(shí)要充分考慮算法的時(shí)間及空間復(fù)雜性。同時(shí)，基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)方法忽略了節(jié)點(diǎn)自身的一些社會屬性，導(dǎo)致準(zhǔn)確性不高。

2.2 基于網(wǎng)絡(luò)節(jié)點(diǎn)的屬性

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

2.2.1 分類算法

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

基于分類的鏈接預(yù)測引入分類器，綜合多個(gè)特征，并利用先驗(yàn)知識訓(xùn)練樣本進(jìn)行預(yù)測，顯著提高了預(yù)測的準(zhǔn)確率[15]。抽取一些特征向量構(gòu)造分類器的難點(diǎn)也在于特征值的正確選取。此外，該方法只能預(yù)測網(wǎng)絡(luò)中已有節(jié)點(diǎn)之間產(chǎn)生鏈接的可能性，未考慮到隨時(shí)間推移而新增的節(jié)點(diǎn)。

2.2.2 馬爾可夫鏈預(yù)測方法

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

Zhu[20-21]等運(yùn)用馬爾可夫鏈對自適應(yīng)網(wǎng)站的用戶瀏覽路徑進(jìn)行了預(yù)測。Bestavros[22]和Sarukkai[23]使用馬爾可夫模型預(yù)測用戶在某確定時(shí)間內(nèi)可能鏈接的網(wǎng)頁。

利用節(jié)點(diǎn)屬性信息雖然可大大提高鏈接預(yù)測的準(zhǔn)確性，但也存在很多問題。如由于隱私和其他方面的原因，信息往往很難獲取，而且對于一些在線社交網(wǎng)絡(luò)，用戶注冊時(shí)填寫信息的真實(shí)性和完整性不高，即便獲得相關(guān)信息也難于確定其準(zhǔn)確性。

2.3 統(tǒng)計(jì)關(guān)系學(xué)習(xí)方法

統(tǒng)計(jì)關(guān)系學(xué)習(xí)又稱為概率邏輯學(xué)習(xí)。它是將概率推理模型和邏輯、關(guān)系模式結(jié)合起來，利用數(shù)據(jù)間的依賴關(guān)系以求得到更高的預(yù)測或分類的準(zhǔn)確度?，F(xiàn)已提出似然關(guān)系模型、貝葉斯邏輯程序模型、關(guān)系馬爾可夫模型等有關(guān)統(tǒng)計(jì)關(guān)系學(xué)習(xí)方面的模型。

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

基于概率模型的算法利用節(jié)點(diǎn)、鏈接的歷史關(guān)系信息，能夠發(fā)掘網(wǎng)絡(luò)中潛在的各種關(guān)聯(lián)，準(zhǔn)確性較好。但是由于多數(shù)人們感興趣的數(shù)據(jù)集是稀疏的，因此鏈接預(yù)測構(gòu)造統(tǒng)計(jì)模型的一個(gè)難點(diǎn)在于鏈接的先驗(yàn)概率往往很低，模型建立的復(fù)雜度往往比較高[27-28]。

2.4 協(xié)同過濾(Collaborative Filtering)算法

隨著互聯(lián)網(wǎng)和電子商務(wù)技術(shù)快速發(fā)展，推薦系統(tǒng)應(yīng)運(yùn)而生。協(xié)同過濾技術(shù)是目前研究最多、應(yīng)用最廣也是最為成功的推薦技術(shù)之一。通過參考與用戶具有相似興趣或需求的其他用戶的選擇對當(dāng)前用戶進(jìn)行推薦的基本思想為“和我興趣愛好相似的人喜歡這樣?xùn)|西，那我也會喜歡這樣?xùn)|西”。Huang[29-30]等人以一個(gè)在線書店為例，在協(xié)同過濾算法中引入社會網(wǎng)絡(luò)鏈接預(yù)測研究中的6種基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的相似性指標(biāo)，并對結(jié)果進(jìn)行了比較，發(fā)現(xiàn)Katz index的效果最好，其次是偏好鏈接、公共近鄰和Adamic/Adar指數(shù)。協(xié)同過濾算法中同樣存在網(wǎng)絡(luò)稀疏性問題。

3 總結(jié)

科學(xué)知識網(wǎng)絡(luò)的結(jié)構(gòu)與演化一直都是情報(bào)學(xué)領(lǐng)域所關(guān)心的核心問題之一[31]。為了描繪科學(xué)知識結(jié)構(gòu)，我們從文章、作者、主題、期刊等不同角度解釋某研究領(lǐng)域的結(jié)構(gòu)及其發(fā)展?fàn)顟B(tài)。但利用社會網(wǎng)絡(luò)分析方法對科學(xué)知識網(wǎng)絡(luò)的研究目前尚且處于“描述”階段，如通過聚類等方法描述某一領(lǐng)域研究熱點(diǎn)。在信息、知識大爆炸的今天，僅僅“描述”并不能夠滿足人們的需求，而是要做到如何“預(yù)測”。如果我們能夠?qū)χR網(wǎng)絡(luò)進(jìn)行很好的預(yù)測，就能在一定程度上把握學(xué)科未來的發(fā)展方向。鏈接預(yù)測研究作為數(shù)據(jù)挖掘領(lǐng)域的一個(gè)新的研究方向，主要集中在復(fù)雜網(wǎng)絡(luò)、計(jì)算機(jī)、物理學(xué)等研究領(lǐng)域。本文總結(jié)了目前鏈接預(yù)測研究的常用方法，總體來看，基于節(jié)點(diǎn)屬性的方法準(zhǔn)確率相對較高，但屬性信息不容易獲?。换诰W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的方法相對容易些。對于實(shí)際中的網(wǎng)絡(luò)，都存在網(wǎng)絡(luò)稀疏性的問題，導(dǎo)致算法的復(fù)雜性大大增加。

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