夏 凱,傅 魁,劉李利
(武漢理工大學(xué)經(jīng)濟(jì)學(xué)院,湖北 武漢 430070)
隨著互聯(lián)網(wǎng)的普及以及Web 2.0的快速發(fā)展,虛擬社區(qū)已經(jīng)成為參與人數(shù)最多、應(yīng)用領(lǐng)域最廣的在線社會(huì)網(wǎng)絡(luò)。虛擬社區(qū)如何運(yùn)營(yíng),是各虛擬社區(qū)網(wǎng)站都要面臨的問(wèn)題,發(fā)現(xiàn)問(wèn)題的潛在回答者可以促進(jìn)虛擬社區(qū)運(yùn)營(yíng)的成功[1-4],而發(fā)現(xiàn)潛在回答者問(wèn)題則可以轉(zhuǎn)換為鏈接預(yù)測(cè)問(wèn)題。目前,鏈接預(yù)測(cè)的方法很多。在早期的研究中,有MARKOV 模型[5],監(jiān)督學(xué)習(xí)[6],最大似然估計(jì)[7]等鏈接預(yù)測(cè)框架和方法。相似性方法中節(jié)點(diǎn)相似性的鏈接預(yù)測(cè)方法由于簡(jiǎn)單、有效、內(nèi)涵豐富等特點(diǎn),成為了當(dāng)今研究熱點(diǎn)[8]。相似性鏈接預(yù)測(cè)方法中基于局部信息的相似性指標(biāo)能取得較好結(jié)果且計(jì)算復(fù)雜度相對(duì)較低,因此筆者主要對(duì)局部信息的相似性指標(biāo)進(jìn)行了研究。LIN[9]利用節(jié)點(diǎn)的屬性定義了節(jié)點(diǎn)間的相似性,可以直接用來(lái)進(jìn)行鏈路預(yù)測(cè)。文獻(xiàn)[10]同時(shí)考慮被預(yù)測(cè)節(jié)點(diǎn)共同鄰居度數(shù)以及共同鄰居組成的小型網(wǎng)絡(luò)對(duì)預(yù)測(cè)結(jié)果的影響。文獻(xiàn)[11]考慮了融合時(shí)間信息的鏈接預(yù)測(cè)方法,該方法認(rèn)為兩個(gè)節(jié)點(diǎn)在相同的時(shí)間發(fā)布相同或相近的信息則節(jié)點(diǎn)間權(quán)重較大?,F(xiàn)有的相似性鏈接預(yù)測(cè)指標(biāo)存在以下兩個(gè)問(wèn)題:①單一地考慮網(wǎng)絡(luò)結(jié)構(gòu)信息或者節(jié)點(diǎn)屬性信息;②靜態(tài)處理節(jié)點(diǎn)之間的關(guān)系。筆者借鑒傳統(tǒng)局部相似性指標(biāo)提出了針對(duì)含權(quán)網(wǎng)絡(luò)的融合節(jié)點(diǎn)屬性和網(wǎng)絡(luò)演化信息的鏈接預(yù)測(cè)指標(biāo),即SNEUGC指標(biāo),該指標(biāo)旨在更全面、準(zhǔn)確地衡量虛擬社區(qū)用戶相似性,提高鏈接預(yù)測(cè)的準(zhǔn)確度。
筆者提出了構(gòu)建基于信息融合相似性算法的鏈接預(yù)測(cè)指標(biāo),即SNEUGC指標(biāo)的方法。該方法的框架如圖1所示。
該框架主要包含5個(gè)模塊:①數(shù)據(jù)的獲取和處理;②基于用戶生成內(nèi)容的相似性計(jì)算;③基于網(wǎng)絡(luò)演化的相似性計(jì)算;④計(jì)算鏈接預(yù)測(cè)SNEUGC指標(biāo)值;⑤鏈接預(yù)測(cè)。
基于用戶生成內(nèi)容的相似性計(jì)算(similarity based on user generated content,SUGC)旨在挖掘虛擬社區(qū)用戶的生成內(nèi)容信息(發(fā)帖、回帖)來(lái)計(jì)算虛擬社區(qū)中兩個(gè)節(jié)點(diǎn)之間的相似性。該計(jì)算過(guò)程分為以下3個(gè)步驟:
(1)用戶生成內(nèi)容文檔構(gòu)建。在虛擬社區(qū)中,挖掘用戶的發(fā)回帖內(nèi)容可以發(fā)現(xiàn)用戶在某一方面的偏好;若用戶具有相似的偏好則認(rèn)為用戶是相似的。因此將用戶在某論壇某一時(shí)間段的所有發(fā)回帖內(nèi)容組織成一篇文檔作為用戶的生成內(nèi)容文檔進(jìn)行輸入計(jì)算。
圖1 SNEUGC指標(biāo)構(gòu)建框架圖
(2)用戶生成內(nèi)容文檔的空間向量模型構(gòu)建。通過(guò)分詞算法對(duì)用戶生成內(nèi)容文檔進(jìn)行分詞,過(guò)濾停用詞,根據(jù)詞頻進(jìn)行詞項(xiàng)選擇,用式(1)計(jì)算詞項(xiàng)權(quán)重,生成空間向量模型。
式中:ni,j為該詞在文件中出現(xiàn)的次數(shù);為文件中所有字詞出現(xiàn)的次數(shù)之和;N為總的文檔數(shù);dfi為包含該詞的文檔數(shù)。
(3)用戶生成內(nèi)容的相似性計(jì)算。運(yùn)用余弦相似度公式計(jì)算空間向量之間的相似性。
式中:n為詞項(xiàng)數(shù);Ai為文檔A中第i個(gè)詞項(xiàng)的tfidf值;Bi為文檔B中第i個(gè)詞項(xiàng)的tfidf值。
將計(jì)算的結(jié)果寫(xiě)入生成內(nèi)容相似性文檔,該文檔記錄了每個(gè)節(jié)點(diǎn)生成內(nèi)容上的相似度值。
基于網(wǎng)絡(luò)演化的相似性計(jì)算(similarity based on network evolution,SNE)旨在挖掘由回復(fù)關(guān)系構(gòu)建的網(wǎng)絡(luò)結(jié)構(gòu)信息計(jì)算虛擬社區(qū)中兩個(gè)節(jié)點(diǎn)之間的相似性。SNE計(jì)算過(guò)程分為以下兩步:①基于靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)用戶相似性計(jì)算(similarity based on static network,SSN);②基于網(wǎng)絡(luò)結(jié)構(gòu)的相似性文檔更新。
1.3.1 SSN計(jì)算
SSN計(jì)算是將t時(shí)刻回復(fù)關(guān)系網(wǎng)絡(luò)結(jié)構(gòu)信息作為輸入,計(jì)算t時(shí)刻網(wǎng)絡(luò)結(jié)構(gòu)中節(jié)點(diǎn)之間的相似性。相鄰節(jié)點(diǎn)相似性和非相鄰節(jié)點(diǎn)相似性的計(jì)算如式(3)和式(4)所示。
其中:S(x,y)為節(jié)點(diǎn) x,y之間的相似性;weight(x,y)為節(jié)點(diǎn) x,y之間的權(quán)重;U(x)為節(jié)點(diǎn)x的鄰接節(jié)點(diǎn);Γ(x,y)為節(jié)點(diǎn)x,y之間的共同鄰居;|Γ(x,y)|為節(jié)點(diǎn) x,y之間的共同鄰居的數(shù)量。權(quán)重weight(x,y)的計(jì)算如式(5)。
式中:m為論壇中主題數(shù);nm為對(duì)某個(gè)主題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é)點(diǎn)相似性。文檔的更新過(guò)程則是追蹤網(wǎng)絡(luò)演化的過(guò)程。網(wǎng)絡(luò)的演化會(huì)發(fā)生如下3種情況:
(1)新增鏈接。根據(jù)式(3)或式(4)計(jì)算出新增鏈接的兩節(jié)點(diǎn)相似性,直接寫(xiě)入文檔。
(2)丟失鏈接。丟失鏈接是指在t-1時(shí)刻節(jié)點(diǎn)a,b之間存在鏈接,t時(shí)刻a,b之間不存在鏈接的情況。對(duì)丟失鏈接情況的處理如式(6)。
式中,n為兩個(gè)節(jié)點(diǎn)連續(xù)出現(xiàn)鏈接丟失的次數(shù)。當(dāng)節(jié)點(diǎn)之間的相似性為0時(shí),將節(jié)點(diǎn)之間的關(guān)系從文檔中刪除。
(3)鏈接權(quán)重變化。鏈接權(quán)重變化是指在t-1時(shí)刻節(jié)點(diǎn)a,b之間存在鏈接,t時(shí)刻a,b之間也存在鏈接的情況。對(duì)鏈接權(quán)重變化的處理如式(7)所示。
將基于網(wǎng)絡(luò)結(jié)構(gòu)的相似性文檔、生成內(nèi)容相似性文檔作為輸入,運(yùn)用式(8)計(jì)算SNEUGC指標(biāo)值。
式中,α為權(quán)重值,用來(lái)調(diào)節(jié)SUGC計(jì)算出來(lái)的相似性與SNE計(jì)算出來(lái)的相似性對(duì)SNEUGC指標(biāo)的影響力。
基于SNEUGC指標(biāo)的鏈接預(yù)測(cè)過(guò)程可用式(9)表示。
式中:v為某個(gè)特定的節(jié)點(diǎn);y為節(jié)點(diǎn)v的相鄰節(jié)點(diǎn)或者與節(jié)點(diǎn)v有共同鄰居的節(jié)點(diǎn);A(v)為可能對(duì)節(jié)點(diǎn)v發(fā)生鏈接的節(jié)點(diǎn)集合;β為選定的某個(gè)閾值。
計(jì)算與節(jié)點(diǎn)v相鄰或者有共同鄰居節(jié)點(diǎn)的SNEUGC指標(biāo)值,并與選定的閾值比較,將超過(guò)閾值的節(jié)點(diǎn)y納入集合A中作為鏈接預(yù)測(cè)集合。
2.1.1 實(shí)驗(yàn)數(shù)據(jù)
通過(guò)網(wǎng)絡(luò)爬蟲(chóng)采集國(guó)內(nèi)39艾滋論壇的數(shù)據(jù),對(duì)提出的鏈接預(yù)測(cè)算法性能進(jìn)行實(shí)驗(yàn)。將用戶最活躍的2009年前9個(gè)月的數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù),刪除無(wú)效數(shù)據(jù)后按月進(jìn)行劃分。然后分別以某月中的數(shù)據(jù)作為預(yù)測(cè)集,前一個(gè)月的數(shù)據(jù)作為訓(xùn)練集。
2.1.2 實(shí)驗(yàn)數(shù)據(jù)與評(píng)價(jià)指標(biāo)
實(shí)驗(yàn)采用ROC曲線(receiver operating characteristic curve)即操作特征曲線來(lái)度量算法的性能。ROC曲線下的面積AUC(area under the roc curve)值越大,說(shuō)明其算法性能越好。ROC曲線實(shí)例定義如表1所示。
表1 ROC曲線實(shí)例定義
2.1.3 實(shí)驗(yàn)設(shè)計(jì)
實(shí)驗(yàn)旨在解決以下4個(gè)問(wèn)題:①比較基于靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)用戶相似性計(jì)算(SSN算法)與基于網(wǎng)絡(luò)演化的相似性計(jì)算(SNE算法)的預(yù)測(cè)效果,驗(yàn)證考慮網(wǎng)絡(luò)演化算法比靜態(tài)網(wǎng)絡(luò)算法有更高的準(zhǔn)確率。②比較基于用戶生成內(nèi)容的相似性計(jì)算(SUGC算法)與基于網(wǎng)絡(luò)演化的相似性計(jì)算(SNE算法)的預(yù)測(cè)效果,定性分析基于信息融合相似性算法的鏈接預(yù)測(cè)指標(biāo)(SNEUGC指標(biāo))中兩部分算法結(jié)果所占的比例。③比較α取不同的值對(duì)SNEUGC指標(biāo)預(yù)測(cè)效果的影響。對(duì)基于信息融合相似性算法的鏈接預(yù)測(cè)指標(biāo)(SNEUGC指標(biāo))進(jìn)行多組實(shí)驗(yàn),定量確定 α取何值時(shí)SNEUGC指標(biāo)預(yù)測(cè)效果能達(dá)到最優(yōu)。④比較基于信息融合相似性算法的鏈接預(yù)測(cè)指標(biāo)(SNEUGC指標(biāo))、基于用戶生成內(nèi)容的相似性計(jì)算(SUGC算法)、基于網(wǎng)絡(luò)演化的相似性計(jì)算(SNE算法)的預(yù)測(cè)效果,驗(yàn)證SNEUGC指標(biāo)具有較高的預(yù)測(cè)準(zhǔn)確率。
首先對(duì)SSN算法進(jìn)行了8組實(shí)驗(yàn),然后對(duì)SNE算法進(jìn)行實(shí)驗(yàn)。通過(guò)觀察實(shí)驗(yàn)數(shù)據(jù)發(fā)現(xiàn),SNE算法在預(yù)測(cè)準(zhǔn)確率和穩(wěn)定性方面比SSN算法表現(xiàn)好。從而得出結(jié)論:考慮網(wǎng)絡(luò)演化因素比利用靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)的預(yù)測(cè)效果要好。
對(duì)SSN算法進(jìn)行了測(cè)試。分別選擇1至9月的數(shù)據(jù)作為訓(xùn)練集,其他月份的數(shù)據(jù)作為測(cè)試集。TPR實(shí)例值表示預(yù)測(cè)鏈接的準(zhǔn)確率;ROC曲線表示整體的預(yù)測(cè)效果。表2為SSN算法TPR實(shí)例值,TPR=TP/(TP+FN)。圖2為SSN算法的整體效果,F(xiàn)PR=FP/(FP+TN)。
表2 SSN算法TPR實(shí)例值
從表2來(lái)看,SSN方法不能穩(wěn)定地預(yù)測(cè)未來(lái)鏈接,且整體預(yù)測(cè)效果很差。SSN算法預(yù)測(cè)的TPR值以訓(xùn)練集所在月份為中心不斷變小。預(yù)測(cè)數(shù)據(jù)所在月份離訓(xùn)練集所在月份越近,預(yù)測(cè)的準(zhǔn)確率越高;預(yù)測(cè)數(shù)據(jù)所在月份離訓(xùn)練集所在月份較遠(yuǎn)的話,預(yù)測(cè)的準(zhǔn)確率不斷降低。1月份的數(shù)據(jù)作為訓(xùn)練集,預(yù)測(cè)8月份、9月份的數(shù)據(jù),TPR值為0;而鄰近的預(yù)測(cè)月份如2月、3月則相對(duì)較高。SSN算法通過(guò)某一時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)作為訓(xùn)練輸入,預(yù)測(cè)未來(lái)發(fā)生的鏈接。這種靜態(tài)預(yù)測(cè)的方法對(duì)于距離訓(xùn)練數(shù)據(jù)較近的月份預(yù)測(cè)效果較好,隨著訓(xùn)練數(shù)據(jù)與預(yù)測(cè)數(shù)據(jù)時(shí)間跨度的增大,預(yù)測(cè)效果會(huì)越來(lái)越差。由于這種預(yù)測(cè)準(zhǔn)確率的不穩(wěn)定性導(dǎo)致了整體的預(yù)測(cè)效果偏低,因此圖2(a)和圖2(b)中無(wú)法形成ROC曲線。
實(shí)驗(yàn)對(duì)SNE算法進(jìn)行了測(cè)試。實(shí)驗(yàn)結(jié)果如圖3、圖4和表3所示,表3中SNE算法的AUC值為0.658 8。實(shí)驗(yàn)結(jié)果表明,SNE算法在預(yù)測(cè)穩(wěn)定性和預(yù)測(cè)效果方面較SSN算法好。
圖2 SSN算法的整體效果
圖3 SNE算法TPR值
圖4 SNE算法的ROC曲線圖
表3 不同算法的AUC值
從圖3可以看出,SNE算法能夠獲得較為穩(wěn)定的TPR值,TPR值都在0.6左右上下波動(dòng)。從圖4和表3可以看出,SNE算法可以獲得整體預(yù)測(cè)效果一般的實(shí)驗(yàn)結(jié)果。較SSN算法,SNE算法考慮了網(wǎng)絡(luò)演化過(guò)程,而不是以某一時(shí)刻的網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)預(yù)測(cè)其他時(shí)刻可能發(fā)生的鏈接。這種方式能夠更準(zhǔn)確地表述節(jié)點(diǎn)之間的關(guān)系,因此能夠獲得較為穩(wěn)定和精確的預(yù)測(cè)結(jié)果。
綜合以上實(shí)驗(yàn)數(shù)據(jù)比較可知,考慮網(wǎng)絡(luò)演化的SNE算法比靜態(tài)網(wǎng)絡(luò)算法SSN預(yù)測(cè)穩(wěn)定性更好,且有更高的預(yù)測(cè)準(zhǔn)確率。
分別對(duì)SUGC算法和SNE算法進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明運(yùn)用網(wǎng)絡(luò)結(jié)構(gòu)信息(SNE算法)進(jìn)行預(yù)測(cè)的效果比運(yùn)用用戶生成內(nèi)容信息(SUGC算法)進(jìn)行預(yù)測(cè)的效果好;SUGC算法的計(jì)算結(jié)果在SNEUGC指標(biāo)中所占的比例比SNE算法所占比例小。實(shí)驗(yàn)結(jié)果如圖5和表3所示。
圖5 SNE、SUGC算法ROC曲線圖
從圖5可以定性地看出,SNE的預(yù)測(cè)效果優(yōu)于SUGC。表3定量計(jì)算了每個(gè)算法的AUC值,SUGC算法不足0.5;SNE的AUC值為0.658 8。
實(shí)驗(yàn)結(jié)果表明,應(yīng)用網(wǎng)絡(luò)結(jié)構(gòu)信息比用戶屬性信息進(jìn)行鏈接預(yù)測(cè)效果好。SUGC是將用戶的發(fā)回帖內(nèi)容構(gòu)建文檔進(jìn)行相似度計(jì)算。SNE算法根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測(cè)節(jié)點(diǎn)之間的相似性。SUGC算法構(gòu)建的文檔中很多都是短文本以及較多難以過(guò)濾的不相干內(nèi)容,因此僅通過(guò)節(jié)點(diǎn)屬性信息預(yù)測(cè)鏈接準(zhǔn)確度不高。SNE算法構(gòu)建網(wǎng)絡(luò)結(jié)構(gòu),能夠較為真實(shí)地反映用戶之間的交互關(guān)系,干擾因素較少。
該實(shí)驗(yàn)分為4 組,分別取 α 為0.1、0.2、0.3 和0.4進(jìn)行實(shí)驗(yàn),比較不同α系數(shù)給實(shí)驗(yàn)結(jié)果帶來(lái)的影響,從而確定α值。實(shí)驗(yàn)結(jié)果如圖6所示。結(jié)果表明,當(dāng)α=0.2時(shí),預(yù)測(cè)效果達(dá)到最佳。
分別對(duì)SUGC算法和SNE算法及SNEUGC指標(biāo)進(jìn)行實(shí)驗(yàn)。SNEUGC指標(biāo)中α取值為0.2。實(shí)驗(yàn)結(jié)果表明運(yùn)用SNEUGC指標(biāo)進(jìn)行預(yù)測(cè)的效果最好。實(shí)驗(yàn)結(jié)果如圖7和表3所示。
圖6 α取值不同情況下SNEUGC的ROC曲線
圖7 SNEUGC、SNE、SUGC算法ROC曲線比較
SNEUGC指標(biāo)融合用戶生成內(nèi)容信息和網(wǎng)絡(luò)演化信息,能夠較好地平衡兩種算法的優(yōu)缺點(diǎn),在預(yù)測(cè)穩(wěn)定性和準(zhǔn)確性方面都有較大的提高。實(shí)驗(yàn)結(jié)果表明,SNEUGC指標(biāo)整體預(yù)測(cè)效果最好。
鏈接預(yù)測(cè)方法可以發(fā)現(xiàn)虛擬社區(qū)的潛在回答者從而促進(jìn)虛擬社區(qū)運(yùn)營(yíng)成功。針對(duì)傳統(tǒng)的節(jié)點(diǎn)相似性鏈接預(yù)測(cè)指標(biāo)僅考慮網(wǎng)絡(luò)結(jié)構(gòu)信息或者節(jié)點(diǎn)屬性信息,且靜態(tài)處理節(jié)點(diǎn)之間關(guān)系的不足,提出了基于信息融合相似性算法的鏈接預(yù)測(cè)指標(biāo),即SNEUGC指標(biāo)。實(shí)驗(yàn)結(jié)果表明,基于網(wǎng)絡(luò)演化信息比基于靜態(tài)網(wǎng)絡(luò)的鏈接預(yù)測(cè)效果好;基于網(wǎng)絡(luò)演化信息的預(yù)測(cè)效果比基于用戶生成內(nèi)容的預(yù)測(cè)效果好;信息融合的預(yù)測(cè)效果比利用單一信息的預(yù)測(cè)效果好。
[1] 李桂華,余偉萍.虛擬社區(qū)文本情感表達(dá)對(duì)用戶參與的作用:模型構(gòu)建與驗(yàn)證[J].情報(bào)學(xué)報(bào),2012,31(8):853-860.
[2] 汪祖柱,吳磊.用戶參與專業(yè)虛擬社區(qū)的滿意度影響因素研究[J].武漢理工大學(xué)學(xué)報(bào):信息與管理工程版,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ù)測(cè)[J].電子科技大學(xué)學(xué)報(bào),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é)點(diǎn)相似性的鏈接預(yù)測(cè)[J].計(jì)算機(jī)科學(xué),2011,38(7):162 -164.
[11] 張昱,張恩德.基于時(shí)間信息的社會(huì)網(wǎng)絡(luò)鏈接預(yù)測(cè)研究[J].計(jì)算機(jī)與數(shù)字工程,2012(11):50-51.