王萌萌,左萬利,王 英

(1.吉林大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,吉林長春 130012; 2.符號計算與知識工程教育部重點實驗室(吉林大學(xué)),吉林長春 130012)

?

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

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

(1.吉林大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,吉林長春 130012; 2.符號計算與知識工程教育部重點實驗室(吉林大學(xué)),吉林長春 130012)

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

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

1 引言

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

3 動態(tài)鏈接預(yù)測特征建模

3.1 動態(tài)鏈接預(yù)測特征定義

3.1.1 用戶概要特征

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

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

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

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

Common Neighbors度量標(biāo)準(zhǔn)假設(shè)兩個用戶間的相似度與其擁有的共同鄰居數(shù)量成正比，Salton度量標(biāo)準(zhǔn)在其基礎(chǔ)上加入了兩個用戶的度信息.基于鏈接的方向性對其改進(jìn)后，用戶和用戶在第個時間片上的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)系決定；|·|為集合的元素數(shù)量.則在時間片流[0,tn]上，u和v的Salton值為：

(2)

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

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

Jaccard度量標(biāo)準(zhǔn)假設(shè)兩個用戶間的相似度正比于其擁有的共同鄰居數(shù)量與其所有鄰居數(shù)量的比值.基于鏈接的方向性對其改進(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è)用戶的度越大，該用戶與其他用戶建立鏈接的可能性就越大.基于鏈接的方向性對其改進(jìn)后，u和v在ti上的Preferential Attachment值為：

(5)

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

(6)

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

有時，情感的“共鳴”使得用戶間更易建立聯(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ā)布的文本信息計算用戶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的動態(tài)發(fā)布內(nèi)容特征為：

(8)

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

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

(9)

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

(10)

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

(11)

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

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

4.1 問題定義

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

4.2 模型算法

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

(12)

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

(13)

其中，S[0,tn](i,j)∈[0,1]為ui和uj間在[0,tn]上的社會關(guān)系因子，S[0,tn](i,j)越大，ui和uj間越可能建立鏈接，則用戶間Frobenius范數(shù)越小，ui和uj間在[0,tn]上的社會關(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為對角矩陣，D中的第i個元素D(i,i)為S[0,tn]中第行元素之和.則加入正則化社會因子的目標(biāo)函數(shù)為：

(15)

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

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

(16)

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

(17)

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

(18)

(19)

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

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

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

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

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

2: 根據(jù)式(11)計算相應(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 時間復(fù)雜度分析

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

5.1 數(shù)據(jù)集及實驗設(shè)置

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

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

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

5.2 對比實驗

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

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

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

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

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

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

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

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

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

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

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

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

5.2.3 時間信息對WNMFLP性能的影響

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

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

6 結(jié)論

針對傳統(tǒng)鏈接預(yù)測方法的不足，本文基于帶權(quán)的動態(tài)鏈接預(yù)測特征集合，以用戶社會關(guān)系因子約束目標(biāo)函數(shù)，構(gòu)建基于加權(quán)非負(fù)矩陣分解的鏈接預(yù)測模型，從而實現(xiàn)鏈接存在性及方向性的預(yù)測.在真實數(shù)據(jù)集上的實驗結(jié)果表明，提出的算法能夠有效地提高鏈接預(yù)測模型的性能.后續(xù)研究中，將群體智慧技術(shù)引入鏈接預(yù)測算法以更準(zhǔn)確可靠地預(yù)測社會網(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é)報,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年出生，吉林長春人，2013年至今于吉林大學(xué)計算機(jī)學(xué)院攻讀博士學(xué)位，從事社會網(wǎng)絡(luò)分析、自然語言處理等有關(guān)研究.

E-mail:wmmwwlh@126.com

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

E-mail:wanli@jlu.edu.cn

王 英(通信作者) 女，1981年出生,吉林長春人，博士，講師，從事社會網(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é)任編輯:馬蘭英

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

TP393.03

A

0372-2112 (2016)10-2391-07

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

10.3969/j.issn.0372-2112.2016.10.016