，

“社會網(wǎng)絡(luò)”是指社會行動者及其之間關(guān)系的集合。一個社會網(wǎng)絡(luò)由多個節(jié)點(diǎn)和節(jié)點(diǎn)之間的鏈接組成，其中節(jié)點(diǎn)代表個人或其他實(shí)體，鏈接表示他們之間的關(guān)系。社會網(wǎng)絡(luò)通過網(wǎng)絡(luò)模型刻畫社會實(shí)體之間的關(guān)系，分析社會關(guān)系之間的模式和隱含規(guī)律，已廣泛用于社會學(xué)、政治學(xué)等多個領(lǐng)域。早期由于數(shù)據(jù)收集等方面的限制，僅局限于小的團(tuán)體。在當(dāng)今大數(shù)據(jù)時代背景下，社會網(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ù)測兩個對象或?qū)嶓w之間是否存在鏈接。它包括兩方面的含義：一方面可以理解為識別實(shí)際存在但當(dāng)前網(wǎng)絡(luò)中并不可見的鏈接，比如蛋白質(zhì)相互作用網(wǎng)絡(luò)、基因調(diào)控網(wǎng)絡(luò)等等；另一方面可理解為基于時刻t的社會網(wǎng)絡(luò)狀態(tài)預(yù)測t+1時刻將會在網(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ī)領(lǐng)域、物理學(xué)領(lǐng)域的學(xué)者都提出了各自的方法。下面介紹幾種目前鏈接預(yù)測研究中的常用方法。

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

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

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

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

(1)公共近鄰(Common Neighbors)：假設(shè)兩個節(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ù)都是簡單的計數(shù)，將所有的近鄰?fù)葘Υ鳤damic/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)是基于路徑的方法中最簡單的方法。兩個節(jié)點(diǎn)之間的路徑越短(除去直接連接的邊)，則越可能鏈接。

Katz方法是Katz在研究社會網(wǎng)絡(luò)時提出一種基于路徑的計算節(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個實(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個指標(biāo)在鏈接預(yù)測時的準(zhǔn)確度及其計算復(fù)雜度。實(shí)驗(yàn)表明，公共近鄰的計算復(fù)雜度最低，但因信息不充足，準(zhǔn)確度較低。另外，Katz指數(shù)為全局算法，精確度較高，同時計算復(fù)雜度也很高。而Local Path是一個很好的權(quán)衡，既可以得到相對較高的準(zhǔn)確度又不會有很高的時間復(fù)雜度。

在利用節(jié)點(diǎn)相似性進(jìn)行鏈接預(yù)測時，對于含權(quán)網(wǎng)絡(luò)的算法的研究還很少。通常我們都認(rèn)為權(quán)重較大的鏈接在預(yù)測中起重要作用，但Lü[11]等人給出了公共近鄰、Adamic-Adar指數(shù)和資源配置的含權(quán)表達(dá)式，并將其應(yīng)用在3個實(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ù)測方法計算相對簡單。由于復(fù)雜網(wǎng)絡(luò)的稀疏性等特點(diǎn)，計算時要充分考慮算法的時間及空間復(fù)雜性。同時，基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)方法忽略了節(jié)點(diǎn)自身的一些社會屬性，導(dǎo)致準(zhǔn)確性不高。

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

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

2.2.1 分類算法

鏈接預(yù)測問題經(jīng)常被看作是一個簡單的二元分類問題：對于可能有鏈接存在的兩個節(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個城市瘧疾和肺結(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ù)測引入分類器，綜合多個特征，并利用先驗(yàn)知識訓(xùn)練樣本進(jìn)行預(yù)測，顯著提高了預(yù)測的準(zhǔn)確率[15]。抽取一些特征向量構(gòu)造分類器的難點(diǎn)也在于特征值的正確選取。此外，該方法只能預(yù)測網(wǎng)絡(luò)中已有節(jié)點(diǎn)之間產(chǎn)生鏈接的可能性，未考慮到隨時間推移而新增的節(jié)點(diǎn)。

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

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

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

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

統(tǒng)計關(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)計關(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)框架，在整個連接圖上定義了一個聯(lián)合概率模型，關(guān)系馬爾可夫網(wǎng)算法在子圖結(jié)構(gòu)上定義了概率模式。在大學(xué)網(wǎng)頁和社會網(wǎng)兩個關(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)計模型的一個難點(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]等人以一個在線書店為例，在協(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)與演化一直都是情報學(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)域的一個新的研究方向，主要集中在復(fù)雜網(wǎng)絡(luò)、計算機(jī)、物理學(xué)等研究領(lǐng)域。本文總結(jié)了目前鏈接預(yù)測研究的常用方法，總體來看，基于節(jié)點(diǎn)屬性的方法準(zhǔn)確率相對較高，但屬性信息不容易獲取；基于網(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é)省時間及開銷。在圖書情報學(xué)領(lǐng)域，有學(xué)者利用分類算法對合著網(wǎng)絡(luò)進(jìn)行鏈接預(yù)測研究，并且近年來有成為熱點(diǎn)的趨勢。圖書情報學(xué)的鏈接預(yù)測研究雖然尚處于初步應(yīng)用性階段，但通過對科研合著網(wǎng)、引文網(wǎng)絡(luò)等進(jìn)行鏈接預(yù)測研究，可以為科研合作、管理決策等提供依據(jù)[32]。