有限節點驅動的微博社會網絡話題推薦方法

吳陳鶴，杜友田，蘇 暢

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

有限節點驅動的微博社會網絡話題推薦方法

吳陳鶴，杜友田，蘇 暢

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

1 引言

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

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

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

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

2 問題及研究框架

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

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

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

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

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

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

3 有限節點驅動的話題推薦方法

3.1 基于修正PageRank的節點影響力計算

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

d為跳躍概率，一般為取經驗值0.15。PageRank算法也常用于計算在線社會網絡中節點的權威性。

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

圖1 雙邊雙權值網絡

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

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

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

其中d仍取經驗值0.15，n為網絡節點總數，Bν，f為關注節點qν的用戶集合，Bν，r為轉發過節點qν的用戶集合。基于式（5）迭代計算可得到節點影響力的排序，取前C個節點構成候選節點集QIS。

3.2 單用戶節點驅動的話題傳播廣度計算

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

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

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

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

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

3.3 多節點聯合驅動下話題傳播廣度最大化

圖2 信息轉發網絡及其推理

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

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

為了提高計算效率，本文基于貪婪算法的策略，依次選擇驅動節點，最終得到次優解：

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

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

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

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

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

4 實驗結果與分析

4.1 節點影響力結果與分析

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

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

表1 節點興趣度值

表2 PageRank算法權威節點信息表

表3 PageRank與InfluentialRank（IR）權威節點對比

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

4.2 單節點傳播能力結果與分析

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

圖3 單節點驅動時的用戶節點激活概率直方圖

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

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

表4 三種節點評價方法對比

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

4.3 多節點聯合傳播能力結果與分析

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

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

圖4 多驅動節點選擇結果對比

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

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

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

5 結論

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

[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]許海玲，吳瀟，李曉東，等.互聯網推薦系統比較研究[J].軟件學報，2009，20（2）：350-362.

[6]黃創光，印鑒，汪靜，等.不確定近鄰的協同過濾推薦算法[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

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

在線社會網絡；信息傳播；話題推薦；節點影響力；動態貝葉斯網絡

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—），男，碩士研究生，研究領域為在線社會網絡；杜友田（1980—），男，博士，講師，研究領域為在線社會網絡，網絡多媒體理解，機器學習；蘇暢（1988—），男，博士研究生，研究領域為在線社會網絡，機器學習。E-mail：duyt@mail.xjtu.edu.cn

2013-02-01

2013-05-21

1002-8331（2013）15-0141-06

◎圖形圖像處理◎