基于加權(quán)非負(fù)矩陣分解的鏈接預(yù)測(cè)算法

王萌萌,左萬利,王 英

(1.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,吉林長(zhǎng)春 130012; 2.符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室(吉林大學(xué)),吉林長(zhǎng)春 130012)

?

基于加權(quán)非負(fù)矩陣分解的鏈接預(yù)測(cè)算法

王萌萌1,2,左萬利1,2,王 英1,2

(1.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,吉林長(zhǎng)春 130012; 2.符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室(吉林大學(xué)),吉林長(zhǎng)春 130012)

本文針對(duì)在線微博，首先，基于帶權(quán)動(dòng)態(tài)鏈接預(yù)測(cè)特征集合，以用戶社會(huì)關(guān)系因子約束目標(biāo)函數(shù)，從用戶概要和用戶發(fā)布內(nèi)容兩個(gè)維度利用非負(fù)矩陣分解方法預(yù)測(cè)社會(huì)網(wǎng)絡(luò)中鏈接的存在性和方向性.然后，在真實(shí)的數(shù)據(jù)集上驗(yàn)證了提出框架的有效性，并通過實(shí)驗(yàn)進(jìn)一步證明了特征權(quán)重和時(shí)間信息在鏈接預(yù)測(cè)問題中的重要性.

有向鏈接預(yù)測(cè);非負(fù)矩陣分解;特征權(quán)重;時(shí)間信息;動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)

1 引言

隨著社會(huì)媒體的普及，每天有大量的用戶通過網(wǎng)絡(luò)中的關(guān)系結(jié)構(gòu)彼此交互并影響.作為關(guān)系結(jié)構(gòu)分析中的基礎(chǔ)問題，鏈接預(yù)測(cè)近年來受到了越來越多的關(guān)注，其不但能夠分析社會(huì)網(wǎng)絡(luò)中的缺失數(shù)據(jù)，還可被應(yīng)用到分子生物學(xué)[1]、犯罪調(diào)查[2]、信息檢索[3]和推薦系統(tǒng)[4]等領(lǐng)域.此外，其還有助于深入理解社會(huì)網(wǎng)絡(luò)的演化機(jī)理.綜上，除廣闊的應(yīng)用前景外，鏈接預(yù)測(cè)還具有重要的理論意義，然而，傳統(tǒng)算法并不能對(duì)動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的有向鏈接進(jìn)行預(yù)測(cè)，因此，本文提出了一種基于加權(quán)非負(fù)矩陣分解的鏈接預(yù)測(cè)模型(Weighted Nonnegative Matrix Factorization Model for Link Prediction，WNMFLP)，主要貢獻(xiàn)如下.

(1)根據(jù)鏈接預(yù)測(cè)特征與類別間的相關(guān)性量化特征的重要性，構(gòu)建帶權(quán)特征集合.

(2)基于用戶網(wǎng)絡(luò)結(jié)構(gòu)信息和發(fā)布內(nèi)容信息的時(shí)間序列構(gòu)建動(dòng)態(tài)鏈接預(yù)測(cè)特征，以刻畫網(wǎng)絡(luò)結(jié)構(gòu)與信息的動(dòng)態(tài)演變過程.

(3)利用用戶社會(huì)關(guān)系因子約束目標(biāo)函數(shù)，將預(yù)測(cè)問題轉(zhuǎn)化為求解用戶概要和用戶發(fā)布內(nèi)容兩個(gè)維度的加權(quán)非負(fù)矩陣分解最優(yōu)解問題，有效降低了時(shí)間復(fù)雜性且使其能夠準(zhǔn)確預(yù)測(cè)鏈接的存在性與方向性.

2 相關(guān)工作

近幾年，社會(huì)網(wǎng)絡(luò)中的鏈接預(yù)測(cè)問題吸引了國(guó)內(nèi)外眾多學(xué)者，學(xué)者們研究并利用不同的數(shù)學(xué)方法構(gòu)建鏈接預(yù)測(cè)模型，大大推動(dòng)了鏈接預(yù)測(cè)建模理論的發(fā)展[5～8].

由于僅基于拓?fù)浣Y(jié)構(gòu)特征的鏈接預(yù)測(cè)方法較為簡(jiǎn)單，所以一些學(xué)者對(duì)拓?fù)浣Y(jié)構(gòu)特征計(jì)算方法進(jìn)行了改進(jìn)：Schall[9]提出了一種基于三元閉合關(guān)系的拓?fù)浣Y(jié)構(gòu)特征，通過圖模式對(duì)節(jié)點(diǎn)間的鏈接進(jìn)行預(yù)測(cè)，并在真實(shí)數(shù)據(jù)集上驗(yàn)證了提出方法的有效性，其為社會(huì)網(wǎng)絡(luò)中有向鏈接的預(yù)測(cè)問題提供了一種新思路.Symeonidis等人[10]基于從Laplacian矩陣特征向量中獲取的信息，通過多路譜聚類方法對(duì)節(jié)點(diǎn)進(jìn)行社區(qū)劃分，并利用正鏈接和負(fù)鏈接的信息計(jì)算節(jié)點(diǎn)間的拓?fù)浣Y(jié)構(gòu)特征，從而實(shí)現(xiàn)鏈接的預(yù)測(cè).Fire等人[11]首先基于鏈接方向定義了一組拓?fù)浣Y(jié)構(gòu)特征，然后利用J48決策樹、Bagging和隨機(jī)森林方法在真實(shí)的數(shù)據(jù)集上進(jìn)行鏈接預(yù)測(cè)取得了較好的實(shí)驗(yàn)結(jié)果.

還有一些學(xué)者通過融合更多類型的信息對(duì)鏈接預(yù)測(cè)算法進(jìn)行改進(jìn)：Lou等人[12]基于地理距離和網(wǎng)絡(luò)同構(gòu)性對(duì)用戶鏈接關(guān)系的影響，提出了一種預(yù)測(cè)Twitter中節(jié)點(diǎn)間社會(huì)關(guān)系的學(xué)習(xí)模型.Jorge和Alneu[13]首先應(yīng)用社區(qū)檢測(cè)算法為節(jié)點(diǎn)劃分社區(qū)標(biāo)簽，然后基于社區(qū)信息和局部信息，分別通過監(jiān)督和非監(jiān)督的學(xué)習(xí)方法對(duì)網(wǎng)絡(luò)中的鏈接進(jìn)行預(yù)測(cè)，該方法首次在鏈接預(yù)測(cè)方法中融入了社區(qū)信息.

此外，一些研究者通過引入時(shí)間信息對(duì)鏈接預(yù)測(cè)算法進(jìn)行改進(jìn)：Soares和Prudêncio[14]基于非鏈接節(jié)點(diǎn)對(duì)間鄰近度分?jǐn)?shù)的時(shí)間序列，分別通過監(jiān)督和非監(jiān)督學(xué)習(xí)方法對(duì)節(jié)點(diǎn)間的鏈接進(jìn)行預(yù)測(cè)，并在其基礎(chǔ)上提出了一種基于時(shí)間事件的鄰近度度量方法[15]，其能夠較好地表示動(dòng)態(tài)變化的網(wǎng)絡(luò)結(jié)構(gòu)，并準(zhǔn)確地預(yù)測(cè)節(jié)點(diǎn)間的鏈接.Zhang等人[16]基于朋友關(guān)系的傳遞性，將以一個(gè)節(jié)點(diǎn)為中心的朋友網(wǎng)絡(luò)的增長(zhǎng)過程表示成樹狀結(jié)構(gòu)，除根節(jié)點(diǎn)外，樹中每個(gè)結(jié)點(diǎn)的位置由其與根節(jié)點(diǎn)建立朋友關(guān)系的時(shí)間決定，為鏈接預(yù)測(cè)模型構(gòu)建提供了一個(gè)新視角.

綜上，在動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)有向鏈接預(yù)測(cè)的研究中，如何刻畫鏈接的方向性和網(wǎng)絡(luò)的動(dòng)態(tài)性、量化不同特征的重要性以及構(gòu)建模型仍是非常具有挑戰(zhàn)性的工作.

3 動(dòng)態(tài)鏈接預(yù)測(cè)特征建模

3.1 動(dòng)態(tài)鏈接預(yù)測(cè)特征定義

3.1.1 用戶概要特征

本文將原始數(shù)據(jù)集[17]中的特征直接作為用戶概要特征，其中具有離散屬性的特征以不同的數(shù)值表示其所屬類別.

3.1.2 用戶動(dòng)態(tài)關(guān)系特征

由于用戶在網(wǎng)絡(luò)中的地位越相近，其拓?fù)浣Y(jié)構(gòu)越相似[18]，故其間越易建立聯(lián)系.根據(jù)社會(huì)網(wǎng)絡(luò)的動(dòng)態(tài)性，本文將網(wǎng)絡(luò)看作一個(gè)時(shí)間片流(一個(gè)時(shí)間片表示一天且一個(gè)時(shí)間片越久，其重要性越低，權(quán)重越小).由于傳統(tǒng)的拓?fù)涠攘课纯紤]鏈接的方向性，因此，首先擬基于鏈接的方向性對(duì)幾種傳統(tǒng)的度量方法進(jìn)行改進(jìn).

(1)改進(jìn)的Salton度量標(biāo)準(zhǔn)

Common Neighbors度量標(biāo)準(zhǔn)假設(shè)兩個(gè)用戶間的相似度與其擁有的共同鄰居數(shù)量成正比，Salton度量標(biāo)準(zhǔn)在其基礎(chǔ)上加入了兩個(gè)用戶的度信息.基于鏈接的方向性對(duì)其改進(jìn)后，用戶和用戶在第個(gè)時(shí)間片上的Salton值為：

Sa(u,v,ti)=

(1)

其中，Γin(u,ti)和Γin(v,ti)分別為u和v在ti上的入鏈接用戶集合；Γout(u,ti)和Γout(v,ti)分別為u和v在ti上的出鏈接用戶集合；入鏈接和出鏈接由用戶間的關(guān)注關(guān)系決定；|·|為集合的元素?cái)?shù)量.則在時(shí)間片流[0,tn]上，u和v的Salton值為：

(2)

其中，β∈[0,1]，βn-i為ti的權(quán)重，n為[0,tn]上的時(shí)間片總數(shù).

(2)改進(jìn)的Jaccard度量標(biāo)準(zhǔn)

Jaccard度量標(biāo)準(zhǔn)假設(shè)兩個(gè)用戶間的相似度正比于其擁有的共同鄰居數(shù)量與其所有鄰居數(shù)量的比值.基于鏈接的方向性對(duì)其改進(jìn)后，u和v在ti上的Jaccard值為：

Ja(u,v,ti)

(3)

本文以與式(2)中相同的βn-i表示ti的權(quán)重，則u和v在[0,tn]上的Jaccard值為：

(4)

(3)改進(jìn)的Preferential Attachment度量標(biāo)準(zhǔn)

Preferential Attachment度量標(biāo)準(zhǔn)假設(shè)用戶的度越大，該用戶與其他用戶建立鏈接的可能性就越大.基于鏈接的方向性對(duì)其改進(jìn)后，u和v在ti上的Preferential Attachment值為：

(5)

本文以與式(2)中相同的βn-i表示ti的權(quán)重，則u和v在[0,tn]上的Preferential Attachment值為：

(6)

3.1.3 用戶動(dòng)態(tài)發(fā)布內(nèi)容特征

有時(shí)，情感的“共鳴”使得用戶間更易建立聯(lián)系：若用戶A最近總是發(fā)布一些消極的狀態(tài)，而用戶B最近總是發(fā)布一些積極的狀態(tài)，則A很有可能建立指向B的鏈接，進(jìn)而從B發(fā)布的狀態(tài)中汲取正能量以平復(fù)自己低落的心情.因此，擬利用知網(wǎng)英文情感分析用詞語集(http://www.keenage.com/download/sentiment.rar)，基于用戶發(fā)布的文本信息計(jì)算用戶u在ti上的發(fā)布內(nèi)容特征：

Em(u,ti)=pn(u,ti)/nn(u,ti)

(7)

其中，pn(u,ti)和nn(u,ti)為u在ti上發(fā)表的微博文本集合中使用的包含在上述詞語集中的正向情感詞數(shù)和負(fù)向情感詞數(shù).以與式(2)中相同的βn-i表示ti的權(quán)重，則在[0,tn]上，u的動(dòng)態(tài)發(fā)布內(nèi)容特征為：

(8)

3.2 動(dòng)態(tài)鏈接預(yù)測(cè)特征權(quán)重分配

由于在鏈接預(yù)測(cè)問題中不同特征重要性不同，故為其合理分配權(quán)重就顯得尤為重要.肯德爾檢驗(yàn)是一種通過計(jì)算相關(guān)系數(shù)測(cè)試兩個(gè)隨機(jī)變量的統(tǒng)計(jì)依賴性的非參數(shù)假設(shè)檢驗(yàn)，因此，擬通過計(jì)算鏈接預(yù)測(cè)特征與類別間的肯德爾相關(guān)系數(shù)量化特征的重要性，隨機(jī)變量X和Y間的肯德爾相關(guān)系數(shù)為：

(9)

其中，τ(X,Y)∈[-1,1]，τ(X,Y)為1、-1和0時(shí)分別表示X和Y的等級(jí)相關(guān)性一致、不一致和相互獨(dú)立.C和D分別為和中擁有一致性和不一致性的元素對(duì)數(shù)；N為隨機(jī)變量的維數(shù)；N1和N2分別為X和Y中重復(fù)元素的總數(shù)，以N1為例，其計(jì)算如下：

(10)

其中，s為擁有相同元素的元素?cái)?shù)量；Ui為第i個(gè)元素?fù)碛邢嗤氐臄?shù)量；則特征i的權(quán)重其計(jì)算如下：

(11)

其中，ωi為特征i的權(quán)重，L∈{1,-1,0}表示鏈接類別，下一節(jié)中會(huì)對(duì)其進(jìn)行詳細(xì)定義，τ(i,L)為特征i與L間的肯德爾相關(guān)系數(shù)；m為特征維數(shù).

4 基于加權(quán)非負(fù)矩陣分解的鏈接預(yù)測(cè)模型

4.1 問題定義

文獻(xiàn)[19]中指出因?yàn)榧兗有院拖∈璧拿枋瞿苁箤?duì)數(shù)據(jù)的解釋變得合理，還因?yàn)橄鄬?duì)稀疏性的表示方式能在一定程度上抑制由外界變化給特征提取帶來的不利影響，所以非負(fù)矩陣分解方法已逐漸成為一種有效的多維數(shù)據(jù)處理工具.由于用戶鏈接矩陣是低秩且稀疏的，因此，擬將動(dòng)態(tài)網(wǎng)絡(luò)中有向鏈接的預(yù)測(cè)問題轉(zhuǎn)化為求解非負(fù)矩陣分解的最優(yōu)解問題.令u={u1,u2,…,um}表示用戶集合，m表示用戶數(shù)量；R∈m×m表示用戶-用戶矩陣，其中，假設(shè)ui到ui不存在鏈接，即；Rii=0;ui和uj(i≠j)間的鏈接預(yù)測(cè)結(jié)果可為：鏈接由ui指向uj(Rij=1)；鏈接由uj指向ui(Rij=-1)；ui與uj間無鏈接(Rij=0)，則本文將動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)中的有向鏈接預(yù)測(cè)問題定義為：給定用戶轉(zhuǎn)發(fā)矩陣R和用戶-特征矩陣U1，找到非負(fù)矩陣V1，使其滿足R≈UiVi，從而獲得鏈接關(guān)系預(yù)測(cè)矩陣R′=U1V1.

4.2 模型算法

首先，將R分解為矩陣U1∈m×d1和矩陣V1∈m×d1，其中，d1?m為用戶概要特征和用戶動(dòng)態(tài)發(fā)布內(nèi)容特征的總數(shù)，V1為R與U1低秩表示間的關(guān)系.然后，最小化預(yù)測(cè)值與實(shí)際值間的均方誤差，并加入U(xiǎn)1和V1的正則化Frobenius范數(shù)以避免發(fā)生過擬合：

(12)

其中，||·||F為Frobenius范數(shù)；λ1和λ2為正則化參數(shù).假設(shè)社會(huì)關(guān)系相似的用戶間用戶概要差異較小，因此，為約束用戶間用戶概要的差異，定義正則化的用戶社會(huì)關(guān)系因子為：

(13)

其中，S[0,tn](i,j)∈[0,1]為ui和uj間在[0,tn]上的社會(huì)關(guān)系因子，S[0,tn](i,j)越大，ui和uj間越可能建立鏈接，則用戶間Frobenius范數(shù)越小，ui和uj間在[0,tn]上的社會(huì)關(guān)系因子為：

S[0,tn](i,j) =ωSa·Sa[0,tn](i,j)+ωJa·Ja[0,tn](i,j)

+ωPa·Pa[0,tn](i,j)

(14)

其中，(U1)i*和(U1)j*分別為ui和uj的特征集合；Tr(·)為矩陣的跡；L=D-S[0,tn]為拉普拉斯矩陣，D為對(duì)角矩陣，D中的第i個(gè)元素D(i,i)為S[0,tn]中第行元素之和.則加入正則化社會(huì)因子的目標(biāo)函數(shù)為：

(15)

雖然較難形式化F1的全局最優(yōu)解，但F1的局部最優(yōu)解可以通過乘性迭代方法求得[20].為計(jì)算U1和V1的更新規(guī)則，去掉式(15)中的常數(shù)，其拉格朗日函數(shù)為：

-Tr(ψU1)-Tr(φV1)

(16)

其中，ψ和φ分別是U1和V1的非負(fù)拉格朗日乘子.然后，分別計(jì)算式(16)中關(guān)于U1和V1的梯度，并設(shè)其為0：

(17)

在式(17)兩邊分別乘以U1和V1：

(18)

(19)

則基于加權(quán)非負(fù)矩陣分解的鏈接預(yù)測(cè)模型如算法1所示.

算法1 基于加權(quán)非負(fù)矩陣分解的鏈接預(yù)測(cè)模型

輸入:用戶轉(zhuǎn)發(fā)矩陣R用戶-特征矩陣U1；用戶社會(huì)關(guān)系因子矩陣S[0,tn]；正則化參數(shù)λ1，λ2，λ3

輸出:鏈接關(guān)系預(yù)測(cè)矩陣R′

1:For U1中的每一列g(shù)Do

2: 根據(jù)式(11)計(jì)算相應(yīng)特征權(quán)重ωg

3: 以ωg乘以列g(shù)中元素，得到帶權(quán)的特征值

4:End for

6:Repeat

7: 根據(jù)式(19)更新U1和V1

8:Until 式(15)中的F1收斂

9:Return R′ ← U1V1

4.3 時(shí)間復(fù)雜度分析

5 實(shí)驗(yàn)及結(jié)果分析

5.1 數(shù)據(jù)集及實(shí)驗(yàn)設(shè)置

本文選用文獻(xiàn)[17]中的數(shù)據(jù)集驗(yàn)證提出方法的有效性，該數(shù)據(jù)集中收集了從2012年9月28日到10月29日的新浪微博網(wǎng)絡(luò)結(jié)構(gòu)信息，其統(tǒng)計(jì)數(shù)據(jù)如表1所示.

表1 新浪微博數(shù)據(jù)集統(tǒng)計(jì)數(shù)據(jù)

則實(shí)驗(yàn)設(shè)置如下：隨機(jī)將數(shù)據(jù)集分為兩部分——A和B.A為訓(xùn)練集合，占數(shù)據(jù)集的90%；余下的10%記作B，作為測(cè)試集合.為確保實(shí)驗(yàn)結(jié)果的可靠性，本文采用10折交叉驗(yàn)證利用準(zhǔn)確率，召回率和F1值對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)估.

5.2 對(duì)比實(shí)驗(yàn)

5.2.1 WNMFLP與其他鏈接預(yù)測(cè)方法的比較

本文基于新浪微博數(shù)據(jù)集將提出的o-WNMFLP與f-J48、f-Bagging、f-RF、o-J48、o-Bagging、o-RF和s-GM進(jìn)行對(duì)比，其中，f、s和o分別表示文獻(xiàn)[11]、文獻(xiàn)[9]和本文中定義的特征；J48、Bagging、RF和GM分別表示J48決策樹、Bagging、隨機(jī)森林和圖模式方法.由于圖模型并不適用于本文提出的特征，因此，本文僅與s-GM進(jìn)行對(duì)比.圖1和圖2中分別為每一種方法的平均F1值和平均執(zhí)行時(shí)間(以秒為單位).

通過圖1和圖2可知，當(dāng)基于相同特征集合時(shí)，本文提出的方法與o-J48、o-Bagging、o-RF相比，其平均F1值分別能夠提升9.6%、3.9%和6.9%：J48決策樹的執(zhí)行時(shí)間最短，但是由于決策樹構(gòu)建時(shí)信息增益的結(jié)果偏向于那些具有更多數(shù)值的特征，故在本文的數(shù)據(jù)集上平均F1值最低；隨機(jī)森林作為一種集成的決策樹，其通過隨機(jī)選擇特征集合的一個(gè)子集構(gòu)建決策樹，進(jìn)而避免了在特征數(shù)量較多時(shí)出現(xiàn)過度擬合現(xiàn)象；Bagging和隨機(jī)森林的平均F1值差別不大，但其執(zhí)行時(shí)間較長(zhǎng)；與其他方法相比，通過將預(yù)測(cè)問題轉(zhuǎn)化為求解加權(quán)非負(fù)矩陣分解問題，WNMFLP可以在相對(duì)較短的執(zhí)行時(shí)間內(nèi)獲得相對(duì)較高的平均F1值.當(dāng)基于不同特征集合時(shí)，本文提出的特征集合與文獻(xiàn)[11]中提出的特征集合相比，在J48決策樹、Bagging和隨機(jī)森林方法上的平均F1值分別能夠提升6.7%、10.7%和2.2%，由此可見，本文提出的動(dòng)態(tài)特征能夠以更高的精度預(yù)測(cè)鏈接的存在性和方向性.最后，僅基于相同的數(shù)據(jù)集，盡管o-WNMFLP的平均F1值略低于s-GM(-2.4%)，但相比于s-GM，o-WNMFLP大大縮短了鏈接預(yù)測(cè)的執(zhí)行時(shí)間(-46.9%).

綜上，相比于其他特征定義和鏈接預(yù)測(cè)方法，本文提出的方法使得鏈接預(yù)測(cè)算法的綜合性能得到了較大提升.

5.2.2 特征權(quán)重對(duì)WNMFLP性能的影響

表2為各特征的權(quán)重平均值.

通過表2可知，用戶動(dòng)態(tài)發(fā)布內(nèi)容特征的權(quán)重平均值高于用戶動(dòng)態(tài)關(guān)系特征，用戶概要特征中，城市、賬戶創(chuàng)建時(shí)間和賬戶認(rèn)證類型的權(quán)重平均值高于用戶動(dòng)態(tài)發(fā)布內(nèi)容特征.

圖3為WNMFLP在不同特征集合上的性能比較，其中，p、r、c和a分別表示用戶概要特征、用戶動(dòng)態(tài)關(guān)系特征、用戶動(dòng)態(tài)發(fā)布內(nèi)容特征和所有特征.

圖3中的實(shí)驗(yàn)結(jié)果也表明，pWNMFLP的精確度總體上高于cWNMFLP和rWNMFLP；就鏈接的方向性預(yù)測(cè)而言，cWNMFLP的精確度高于rWNMFLP；就鏈接的存在性預(yù)測(cè)而言，rWNMFLP的精確度高于cWNMFLP.

表2 各特征權(quán)重平均值

此外，本文分別在未分配權(quán)重和分配權(quán)重的數(shù)據(jù)集合上以50%，60%，80%和100%的數(shù)據(jù)作為訓(xùn)練集合進(jìn)行10折交叉驗(yàn)證，實(shí)驗(yàn)結(jié)果如圖4所示.

圖4中的實(shí)驗(yàn)結(jié)果表明，WNMFLP在帶有權(quán)重的數(shù)據(jù)集上的性能優(yōu)于其在不帶有權(quán)重的數(shù)據(jù)集上的性能.綜上，在WNMFLP中考慮特征權(quán)重有助于提升算法性能.

5.2.3 時(shí)間信息對(duì)WNMFLP性能的影響

為驗(yàn)證時(shí)間信息對(duì)WNMFLP性能的影響，實(shí)驗(yàn)設(shè)置如下：β分別取值0.01，0.1，0.5，0.7，1，以A中50%，60%，80%和100%的數(shù)據(jù)作為訓(xùn)練集合進(jìn)行10折交叉驗(yàn)證，實(shí)驗(yàn)結(jié)果如圖5所示.

由圖5可知：當(dāng)β=1時(shí)，即不考慮時(shí)間信息對(duì)鏈接預(yù)測(cè)問題的影響，此時(shí)的F1值比峰值低很多，而當(dāng)β較大時(shí)，鏈接預(yù)測(cè)學(xué)習(xí)過程主要受時(shí)間信息控制，此時(shí)通過學(xué)習(xí)得到的矩陣V1會(huì)出現(xiàn)失真，從而不能得到精確的鏈接預(yù)測(cè)結(jié)果.綜上，將時(shí)間信息融入鏈接預(yù)測(cè)問題中可以有效地提高預(yù)測(cè)算法的性能.

6 結(jié)論

針對(duì)傳統(tǒng)鏈接預(yù)測(cè)方法的不足，本文基于帶權(quán)的動(dòng)態(tài)鏈接預(yù)測(cè)特征集合，以用戶社會(huì)關(guān)系因子約束目標(biāo)函數(shù)，構(gòu)建基于加權(quán)非負(fù)矩陣分解的鏈接預(yù)測(cè)模型，從而實(shí)現(xiàn)鏈接存在性及方向性的預(yù)測(cè).在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，提出的算法能夠有效地提高鏈接預(yù)測(cè)模型的性能.后續(xù)研究中，將群體智慧技術(shù)引入鏈接預(yù)測(cè)算法以更準(zhǔn)確可靠地預(yù)測(cè)社會(huì)網(wǎng)絡(luò)中的有向鏈接將成為主要目標(biāo).

[1]Airoldi E M,et al.Mixed membership stochastic block models for relational data with application to protein-protein interactions[A].Proceedings of ICML Workshop on Statistical Network Analysis[C].Pittsburgh,Pennsylvania,USA:Springer,2006.57-74.

[2]Hasan M Al,et al.Link prediction using supervised learning[A].Proceedings of Workshop on Link Analysis,Counter-terrorism and Security[C].Maryland,USA:SIAM,2006.322-331.

[3]Henzinger M R.Link analysis in web information retrieval[J].IEEE Data Engineering Bulletin,2000,23(3):3-8.

[4]Huang Z,et al.Link prediction approach to collaborative filtering[A].Proceedings of the 5th ACM/IEEE-CS Joint Conference on Digital libraries[C].Denver,Colorado,USA:ACM,2005.141-142.

[5]Lichtenwalter R N,et al.New perspectives and methods in link prediction[A].Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Washington,DC,USA:ACM,2010.243-252.

[6]Hasan M A,Zaki M J.A survey of link prediction in social networks[J].Social Network Data Analytics,2011,(2011):243-275.

[7]Lu L,Zhou T.Link prediction in complex networks:a survey[J].Physica A,2011,390(6):1150-1170.

[8]An J,et al.Social relation predictive model of mobile nodes in Internet of things[J].Elektronika Ir Elektrotechnika,2013,19(4):81-86.

[9]Schall D.Link prediction in directed social networks[J].Social Network Analysis and Mining,2014,4(1):1-14.

[10]Symeonidis P,Mantas N.Spectral clustering for link prediction in social networks with positive and negative links[J].Social Network Analysis and Mining,2013,3(4):1433-1447.

[11]Fire M,et al.Computationally efficient link prediction in a variety of social networks[J].ACM Transactions on Intelligent Systems and Technology,2013,5(1):10.

[12]Lou T,et al.Learning to predict reciprocity and triadic closure in social networks[J].ACM Transactions on Knowledge Discovery from Data,2013,7(2):5.

[13]Jorge V R,Alneu A L.Exploiting behaviors of communities of twitter users for link prediction[J].Social Network Analysis and Mining,2013,3(4):1063-1074.

[14]Soares Paulo R S,Prudêncio Ricardo B C.Time series based link prediction[A].Proceedings of the 2012 International Joint Conference on Neural Networks[C].Brisbane,Australia:IEEE,2012.1-7.

[15]Soares Paulo R S,Prudêncio Ricardo B C.Proximity measures for link prediction based on temporal events[J].Expert Systems with Applications,2013,40(16):6652-6660.

[16]Zhang J,et al.LaFT-tree:perceiving the expansion trace of one′s circle of friends in online social networks[A].Proceedings of the sixth ACM International Conference on Web Search and Data Mining[C].Rome,Italy:ACM,2013.597-606.

[17]Zhang J,et al.Social influence locality for modeling retweeting behaviors[A].Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence[C].Beijing,China:IJCAI/AAAI,2013.2761-2767.

[18]Leskovec J,et al.Signed networks in social media[A].Proceedings of the SIGCHI Conference on Human Factors in Computing Systems[C].Atlanta,Georgia,USA:ACM,2010.1361-1370.

[19]李樂,章毓晉.非負(fù)矩陣分解算法綜述[J].電子學(xué)報(bào),2008,36(4):737-743.

Li L，Zhang Y J.A survey on algorithms of non-negative matrix factorization[J].Acta Electronica Sinica,2008,36(4):737-743.(in Chinese)

[20]Lee D D,Seung H S.Learning the parts of objects by non-negative matrix factorization[J].Nature,1999,401(6755):788-791.

王萌萌 女，1987年出生，吉林長(zhǎng)春人，2013年至今于吉林大學(xué)計(jì)算機(jī)學(xué)院攻讀博士學(xué)位，從事社會(huì)網(wǎng)絡(luò)分析、自然語言處理等有關(guān)研究.

E-mail:wmmwwlh@126.com

左萬利 男，1957年出生,吉林長(zhǎng)春人，博士，教授、博士生導(dǎo)師，從事社會(huì)網(wǎng)絡(luò)分析、網(wǎng)絡(luò)搜索引擎、自然語言處理等有關(guān)研究.

E-mail:wanli@jlu.edu.cn

王 英(通信作者) 女，1981年出生,吉林長(zhǎng)春人，博士，講師，從事社會(huì)網(wǎng)絡(luò)分析、搜索引擎等有關(guān)研究.

E-mail:wangying2010@jlu.edu.cn

Link Prediction Model Based on Weighted Nonnegative Matrix Factorization

WANG Meng-meng1,2,ZUO Wan-li1,2,WANG Ying1,2

(1.CollegeofCompuerScienceandTechnology,JilinUniversity,Changchun,Jilin130012,China;2.KeyLaboratoryofSymbolicComputationandKnowledgeEngineering(JilinUniversity),MinistryofEducation,Changchun,Jilin130012,China)

Targeted at on-line microbloggings,on the basis of weighted and dynamic link prediction features,we utilize nonnegative matrix factorization to predict existence and directivity of link from user-based and post-based dimension by employing relationship-based factor to constrain objective function.Experiments on real-world dataset demonstrate the effectiveness of the proposed framework.Further experiments are conducted to understand the importance of features’ weights and temporal information in link prediction.

directed link prediction;nonnegative matrix factorization;features’ weights;temporal information;dynamic social networks

2015-03-30;

2015-08-03;責(zé)任編輯:馬蘭英

國(guó)家自然科學(xué)基金(No.61300148);吉林省科技發(fā)展計(jì)劃(No.20130206051GX);吉林省科技計(jì)劃(No.20130522112JH);吉林大學(xué)基本科研業(yè)務(wù)費(fèi)科學(xué)前沿與交叉項(xiàng)目(No.201103129)

TP393.03

A

0372-2112 (2016)10-2391-07

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.10.016