一种博客信息传播中识别关键博客集的方法

摘要

本发明公开了一种可以快速、准确在博客信息传播中识别关键博客集的方法，其步骤是：1)以博客为单位收集和确定博客之间的关注关系和链接关系；2)以博客为节点构建博客网络图，图的边为博客间的关联；3)根据信息传播模型确定博客间关联(有向边)的权重；4)基于博客网络图计算每个博客对其他博客传播影响力的期望值；5)识别博客网络图中信息传播影响力最大的关键节点集合。本发明结合信息传播模型，应用博客之间的关联关系，通过计算信息传播期望，快速识别博客信息传播中关键的博客集合，以方便博客信息的监督。

说明书

技术领域

本发明涉及博客信息传播中关键博客节点集合的快速识别问题，特别针对互联网时 代博客网站(尤其是微博)越来越普及，已经成为新闻和评论等信息传播的主流平台之 一，需要有效监督以帮助互联网上信息的鉴别和控制。

背景技术

博客(Weblog或blog)是以互联网为载体、同时由个人管理的信息共享平台。一 个博客是一组包含文字、链接、图像等的网页集合，由博主(即注册在博客网站的用户) 个人管理，不定期粘贴新文章(Posts)供人们浏览或转载。随着大量博客网站(如国外 著名的Twitter，国内的新浪微博等)的涌现，博客已成为人们日常获取信息的主流平台 之一。微博(Micro-Blog)的出现更降低了博客对用户技术和知识背景的要求，使得越 来越多的人们主动加入到博客信息平台，共享新闻和自己的见解。互联网上各种信息真 假莫辩，这要求对博客信息传播做适当的监督和引导；由于博客数量庞大且更新迅速， 不可能对每一个博客随时进行跟踪，这就增加了监督的难度。

解决信息传播领域影响最大化问题，需要给定信息传播的网络图，设定信息传播模 型，以寻找影响力最大的关键节点集合：集合中的节点数量给定，且节点上的信息可以 传播到图中最多的节点上。目前解决影响最大化问题的主流技术有两类：其一是启发式 方法；其二是随机模拟方法。启发式方法根据节点的拓扑特征，包括度数和到其他节点 的平均最短距离等，选择度数大或者平均最短距离小的节点作为影响力大的节点。启发 式方法的优点是执行性能较高；缺点是所识别的节点准确率低，即实际不能达到最大的 影响力，而且所适用的传播模型过于简单，与实际网络中的信息传播方式不相符合。随 机模拟方法基于设定的信息传播模型，运用蒙特卡洛随机模拟，在模拟足够多次(如 10000次以上)的基础上确定节点或节点集合所能够影响的范围，再基于贪婪方法选择 边际增益最高(即额外影响的节点数量最多)的节点作为关键节点。模拟方法的优点是 可以适用于不同的信息传播模型，且识别的关键节点集准确率较高；缺点是执行性能过 低，适用于相对静态的信息传播网络。博客信息传播网络信息量大，更新迅速，信息传 播形式多样，现有方法尚不能满足博客信息传播的关键节点集识别要求。

发明内容

本发明所要解决的技术问题是提供一种可以快速识别博客信息传播中关键博客节 点集合的方法，该方法能够以较高的执行性能更准确的识别关键节点集，适于博客信息 平台数据量大更新快的特点，计算简单，具有扩展性和适应性，可以有效辅助博客信息 平台的监督。

为实现上述目的，本发明采用如下的步骤：

1)以博客为单位收集和确定博主间的关联；

2)以博客为节点构建博客网络图，图的边为博客间的关联，对应博客间的链接关 系或者博主之间的关注关系；

3)根据信息传播模型确定博客网络图中博客间的关联的权重；

4)基于博客网络图和关联权重的设置计算每个博客对其他博客信息传播影响力的 期望值；

5)根据博客间信息传播影响力的期望值，识别博客网络图中信息传播影响力最大 的关键节点集合，即关键博客集。

上述步骤1)中的关联包括关注关系以及博客中文章间的链接关系；而收集和确定博 客间的关联的过程为：首先从博客网站获取博客数据，为每一个博客(博主)赋予唯一 标识，如B_i。然后获取博主的好友列表或关注列表；好友列表确定博主间双向的好友关 系；关注列表确定博主间单向的关注关系；好友关系可以表示为两个互为反向的关注关 系；如果博主B_i关注博主B_j，则两者之间的关注关系标记为<B_j，B_i，f>。接下来获取 博客B_i在t日内粘贴的文章，参数t可设为20。对博客B_i中的每一篇文章P_ix，如果P_ix链 接(引用)了博客B_j中的文章B_jy，则认为博客B_i与博客B_j之间存在链接关系，标记为 <B_j，B_i，Δt>，其中Δt表示文章B_ix粘贴日期与当前日期的差值。如果博客B_i多次引用 博客B_j中文章，则Δt为其中的最小值。

上述步骤2)中构建博客网络图的流程是：首先定义博客网络图为有向图， 其中为博客集合，每个博客作为图中节点；E为博客之间关联(有 向边)的集合。然后对博客群中任意两个博客B_i和B_j，如果B_i和B_j间存在关注关系 <B_j，B_i，f>，或者存在链接关系<B_j，B_i，Δt>，则在B_i和B_j之间定义有向边 e_ji：B_j→B_i；同理如果是<B_i，B_j，f>或者<B_i，B_j，Δt>，则定义有向边e_ij：B_i→B_j。

上述步骤3)中确定博客网络图中边的权重。对边集E中的每一条有向边e_ij，分析e_ij对应的关联关系。如果是链接关系：<B_i，B_j，Δt>，则采用独立级联模型为边赋权重(其 中链接关系权重的初始值λ可设为0.1，指数参数α可设为0.5)：

w_ij＝λe^-α·Δt

如果是关注关系：<B_i，B_j，f>，则采用加权级联模型为边赋权重(其中集合F_j是 博主B_j的关注集，|F_j|指集合的规模；关注关系权重的最大值δ可设为0.6)：

$w_{\mathrm{ij}}=\frac{\delta }{\left|F_j\right|}$

如果边e_ij即对应链接关系，又对应关注关系，则选择两者所确定权重的最大值作为 该边上的权重：

$w_{\mathrm{ij}}=\max ({\mathrm{\lambda e}}^{-\alpha ·\mathrm{\Delta t}},\frac{\delta }{\left|F_j\right|})$

上述步骤4)中计算每个博客对其他博客信息传播影响力的期望值。首先对于博客节 点B_i和B_j，标记p(i，j)为节点B_i对B_j的信息影响力期望值，等同于信息传播影响的概率。 然后p(i，i)＝1，表示节点肯定影响自己。若j≠i，则寻找网络图中节点B_i到节点B_j的 最短路径，标记为Path_I(B_i，B_j)；p(i，j)定义为最短路径Path_I(B_i，B_j)的权值(路径中所 包含边权重的乘积)：

$p(i,j)=\underset{e_{\mathrm{uv}}\in {\mathrm{Path}}_I(B_i,B_j)}{\Pi }{w}_{\mathrm{uv}}$

如果节点B_i到节点B_j不可达，则p(i，j)＝0。节点间最短路径定义为节点间所有简 单路径(路径上节点不重复出现)中权值最大的路径。可采用广度优先搜索算法遍历网 络图中节点B_i到所有其他可达博客节点的最短路径。

上述步骤5)中识别博客网络图中信息传播影响力最大的关键节点集合。首先确定集 合S的规模，如20(即最关键的20个节点)；定义σ(S)为网络图中受集合S中博客节点 影响的节点数量的期望值。然后选择网络图中影响范围最大的单个节点构成初始集合 S＝{B_max}。对应的σ({B_max})计算如下：

$\sigma \left(\right\{B_{\max }\left\}\right)=\underset{j=1}{\overset{n}{\Sigma }}p(\max ,j)$

其中max为节点下标。确定p(S，j)的初始值，即p({B_max}，j)＝p(max，j)。接下来 迭代，每次选择边际增益最大的节点B_u()加入集合S。节点B_u的边际增益按如 下公式计算：

${\delta }_S\left(B_u\right)=\underset{j=1}{\overset{n}{\Sigma }}(1-p(S,j))·p(u,j)$

集合S中增加节点B_u后，按如下公式调整集合S对节点B_j的影响力期望值：

重复上述两个步骤直至给定数量的节点被选入集合S。集合S即为博客网络图中信 息传播影响力最大的关键节点集合。

本发明通过分析博客间关联，基于信息传播模型快速识别博客网络中信息传播影响 力最大的博客节点集合，能够帮助确定信息传播的源头和集散地，协助博客信息传播链 追踪等。其中根据关联关系，包括博客间链接关系和博主之间的关注关系，构建博客网 络图；基于信息传播模型确定博客间关联(即博客网络图的边)的信息传播权重；据以 计算每一个博客对其他博客信息影响力的期望值；进而根据博客网络的拓扑图快速识别 其中影响力最大的博客节点集合。

本发明方法基于关键节点集合扩充中的边际增益递减特点，应用贪婪算法每次选择 增益最大的博客节点。所识别的关键节点集合具有很高的准确性。另外本发明方法计算 简单有效，能够快速识别博客信息传播网络中的关键节点集合，具有灵活性、适用性和 扩展性。同已有方法相比较，本发明方法更加适用于数据量大、且更新频繁快速的博客 信息传播平台的影响最大化分析。

附图说明

图1是博客信息传播关键博客节点集识别方法的总体框架；

图2是获取博客数据并确定博客间关联关系的处理流程；

图3是根据博客间关联构建博客网络图的处理流程；

图4是一个博客群的示例及其对应的博客网络图；

图5是为博客网络图中边赋予权重的处理流程；

图6是博客群示例对应的加权博客网络图；

图7是博客间信息传播影响力之期望值计算的处理流程；

图8是加权博客网络图中识别关键节点集的处理流程。

具体实施方式

图1所示为博客信息传播关键博客节点集识别方法的总体技术框架。方法的输入是 博客网站上的博客网页数据，包括粘贴的文章、文章之间的链接关系、以及博主间的好 友关系或关注关系等。方法的输出是给定数量(如20个)的关键博客节点集合，其联 合影响力在已获取的博客群中最大。技术框架分为5个模块：确定博客和博主之间的链 接关系或关注关系；以博客为节点、博客间关联为边构建博客网络图；设定信息传播模 型为网络图中的边(即博客间关联)赋予权重；计算每个博客对其他博客信息影响力的 期望值；最后识别博客网络图中信息传播影响力最大的关键节点集合。

本发明方法的第一个模块是确定博客和博主之间的链接关系或关注关系。如图2所 示。首先从博客网站(如网易微博、新浪微博、博客中国等)获取博客数据，包括近期 粘贴的文章、文章间的链接关系、以及博主的关注列表或好友列表等。为每一个博客赋 予唯一标识B_i，因为博主与博客一一对应，所以B_i也可以用于标识博主。令所获取的博 客群为：然后针对每一个博客B_i，获取B_i的好友列表或关注列表 (一些博客网站为好友列表，而微博网站通常为关注列表)。其中好友关系一般是双向 的，如果博主B_i和博主B_j是好友，则博主B_j和博主B_i也是好友；而关注关系一般是单向 的，博主B_i关注博主B_j并不意味着博主B_j也会关注博主B_i(此时网站一般会注明博主B_i是博主B_j的“粉丝”)。为取得一致，好友关系被视为两个互为反向的关注关系；而博主B_i关注B_j标记为<B_j，B_i，f>，其中f表示“被关注”。

接下来分析博客B_i中近期粘贴的文章。设定参数t，表示获取博客中近t日粘贴的文 章。参数t的设置可以参考博客群信息的平均更新速度，信息更新越快则t值越小，反之 则越大；一个可选的参考值是20。对每一篇文章P_ix，分析其中的链接关系。如果P_ix链 接(引用)了博客B_j中的文章P_jy，则认为博客B_i与博客B_j之间存在链接关系，标记为 <B_j，B_i，Δt>，其中Δt表示文章P_ix粘贴日期与当前日期的差值。例如P_ix为2天前粘贴， 则Δt＝2。如果博客B_i多次引用了博客B_j中的文章，则链接关系中的Δt为博客B_i中最近 一次文章链接的日期与当前日期的时间差。

本方法的第二个模块是以博客为节点、博客间关联为边构建博客网络图。如图3所 示。定义博客网络图为有向图，其中为博客节点集合，E为博客之间关联(有 向边)的集合。对博客群中任意两个博客B_i和B_j，如果B_i和B_j间存在关注关系 <B_j，B_i，f>，或者存在链接关系<B_j，B_i，Δt>，则在B_i和B_j之间定义有向边 e_ji：B_j→B_i。从信息传播角度，存在边e_ji代表博客B_j对博客B_i有信息影响。如果是关 注关系，因为B_i关注B_j，所以B_j对B_i存在一定的影响力；如果是链接关系，因为B_i中文 章链接B_j中文章，说明B_j的信息传播到B_i，B_j对B_i亦存在影响力。同理，如果博客B_i和 B_j间还存在关联<B_i，B_j，f>或者<B_i，B_j，Δt>，则定义有向边e_ij：B_i→B_j。

图4所示为一个博客群示例及其对应的博客网络图。如图4(a)，该博客群由6个博 客组成每一个博客有自己的关注列表和近期粘贴的文章列表。例 如博客B₁包含3篇粘贴的文章“P₁₁，P₁₂，P₁₃”，关注列表中包含博客(博主)B₂和B₄。各 文章之间存在链接关系，如文章P₁₁被博客B₂中的文章P₂₂引用；文章P₁₂被博客B₅中的文 章P₅₁引用；而文章P₁₃引用了博客B₄中的文章P₄₁。图4(b)为该博客群对应的博客网络图， 考虑节点B₁，根据其关注关系构成2条有向边e₂₁和e₄₁，根据文章间链接关系可构成3 条有向边：e₁₂，e₁₅和e₄₁；于是边e₄₁同时对应关注关系和链接关系，其信息传播权重由 这两项关系综合决定。由图4不难发现，博客B₆中的文章最多，所引用的文章数量也最 大；似乎信息最全面且值得监督。但是从信息传播的角度来看，博客B₆的影响力其实最 小，没有其他博客关注B₆或引用B₆中的文章。考虑图4(a)中的信息传播链 P₁₁→P₂₂→P₃₂→P₆₁，如果到B₆中才发现，该信息传播已经影响到了博客B₂，B₃和B₆。

本方法的第三个模块是设定信息传播模型，为网络图中的有向边赋予权重。信息传 播模型有阈值模型(threshold model)和级联模型(cascade model)两类。根据博客信 息传播的特点，本发明方法采用级联模型。级联模型又包含独立级联模型(independent  cascade)和加权级联模型(weighted cascade)，本发明方法综合应用这两个模型。在博 客网络信息传播过程中，博客节点只有两个状态：活跃状态和非活跃状态。其中活跃状 态指博客节点受到信息传播影响，表现为引用了某条信息而加入到信息传播链中；非活 跃状态指尚未受到信息传播影响。博客节点可以从非活跃状态转入活跃状态，并进一步 影响其他节点；一旦进入活跃状态，节点就不会再转回非活跃状态。

如图5所示，对边集E中的每一条有向边e_ij，分析e_ij对应的关联关系。如果是链接 关系：<B_i，B_j，Δt>，则采用独立级联模型为边赋权重，如公式(1)所示。

w_ij＝λe^-α·Δt                (1)

其中链接关系权重的初始值λ可设为0.1，指数参数α可设为0.5。随着时间差Δt的 增加，链接关系权重按指数衰减。参数λ和α的设置可基于博客群中信息更新的速度。信 息更新速度越快，则λ和α的值越大；反之更新速度越慢，则λ和α值越小。

如果边e_ij对应的是关注关系：<B_i，B_j，f>，则采用加权级联模型为边赋权重，如 公式(2)所示。

$w_{\mathrm{ij}}=\frac{\delta }{\left|F_j\right|}---\left(2\right)$

其中集合F_j是博主B_j的关注集，|F_j|指集合的规模；关注关系权重的最大值δ可设为 0.6。表示博主有60％的几率被关注的博客集影响；随着博主关注集规模的不断增加， 博主被关注集中某个博主影响的几率将不断降低。

如果边e_ij即对应链接关系，又对应关注关系，则选择两者所确定权重的最大值作为 该边上的权重。如公式(3)所示。

$w_{\mathrm{ij}}=\max ({\mathrm{\lambda e}}^{-\alpha ·\mathrm{\Delta t}},\frac{\delta }{\left|F_j\right|})---\left(3\right)$

图6所示为博客群示例所对应的加权博客网络图。其中假设所有链接关系距离当前 日期都是1天(即Δt＝1)，于是链接关系的权重皆为：0.1×e^-0.5＝0.06。图6中的边 e₄₁同时对应关注关系<e₄，e₁，f>和链接关系<e₄，e₁，1>。其中关注关系对应的权重为 0.6/2＝0.3，而链接关系对应的权重为0.06；取两者的最大值，求得边e₄₁上的权重为 w₄₁＝0.3。注意本例中关注关系的权重较大，这是由于示例规模小，每一位博主最多只 有2个关注。在实际的博客群中，一位博主往往有数十乃至数百个关注，按公式(2)计算 的关注关系权重基本同链接关系的权重相当。

本方法的第四个模块是在加权博客网络图的基础上，计算每个博客对其他博客信息 影响力的期望值。对于博客节点B_i和B_j，标记p(i，j)为节点B_i对B_j的信息影响力期望值。 由于对节点B_j的信息影响只有两种结果：影响(值为1)和不影响(值为0)，因此信息 影响力的期望值等同于信息传播影响的概率。首先p(i，i)＝1，表示节点肯定影响自己。 若j≠i，为计算p(i，j)，需要寻找网络图中节点B_i到节点B_j的最短路径，标记为 Path_I(B_i，B_j)；如果节点B_i到节点B_j不可达，则p(i，j)＝0。

网络图中一条路径的权值定义为路径上所有边的权重乘积。节点间最短路径定义为 节点间所有简单路径(路径上节点不重复出现)中权值最大的路径。期望值p(i，j)定义 为最短路径Path_I(B_i，B_j)的权值，如公式(4)所示。

$p(i,j)=\underset{e_{\mathrm{uv}}\in {\mathrm{Path}}_I(B_i,B_j)}{\Pi }{w}_{\mathrm{uv}}---\left(4\right)$

其中e_uv为最短路径Path_I(B_i，B_j)上的边，w_uv为边e_uv的权重。例如图6所示的加权 网络中，从节点B₂到节点B₆的一条路径<e₂₃，e₃₆>其权值为：0.06×0.06＝3.6×10^-3。 图中节点B₂到节点B₆共有6条简单路径，其中路径<e₂₁，e₁₆>为最短路径Path_I(B₂，B₆)， 路径权值为0.09。于是节点B₂对节点B₆的信息影响力期望值为p(2，6)＝0.09。

如图7所示，从博客B_i开始，采用广度优先搜索算法遍历网络图中节点B_i到所有其 他可达博客节点的最短路径。该算法运用了一个基本原理：如果节点B_i到节点B_j的最短 路径经过某个中间节点B_k，则最短路径Path_I(B_i，B_j)必然包含最短路径Path_I(B_i，B_k)。 根据这一原理，只需遍历网络图中的所有边，就可以计算节点B_i到所有其他可达节点的 最短路径，因此算法的执行性能较高。本模块执行完毕后的输出结果是信息影响力期望 值矩阵P_n×n，其中n为博客集合的规模，行表示节点施加影响力，列表示节点被其他 节点影响，期望值p(i，j)为矩阵中元素。

本方法的第五个模块是基于期望值矩阵，识别博客网络图中信息传播影响力最大的 关键节点集合。令为博客节点集合，定义σ(S)为网络图中受S中博客节点影响的节 点数量的期望值。不难得出，如果集合S仅包含1个节点，即S＝{B_i}，则σ(S)可以按 照公式(5)直接计算。

$\sigma \left(\right\{B_i\left\}\right)=\underset{j=1}{\overset{n}{\Sigma }}p(i,j)---\left(5\right)$

如果集合S中有2个以上的节点，则由于节点影响范围的重叠，不能直接累加S中 各节点影响力期望值。由此定义集合S对网络图中节点，如B_j的信息影响力期望值，标 记为p(S，j)；如果节点B_j∈S，则p(S，j)＝1。基于该定义，σ(S)可以按照公式(6)计算。

$\sigma \left(S\right)=\underset{j=1}{\overset{n}{\Sigma }}p(S,j)---\left(6\right)$

如果集合S中只有一个节点，如B_i，则p({B_i}，j)＝p(i，j)。如果多于一个节点，可 按照公式(7)逐步更新集合S对任一节点B_j的影响力期望值。

其中。由此在已选定节点集合S的基础上，可计算添加节点B_u后的边际增益 δ_S(B_u)＝σ(S∪{B_u})-σ(S)，即增加节点B_u后，网络图中受S影响的节点数量增加的 期望值。边际增益δ_S(B_u)的计算如公式(8)所示。

${\delta }_S\left(B_u\right)=\underset{j=1}{\overset{n}{\Sigma }}(1-p(S,j))·p(u,j)---\left(8\right)$

其中要求。应用公式(5)、(7)和(8)，可基于贪婪算法识别网络图中联合信息 影响力最大的关键节点集合。如图8所示。首先确定集合S的规模，如20(即最关键的 20个节点)。然后应用公式(5)选择网络图中影响范围最大的单个节点构成初始集合 S＝{B_max}；同时确定p(S，j)的初始值，即p({B_max}，j)＝p(max，j)(其中max为初始 选定节点的下标)。

接下来迭代，第一步应用公式(8)每次选择边际增益最大的节点B_u加入集合S。第二 步按照公式(7)更新p(S，j)，注意如果B_j∈S或者j＝u，则p(S，j)＝1。重复上述两个步 骤直至给定数量的节点被选入集合S。最后输出的集合S即为博客网络图中信息传播影 响力最大的关键节点集合。

理论和实践证明，由于关键博客集合的选择具有边际增益递减的特点，即当选定的 集合S规模不断增加时，新增节点B_u()后所带来的边际增益δ_S(B_u)逐渐减少。

基于这一特性，本发明方法采用的贪婪算法具有很高的准确性。另外本发明方法计算简 单有效，能够快速识别博客信息传播网络中的关键博客集合，具有灵活性、适用性和扩 展性。同已有方法相比较，本发明方法更加适用于数据量大、且更新频繁快速的博客信 息传播平台的影响最大化分析。