有限节点驱动的微博社会网络话题推荐方法

吴陈鹤，杜友田，苏 畅

西安交通大学 智能网络与网络安全教育部重点实验室，西安 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

◎图形图像处理◎