有限節(jié)點(diǎn)驅(qū)動的微博社會網(wǎng)絡(luò)話題推薦方法

吳陳鶴，杜友田，蘇 暢

西安交通大學(xué) 智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點(diǎn)實驗室，西安 710049

有限節(jié)點(diǎn)驅(qū)動的微博社會網(wǎng)絡(luò)話題推薦方法

吳陳鶴，杜友田，蘇 暢

西安交通大學(xué) 智能網(wǎng)絡(luò)與網(wǎng)絡(luò)安全教育部重點(diǎn)實驗室，西安 710049

1 引言

近年來，微博、博客和論壇等新型網(wǎng)絡(luò)應(yīng)用服務(wù)的出現(xiàn)深刻改變了人們的信息交流方式，成為了人們獲取、傳播信息的重要平臺。由此形成的在線社會網(wǎng)絡(luò)（Online Social Networks，OSN）[1]已經(jīng)成為了當(dāng)前研究的熱點(diǎn)。微博是在線社會網(wǎng)絡(luò)的典型代表之一，已成為一種重要的信息交流平臺和公共話題傳播平臺。

在線社會網(wǎng)絡(luò)研究主要涉及網(wǎng)絡(luò)結(jié)構(gòu)和用戶行為分析、信息傳播建模以及內(nèi)容推薦等，這些研究彼此之間存在密切的關(guān)系[2-3]。目前，內(nèi)容推薦研究側(cè)重于通過分析用戶關(guān)注的內(nèi)容將符合用戶興趣的內(nèi)容進(jìn)行推薦，在電子商務(wù)系統(tǒng)和視頻分享網(wǎng)站等領(lǐng)域得到廣泛應(yīng)用[4-5]。采用的技術(shù)主要是協(xié)同過濾，即通過對用戶的顯式輸入或隱式輸入的歷史數(shù)據(jù)收集并統(tǒng)計，預(yù)測與此用戶興趣相似的用戶，并將相似用戶感興趣的項目推薦給此用戶[4]。文獻(xiàn)[6]提出了一種不確定近鄰的協(xié)同過濾推薦算法，該方法基于用戶以及產(chǎn)品的相似性計算，自適應(yīng)地選擇預(yù)測目標(biāo)的近鄰對象作為推薦群。

以上內(nèi)容推薦研究主要考慮了內(nèi)容的匹配程度。實際上，對于微博社會網(wǎng)絡(luò)來說內(nèi)容推薦還有另外一種類型：將內(nèi)容推薦至多個用戶節(jié)點(diǎn)，基于這些驅(qū)動節(jié)點(diǎn)的粉絲的關(guān)注和轉(zhuǎn)發(fā)來實現(xiàn)信息傳播并將內(nèi)容推薦至更多的用戶。該問題的核心是：如何確定多個用戶節(jié)點(diǎn)，使得由這些節(jié)點(diǎn)聯(lián)合驅(qū)動時話題傳播廣度最大。信息傳播受用戶興趣度、用戶朋友數(shù)、用戶的轉(zhuǎn)發(fā)行為等多種因素影響[7-10]。Saito[7]和Τang[8]等人通過實驗發(fā)現(xiàn)，由于用戶對話題存在不同喜好，同一節(jié)點(diǎn)對不同話題的傳播能力也有很大差異。Yang等人發(fā)現(xiàn)信息內(nèi)容對相關(guān)用戶的提及率是影響該信息傳播速度、規(guī)模以及范圍的重要因素[9]。目前還沒有研究工作深入討論如何選取多個驅(qū)動用戶節(jié)點(diǎn)，使得推薦信息能夠得到最大化的傳播廣度。

本文提出了一種新的信息推薦方法，該方法可以求得次優(yōu)的驅(qū)動節(jié)點(diǎn)集合使得推薦的信息能達(dá)到近似最大的傳播廣度。該方法包含三個環(huán)節(jié)：（1）通過修正的PageRank算法計算各節(jié)點(diǎn)的影響力，得到若干個候選節(jié)點(diǎn)；（2）基于動態(tài)貝葉斯網(wǎng)絡(luò)推理計算每個候選節(jié)點(diǎn)作為驅(qū)動節(jié)點(diǎn)時帶來的話題傳播廣度；（3）計算多個節(jié)點(diǎn)聯(lián)合驅(qū)動時的話題傳播廣度并選擇最終的驅(qū)動節(jié)點(diǎn)集合。該方法綜合考慮了微博社會網(wǎng)絡(luò)中的關(guān)注關(guān)系、轉(zhuǎn)發(fā)行為和對話題的興趣度等要素，準(zhǔn)確地度量了信息傳播廣度，有效地選取了信息傳播能力最強(qiáng)的驅(qū)動節(jié)點(diǎn)集。

2 問題及研究框架

微博社會網(wǎng)絡(luò)中的每個用戶節(jié)點(diǎn)所發(fā)布話題的傳播范圍是有限的。本文關(guān)注的問題是：將話題tp推薦給c個用戶Q={qn1，qn2，…，qnc}，使節(jié)點(diǎn)集合Q首次發(fā)布該話題并使其得到最廣泛傳播，即

其中，Q和QP分別為c個驅(qū)動節(jié)點(diǎn)和c個最優(yōu)驅(qū)動節(jié)點(diǎn)，qi表示用戶節(jié)點(diǎn)，TIP表示話題的信息傳播廣度，本文第3章中給出具體描述。

節(jié)點(diǎn)對話題的一次傳播能力取決于粉絲數(shù)目、對話題的興趣度及轉(zhuǎn)發(fā)活躍度。傳播廣泛程度取決于該話題的多次傳播。一般來說，粉絲數(shù)目越多，興趣度越大，轉(zhuǎn)發(fā)活躍性越強(qiáng)，則傳播范圍越廣。在大規(guī)模的用戶節(jié)點(diǎn)中，準(zhǔn)確描述節(jié)點(diǎn)的話題傳播廣度并根據(jù)式（1）求取最優(yōu)的c個驅(qū)動節(jié)點(diǎn)是非常困難的。本文將問題（1）的求解分解為三個環(huán)節(jié)：

（1）通過修正的PageRank算法計算各節(jié)點(diǎn)的影響力，并選取C(C＞c)個影響力最大的節(jié)點(diǎn)構(gòu)成候選節(jié)點(diǎn)集QIS。其中，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)考慮了用戶節(jié)點(diǎn)的關(guān)注關(guān)系、轉(zhuǎn)發(fā)行為以及話題興趣度。該環(huán)節(jié)能夠快速地計算出候選節(jié)點(diǎn)集。

（2）計算QIS中各節(jié)點(diǎn)的話題傳播廣度。步驟（1）的節(jié)點(diǎn)影響力粗略地反映該節(jié)點(diǎn)的話題傳播廣度，但是不夠準(zhǔn)確。在該環(huán)節(jié)中準(zhǔn)確計算以QIS中的單個節(jié)點(diǎn)為驅(qū)動節(jié)點(diǎn)時，網(wǎng)絡(luò)中的節(jié)點(diǎn)參與該話題傳播的概率，并通過該概率來度量QIS中各節(jié)點(diǎn)的信息傳播廣度。

（3）選取聯(lián)合驅(qū)動下話題傳播廣度最大的c個節(jié)點(diǎn)。該環(huán)節(jié)采用貪婪策略：首先選擇步驟（2）中傳播廣度最大的節(jié)點(diǎn)，通過計算重疊系數(shù)，選出第二個節(jié)點(diǎn)，使得兩者聯(lián)合傳播廣度最大；以此類推，最終得到c個節(jié)點(diǎn)。由于采用貪婪策略，故得到的節(jié)點(diǎn)可能不是全局最優(yōu)解，但計算效率高，且大多情況下完全滿足需要。

3 有限節(jié)點(diǎn)驅(qū)動的話題推薦方法

3.1 基于修正PageRank的節(jié)點(diǎn)影響力計算

PageRank算法[11]是用于計算網(wǎng)頁權(quán)威度的方法。該方法認(rèn)為被越多其他網(wǎng)頁鏈接的網(wǎng)頁權(quán)威性越高，被越權(quán)威網(wǎng)頁鏈接的網(wǎng)頁權(quán)威性越高。具體計算如下：給定有向圖G=(V，E)，其中頂點(diǎn)V為網(wǎng)頁集合，邊E為網(wǎng)頁間的鏈接集合。設(shè)n為網(wǎng)頁數(shù)目，Bu為鏈接網(wǎng)頁u的網(wǎng)頁集合，u的權(quán)威度為：

d為跳躍概率，一般為取經(jīng)驗值0.15。PageRank算法也常用于計算在線社會網(wǎng)絡(luò)中節(jié)點(diǎn)的權(quán)威性。

微博社會網(wǎng)絡(luò)中，節(jié)點(diǎn)發(fā)布的話題主要依靠其粉絲的關(guān)注和轉(zhuǎn)發(fā)進(jìn)行傳播，具有類似于上述網(wǎng)頁的特點(diǎn)：被大量節(jié)點(diǎn)或高影響力節(jié)點(diǎn)進(jìn)行關(guān)注（或話題轉(zhuǎn)發(fā)）的用戶節(jié)點(diǎn)具有較高的影響力。但PageRank算法只考慮了網(wǎng)絡(luò)結(jié)構(gòu)，而沒有考慮節(jié)點(diǎn)的轉(zhuǎn)發(fā)行為和對話題的興趣。本文提出一種修正的PageRank算法（本文稱為InfluentialRank，簡稱IR算法）并用于節(jié)點(diǎn)影響力的計算。在話題的傳播中，節(jié)點(diǎn)影響力與話題興趣度、粉絲數(shù)量及粉絲對話題的轉(zhuǎn)發(fā)概率等多個要素相關(guān)。圖1是基于這些要素構(gòu)建的雙邊雙權(quán)值網(wǎng)絡(luò)，其中頂點(diǎn)為用戶，邊包括關(guān)注關(guān)系（follow）與轉(zhuǎn)發(fā)關(guān)系（retweet），兩種邊都有各自的權(quán)重，分別對應(yīng)于興趣度和轉(zhuǎn)發(fā)率。

圖1 雙邊雙權(quán)值網(wǎng)絡(luò)

在圖1中，qu，qν，qm和qn為用戶節(jié)點(diǎn)；實線邊（稱做關(guān)注邊）表示關(guān)注，從qu指向qν的邊表示qu是qν的粉絲；虛線邊（稱做轉(zhuǎn)發(fā)邊）表示轉(zhuǎn)發(fā)，從qu指向qν的邊表示qu轉(zhuǎn)發(fā)過qν的帖子。qν的影響力IR()qν與其粉絲的關(guān)注邊和轉(zhuǎn)發(fā)邊都有關(guān)系，其粉絲的關(guān)注邊和轉(zhuǎn)發(fā)邊都會從自身節(jié)點(diǎn)上分配到一定比例的影響力，并傳遞給qν。令每條關(guān)注邊分配到的影響力相同，每條轉(zhuǎn)發(fā)邊分配到的影響力相同，即

其中，ODf(qu)表示從qu發(fā)出的關(guān)注邊數(shù)目，ODr(qu)表示從qu發(fā)出的轉(zhuǎn)發(fā)邊數(shù)目，α用來調(diào)節(jié)兩類邊的重要程度。wuν，f為關(guān)注邊權(quán)值，表示qν對推薦話題的興趣度；wuν，r是轉(zhuǎn)發(fā)邊權(quán)值，其值等于qu轉(zhuǎn)發(fā)qν話題的概率，即

其中Nν是節(jié)點(diǎn)qν的發(fā)帖總數(shù)，Nuν，r是節(jié)點(diǎn)qu轉(zhuǎn)發(fā)qν的帖子數(shù)量。節(jié)點(diǎn)對話題的興趣度采用LDA（Latent Dirichlet Allocation）算法[12-13]計算。通過LDA計算用戶歷史發(fā)帖內(nèi)容和推薦話題的相似度，可作為用戶對話題的興趣度。在圖1的網(wǎng)絡(luò)構(gòu)建基礎(chǔ)上，InfluentialRank算法用下式表示：

其中d仍取經(jīng)驗值0.15，n為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)，Bν，f為關(guān)注節(jié)點(diǎn)qν的用戶集合，Bν，r為轉(zhuǎn)發(fā)過節(jié)點(diǎn)qν的用戶集合。基于式（5）迭代計算可得到節(jié)點(diǎn)影響力的排序，取前C個節(jié)點(diǎn)構(gòu)成候選節(jié)點(diǎn)集QIS。

3.2 單用戶節(jié)點(diǎn)驅(qū)動的話題傳播廣度計算

對于3.1節(jié)求得的用戶節(jié)點(diǎn)q∈QIS，建立由q作為單一驅(qū)動節(jié)點(diǎn)時的話題轉(zhuǎn)發(fā)網(wǎng)絡(luò)，并基于該網(wǎng)絡(luò)計算話題傳播廣度。在該網(wǎng)絡(luò)中，若某用戶接收（即關(guān)注）到該信息，則認(rèn)為該用戶被激活，并以概率p（p可能為0）轉(zhuǎn)發(fā)該信息。通過計算網(wǎng)絡(luò)中被激活用戶的概率和數(shù)量可以得出話題傳播廣度。圖2（a）是基于轉(zhuǎn)發(fā)關(guān)系構(gòu)建的網(wǎng)絡(luò)，為了使該圖清晰，關(guān)注關(guān)系被忽略掉。在該網(wǎng)絡(luò)中，每個節(jié)點(diǎn)qi對應(yīng)一個二值隨機(jī)變量Xi，其中Xi=1表示轉(zhuǎn)發(fā)，Xi=0表示不轉(zhuǎn)發(fā)。該轉(zhuǎn)發(fā)網(wǎng)絡(luò)是一個有向有環(huán)概率圖（Directed Cyclic Graph，DCG）。若已知各節(jié)點(diǎn)轉(zhuǎn)發(fā)信息的條件概率Pr(Xi|Pa(Xi))，則可以推理出每個節(jié)點(diǎn)轉(zhuǎn)發(fā)信息的概率Pr(Xi)。

n′為隨機(jī)變量個數(shù)。隨著t的增大，Pr(Xt)結(jié)果會收斂。可以選取式（6）的最大計算次數(shù)T或計算誤差ε，使得ε時算法停止計算。Pr(即為節(jié)點(diǎn)轉(zhuǎn)發(fā)信息的條件概率Pr(Xi|Pa(Xi))，在計算過程中不隨t的變化而變化。用戶節(jié)點(diǎn)qi轉(zhuǎn)發(fā)話題的概率為：

實際上，由于節(jié)點(diǎn)數(shù)目較大，直接根據(jù)式（6）和式（7）計算難以進(jìn)行?？勺魅缦潞喕喊凑漳硞€節(jié)點(diǎn)順序依次計算每個節(jié)點(diǎn)對應(yīng)隨機(jī)變量的概率：

由式（9）可知，只需知道qi轉(zhuǎn)發(fā)qj話題的概率Pr(Xi|Xj)即可。該概率可按下式進(jìn)行計算：

其中Nj→i為節(jié)點(diǎn)qi轉(zhuǎn)發(fā)qj的帖子數(shù)，Ni為節(jié)點(diǎn)qi發(fā)表的帖子數(shù)，一旦節(jié)點(diǎn)qi轉(zhuǎn)發(fā)了目標(biāo)帖，則認(rèn)為其粉絲fans(qi)均接收到了該帖子信息。若節(jié)點(diǎn)qi和qj均以一定的概率轉(zhuǎn)發(fā)目標(biāo)帖子，而qi和qj的公共粉絲接收到該信息的概率近似估計為：

3.3 多節(jié)點(diǎn)聯(lián)合驅(qū)動下話題傳播廣度最大化

圖2 信息轉(zhuǎn)發(fā)網(wǎng)絡(luò)及其推理

由于各個驅(qū)動節(jié)點(diǎn)引起的信息傳播范圍可能有交疊，所以多個節(jié)點(diǎn)聯(lián)合驅(qū)動時話題傳播廣度不一定等于多個單節(jié)點(diǎn)驅(qū)動時的傳播廣度之和。首先針對兩個驅(qū)動節(jié)點(diǎn)情況定義重疊系數(shù)：

其中Sij為qi和qj做驅(qū)動節(jié)點(diǎn)時傳播的重疊系數(shù)，Si和Sj分別為qi和qj驅(qū)動下被激活的節(jié)點(diǎn)集合分別為qk在qi和qj驅(qū)動下的激活概率。

為了提高計算效率，本文基于貪婪算法的策略，依次選擇驅(qū)動節(jié)點(diǎn)，最終得到次優(yōu)解：

（1）令QP=，選擇傳播廣度最大的節(jié)點(diǎn)放入QP，作為QP中的第一個節(jié)點(diǎn)qm1，同時刪除候選節(jié)點(diǎn)集QIS中的該節(jié)點(diǎn)。

（2）計算與QIS中各節(jié)點(diǎn)之間的重疊系數(shù)，取重疊系數(shù)最小的節(jié)點(diǎn)放入QP，作為第二個驅(qū)動節(jié)點(diǎn)，同時刪除QIS中的該節(jié)點(diǎn)。

（3）將和的驅(qū)動范圍和合并得到聯(lián)合驅(qū)動范圍SJ，并與QIS中每個節(jié)點(diǎn)的驅(qū)動范圍做重疊系數(shù)計算，將重疊系數(shù)最小的節(jié)點(diǎn)放入QP，作為QP中的第三個節(jié)點(diǎn)，同時刪除QIS中的該節(jié)點(diǎn)。在SJ中同時被和激活的節(jié)點(diǎn)，其激活概率取兩者最大值。

（4）以此類推，直到選出c個節(jié)點(diǎn)組成QP為止。

嚴(yán)格來說，信息傳播帶來的影響與激活節(jié)點(diǎn)的分布等要素也有密切關(guān)系。本文將該問題作了簡化，只考慮了重疊情況帶來的影響。

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

4.1 節(jié)點(diǎn)影響力結(jié)果與分析

本文實驗用新浪微博數(shù)據(jù)，選取了一個包含29 514個用戶節(jié)點(diǎn)和421 140條邊的網(wǎng)絡(luò)社區(qū)，以及這些節(jié)點(diǎn)近三個月內(nèi)發(fā)的3 248 734條帖子，其中包括776 641條轉(zhuǎn)發(fā)帖。計算興趣度時選取的是時尚類話題。表1所示是通過LDA算法計算興趣度后排名前十的節(jié)點(diǎn)信息與興趣度值。從表1看，排名第一的是節(jié)點(diǎn)234526481，該節(jié)點(diǎn)是經(jīng)過新浪認(rèn)證的服飾類進(jìn)出口公司，服飾是時尚中最重要的話題之一，因此其興趣度會高。而下文根據(jù)PageRank算法得到的排名第一節(jié)點(diǎn)“新浪天氣”興趣度排到了第23 076名，因為該節(jié)點(diǎn)主要是發(fā)布天氣信息，與時尚類很不相關(guān)。

表2列出了PageRank算法中排名前十的節(jié)點(diǎn)信息。從表3可以看出，PageRank中節(jié)點(diǎn)影響力基本上是由用戶粉絲數(shù)量決定，這是因為PageRank算法只考慮節(jié)點(diǎn)間關(guān)注關(guān)系。粉絲的影響力在一定程度上也會影響節(jié)點(diǎn)影響力。如表2所示，八號節(jié)點(diǎn)粉絲數(shù)只有371個，但是排名前十的節(jié)點(diǎn)中有7個都是其粉絲，所以影響力也較高。但是，忽略了對信息傳播占重要影響的轉(zhuǎn)發(fā)行為使得PageRank算法得到的影響力結(jié)果不夠準(zhǔn)確。如節(jié)點(diǎn)“新浪天氣”雖然粉絲眾多，其粉絲基本上只看天氣信息很少轉(zhuǎn)發(fā)，而且其話題內(nèi)容與實驗中分析的時尚類話題相關(guān)性也較弱，所以在實際中對于時尚類話題傳播的影響力較弱。

表1 節(jié)點(diǎn)興趣度值

表2 PageRank算法權(quán)威節(jié)點(diǎn)信息表

表3 PageRank與InfluentialRank（IR）權(quán)威節(jié)點(diǎn)對比

表3列出了不同α下，InfluentialRank算法中排名前十的節(jié)點(diǎn)ID，從該表格中可以看到，在PageRank只排41位的79660節(jié)點(diǎn)“晴娃娃79660”，在InfluentialRank中排名非常靠前，這是因為79660雖然粉絲不多，但其粉絲關(guān)注內(nèi)容和時尚話題很相關(guān)，轉(zhuǎn)發(fā)率較高。而PageRank中排第一的“新浪天氣”，在InfluentialRank算法結(jié)果中排到了第60名之后。由此可見，InfluentialRank算法有效結(jié)合了節(jié)點(diǎn)粉絲數(shù)目、轉(zhuǎn)發(fā)行為和話題興趣度，綜合計算出節(jié)點(diǎn)影響力，克服了PageRank算法缺陷。

4.2 單節(jié)點(diǎn)傳播能力結(jié)果與分析

信息在網(wǎng)絡(luò)中傳播，當(dāng)網(wǎng)絡(luò)中任意節(jié)點(diǎn)接收到該信息時（若一個節(jié)點(diǎn)轉(zhuǎn)發(fā)了某個信息，則視其粉絲均接收到該信息），認(rèn)為該節(jié)點(diǎn)被激活。當(dāng)把信息注入給驅(qū)動節(jié)點(diǎn)時，相當(dāng)于該節(jié)點(diǎn)以1的概率進(jìn)行轉(zhuǎn)發(fā)并在網(wǎng)絡(luò)中擴(kuò)散，網(wǎng)絡(luò)中所有節(jié)點(diǎn)都得到一個激活概率（接收到信息的概率）。最大計算次數(shù)選T=10。圖3為將時尚類信息注入給節(jié)點(diǎn)10473、11075和18681337時的網(wǎng)絡(luò)節(jié)點(diǎn)激活概率直方圖。

圖3 單節(jié)點(diǎn)驅(qū)動時的用戶節(jié)點(diǎn)激活概率直方圖

從圖中可以看出，有大量節(jié)點(diǎn)（約1 500左右）的激活概率在0.9以上，這是因為選取的驅(qū)動節(jié)點(diǎn)是根據(jù)Influential-Rank算法計算后挑選出的排名高的節(jié)點(diǎn)，擁有較多的粉絲，一旦驅(qū)動節(jié)點(diǎn)轉(zhuǎn)發(fā)了目標(biāo)信息，其粉絲都會被激活，體現(xiàn)了OSN中信息的廣度傳播；另一方面，絕大多數(shù)節(jié)點(diǎn)的激活概率在0.2以下，但是這些節(jié)點(diǎn)數(shù)量眾多，故其在信息傳播過程中的作用也是十分重要的，這一現(xiàn)象體現(xiàn)了OSN中信息的深度傳播，以及網(wǎng)絡(luò)中信息傳播的重尾特性。

本文采用激活概率之和來進(jìn)行度量信息傳播廣度：

表4 三種節(jié)點(diǎn)評價方法對比

其中為qk在qi驅(qū)動下的激活概率。表4列出了α=0.6時分別根據(jù)單驅(qū)動節(jié)點(diǎn)激活期望、InfluentialRank和PageRank算法排序后前十名的ID信息。可以發(fā)現(xiàn)三種算法的排序結(jié)果有較大差別，這源自三種算法側(cè)重點(diǎn)的不同。例如，節(jié)點(diǎn)3004005在InfluentialRank和PageRank算法下都排名較低，但由于其帖子具有很強(qiáng)的被轉(zhuǎn)發(fā)傾向，從而在平均激活概率排序下3004005具有很高的排名。另一方面，節(jié)點(diǎn)1015414785在平均激活概率和PageRank算法下排名較低，而在InfluentialRank算法下排名很高，這是因為該節(jié)點(diǎn)擁有相對較多的被轉(zhuǎn)發(fā)邊，而粉絲總數(shù)相對較少，在信息傳播的橫向傳播能力上較為欠缺，從而對整個網(wǎng)絡(luò)的激活能力有限。實驗發(fā)現(xiàn)α=0.6時的所有驅(qū)動節(jié)點(diǎn)的平均激活期望較高，因此后續(xù)實驗采用InfluentialRank算法α=0.6的結(jié)果。

4.3 多節(jié)點(diǎn)聯(lián)合傳播能力結(jié)果與分析

根據(jù)上一階段得出的50個候選節(jié)點(diǎn)傳播能力的排序，通過計算重疊系數(shù)，本文選出了C個節(jié)點(diǎn)組成聯(lián)合驅(qū)動節(jié)點(diǎn)，并計算這些節(jié)點(diǎn)聯(lián)合驅(qū)動下對網(wǎng)絡(luò)中其他節(jié)點(diǎn)的激活概率，該激活概率定義為各個驅(qū)動節(jié)點(diǎn)對該節(jié)點(diǎn)激活概率的最大值：

其中Pk表示節(jié)點(diǎn)qk在驅(qū)動節(jié)點(diǎn)集QP聯(lián)合驅(qū)動下的激活概率。為了驗證本文方法的有效性，與下述兩種算法作了對比：（1）直接選取排名靠前的節(jié)點(diǎn)；（2）與ΤwitterRank[16]算法所選C個驅(qū)動節(jié)點(diǎn)作對比。實驗中，C分別取5和20，結(jié)果如圖4所示。由圖4可以看出，節(jié)點(diǎn)激活概率基本上集中在0.2以下和0.9以上，這是因為多節(jié)點(diǎn)聯(lián)合驅(qū)動時這些節(jié)點(diǎn)的粉絲全部被激活；同時由于社會網(wǎng)絡(luò)的重尾效應(yīng)，其他被激活節(jié)點(diǎn)激活概率較低。

圖4 多驅(qū)動節(jié)點(diǎn)選擇結(jié)果對比

在多個驅(qū)動節(jié)點(diǎn)情況下，采用節(jié)點(diǎn)被激活概率之和P描述信息傳播的廣度：

表5所示是三種不同方法在C分別取5和20時對網(wǎng)絡(luò)中其他節(jié)點(diǎn)激活概率之和。由圖4和表5可以看出，當(dāng)驅(qū)動節(jié)點(diǎn)個數(shù)為5時，由于驅(qū)動節(jié)點(diǎn)數(shù)量較少，節(jié)點(diǎn)重合系數(shù)較低，近似最優(yōu)的驅(qū)動節(jié)點(diǎn)集合的激活能力比直接選取排名靠前節(jié)點(diǎn)改善不太明顯，比ΤwitterRank算法所選節(jié)點(diǎn)也僅有略微改善；當(dāng)驅(qū)動節(jié)點(diǎn)為20個時，本文方法選擇的近似最優(yōu)驅(qū)動節(jié)點(diǎn)集合要比直接選取前20個和ΤwitterRank算法選取節(jié)點(diǎn)均有較大提升。

表5 三種不同方法下綜合激活概率之和

5 結(jié)論

本文提出了一種新的針對微博在線社會網(wǎng)絡(luò)的信息推薦方法。該方法可以求得一個次優(yōu)的驅(qū)動節(jié)點(diǎn)集合，使得推薦的信息可以得到近似最大的傳播廣度。該方法綜合考慮了微博社會網(wǎng)絡(luò)中的關(guān)注關(guān)系、轉(zhuǎn)發(fā)行為和對話題的興趣度等要素，準(zhǔn)確地度量了信息傳播廣度，有效地選取了信息傳播能力最強(qiáng)的驅(qū)動節(jié)點(diǎn)集。實驗結(jié)果表明，本文計算得到的節(jié)點(diǎn)的影響力更為準(zhǔn)確，最終選取的近似最優(yōu)驅(qū)動節(jié)點(diǎn)集合能夠得到更高的激活期望，使得推薦的信息可以得到更大廣度的傳播。

[1]Katarzyna M，Przemys?aw K.Social networks on the Internet[J]. World Wide Web Journal，2013，16.

[2]Alan M，Massimiliano M，Krishna P G，et al.Measurement and analysis of online social networks[C]//7th ACM SIGCOMM Conference on Internet Measurement，2007：24-26.

[3]Zhao Jichang，Wu Junjie，Xu Ke.Weak ties：subtle role of information diffusion in onlinesocialnetworks[J].Physical Review E，2010，82（1）.

[4]Ido G，Naama Z，Inbal R，et al.Social media recommendation based on people and tags[C]//ACM SIGIR Conference，2010：194-201.

[5]許海玲，吳瀟，李曉東，等.互聯(lián)網(wǎng)推薦系統(tǒng)比較研究[J].軟件學(xué)報，2009，20（2）：350-362.

[6]黃創(chuàng)光，印鑒，汪靜，等.不確定近鄰的協(xié)同過濾推薦算法[J].計算機(jī)學(xué)報，2010，33（8）：1369-1377.

[7]Saito K，Kimura M，Ohara K，et al.Behavioral analyses of information diffusion models by observed data of social network[C]//LNCS，2010：149-158.

[8]Τang Jie，Sun Jimeng，Wang Chi，et al.Social influence analysis in large-scale networks[C]//ACM SIGKDD，2009：807-816.

[9]Yang Jiang，Scott C.Predicting the speed，scale，and range of information diffusion in twitter[C]//Fourth International AAAI Conference on Weblogs and Social Media，2010：355-358.

[10]KristinaL，Rumi G.Information contagion：an empirical study of the spread of news on digg and twitter social networks[C]//Fourth International AAAI Conference on Weblogs and Social Media，2010：90-97.

[11]李稚楹，楊武，謝治軍.PageRank算法研究綜述[J].計算機(jī)科學(xué)，2011，38（S1）：185-188.

[12]David M B，Andrew Y N，Michael I J.Latent Dirichlet allocation[J].Τhe Journal of Machine Learning Research，2003，3：993-1022.

[13]張曉艷，王挺，梁曉波.LDA模型在話題追蹤中的應(yīng)用[J].計算機(jī)科學(xué)，2011，38（S1）：136-139.

[14]Natarajan P，Nevatia R.Coupled hidden semi Markov models for activity recognition[C]//IEEE Workshop on Motion and Video Computing，2007：47-57.

[15]Saul L，Jordan M.Mixed memory markov models：decomposing complex stochastic processes as mixtures of simpler ones[J].Machine Learning，1999，37：75-87.

[16]Yuto Y，Τsubasa Τ，Τoshiyuki A.ΤURank_twitter user ranking based on user-tweet graph analysis[C]//Lecture Notes in Computer Science，2010：240-253.

WU Chenhe,DU Youtian,SU Chang

Ministry of Education Key Lab for Intelligent Networks and Network Security,Xi’an Jiaotong University,Xi’an 710049,China

Aiming at the topic recommendation problem in online social networks,this paper focuses on how to find a set of driving nodes which can make the information diffusion broadly,and proposes a new recommendation method that can obtain an approximately optimal set of driving nodes.Τhis method includes three steps：finding the candidate set of driving nodes which have the greatest influence with an extended PageRank algorithm;calculating the breadth of topic diffusion for each driving node in candidate set;and calculating the breadth of topic diffusion for a number of joint driving nodes and finding an approximately optimal set of driving nodes.Experimental results show that the achieved approximately optimal driving node set leads to larger breadth of topic diffusion.

online social network;information propagation;topic recommendation;user influence;dynamic Bayesian network

針對微博在線社會網(wǎng)絡(luò)中的話題推薦問題，研究了如何選取多個驅(qū)動用戶節(jié)點(diǎn)使得推薦話題能夠得到大的傳播廣度，提出了一種新的信息推薦方法，可以求得次優(yōu)的驅(qū)動節(jié)點(diǎn)集合使得推薦話題得到近似最大的傳播廣度。通過三個環(huán)節(jié)進(jìn)行計算：通過修正的PageRank算法求得影響力大的節(jié)點(diǎn)；計算第一步得到的每個節(jié)點(diǎn)引起的話題傳播廣度；計算多個節(jié)點(diǎn)聯(lián)合驅(qū)動時話題傳播的廣度，選擇使傳播廣度最大的驅(qū)動節(jié)點(diǎn)集合。實驗結(jié)果表明選取的近似最優(yōu)驅(qū)動節(jié)點(diǎn)集合能夠使得推薦信息得到更大廣度的傳播。

在線社會網(wǎng)絡(luò)；信息傳播；話題推薦；節(jié)點(diǎn)影響力；動態(tài)貝葉斯網(wǎng)絡(luò)

A

ΤP393.0

10.3778/j.issn.1002-8331.1301-0374

WU Chenhe,DU Youtian,SU Chang.Topic recommendation method with finite driving user nodes in micro-blogging. Computer Engineering and Applications,2013,49（15）：141-146.

國家自然科學(xué)基金（No.60905018）；“十二五”國家科技支撐計劃重點(diǎn)課題（No.2011BAK08B02）。

吳陳鶴（1987—），男，碩士研究生，研究領(lǐng)域為在線社會網(wǎng)絡(luò)；杜友田（1980—），男，博士，講師，研究領(lǐng)域為在線社會網(wǎng)絡(luò)，網(wǎng)絡(luò)多媒體理解，機(jī)器學(xué)習(xí)；蘇暢（1988—），男，博士研究生，研究領(lǐng)域為在線社會網(wǎng)絡(luò)，機(jī)器學(xué)習(xí)。E-mail：duyt@mail.xjtu.edu.cn

2013-02-01

2013-05-21

1002-8331（2013）15-0141-06

◎圖形圖像處理◎