一种基于有限节点驱动的微博社会网络信息推荐方法

技术领域

本发明属于在线社会网络技术领域，涉及一种基于有限节点驱动的微博社会网络信息推荐方法。

背景技术

近年来，微博、博客和论坛等新型网络应用服务的出现深刻改变了人们的信息交流方式，成为了人们获取、传播信息的重要平台。由此形成的在线社会网络（Online Social Networks，OSN）已经成为了当前研究的热点。微博是在线社会网络的典型代表之一，已成为一种重要的信息交流平台和公共话题传播平台。

在线社会网络研究主要涉及网络结构和用户行为分析、信息传播建模以及内容推荐等。目前，内容推荐研究侧重于通过分析用户关注的内容将符合用户兴趣的内容直接推荐至用户，在电子商务系统和视频分享网站等领域得到广泛应用。采用的技术主要是协同过滤，即通过对用户的显式输入或隐式输入的历史数据收集并统计，预测与此用户兴趣相似的用户，并将相似用户感兴趣的对象或信息推荐给此用户。

基于协同过滤的内容推荐研究主要考虑了内容的匹配程度。实际上，对于微博社会网络来说内容推荐还有另外一种类型：将内容推荐至多个用户节点，基于这些驱动节点及其粉丝的关注和转发来实现信息传播并将内容推荐至更多的用户。该问题的核心是：如何确定多个驱动用户节点，使得由这些节点联合驱动时话题的传播广度最大。信息传播受用户兴趣度、用户粉丝数、用户的转发行为等多种因素影响。以往研究表明，由于用户对话题存在不同喜好，同一节点对不同话题的传播能力有很大差异。此外，信息内容对相关用户的提及率也是影响该信息传播速度、规模以及范围的重要因素。

发明内容

本发明解决的问题在于提供一种基于有限节点驱动的微博社会网络信息推荐方法，使得推荐信息在微博网络中传播能达到近似最大的广度。

本发明是通过以下技术方案来实现：

一种基于有限节点驱动的微博社会网络信息推荐方法，包括以下操作：

1）在微博社会网络中，构建以用户节点为顶点，顶点之间的边包括关注边和转发边的双边双权值网络，其中关注边和转发边分别有各自的权重；

按照下式计算微博社会网络中节点的影响力IR，并选取C个影响力最大的节点构成候选节点集Q_C：

$>\mathrm{IR}\left(q_v\right)=\frac{d}{N}+(1-d)[\underset{q_u\in B_{v,f}}{\Sigma }{t}_{u,f}{w}_{\mathrm{uv},f}+\underset{q_u\in B_{v,r}}{\Sigma }{t}_{u,r}{w}_{\mathrm{uv},r}]$>

其中，d为跳变概率，N为网络中的用户节点数，B_v,f和B_v,r分别为节点q_v关注和转发过的节点集；

$>t_{u,f}=\frac{\alpha ·\mathrm{IR}\left(q_u\right)}{{\mathrm{OD}}_f\left(q_u\right)},$>$>t_{u,r}=\frac{(1-\alpha )·\mathrm{IR}\left(q_u\right)}{{\mathrm{OD}}_r\left(q_u\right)}$>

OD_f(q_u)表示从节点q_u发出的关注边数目，OD_r(q_u)表示从节点q_u发出的转发边数目，α表示调节两类边的重要程度；w_uv,f为关注边权值，w_uv,r为转发边权值，等于节点q_u转发节点q_v话题的概率；

w_uv,f=I_v,$>w_{\mathrm{uv},r}=\frac{M_{\mathrm{uv},r}}{M_v}$>

I_v为节点q_v对所推荐的信息或话题的兴趣度，M_v是节点q_v的发帖总数，M_uv,r是节点q_v转发节点q_u的帖子数量；

2）对于候选节点集Q_C中的单个节点q，q∈Q_C，建立由q作为单一驱动节点时的推荐话题转发网络，并基于该网络计算单个节点驱动时的推荐信息或话题传播广度的期望值；

3）计算候选节点集Q_C中个节点n个节点联合驱动下信息传播的广度的期望值，n<C，选取使得信息传播广度最大的n个用户节点，以所选择的n个用户节点作为驱动节点进行推荐信息或话题的传播。

所述的兴趣度I_v通过LDA算法计算用户节点q_v历史发帖内容和推荐信息的相似度，以所计算的结果作为q_v对推荐话题的兴趣度。

所述在步骤2）中，在构建推荐话题转发网络时以网络拓扑结构和用户转发行为基础进行构建，并用动态贝叶斯网络推理方法进行推理，从而计算以单个节点q为信息传播的驱动节点时，网络中的所有节点参与推荐信息或话题传播的概率，在所构建的网络中当某用户节点接收推荐信息或话题时，则该用户节点被激活并以概率p转发该信息或话题，通过计算网络中被激活用户的概率和数量来计算单个节点驱动时的信息传播广度的期望值。

所述在构建的推荐话题转发网络中，每个节点q_i对应一个二值随机变量X_i，其中X_i=1表示转发，X_i=0表示不转发；用户的转发行为用条件概率Pr(X_i|F(X_i))表示，其中F(X_i)为推荐信息或话题被节点q_i转发过的用户节点状态；获知各节点转发信息的条件概率后，推理出每个节点转发信息的概率Pr(X_i)。

所构建的推荐话题转发网络为动态贝叶斯网络，包括初始网B₀和转移网B_→，变量集表示t时刻的随机变量集，

令初始网B₀中的其它变量均为0；在t时刻上的联合概率分布Pr(X^t)为：

$>\mathrm{Pr}\left(X^t\right)=\underset{\mathrm{pa}\left(X_i^t\right)}{\Sigma }\mathrm{Pr}\left(\mathrm{pa}\left(X_i^t\right)\right)·\underset{i=1}{\overset{N}{\Pi }}\mathrm{Pr}\left(X_i^t\right|\mathrm{pa}\left(X_i^t\right))$>

其中，表示在动态贝叶斯网络中的父节点，随着t的增大，将收敛于Pr(X_i)；选取预定义阈值δ，使得时停止计算；

为节点转发推荐信息的条件概率Pr(X_i|pa(X_i))，在计算过程中不随t的变化而变化，则用户节点q_i转发推荐话题的概率为

$>\mathrm{Pr}\left(X_i^t\right)=\underset{X_j^t\ne X_i^t}{\Sigma }\mathrm{Pr}(X_1^t,X_2^t,...,X_n^t)$>

并对条件概率进行如下分解：

$>\mathrm{Pr}\left(X_i^t\right|\mathrm{pa}\left(X_i^t\right))=\underset{X_j^{t-1}\in \mathrm{pa}\left(X_i^t\right)}{\Sigma }{\theta }_i^j·\mathrm{Pr}\left(X_i^t\right|X_j^{t-1})$>

其中，为需要学习的参数，对于所有节点q_i选取其中表示的个数，不受时间t影响，其中X_j∈F(X_i)；而Pr(X_i|X_j)按下式进行计算：

$>\mathrm{Pr}\left(X_i\right|X_j)=\frac{M_{\mathrm{ji},r}}{M_i}$>

其中M_ji,r为节点q_i转发q_j的帖子数，M_i为节点q_i发表的帖子数。

所述在进行步骤3）的计算时，采用贪婪策略：先选择候选节点集Q_C中对推荐话题传播广度最大的节点，通过该节点与其它节点之间的连接强度，选出第二个节点，使得两者联合传播广度最大；以此类推，最终得到n个节点。

所述在进行步骤3）的计算时，n个节点联合驱动下信息传播的广度的期望值的计算为：

任意两个节点q_u和q_v之间的连接强度定义为：

$>w(q_u,q_v)=\frac{o_{\mathrm{uv}}}{k_u-1+k_v-1-o_{\mathrm{uv}}}$>

其中，k_u、k_v为q_u、q_v的粉丝数目，o_uv为q_u、q_v的公共粉丝数；而驱动节点集Q与单一驱动节点q_v之间的连接强度为：

$>w(Q,q_v)=\frac{1}{\left|Q\right|}\underset{q_u\in Q}{\Sigma }w(q_u,q_v)---\left(10\right)$>

其中|Q|为Q包含的节点数；

当一个节点接收到推荐信息或话题时，认为其被激活，且其接收到推荐信息或话题的概率为激活概率；通过激活期望AE来度量单一节点q_v的传播能力，即

$>E_a\left(q_v\right)=\frac{1}{N}\underset{k=1}{\overset{N}{\Sigma }}{p}_k^v$>

其中，为当q_v为驱动节点时节点q_k的激活概率；

则节点集Q的联合激活期望JAE为：

$>E_a\left(Q\right)={\Sigma }_{k=1}^N{p}_k^Q/N;$>

其中为给定点集Q时q_k的激活概率；

多个节点联合驱动话题传播的能力与各单节点的驱动能力的连接强度呈线性关系：

E_a(Q)=Aw(Q′,q_v)+BE_a(q_v)+b+ε    (12)

其中Q′为给定的驱动点集，Q={Q′,q_v}，A、B、b为待估参数，待估参数根据实际数据利用最小二乘算法进行估计，ε为随机噪声。

进一步，基于贪婪算法的策略，依次选择驱动节点，最终得到次优解：

a）初始化选择Q_C中驱动能力最大的节点q_p∈Q_C放入Q_P，同时将它从候选节点集Q_C中删除，即Q_P←Q_P∪q_p，Q_C←Q_Cq_p；

b）根据公式(10)，计算点集Q_P与Q_C中各节点的连接强度，并选取使得公式(12)最大化的节点q_p∈Q_C放入Q_P，即Q_P←Q_P∪q_p，Q_C←Q_Cq_p。

重复步骤b），直到Q_P包含n个驱动节点。

与现有技术相比，本发明具有以下有益的技术效果：

本发明提供的基于有限节点驱动的微博社会网络信息推荐方法，可以求得近似最优的驱动节点集合，使得推荐信息通过这些驱动节点集合驱动后，能够在微博网络中传播能达到近似最大的广度。其中，本发明综合考虑用户间的连接结构、用户对话题的兴趣分布以及用户的转发行为来选择近似最优的驱动用户节点的集合，通过该驱动节点集合进行发布的推荐信息或话题的信息传播广度近似最大。

进一步，本发明除了综合考虑了微博社会网络中用户的连接关系、用户转发行为和对话题的兴趣度等要素，设计合适的网络数学模型之外，还提出了改进的PageRank算法，并基于改进的PageRank算法并结合动态贝叶斯网络推理计算，准确地度量信息传播广度，在此基础上选取信息传播能力最强的驱动节点集合。

附图说明

图1为双边双权值网络的示意图；

图2为信息转发网络的示意图；

图3为动态贝叶斯网络的示意图；其中1～7均为用户节点；

图4为联合激活期望的示意图；其中x坐标为连接强度，y坐标为单节点驱动的激活期望值；z坐标为多节点联合驱动的激活期望值。

具体实施方式

下面结合具体的实施例对本发明做进一步的详细说明，所述是对本发明的解释而不是限定。

本发明提供的基于有限节点驱动的微博社会网络信息推荐方法，可以求得近似最优的驱动节点集合，使得推荐信息在微博网络中传播能达到近似最大的广度。该方法综合考虑了微博社会网络中用户的连接关系、用户转发行为和对话题的兴趣度等要素，设计了合适的网络数学模型，并提出了改进的PageRank算法，进一步结合动态贝叶斯网络推理计算，准确地度量信息传播广度，在此基础上选取信息传播能力最强的驱动节点集合。

一种基于有限节点驱动的微博社会网络信息推荐方法，包括以下操作：

1）首先计算所有节点的影响力，选取C个影响力最大的节点构成候选节点集Q_C；

2）其次，候选节点集Q_C的节点影响力粗略地反映该节点对话题的传播能力，但是还不够精确。因此，构建信息转发网络，准确计算以Q_C中的单个节点为信息传播的驱动节点时，网络中的所有节点参与推荐信息传播的概率，并基于得到的概率来计算单个节点驱动时的信息传播广度的期望值。

3）最后，计算n(n<C)个节点联合驱动下信息传播的广度的期望值，选取使得信息传播广度最大的n个驱动节点作为近似最优的信息推荐节点。

下面对各个步骤进行详细的说明。

步骤1，基于修正PageRank的节点影响力计算

在微博社会网络中，构建以用户节点为顶点，顶点之间的边包括关注边和转发边的双边双权值网络，其中关注边和转发边分别有各自的权重；计算微博社会网络中节点的影响力，并选取C个影响力最大的节点构成候选节点集Q_C。

PageRank算法是用于计算网页权威度的方法，该算法也常用于计算在线社会网络中节点的权威度。因为微博社会网络中，节点发布的话题主要依靠其朋友的关注和转发进行传播，具有类似于网页连接的特点：被大量节点或高影响力节点进行关注（或话题转发）的用户节点具有较高的影响力。

但PageRank算法只考虑了网络结构，而没有考虑用户节点的转发行为以及对话题的兴趣分布。本发明提出一种修正的PageRank算法（本发明称为InfluentialRank,简称IR算法）并用于节点影响力的计算。在话题的传播中，节点影响力与话题兴趣度、粉丝数量及粉丝对话题的转发概率等多个要素相关。

图1是基于这些要素构建的双边双权值网络，其中顶点为用户，边包括关注关系（follow）与转发关系（retweet），两种边都有各自的权重，分别对应于兴趣度和转发率。

在图1所示的双边双权值网络中，q_u,q_v,q_m和q_n为用户节点；从q_u指向q_v的实线边表示q_v是q_u的粉丝；从q_u指向q_v的虚线边表示q_v转发过q_u的帖子。q_v的影响力IR(q_v)与其粉丝的关注边和转发边都有关系，其粉丝的关注边和转发边都会从自身节点上分配到一定比例的影响力，并传递给q_v。

令每条关注边分配到的影响力t_u,f相同，每条转发边分配到的影响力t_u,r相同，即：

$>t_{u,f}=\frac{\alpha ·\mathrm{IR}\left(q_u\right)}{{\mathrm{OD}}_f\left(q_u\right)},$>$>t_{u,r}=\frac{(1-\alpha )·\mathrm{IR}\left(q_u\right)}{{\mathrm{OD}}_r\left(q_u\right)}---\left(1\right)$>

其中，OD_f(q_u)表示从q_u发出的关注边数目，OD_r(q_u)表示从q_u发出的转发边数目，α用来调节两类边的重要程度；

关注边权值w_uv,f，用q_v对推荐话题的兴趣度I_v来度量；

转发边权值w_uv,r，其值等于q_u转发q_v话题的概率，即：

w_uv,f=I_v,$>w_{\mathrm{uv},r}=\frac{M_{\mathrm{uv},r}}{M_v}---\left(2\right)$>

其中M_v是节点q_v的发帖总数，M_uv,r是节点q_v转发q_u的帖子数量。节点对话题的兴趣度I_v采用LDA（Latent Dirichlet Allocation）算法计算。通过LDA计算用户历史发帖内容和推荐信息的相似度，可作为用户对话题的兴趣度。

在图1的网络构建基础上，InfluentialRank算法用下式表示：

$>\mathrm{IR}\left(q_v\right)=\frac{d}{N}+(1-d)[\underset{q_u\in B_{v,f}}{\Sigma }{t}_{u,f}{w}_{\mathrm{uv},f}+\underset{q_u\in B_{v,r}}{\Sigma }{t}_{u,r}{w}_{\mathrm{uv},r}]---\left(3\right)$>

其中，跳变概率d取经验值0.15，N为网络中的用户节点数，B_v,f和B_v,r分别为节点q_v关注和转发过的节点集。

最后，根据式（3）选取C个影响力最大的节点构成Q_C。

步骤2，对于候选节点集Q_C中的单个节点q，q∈Q_C，建立由q作为单一驱动节点时的推荐话题转发网络，并基于该网络计算单个节点驱动时的推荐信息或话题传播广度的期望值；

对于步骤1求得的用户节点q∈Q_C，建立由q作为单一驱动节点时的话题转发网络，并基于该网络计算话题传播广度。在构建推荐话题转发网络时以网络拓扑结构和用户转发行为基础进行构建，并用动态贝叶斯网络推理方法进行推理，从而计算以单个节点q为信息传播的驱动节点时，网络中的所有节点参与推荐信息或话题传播的概率，在所构建的网络中当某用户节点接收（即关注）推荐信息或话题时，则该用户节点被激活并以概率p（p可能为0）转发该信息或话题，通过计算网络中被激活用户的概率和数量来计算单个节点驱动时的信息传播广度的期望值。

图2是基于转发关系构建的网络，为了使该图清晰，关注关系被省略掉。在该网络中，每个节点q_i对应一个二值随机变量X_i，其中X_i=1表示转发，X_i=0表示不转发。于是用户的转发行为可以用条件概率Pr(X_i|F(X_i))表示，其中F(X_i)为帖子被节点q_i转发过的用户节点状态。该转发网络是一个有向有环概率图（Directed Cyclic Graph，简称DCG）。若已知各节点转发信息的条件概率，则可以推理出每个节点转发信息的概率Pr(X_i)。

有向有环概率图的推理较为复杂，不能直接采用贝叶斯网络推理的算法进行计算，通常采用迭代的近似算法进行计算。本发明将该概率图转化为动态贝叶斯网络（DBN），每一次迭代计算对应到DBN的一个时间片，如图3所示。

动态贝叶斯网络包括初始网B₀和转移网B_→，变量集表示t时刻的随机变量集。此步骤计算在单一用户节点驱动下的话题传播情况，故可令初始网B₀中的其它变量均为0。在t时刻上的联合概率分布Pr(X^t)为：

$>\mathrm{Pr}\left(X^t\right)=\underset{\mathrm{pa}\left(X_i^t\right)}{\Sigma }\mathrm{Pr}\left(\mathrm{pa}\left(X_i^t\right)\right)·\underset{i=1}{\overset{N}{\Pi }}\mathrm{Pr}\left(X_i^t\right|\mathrm{pa}\left(X_i^t\right))---\left(4\right)$>

其中，表示在动态贝叶斯网络中的父节点，即图2中节点qi对其帖子进行过转发行为的用户节点。随着t的增大，将收敛于Pr(X_i)。这里选取预定义阈值δ，使得时停止计算。即为节点转发信息的条件概率Pr(X_i|pa(X_i))，在计算过程中不随t的变化而变化。用户节点q_i转发话题的概率为

$>\mathrm{Pr}\left(X_i^t\right)=\underset{X_j^t\ne X_i^t}{\Sigma }\mathrm{Pr}(X_1^t,X_2^t,...,X_n^t)---\left(5\right)$>

实际上，由于节点数目较大，直接根据式(4)和(5)计算难以进行。式(4)中，条件概率表随着数目的增多呈指数增加，致使计算复杂度很高。因此对条件概率进行如下分解：

$>\mathrm{Pr}\left(X_i^t\right|\mathrm{pa}\left(X_i^t\right))=\underset{X_j^{t-1}\in \mathrm{pa}\left(X_i^t\right)}{\Sigma }{\theta }_i^j·\mathrm{Pr}\left(X_i^t\right|X_j^{t-1})---\left(6\right)$>

其中，为需要学习的参数。简化计算，对于所有节点q_i选取其中表示的个数。不受时间t影响，即等于Pr(X_i|X_j)，其中X_j∈F(X_i)。由(6)可知，只需知道q_i转发q_j话题的概率Pr(X_i|X_j)即可。该概率可按下式进行计算：

$>\mathrm{Pr}\left(X_i\right|X_j)=\frac{M_{\mathrm{ji},r}}{M_i}---\left(7\right)$>

其中M_ji,r为节点q_i转发q_j的帖子数，M_i为节点q_i发表的帖子数，一旦节点q_i转发了目标帖，则认为其粉丝均接收到了该帖子信息。也就是说，q_i的粉丝q_k接收到该信息的概率为Pr(X_i=1)。若q_k为已经接收到推荐信息的节点集Q_F中节点的公共粉丝，则其接收到该信息的概率可近似为：

$>p_k=\underset{i:q_i\in Q_F}{\max }\left\{\mathrm{Pr}(X_i=1)\right\}---\left(8\right)$>

步骤3：计算候选节点集Q_C中个节点n个节点联合驱动下信息传播的广度的期望值，n<C，选取使得信息传播广度最大的n个用户节点，以所选择的n个用户节点作为驱动节点进行推荐信息或话题的传播，使推荐信息或话题传播广度最大化。

优选的该环节采用贪婪策略：先选择传播广度最大的节点，通过该节点与其它节点之间的连接强度，选出第二个节点，使得两者联合传播广度最大；以此类推，最终得到c个节点。由于采用贪婪策略，故得到的节点可能不是全局最优解，但计算效率高，且大多情况下完全满足需要。

具体的，由于各个驱动节点引起的信息传播范围可能有交叠，所以多个节点联合驱动时话题的传播广度通常不等于多个单节点驱动时的传播广度之和。研究表明，多个节点联合驱动话题传播的能力与各单节点的驱动能力以及它们之间的连接强度近似呈线性关系。这里，任意两个节点qu和qv之间的连接强度定义为：

$>w(q_u,q_v)=\frac{o_{\mathrm{uv}}}{k_u-1+k_v-1-o_{\mathrm{uv}}}---\left(9\right)$>

其中，k_u、k_v为q_u、q_v的出度（即粉丝数目），o_uv为q_u、q_v的公共粉丝数。进一步，扩展定义一个驱动节点集Q与单一驱动节点q_v之间的连接强度为：

$>w(Q,q_v)=\frac{1}{\left|Q\right|}\underset{q_u\in Q}{\Sigma }w(q_u,q_v)---\left(10\right)$>

其中|Q|为Q包含的节点数。

当一个节点接收到目标主题时，认为其被激活，且其接收到目标主题的概率为激活概率。为此引入激活期望（activation expectation，AE）来度量单一节点q_v的传播能力，即

$>E_a\left(q_v\right)=\frac{1}{N}\underset{k=1}{\overset{N}{\Sigma }}{p}_k^v---\left(11\right)$>

其中，为当q_v为驱动节点时，节点q_k的激活概率，由式(8)计算得到。

相似地，可以得到节点集Q的联合激活期望（joint activationexpectation，JAE）：其中为给定点集Q时，q_k的激活概率。

如图4所示，多个节点联合驱动话题传播的能力与各单节点的驱动能力以及它们之间的连接强度呈线性关系，具体可以表示为：

E_a(Q)=Aw(Q′,q_v)+BE_a(q_v)+b+ε    (12)

其中Q′为给定的驱动点集，Q={Q′,q_v}，A、B、b为待估参数，待估参数根据实际数据利用最小二乘算法进行估计，ε为随机噪声。

为了提高计算效率，本发明基于贪婪算法的策略，依次选择驱动节点，最终得到次优解：

1）初始化选择Q_C中驱动能力最大的节点q_p∈Q_C放入Q_P，同时将它从候选节点集Q_C中删除，即Q_P←Q_P∪q_p，Q_C←Q_Cq_p。

2）根据公式(10)，计算点集Q_P与Q_C中各节点的连接强度，并选取使得公式(12)最大化的节点q_p∈Q_C放入Q_P，即Q_P←Q_P∪q_p，Q_C←Q_Cq_p。

重复第2)步，直到Q_P包含n个驱动节点。

从而以所选择的n个用户节点作为驱动节点进行推荐信息或话题的传播，使得推荐信息或话题在微博网络中传播能达到近似最大的广度。