吳陳鶴，杜友田，蘇 暢

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

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

吳陳鶴，杜友田，蘇 暢

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

1 引言

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

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

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

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

2 問題及研究框架

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

實際上，由于節(jié)點數(shù)目較大，直接根據(jù)式（6）和式（7）計算難以進行。可作如下簡化：按照某個節(jié)點順序依次計算每個節(jié)點對應隨機變量的概率：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

[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].軟件學報，2009，20（2）：350-362.

[6]黃創(chuàng)光，印鑒，汪靜，等.不確定近鄰的協(xié)同過濾推薦算法[J].計算機學報，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].計算機科學，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模型在話題追蹤中的應用[J].計算機科學，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)絡中的話題推薦問題，研究了如何選取多個驅(qū)動用戶節(jié)點使得推薦話題能夠得到大的傳播廣度，提出了一種新的信息推薦方法，可以求得次優(yōu)的驅(qū)動節(jié)點集合使得推薦話題得到近似最大的傳播廣度。通過三個環(huán)節(jié)進行計算：通過修正的PageRank算法求得影響力大的節(jié)點；計算第一步得到的每個節(jié)點引起的話題傳播廣度；計算多個節(jié)點聯(lián)合驅(qū)動時話題傳播的廣度，選擇使傳播廣度最大的驅(qū)動節(jié)點集合。實驗結(jié)果表明選取的近似最優(yōu)驅(qū)動節(jié)點集合能夠使得推薦信息得到更大廣度的傳播。

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

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.

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

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

2013-02-01

2013-05-21

1002-8331（2013）15-0141-06

◎圖形圖像處理◎