信息融合相似性算法下的虛擬社區(qū)鏈接預(yù)測

夏 凱，傅 魁，劉李利

(武漢理工大學(xué)經(jīng)濟學(xué)院，湖北 武漢 430070)

隨著互聯(lián)網(wǎng)的普及以及Web 2．0的快速發(fā)展，虛擬社區(qū)已經(jīng)成為參與人數(shù)最多、應(yīng)用領(lǐng)域最廣的在線社會網(wǎng)絡(luò)。虛擬社區(qū)如何運營，是各虛擬社區(qū)網(wǎng)站都要面臨的問題，發(fā)現(xiàn)問題的潛在回答者可以促進虛擬社區(qū)運營的成功［1－4］，而發(fā)現(xiàn)潛在回答者問題則可以轉(zhuǎn)換為鏈接預(yù)測問題。目前，鏈接預(yù)測的方法很多。在早期的研究中，有MARKOV 模型［5］，監(jiān)督學(xué)習(xí)［6］，最大似然估計［7］等鏈接預(yù)測框架和方法。相似性方法中節(jié)點相似性的鏈接預(yù)測方法由于簡單、有效、內(nèi)涵豐富等特點，成為了當今研究熱點［8］。相似性鏈接預(yù)測方法中基于局部信息的相似性指標能取得較好結(jié)果且計算復(fù)雜度相對較低，因此筆者主要對局部信息的相似性指標進行了研究。LIN［9］利用節(jié)點的屬性定義了節(jié)點間的相似性，可以直接用來進行鏈路預(yù)測。文獻［10］同時考慮被預(yù)測節(jié)點共同鄰居度數(shù)以及共同鄰居組成的小型網(wǎng)絡(luò)對預(yù)測結(jié)果的影響。文獻［11］考慮了融合時間信息的鏈接預(yù)測方法，該方法認為兩個節(jié)點在相同的時間發(fā)布相同或相近的信息則節(jié)點間權(quán)重較大?，F(xiàn)有的相似性鏈接預(yù)測指標存在以下兩個問題:①單一地考慮網(wǎng)絡(luò)結(jié)構(gòu)信息或者節(jié)點屬性信息;②靜態(tài)處理節(jié)點之間的關(guān)系。筆者借鑒傳統(tǒng)局部相似性指標提出了針對含權(quán)網(wǎng)絡(luò)的融合節(jié)點屬性和網(wǎng)絡(luò)演化信息的鏈接預(yù)測指標，即SNEUGC指標，該指標旨在更全面、準確地衡量虛擬社區(qū)用戶相似性，提高鏈接預(yù)測的準確度。

1 基于SNEUGC指標的鏈接預(yù)測

1．1 SNEUGC指標構(gòu)建框架

筆者提出了構(gòu)建基于信息融合相似性算法的鏈接預(yù)測指標，即SNEUGC指標的方法。該方法的框架如圖1所示。

該框架主要包含5個模塊:①數(shù)據(jù)的獲取和處理;②基于用戶生成內(nèi)容的相似性計算;③基于網(wǎng)絡(luò)演化的相似性計算;④計算鏈接預(yù)測SNEUGC指標值;⑤鏈接預(yù)測。

1．2 基于用戶生成內(nèi)容的相似性計算

基于用戶生成內(nèi)容的相似性計算(similarity based on user generated content，SUGC)旨在挖掘虛擬社區(qū)用戶的生成內(nèi)容信息(發(fā)帖、回帖)來計算虛擬社區(qū)中兩個節(jié)點之間的相似性。該計算過程分為以下3個步驟:

(1)用戶生成內(nèi)容文檔構(gòu)建。在虛擬社區(qū)中，挖掘用戶的發(fā)回帖內(nèi)容可以發(fā)現(xiàn)用戶在某一方面的偏好;若用戶具有相似的偏好則認為用戶是相似的。因此將用戶在某論壇某一時間段的所有發(fā)回帖內(nèi)容組織成一篇文檔作為用戶的生成內(nèi)容文檔進行輸入計算。

圖1 SNEUGC指標構(gòu)建框架圖

(2)用戶生成內(nèi)容文檔的空間向量模型構(gòu)建。通過分詞算法對用戶生成內(nèi)容文檔進行分詞，過濾停用詞，根據(jù)詞頻進行詞項選擇，用式(1)計算詞項權(quán)重，生成空間向量模型。

式中:ni，j為該詞在文件中出現(xiàn)的次數(shù);為文件中所有字詞出現(xiàn)的次數(shù)之和;N為總的文檔數(shù);dfi為包含該詞的文檔數(shù)。

(3)用戶生成內(nèi)容的相似性計算。運用余弦相似度公式計算空間向量之間的相似性。

式中:n為詞項數(shù);Ai為文檔A中第i個詞項的tfidf值;Bi為文檔B中第i個詞項的tfidf值。

將計算的結(jié)果寫入生成內(nèi)容相似性文檔，該文檔記錄了每個節(jié)點生成內(nèi)容上的相似度值。

1．3 基于網(wǎng)絡(luò)演化的相似性計算

基于網(wǎng)絡(luò)演化的相似性計算(similarity based on network evolution，SNE)旨在挖掘由回復(fù)關(guān)系構(gòu)建的網(wǎng)絡(luò)結(jié)構(gòu)信息計算虛擬社區(qū)中兩個節(jié)點之間的相似性。SNE計算過程分為以下兩步:①基于靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)用戶相似性計算(similarity based on static network，SSN);②基于網(wǎng)絡(luò)結(jié)構(gòu)的相似性文檔更新。

1．3．1 SSN計算

SSN計算是將t時刻回復(fù)關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)信息作為輸入，計算t時刻網(wǎng)絡(luò)結(jié)構(gòu)中節(jié)點之間的相似性。相鄰節(jié)點相似性和非相鄰節(jié)點相似性的計算如式(3)和式(4)所示。

其中:S(x，y)為節(jié)點 x，y之間的相似性;weight(x，y)為節(jié)點 x，y之間的權(quán)重;U(x)為節(jié)點x的鄰接節(jié)點;Γ(x，y)為節(jié)點x，y之間的共同鄰居;|Γ(x，y)|為節(jié)點 x，y之間的共同鄰居的數(shù)量。權(quán)重weight(x，y)的計算如式(5)。

式中:m為論壇中主題數(shù);nm為對某個主題m的回復(fù)數(shù)。

1．3．2 基于網(wǎng)絡(luò)結(jié)構(gòu)的相似性文檔更新

基于網(wǎng)絡(luò)結(jié)構(gòu)的相似性文檔記錄了挖掘網(wǎng)絡(luò)結(jié)構(gòu)信息獲得的節(jié)點相似性。文檔的更新過程則是追蹤網(wǎng)絡(luò)演化的過程。網(wǎng)絡(luò)的演化會發(fā)生如下3種情況:

(1)新增鏈接。根據(jù)式(3)或式(4)計算出新增鏈接的兩節(jié)點相似性，直接寫入文檔。

(2)丟失鏈接。丟失鏈接是指在t－1時刻節(jié)點a，b之間存在鏈接，t時刻a，b之間不存在鏈接的情況。對丟失鏈接情況的處理如式(6)。

式中，n為兩個節(jié)點連續(xù)出現(xiàn)鏈接丟失的次數(shù)。當節(jié)點之間的相似性為0時，將節(jié)點之間的關(guān)系從文檔中刪除。

(3)鏈接權(quán)重變化。鏈接權(quán)重變化是指在t－1時刻節(jié)點a，b之間存在鏈接，t時刻a，b之間也存在鏈接的情況。對鏈接權(quán)重變化的處理如式(7)所示。

1．4 SNEUGC值計算

將基于網(wǎng)絡(luò)結(jié)構(gòu)的相似性文檔、生成內(nèi)容相似性文檔作為輸入，運用式(8)計算SNEUGC指標值。

式中，α為權(quán)重值，用來調(diào)節(jié)SUGC計算出來的相似性與SNE計算出來的相似性對SNEUGC指標的影響力。

1．5 基于SNEUGC指標的鏈接預(yù)測

基于SNEUGC指標的鏈接預(yù)測過程可用式(9)表示。

式中:v為某個特定的節(jié)點;y為節(jié)點v的相鄰節(jié)點或者與節(jié)點v有共同鄰居的節(jié)點;A(v)為可能對節(jié)點v發(fā)生鏈接的節(jié)點集合;β為選定的某個閾值。

計算與節(jié)點v相鄰或者有共同鄰居節(jié)點的SNEUGC指標值，并與選定的閾值比較，將超過閾值的節(jié)點y納入集合A中作為鏈接預(yù)測集合。

2 實驗結(jié)果設(shè)計與分析

2．1 實驗設(shè)計

2．1．1 實驗數(shù)據(jù)

通過網(wǎng)絡(luò)爬蟲采集國內(nèi)39艾滋論壇的數(shù)據(jù)，對提出的鏈接預(yù)測算法性能進行實驗。將用戶最活躍的2009年前9個月的數(shù)據(jù)作為實驗數(shù)據(jù)，刪除無效數(shù)據(jù)后按月進行劃分。然后分別以某月中的數(shù)據(jù)作為預(yù)測集，前一個月的數(shù)據(jù)作為訓(xùn)練集。

2．1．2 實驗數(shù)據(jù)與評價指標

實驗采用ROC曲線(receiver operating characteristic curve)即操作特征曲線來度量算法的性能。ROC曲線下的面積AUC(area under the roc curve)值越大，說明其算法性能越好。ROC曲線實例定義如表1所示。

表1 ROC曲線實例定義

2．1．3 實驗設(shè)計

實驗旨在解決以下4個問題:①比較基于靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)用戶相似性計算(SSN算法)與基于網(wǎng)絡(luò)演化的相似性計算(SNE算法)的預(yù)測效果，驗證考慮網(wǎng)絡(luò)演化算法比靜態(tài)網(wǎng)絡(luò)算法有更高的準確率。②比較基于用戶生成內(nèi)容的相似性計算(SUGC算法)與基于網(wǎng)絡(luò)演化的相似性計算(SNE算法)的預(yù)測效果，定性分析基于信息融合相似性算法的鏈接預(yù)測指標(SNEUGC指標)中兩部分算法結(jié)果所占的比例。③比較α取不同的值對SNEUGC指標預(yù)測效果的影響。對基于信息融合相似性算法的鏈接預(yù)測指標(SNEUGC指標)進行多組實驗，定量確定 α取何值時SNEUGC指標預(yù)測效果能達到最優(yōu)。④比較基于信息融合相似性算法的鏈接預(yù)測指標(SNEUGC指標)、基于用戶生成內(nèi)容的相似性計算(SUGC算法)、基于網(wǎng)絡(luò)演化的相似性計算(SNE算法)的預(yù)測效果，驗證SNEUGC指標具有較高的預(yù)測準確率。

2．2 SSN算法與SNE算法預(yù)測效果比較

首先對SSN算法進行了8組實驗，然后對SNE算法進行實驗。通過觀察實驗數(shù)據(jù)發(fā)現(xiàn)，SNE算法在預(yù)測準確率和穩(wěn)定性方面比SSN算法表現(xiàn)好。從而得出結(jié)論:考慮網(wǎng)絡(luò)演化因素比利用靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)的預(yù)測效果要好。

對SSN算法進行了測試。分別選擇1至9月的數(shù)據(jù)作為訓(xùn)練集，其他月份的數(shù)據(jù)作為測試集。TPR實例值表示預(yù)測鏈接的準確率;ROC曲線表示整體的預(yù)測效果。表2為SSN算法TPR實例值，TPR=TP/(TP+FN)。圖2為SSN算法的整體效果，F(xiàn)PR=FP/(FP+TN)。

表2 SSN算法TPR實例值

從表2來看，SSN方法不能穩(wěn)定地預(yù)測未來鏈接，且整體預(yù)測效果很差。SSN算法預(yù)測的TPR值以訓(xùn)練集所在月份為中心不斷變小。預(yù)測數(shù)據(jù)所在月份離訓(xùn)練集所在月份越近，預(yù)測的準確率越高;預(yù)測數(shù)據(jù)所在月份離訓(xùn)練集所在月份較遠的話，預(yù)測的準確率不斷降低。1月份的數(shù)據(jù)作為訓(xùn)練集，預(yù)測8月份、9月份的數(shù)據(jù)，TPR值為0;而鄰近的預(yù)測月份如2月、3月則相對較高。SSN算法通過某一時刻的網(wǎng)絡(luò)結(jié)構(gòu)作為訓(xùn)練輸入，預(yù)測未來發(fā)生的鏈接。這種靜態(tài)預(yù)測的方法對于距離訓(xùn)練數(shù)據(jù)較近的月份預(yù)測效果較好，隨著訓(xùn)練數(shù)據(jù)與預(yù)測數(shù)據(jù)時間跨度的增大，預(yù)測效果會越來越差。由于這種預(yù)測準確率的不穩(wěn)定性導(dǎo)致了整體的預(yù)測效果偏低，因此圖2(a)和圖2(b)中無法形成ROC曲線。

實驗對SNE算法進行了測試。實驗結(jié)果如圖3、圖4和表3所示，表3中SNE算法的AUC值為0．658 8。實驗結(jié)果表明，SNE算法在預(yù)測穩(wěn)定性和預(yù)測效果方面較SSN算法好。

圖2 SSN算法的整體效果

圖3 SNE算法TPR值

圖4 SNE算法的ROC曲線圖

表3 不同算法的AUC值

從圖3可以看出，SNE算法能夠獲得較為穩(wěn)定的TPR值，TPR值都在0．6左右上下波動。從圖4和表3可以看出，SNE算法可以獲得整體預(yù)測效果一般的實驗結(jié)果。較SSN算法，SNE算法考慮了網(wǎng)絡(luò)演化過程，而不是以某一時刻的網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)預(yù)測其他時刻可能發(fā)生的鏈接。這種方式能夠更準確地表述節(jié)點之間的關(guān)系，因此能夠獲得較為穩(wěn)定和精確的預(yù)測結(jié)果。

綜合以上實驗數(shù)據(jù)比較可知，考慮網(wǎng)絡(luò)演化的SNE算法比靜態(tài)網(wǎng)絡(luò)算法SSN預(yù)測穩(wěn)定性更好，且有更高的預(yù)測準確率。

2．3 SUGC算法與SNE算法預(yù)測效果比較

分別對SUGC算法和SNE算法進行實驗。實驗結(jié)果表明運用網(wǎng)絡(luò)結(jié)構(gòu)信息(SNE算法)進行預(yù)測的效果比運用用戶生成內(nèi)容信息(SUGC算法)進行預(yù)測的效果好;SUGC算法的計算結(jié)果在SNEUGC指標中所占的比例比SNE算法所占比例小。實驗結(jié)果如圖5和表3所示。

圖5 SNE、SUGC算法ROC曲線圖

從圖5可以定性地看出，SNE的預(yù)測效果優(yōu)于SUGC。表3定量計算了每個算法的AUC值，SUGC算法不足0．5;SNE的AUC值為0．658 8。

實驗結(jié)果表明，應(yīng)用網(wǎng)絡(luò)結(jié)構(gòu)信息比用戶屬性信息進行鏈接預(yù)測效果好。SUGC是將用戶的發(fā)回帖內(nèi)容構(gòu)建文檔進行相似度計算。SNE算法根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測節(jié)點之間的相似性。SUGC算法構(gòu)建的文檔中很多都是短文本以及較多難以過濾的不相干內(nèi)容，因此僅通過節(jié)點屬性信息預(yù)測鏈接準確度不高。SNE算法構(gòu)建網(wǎng)絡(luò)結(jié)構(gòu)，能夠較為真實地反映用戶之間的交互關(guān)系，干擾因素較少。

2．4 SNEUGC指標α系數(shù)定量實驗

該實驗分為4 組，分別取 α 為0．1、0．2、0．3 和0．4進行實驗，比較不同α系數(shù)給實驗結(jié)果帶來的影響，從而確定α值。實驗結(jié)果如圖6所示。結(jié)果表明，當α=0．2時，預(yù)測效果達到最佳。

2．5 SUGC和SNE算法、SNEUGC指標預(yù)測比較

分別對SUGC算法和SNE算法及SNEUGC指標進行實驗。SNEUGC指標中α取值為0．2。實驗結(jié)果表明運用SNEUGC指標進行預(yù)測的效果最好。實驗結(jié)果如圖7和表3所示。

圖6 α取值不同情況下SNEUGC的ROC曲線

圖7 SNEUGC、SNE、SUGC算法ROC曲線比較

SNEUGC指標融合用戶生成內(nèi)容信息和網(wǎng)絡(luò)演化信息，能夠較好地平衡兩種算法的優(yōu)缺點，在預(yù)測穩(wěn)定性和準確性方面都有較大的提高。實驗結(jié)果表明，SNEUGC指標整體預(yù)測效果最好。

3 結(jié)論

鏈接預(yù)測方法可以發(fā)現(xiàn)虛擬社區(qū)的潛在回答者從而促進虛擬社區(qū)運營成功。針對傳統(tǒng)的節(jié)點相似性鏈接預(yù)測指標僅考慮網(wǎng)絡(luò)結(jié)構(gòu)信息或者節(jié)點屬性信息，且靜態(tài)處理節(jié)點之間關(guān)系的不足，提出了基于信息融合相似性算法的鏈接預(yù)測指標，即SNEUGC指標。實驗結(jié)果表明，基于網(wǎng)絡(luò)演化信息比基于靜態(tài)網(wǎng)絡(luò)的鏈接預(yù)測效果好;基于網(wǎng)絡(luò)演化信息的預(yù)測效果比基于用戶生成內(nèi)容的預(yù)測效果好;信息融合的預(yù)測效果比利用單一信息的預(yù)測效果好。

［1］ 李桂華，余偉萍．虛擬社區(qū)文本情感表達對用戶參與的作用:模型構(gòu)建與驗證［J］．情報學(xué)報，2012，31(8):853－860．

［2］ 汪祖柱，吳磊．用戶參與專業(yè)虛擬社區(qū)的滿意度影響因素研究［J］．武漢理工大學(xué)學(xué)報:信息與管理工程版，2013，35(5):784 －788．

［3］ KOH J B，KIM Y G，BUTLER B．Encouraging participation in virtual communities［J］．Communications of the ACM ，2007，50(2):69－73．

［4］ MURATA T，MORIYASU S．Link prediction based on structural properties of online social networks［J］．New Generation Computing，2008(26):245 －257．

［5］ LICHTEN W R N，LUSSIER J T，CHAWLA N V．New perspectives and methods in link prediction［C］∥Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Disugcovery and Data Mining．［S．l．］:ACM，2010:243 －252．

［6］ CLAUSET A，MOORE C，NEWMAN M E J．Hierarchical structure and the prediction of missing links in networks［J］．Nature，2008(453):98 －101．

［7］ 呂琳媛．復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測［J］．電子科技大學(xué)學(xué)報，2010，39(5):652 －660．

［8］ LIN D．An information－theoretic definition of similarity［J］．ICML，1998(98):296 －304．

［9］ LIN A，ADAR E．Friends and neighbors on the Web［J］．Social Networks，2003，25(3):211 －230．

［10］ 東昱曉，柯慶，吳斌．基于節(jié)點相似性的鏈接預(yù)測［J］．計算機科學(xué)，2011，38(7):162 －164．

［11］ 張昱，張恩德．基于時間信息的社會網(wǎng)絡(luò)鏈接預(yù)測研究［J］．計算機與數(shù)字工程，2012(11):50－51．