王智強 梁吉業(yè), 李 茹,

1(山西大學(xué)計算機與信息技術(shù)學(xué)院 太原 030006)2 (計算智能與中文信息處理教育部重點實驗室(山西大學(xué)) 太原 030006)

社交信息(social-information)網(wǎng)絡(luò)[1](如微博，Twitter等)，不僅包含用戶間的網(wǎng)絡(luò)結(jié)構(gòu)，同時存在大量用戶所分享的文本信息，具有規(guī)模大、動態(tài)變化、信息混雜等大數(shù)據(jù)通常所具有的特點，屬于典型的網(wǎng)絡(luò)大數(shù)據(jù)[2].圖1為一個帶有文本信息的Twitter數(shù)據(jù)集可視化示例，圖1(a)中的網(wǎng)絡(luò)代表用戶間關(guān)注被關(guān)注(follwingfollowed)的有向網(wǎng)絡(luò)，圖1(b)分別對應(yīng)網(wǎng)絡(luò)中每個用戶所分享的Tweet文本信息.

Fig. 1 A Twitter example of social-information network with text information圖1 帶有文本信息的社交信息網(wǎng)絡(luò)Twitter示例

鏈路預(yù)測作為網(wǎng)絡(luò)數(shù)據(jù)挖掘中一項基本挖掘任務(wù)[3]，它在許多研究及應(yīng)用領(lǐng)域發(fā)揮著重要作用.例如對于網(wǎng)絡(luò)演化[4-5]、網(wǎng)絡(luò)數(shù)據(jù)補齊[6-7]等問題的研究具有重要意義，同時在推薦[8-9]、生物信息[10]等領(lǐng)域發(fā)揮著重要應(yīng)用價值.鏈路預(yù)測的研究目標[11-13]是預(yù)測當前網(wǎng)絡(luò)中節(jié)點之間是否存在缺失的連邊或是未來網(wǎng)絡(luò)中是否會產(chǎn)生新的連邊.本文將面向社交信息網(wǎng)絡(luò)，針對其信息混雜特點，從信息融合角度研究社交信息網(wǎng)絡(luò)中的鏈路預(yù)測問題.

目前針對鏈路預(yù)測的研究已有來自計算機、物理、生物等許多不同領(lǐng)域的研究者，針對不同的網(wǎng)絡(luò)提出針對性的鏈路預(yù)測方法.現(xiàn)有鏈路預(yù)測方法通常從網(wǎng)絡(luò)的拓撲結(jié)構(gòu)出發(fā)，通過定義網(wǎng)絡(luò)中節(jié)點間的拓撲度量或通過建立網(wǎng)絡(luò)的統(tǒng)計學(xué)習(xí)模型來獲得網(wǎng)絡(luò)中節(jié)點間鏈路的可能性.已有基于度量的方法中，如基于鄰居信息[14-16]、路徑信息[17-18]、隨機游走[19-20]等度量方法考慮了網(wǎng)絡(luò)中節(jié)點間的拓撲相似度距離.基于學(xué)習(xí)的方法如層次網(wǎng)絡(luò)模型[6]、隨機塊模型[21-22]、潛在特征模型[23-25]及矩陣分解模型[26-27]等從網(wǎng)絡(luò)結(jié)構(gòu)全局出發(fā)來學(xué)習(xí)節(jié)點間的鏈路可能性，相比基于度量的方法具有更好的適用范圍.

盡管當前針對不同網(wǎng)絡(luò)的鏈路預(yù)測方法研究已經(jīng)取得了許多進展，但面向信息混雜的社交信息網(wǎng)絡(luò)的鏈路預(yù)測研究仍然有待深入.用戶所分享的文本信息作為眾多形式信息中廣泛存在的數(shù)據(jù)載體，如何充分利用用戶所分享的文本信息來提高面向社交信網(wǎng)絡(luò)的鏈路預(yù)測是一個挑戰(zhàn).社交信息網(wǎng)絡(luò)中，信息的傳播依賴于網(wǎng)絡(luò)中節(jié)點間的關(guān)注被關(guān)注關(guān)系，1條Tweet會從其發(fā)布者傳遞到其跟隨者(關(guān)注者)，同時在Tweet的傳播過程中也會影響到網(wǎng)絡(luò)中鏈路關(guān)系的形成.如當用戶對某條Tweet十分感興趣時，該用戶將有一定可能性成為此信息發(fā)布者的關(guān)注者.當然除此之外，社交信息網(wǎng)絡(luò)中鏈路的變化與信息傳播間相互影響的情況還有許多.從建模角度來講，如何將拓撲的網(wǎng)絡(luò)結(jié)構(gòu)與非拓撲的文本信息進行融合建模是面向社交信息網(wǎng)絡(luò)鏈路預(yù)測的關(guān)鍵.

本文試圖從信息融合的角度，在抽取用戶主題信息的基礎(chǔ)上，構(gòu)建用戶間的主題相似網(wǎng)絡(luò)，并提出融合用戶間關(guān)注被關(guān)注網(wǎng)絡(luò)與主題相似網(wǎng)絡(luò)的概率矩陣分解模型；進一步基于模型學(xué)習(xí)到的用戶潛在特征表示與用戶間的鏈路參數(shù)計算用戶間的鏈路可能性，實現(xiàn)面向社交信息網(wǎng)絡(luò)的鏈路預(yù)測.

1 相關(guān)研究

目前針對網(wǎng)絡(luò)中鏈路預(yù)測問題所提出的方法主要包括：基于度量的方法、基于分類的方法、基于概率圖的方法及基于矩陣分解方法等.

1.1 基于度量的方法

通過定義網(wǎng)絡(luò)節(jié)點間拓撲或非拓撲上的度量來對網(wǎng)絡(luò)節(jié)點間的連邊可能性進行打分是鏈路預(yù)測中最為常見的方法.拓撲度量是利用網(wǎng)絡(luò)中節(jié)點對間的各種拓撲信息來定義，如基于鄰居信息的度量有公共鄰居(common neighbors， CN)[15]、Jaccard[28]、大度節(jié)點有利(hub promoted， HP)[29]、大度節(jié)點不利(hub depressed， HD)[13]、鄰居貢獻(adamic-adar， AA)[14]、偏好性(preferential attachment， PA)[16]以及資源分配(resource allocation， RA)[7]等.Katz[17]，Local Path[18]，F(xiàn)riendLink[30]等方法利用了網(wǎng)絡(luò)中節(jié)點間路徑信息；平均通勤時間(average commute time， ACT)[13]、余弦相似度時間(cosine similarity time， CST)[19]、重啟隨機游走(random walk with restart， RWR)[31]、SimRank[20]、局部隨機游走(local random walk， LRW)[32]等則是基于網(wǎng)絡(luò)隨機游走過程來定義.社交網(wǎng)絡(luò)中常見的非拓撲信息包括用戶的簡介、標簽、文本信息、關(guān)鍵詞等[25,33-35].Matthew等人[33]基于用戶標簽進行用戶相似度度量.Prantik等人[35]基于關(guān)鍵詞分析社交網(wǎng)絡(luò)用戶的相似度.已有基于拓撲或非拓撲信息度量的鏈路方法通常與具體網(wǎng)絡(luò)的性質(zhì)、領(lǐng)域等密切相關(guān)，單一度量方法往往容易領(lǐng)域受限.

1.2 基于分類的方法

基于分類的方法是將鏈路預(yù)測看作二分類問題，其中將網(wǎng)絡(luò)中存在連邊的節(jié)點對看作正例，沒有連邊的節(jié)點對看作負例.在建立分類模型時，許多分類器如支撐向量機(support vector machine， SVM)、邏輯斯蒂回歸(logistic regression， LR)、k近鄰(k-nearest neighbor，kNN)、樸素貝葉斯(Naive Bayesian， NB)等被用在鏈路預(yù)測問題中，而影響預(yù)測結(jié)果的關(guān)鍵因素之一是特征選擇問題.Sa等人[36]利用節(jié)點對間的公共鄰居、Jaccard、鄰居貢獻、偏好性及局部路徑等來作為分類的特征；Lichtenwalter等人[37]提出了一種基于節(jié)點搭配的局部拓撲特征；Leskovec等人[38]利用節(jié)點的度和三元組特征來實現(xiàn)鏈路預(yù)測；Chiang等人[39]擴展了Leskovec等人[38]的工作，提出從更長的網(wǎng)絡(luò)環(huán)路中來抽取拓撲特征.同1.1節(jié)中的度量方法類似，分類模型的特征選擇同樣容易受網(wǎng)絡(luò)性質(zhì)、領(lǐng)域等影響，且類的非平衡性問題也是制約基于分類模型進行鏈路預(yù)測的一個瓶頸.

1.3 基于概率圖模型的方法

概率圖模型是對網(wǎng)絡(luò)數(shù)據(jù)進行建模的一類重要方法，它能夠從網(wǎng)絡(luò)全局出發(fā)揭示深層次的網(wǎng)絡(luò)結(jié)構(gòu)與性質(zhì).Clauset等人[6]提出一種層次網(wǎng)絡(luò)模型，將網(wǎng)絡(luò)建模為一種層次結(jié)構(gòu)，其中葉子節(jié)點對應(yīng)網(wǎng)絡(luò)節(jié)點，中心節(jié)點對應(yīng)不同葉子節(jié)點間的鏈路概率.隨機塊模型[21-22]假設(shè)網(wǎng)絡(luò)節(jié)點可以被劃分為不同的組，節(jié)點間的鏈路可能性由節(jié)點所在的組決定.潛在特征模型[23-24]是一種產(chǎn)生式模型，它假設(shè)網(wǎng)絡(luò)中的節(jié)點可以用潛在特征向量來表示，網(wǎng)絡(luò)中連邊的產(chǎn)生式基于節(jié)點的潛在特征表示和連邊產(chǎn)生的分布假設(shè).已有網(wǎng)絡(luò)概率圖模型通常能夠獲得較好的鏈路預(yù)測效果，然而此類模型具有較高的計算復(fù)雜度，難以適用于較大規(guī)模的網(wǎng)絡(luò)，且難以擴展到具有混雜信息的網(wǎng)絡(luò)中.

1.4 基于矩陣分解的方法

矩陣分解方法是通過對網(wǎng)絡(luò)的鄰接矩陣進行低秩近似來解決鏈路預(yù)測問題.目前，矩陣分解方法如奇異值分解(singular value decomposition, SVD)[40]、非負矩陣分解(non-negative matrix factorization, NNMF)[41]及概率矩陣分解(probabilistic matrix factorization, PMF)[42]等已被廣泛用于推薦系統(tǒng).相比基于推薦方法，基于矩陣分解的網(wǎng)絡(luò)鏈路預(yù)測方法研究仍有待深入.Menon等人[26]通過在矩陣分解時加入排序損失來克服鏈路預(yù)測中的非平衡問題，在鏈路預(yù)測準確率與效率2方面都獲得了較好的結(jié)果.Zhai等人[27]提出一種結(jié)合矩陣分解和自編碼的鏈路預(yù)測方法，獲得了較好的鏈路預(yù)測效果.矩陣分解方法通?？梢圆捎秒S機梯度下降等快速算法來實現(xiàn)，容易適用于大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)[26].總體來講，矩陣分解方法在解決網(wǎng)絡(luò)鏈路預(yù)測問題時通常具有時間與效果兩方面的綜合優(yōu)勢，但目前仍缺乏面向帶有混雜信息網(wǎng)絡(luò)的矩陣分解鏈路預(yù)測方法.

本文試圖從矩陣分解方法入手，通過結(jié)合社交信息網(wǎng)絡(luò)中用戶的文本內(nèi)容信息，建立一種能夠融合用戶網(wǎng)絡(luò)結(jié)構(gòu)和文本信息的矩陣分解方法，在此基礎(chǔ)上實現(xiàn)面向社交信息網(wǎng)絡(luò)的鏈路預(yù)測.

2 融合的概率矩陣分解模型

社交信息網(wǎng)絡(luò)既包含用戶間的網(wǎng)絡(luò)拓撲結(jié)構(gòu)信息，同時還包括豐富的用戶文本信息.本文基于概率矩陣分解模型來建模的目標是為了將2種信息融合在統(tǒng)一的概率分解框架下，以獲得新空間下融合2種信息的用戶表示，將此模型稱為：融合概率矩陣分解模型(fusion probability matrix factorization, FPMF).以下分3小節(jié)來介紹FPMF模型.為便于理解，在此將文中涉及的主要符號匯總為表1：

Table 1 The List of the Main Notations表1 主要符號列表

2.1 用戶主題相似網(wǎng)絡(luò)構(gòu)建

同質(zhì)性[43-44]是社交網(wǎng)絡(luò)中普遍存在的一種特性，它指社交網(wǎng)絡(luò)中具有相似性的人之間容易產(chǎn)生鏈接，而存在鏈接的人之間也會因為相互影響而具有一定相似性.同質(zhì)性說明社交網(wǎng)絡(luò)中鏈路的產(chǎn)生與用戶相似性之間具有一定相關(guān)性.本節(jié)試圖從用戶的主題相似度出發(fā)，利用社交信息網(wǎng)絡(luò)中用戶分享的文本信息抽取用戶主題表示，并定義用戶間的主題相似度，進一步基于主題相似度構(gòu)建一種用戶間的主題相似網(wǎng)絡(luò).

為獲取用戶主題信息，我們將每個用戶歷史所分享的所有微博信息看作一個文檔，n個用戶組成包含n個文檔的文檔集合D.基于潛在狄利克雷(latent Dirichlet allocation, LDA)主題模型[45]，抽取每個用戶的主題分布表示(見4.1節(jié)關(guān)于數(shù)據(jù)預(yù)處理的內(nèi)容).

由于LDA模型所抽取的用戶主題向量是一種多項分布表示，而KL(Kullback-Leibler)[46]散度適合于度量分布之間的距離，因此首先采用了KL散度來度量用戶間的主題分布距離；然后基于指數(shù)函數(shù)exp(-x)將此距離映射到(0,1)之間作為相似度度量.考慮到KL度量是一種非對稱的距離度量，對其進行了對稱化處理.具體地，用戶主題相似度定義如下：

(1)

基于主題相似度(式(1))，定義用戶之間的主題相似網(wǎng)絡(luò)如下：

定義2. 用戶主題相似網(wǎng)絡(luò).用四元組NS=(V,E,S,Sthr)表示用戶主題相似度網(wǎng)絡(luò).V表示此網(wǎng)絡(luò)的節(jié)點集合；E表示網(wǎng)絡(luò)中邊的集合；S表示該網(wǎng)絡(luò)的鄰接矩陣，其中矩陣S中每個元素的取值Si j代表用戶i與用戶j之間的主題相似度；Sthr表示構(gòu)建主題相似網(wǎng)絡(luò)的稀疏化參數(shù)，即當用戶間的主題相似度值大于Sthr時，為其建立一條無向的邊，反之不建立邊，因此，Sthr的取值直接影響主題相似網(wǎng)絡(luò)的稀疏性，Sthr越大網(wǎng)絡(luò)越稀疏.

如圖2所示，一個包含282個用戶的Twitter數(shù)據(jù)集的主題相似網(wǎng)絡(luò)構(gòu)建過程.圖2中從左至右分別表示用戶的Tweets信息、主題向量以及用戶間的主題相似網(wǎng)絡(luò)，其中網(wǎng)絡(luò)稀疏化參數(shù)Sthr=0.7.需要提及的是，對用戶主題相似網(wǎng)絡(luò)進行稀疏化，主要基于2方面考慮：一方面在利用用戶大量的文本信息來計算用戶間主題相似度時不可避免會有噪聲，稀疏化設(shè)置使后續(xù)建模中只關(guān)注相似性較大的連邊，緩解噪聲影響；另一方面，網(wǎng)絡(luò)稀疏化能夠減小模型的計算復(fù)雜度.稀疏化參數(shù)Sthr的具體選取將在實驗部分(4.4.3節(jié))進行詳細實驗分析與討論.

Fig. 2 The construction process of the users’ topic similarity-based network圖2 用戶主題相似網(wǎng)絡(luò)構(gòu)建

2.2 FPMF模型

從概率產(chǎn)生式角度，網(wǎng)絡(luò)NA和NS的產(chǎn)生式過程可以用3個步驟來描述：

其對應(yīng)的概率圖如圖3所示.

Fig. 3 The probabilistic graph model of FPMF圖3 FPMF模型概率圖表示

在網(wǎng)絡(luò)產(chǎn)生式過程的第1步，網(wǎng)絡(luò)中每個節(jié)點i的潛在向量Ui∈1×L從高斯先驗分布N(0,中產(chǎn)生，網(wǎng)絡(luò)中所有節(jié)點的潛在特征矩陣U的先驗分布滿足

(2)

(3)

在生成網(wǎng)絡(luò)節(jié)點的潛在特征表示矩陣U和網(wǎng)絡(luò)NA的鏈路關(guān)系矩陣參數(shù)W的基礎(chǔ)上，進一步產(chǎn)生網(wǎng)絡(luò)NA和NS中的連邊與非連邊.見網(wǎng)絡(luò)產(chǎn)生式過程的第3步：網(wǎng)絡(luò)NA中任意節(jié)點對i,j間的連邊Ai j=1或非連邊Ai j=0是基于高斯分布N(gA(Ui,Uj),產(chǎn)生的，即

(4)

其中，gA(Ui,Uj)是為了度量網(wǎng)絡(luò)NA中任意節(jié)點對i,j間鏈路關(guān)系而定義的關(guān)系函數(shù)：

(5)

基于網(wǎng)絡(luò)NA中每對節(jié)點連邊與非連邊的產(chǎn)生過程，其概率分布可以記為

在此統(tǒng)一的概率產(chǎn)生式框架下，主題相似網(wǎng)絡(luò)NS中任意節(jié)點對i,j連邊與不連邊同樣基于一個高斯分布N(gS(Ui,Uj),而產(chǎn)生，即

(7)

其中，gS(Ui,Uj)是度量主題相似網(wǎng)絡(luò)NS中任意節(jié)點對i,j之間的鏈路關(guān)系度量函數(shù)，定義如下：

(8)

依據(jù)第3步中主題相似網(wǎng)絡(luò)NS的產(chǎn)生過程，其概率分布表示為

基于網(wǎng)絡(luò)NA和網(wǎng)絡(luò)NS的整個產(chǎn)生過程，融合概率矩陣分解的目標就是通過極大化網(wǎng)絡(luò)中節(jié)點的潛在特征表示U和鏈路參數(shù)矩陣W的后驗分布，來估計極大后驗下的U和W，即

(10)

由于網(wǎng)絡(luò)NA和NS是已知可觀察的，式(10)中的后驗分布正比于如下聯(lián)合概率分布：

(11)

因此，式(10)等價于

(13)

將式(2)(3)(6)(9)帶入式(13)，并取對數(shù)形式，可以推導(dǎo)出式(13)的優(yōu)化目標等價于最小化如下目標函數(shù)：

,

(14)

.

(15)

目標函數(shù)的局部最小值可以采用梯度下降方法進行求解[47]，參數(shù)U和W的梯度下降公式為

(16)

(17)

以包含有282個用戶的社交信息網(wǎng)絡(luò)Twitter為例(如圖4)，圖4(a)為用戶之間的關(guān)注被關(guān)注網(wǎng)絡(luò)NA，圖4(b)為構(gòu)建的用戶主題相似網(wǎng)絡(luò)NS.模型的意義在于：通過共享同一個網(wǎng)絡(luò)節(jié)點的潛在特征表示U，將網(wǎng)絡(luò)NA鄰接矩陣A的近似A≈UWUT和網(wǎng)絡(luò)NS鄰接矩陣S的近似S≈UUT融合在一個矩陣分解模型中.

Fig. 4 Sketch of the FPMF model圖4 FPMF模型示意圖

2.3 模型復(fù)雜度分析

由于矩陣A與矩陣S的稀疏性，A與U乘積的計算復(fù)雜度為O(ηAL)，其中ηA為稀疏網(wǎng)絡(luò)A中非0項個數(shù)；類似地，SU的乘積復(fù)雜度為O(ηSL)，ηS為矩陣S中的非零項個數(shù)；剩余部分乘積的計算復(fù)雜度為O(nL2).因此，模型求解時每次迭代的總時間復(fù)雜度為O(ηAL+ηSL+nL2).由于網(wǎng)絡(luò)的稀疏性，網(wǎng)絡(luò)中邊的個數(shù)幾乎是網(wǎng)絡(luò)節(jié)點數(shù)的倍數(shù)，則有ηA=O(n)與ηS=O(n)，因此模型每次迭代的復(fù)雜度理論上與網(wǎng)絡(luò)節(jié)點個數(shù)成近似的線性關(guān)系.

3 基于FPMF的鏈路預(yù)測

基于FPMF模型，能夠?qū)W習(xí)到網(wǎng)絡(luò)NA和網(wǎng)絡(luò)NS中節(jié)點共同的潛在特征表示U以及網(wǎng)絡(luò)NA中的鏈路參數(shù)矩陣W.依據(jù)模型中所描述的網(wǎng)絡(luò)NA的產(chǎn)生式過程，對于任意節(jié)點對i,j間產(chǎn)生連邊的概率可以計算如下：

P(i,j=1)=P(Ai j=1|Ui,Uj,W,
.

(18)

算法1. 基于FPMF模型的鏈路預(yù)測.

輸入：關(guān)注網(wǎng)絡(luò)鄰接矩陣A、主題相似網(wǎng)絡(luò)鄰接矩陣S；

輸出：鏈路預(yù)測的AUC(area under the receiver operating characteristic)值和Accuracy值.

① 初始化：網(wǎng)絡(luò)節(jié)點的潛在特征矩陣UN×L，網(wǎng)絡(luò)A的鏈路參數(shù)矩陣UL×L，L=integer?n；

② REPEAT

UnewUold-γ，見式(16)；

WnewWold-γ，見式(17)；

③ UNTIL CONVERGENCE

END FOR

⑤ 基于P值對所有未知節(jié)點對進行排序；

⑥ 基于排序計算鏈路預(yù)測結(jié)果的AUC值和Accuracy值，見式(19)(20)；

⑦ RETRUN:AUC和Accuracy.

4 實驗及結(jié)果分析

4.1 實驗數(shù)據(jù)

驗證本文方法所需的數(shù)據(jù)集需同時包含用戶間的網(wǎng)絡(luò)結(jié)構(gòu)和用戶的文本信息，本文采用了兩種社交信息網(wǎng)絡(luò)數(shù)據(jù)集，Weibo和Twitter，均來源于唐杰團隊在文獻[48]中所共享的數(shù)據(jù).由于原始數(shù)據(jù)集中有許多用戶沒有發(fā)表過或者很少發(fā)表微博Tweets，難以滿足用戶主題抽取需求，因此實驗中僅抽取了網(wǎng)絡(luò)中發(fā)表或轉(zhuǎn)發(fā)微博Tweets數(shù)量超過100條的用戶.最終在2個原始的數(shù)據(jù)集中分別抽取了4組子數(shù)據(jù)集：Weibo 1，Weibo 2，Twitter 1，Twitter 2，如表2所示：

Table 2 Datasets表2 數(shù)據(jù)集

針對中文數(shù)據(jù)集Weibo 1和Weibo 2的微博文本預(yù)處理主要包括：首先去除掉其中的非文本字符，如數(shù)字、表情符號等；然后進行分詞和停用詞去除處理，并對用戶發(fā)表或轉(zhuǎn)發(fā)微博時經(jīng)常會出現(xiàn)的“分享”、“轉(zhuǎn)發(fā)”、“微博”等頻繁詞也進行去除處理.針對Twitter數(shù)據(jù)集，由于文獻[48]中的原始數(shù)據(jù)集已對Tweets進行了預(yù)處理，本實驗中不作進一步處理.

在數(shù)據(jù)集預(yù)處理基礎(chǔ)上，為獲得用戶主題表示，我們將網(wǎng)絡(luò)中每個用戶所有發(fā)表或轉(zhuǎn)發(fā)微博Tweets看作一個文檔，然后采用Scikit-learn[49]工具包所提供的LDA主題抽取工具對網(wǎng)絡(luò)用戶的主題進行抽取，獲得用戶的分布式主題向量表示.

4.2 實驗設(shè)置與評價指標

依據(jù)鏈路預(yù)測相關(guān)文獻通常采用的實驗設(shè)置[6,13,27]，實驗中將數(shù)據(jù)集中的網(wǎng)絡(luò)劃分為訓(xùn)練集和測試集.具體地，本實驗將網(wǎng)絡(luò)劃分為90%∶10%，其中90%的部分作為訓(xùn)練集，10%作為測試集，且劃分時分別執(zhí)行獨立隨機劃分5次，每次隨機劃分保證訓(xùn)練集網(wǎng)絡(luò)的連通性.

結(jié)果評價時，采用了2種評價指標：一是鏈路預(yù)測中最為常用的AUC評價指標[13]；另一種是鏈路預(yù)測結(jié)果的準確率指標Accuracy.

1)AUC指標

AUC是指ROC曲線(receiver operating char-acteristic curve)下方的面積.實際計算時可以采用抽樣的方法來計算AUC值[13,50]，即在測試集中隨機選擇一條邊的分值比在不存在的邊集合中隨機選擇一條邊的分值高的概率.具體計算公式為

(19)

其中，n′表示隨機從測試集與不存在邊的集合中抽取n次出現(xiàn)n′次抽取的測試集邊的分值大于沒有邊的分值，而n″是分值相等的次數(shù).

2)Accuracy指標

Accuracy是指預(yù)測的準確率，其計算公式為：

(20)

其中，L表示測試集中共有L條邊，k表示在排序前L個節(jié)點對中正確的個數(shù).

4.3 比較方法

為驗證本文方法在社交信息網(wǎng)絡(luò)中鏈路預(yù)測的有效性，設(shè)置了2部分比較實驗：一是本文方法與2種基線(baseline)方法作比較；二是本文與已有相關(guān)文獻中常見的鏈路預(yù)測方法進行比較.

4.3.1 基線方法

基線方法的設(shè)定是為了驗證本文融合模型將2種信息(網(wǎng)絡(luò)和主題)在融合后相比融合前的優(yōu)勢.具體設(shè)定了2種基線方法：

1) 基本概率矩陣分解的方法

基本概率矩陣分解的方法是只針對網(wǎng)絡(luò)結(jié)構(gòu)進行概率矩陣分解，即只針對網(wǎng)絡(luò)A進行概率矩陣分解，其形式化表示為：

(21)

2) 基于主題相似度量的方法

基于主題相似度量的方法是利用用戶的主題信息，通過度量用戶間主題相似度的大小進行鏈路預(yù)測.用戶間主題相似度的計算見式(1)，此方法記為TS(topic similarity).

4.3.2 已有的鏈路預(yù)測方法

1) Katz

Katz是在已有文獻[13]中被驗證表現(xiàn)最好的方法之一.對于給定網(wǎng)絡(luò)中的節(jié)點對i,j，Katz方法定義如下：

(22)

2) 公共鄰居(CN)[13]

CN指標是鏈路預(yù)測中非常廣泛使用的指標，它在許多網(wǎng)絡(luò)也被驗證通常具有良好的表現(xiàn)[13].由于社交信息網(wǎng)絡(luò)中用戶之間是關(guān)注與被關(guān)注的關(guān)系，用戶之間具有不同類型的鄰居，即關(guān)注者或被關(guān)注者.因此，在定義用戶間CN指標時利用了不同類型的鄰居，最終采用4種CN指標：CN1，CN2，CN3，CN4，如表3所示：

Table 3 CN Indexes表3 CN指標

表3中Γ+(i)表示社交信息網(wǎng)絡(luò)中關(guān)注用戶i的用戶集合，Γ-(i)表示被用戶i關(guān)注的用戶集合，|Γ+(i)|和|Γ-(i)|分別代表集合Γ+(i)與Γ-(i)的用戶數(shù)量.

3) 偏好性(PA)

偏好性指標PA也是在社交網(wǎng)絡(luò)中常用的鏈路預(yù)測方法[13].給定網(wǎng)絡(luò)中用戶i與用戶j的鄰居數(shù)量，PA指標等于2個用戶鄰居數(shù)據(jù)的乘積.同CN類似，依據(jù)社交信息網(wǎng)絡(luò)中不同類型的鄰居，采用了4組不同的PA指標：PA1，PA2，PA3，PA4，如表4所示：

Table 4 PA Indexes表4 PA指標

4) 低秩近似(low-rank approximation, LAR)

低秩近似方法的目的是尋找一個低秩矩陣用來近似原始的矩陣.在鏈路預(yù)測中，低秩近似方法通過計算得到一個秩為k的最優(yōu)低秩矩陣Ak用來近似原始的網(wǎng)絡(luò)鄰接矩陣A.進行鏈路預(yù)測時，將矩陣Ak中的第i行和第j列對應(yīng)位置取值作為節(jié)點對i,j間鏈路的打分.文獻[12]采用了奇異值分解SVD方法對原始網(wǎng)絡(luò)矩陣進行低秩近似表示.本文實驗中不僅采用了SVD方法，同時也采用了非負矩陣分解方法NNMF，將2種基于低秩近似表示的鏈路預(yù)測方法分別記為：LAR-SVD和LAR-NNMF.

4.4 實驗結(jié)果及分析

實驗中經(jīng)過反復(fù)測試發(fā)現(xiàn)，參數(shù)分別進行設(shè)置時結(jié)果最優(yōu)：

Twitter 1中，L=80，Sthr=0.9，λS=0.8,

Twitter 2中，L=40，Sthr=0.97，λS=0.6,

Weibo 1中，L=80，Sthr=0.9，λS=1.6,

Weibo 2中，L=60，Sthr=0.9，λS=0.6.

除上述參數(shù)外，模型中的正則化參數(shù)設(shè)置為λU=λW=0.05.以下實驗中若非特別說明，上述參數(shù)均為最優(yōu)結(jié)果時的參數(shù).

4.4.1 基線方法比較

表5為本文方法FPMF與基線方法BPMF和TS在4組數(shù)據(jù)集中的比較結(jié)果.

Table 5 Comparison of Baseline Methods表5 基線方法比較(AUC±std)

從表5中可以看出FPMF方法在4組數(shù)據(jù)集中比2個基線方法獲得了更好的AUC結(jié)果.2種基線方法BPMF和TS分別是基于用戶網(wǎng)絡(luò)結(jié)構(gòu)和主題相似信息進行鏈路預(yù)測，而FPMF是將2種信息融合在統(tǒng)一的概率產(chǎn)生式框架下進行鏈路預(yù)測.實驗中融合后的方法能夠優(yōu)于融合前的2種方法，驗證了本文融合概率矩陣分解的有效性.

4.4.2 與已有方法比較

圖5與圖6分別顯示了本文方法與已有4類共11種常見鏈路預(yù)測方法比較的AUC和Accuracy結(jié)果.從圖5,6中可看到，F(xiàn)PMF方法在4組數(shù)據(jù)集中大多數(shù)情況下獲得了最好的Accuracy和AUC，并在不同的數(shù)據(jù)集中FPMF方法能夠獲得較為穩(wěn)定的結(jié)果.比較方法中，基于公共鄰居的4種方法(CN1，CN2，CN3，CN4)在2組Weibo數(shù)據(jù)集上的表現(xiàn)都要差于2組Twitter數(shù)據(jù)集，說明其預(yù)測能力的不穩(wěn)定.在基于偏好指標的方法(PA1，PA2，PA3，PA4)中，PA1與PA2表現(xiàn)較好，且能夠獲得相比公共鄰居更好的AUC結(jié)果，同時在2類數(shù)據(jù)集中保持了較好的穩(wěn)定性，但就Accuracy結(jié)果而言明顯低于本文FPMF方法.同偏好指標類似，基于Katz的方法能夠獲得相對不錯的AUC結(jié)果，但Accuracy結(jié)果也明顯低于本文方法.這說明在鏈路預(yù)測排序精度方面，本文FPMF方法能夠獲得更好的鏈路排序結(jié)果.

Fig. 5 Accuracy results of comparison methods圖5 比較方法的Accuracy結(jié)果

Fig. 6 AUC results of comparison methods圖6 比較方法的AUC結(jié)果

相比基于公共鄰居、偏好性和Katz方法，基于低秩近似的方法(LAR-SVD，LAR-NNMF)在不同數(shù)據(jù)集中獲得了更穩(wěn)定的AUC和Accuracy結(jié)果，但這2種方法仍然低于本文FPMF方法.總的來說，本文方法既繼承了低秩近似方法的穩(wěn)定性，同時由于融合了社交信息網(wǎng)絡(luò)中拓撲和非拓撲2方面信息，使得該方法與已有鏈路預(yù)測方法相比有明顯提升.

4.4.3 稀疏參數(shù)Sthr分析

本文FPMF方法中，參數(shù)Sthr用來控制用戶主題相似網(wǎng)絡(luò)S的稀疏化程度，Sthr取值越大主題相似網(wǎng)絡(luò)越稀疏.圖7顯示了稀疏化參數(shù)Sthr的不同取值在4組數(shù)據(jù)集中對鏈路預(yù)測結(jié)果和算法性能的影響.每個圖中橫軸代表稀疏化參數(shù)Sthr的取值(從0.1～0.99)，2個縱軸分別代表模型算法迭代1 000次所花費的時間和鏈路預(yù)測的AUC結(jié)果.從圖7(a)～(d)中時間曲線可以看出，隨著稀疏化參數(shù)Sthr取值變大，模型算法迭代所花費的時間會明顯減小.這說明用戶主題相似網(wǎng)絡(luò)越稀疏，算法運行所需時間越少.觀察圖7(a)～(d)中的AUC曲線，可以發(fā)現(xiàn)隨著稀疏化參數(shù)Sthr取值增大，鏈路預(yù)測AUC的結(jié)果也在提高，而當稀疏化參數(shù)Sthr達到一定閾值時預(yù)測結(jié)果將會停止提高甚至減小.以上現(xiàn)象說明用戶主題相似網(wǎng)絡(luò)的稀疏化程度在一定程度影響最終鏈路預(yù)測的結(jié)果與性能，合理選擇Sthr取值能夠有效提升鏈路預(yù)測結(jié)果.分析其原因，我們認為當Sthr取值很大時，用戶主題相似網(wǎng)絡(luò)會十分稀疏，F(xiàn)PMF模型中只能考慮少量的用戶對之間具有很高主題相似度的信息，而當Sthr取值很小時，模型中將會考慮大量用戶對之間的主題相似度信息，從而增加噪聲，一定程度影響鏈路預(yù)測結(jié)果.

Fig. 7 Analysis of the sparse parameters圖7 稀疏化參數(shù)分析

4.4.4 參數(shù)λS分析

λS參數(shù)是平衡FPMF模型中用戶關(guān)注被關(guān)注網(wǎng)絡(luò)和主題相似網(wǎng)絡(luò)2種信息的.如果模型中λS=0，等同于只考慮用戶間關(guān)注網(wǎng)絡(luò)的信息(如基線中的BPMF方法)；如果λS取無窮大，模型只考慮用戶間主題相似網(wǎng)絡(luò)的信息.

圖8(a)～(d)顯示了該模型在4組數(shù)據(jù)集中隨著λS參數(shù)取值變化時AUC結(jié)果的變化.可以看到隨著λS參數(shù)取值增大，AUC結(jié)果開始提升;當λS參數(shù)增加到一定閾值時，AUC結(jié)果會停止提升甚至開始下降.這說明在模型中應(yīng)選擇適中的λS參數(shù)來平衡用戶關(guān)注被關(guān)注網(wǎng)絡(luò)和用戶主題相似網(wǎng)絡(luò)2種信息.

Fig. 8 Analysis of the weight parameters圖8 權(quán)重參數(shù)分析

5 結(jié)論與展望