1多源信息扩散问题的距离度量
文献[6]在讨论单源信息扩散问题时，将信息扩散看成空间-时间两个方向同时进行的扩散过程，并用好友用户节点之间最小的好友关系跳数（即最短路径）来度量两个用户之间的距离。类似的，本文用好友关系的度量来表示两个节点之间的距离。但不同的是，多源信息扩散问题中的信息源由多个源点构成。可以定义某个用户节点到信息源的距离为该用户节点到信息源的所有最短路径中最短的那条路径长度。为便于说明，可令U表示在线社会网络中所有的用户节点集合，S{s|i1,2,..n.},i表示新闻消息m的信息源集合（即多源），对网络中任意一个用户节点u，令d(s,u)i表示用户u到源点is的距离。则min{()|1,2,...,}min,ddsuini表示用户u到多源的距离。该距离定义是基于现实情形中一个简单而且直观的观察：当某条信息在社会网络中传播的时候，如果存在多个用户节点同时发布了这条信息，则该信息同时具有多条可能路径到达网络中的另一个用户且影响该用户，显然最可能影响该用户的传播路径应该是多条可达路径中距离最短的那一条，因为最短的路径具有最短的好友关系跳数。在线社会网络中，用户到信息源的距离实际表明了用户与信息源之间的“亲密”程度，越短的距离表明具有越近的好友关系，两者之间彼此影响就越大。基于上述距离定义，根据用户到多源之间的距离不同，可将社会网络中所有的用户分成不同的用户组。则用户集合U可以表示为U{U|i1,2,...,m}i。其中，m表示在线社会网络中用户节点到信息源距离的最大值，分组iU表示距离为i的用户集合，iU包含了到信息源距离为i的所有用户节点。
2多源信息实例的选取
为了研究多源信息扩散的本质特征，需要对大量真实数据进行全面实验分析。本文实验用到的数据集来源于美国知名新闻分享网站Digg。Digg中的用户通过彼此的“关注”而形成好友关系从而构成庞大的在线社会网络。新闻提交者负责发布他们在博客、新闻网站或者其它地方找到的新闻报道。网站允许用户能对发布的新闻消息进行投票（即digg操作）和评论。发布的新闻报道都会列入Digg的内容序列中，Digg用户则在这些内容序列中查找自己感兴趣的内容并将其“掘”（digg）出来，让Digg知道他们认为这篇报道很出色。如果一篇文章或一则新闻信息得到足够的“digg”次数之后，它会被提升到主页中。Digg中第一个将新闻发布（submit）到网络中的用户被称作该新闻的“发起者”（submitter）或“信息源”（source），之后信息会沿着好友路径不断在整个网络中扩散。本文的数据集包含了Digg网站2009年6月份最受欢迎的3553条新闻故事。这些新闻故事总共收到了来自于139,409条Digg用户的约300万次投票。数据集中的数据信息包括对每条新闻进行了投票所有投票者的ID帐号，以及每个用户对该新闻投票的时间戳，其时间单位的粒度为“秒”。这种过于精确的时间粒度使得找出多源信息的实例几乎不可能。分别对该Digg数据集中全部3553条新闻的发布时间进行了实验分析发现：每一条新闻信息都不存在具有两个及两个以上的最先且同时进行发布的用户。也就是说，无法从原始数据集中得到多源信息传播的实例。考虑到实际情况中信息发布时某些客观或主观原因可能造成的延迟，我们可以近似认为在某个允许的时间范围内发布信息的用户均可以看作是该信息的同时发布者。比如，当Digg网络中一条信息被用户A发布之后的某个时间t时（如t<=300秒），用户B也发布了该信息，那么用户A和B可被看作是“同时”发布了该信息，即A、B同为该信息的信息源。但是并不能简单认为只要某条信息存在这样的“同时”发布者就是一个多源信息的实例。在多源信息传播情形中，应该存在多个用户独立而不受彼此影响（这些用户都认为自己是信息的第一个发布者）的同时发布某条信息。考虑如下情形：用户A在时刻T发布了新闻，B在T+50秒时也发布了该新闻，若A、B之间存在好友关系，则很有可能B是由于受到了A的影响（若没有A，B不会产生发布动作）。此时B只是A的被影响用户，而不是该新闻的源。基于以上分析，应该选取“同时”发布者中两两之间都不存在好友关系的用户集合看作信息源。对应的，该信息则可作为多源信息传播的实例。Digg数据集中多源选取过程如图1所示。3、4号用户作为该信息的多源，该信息即为3源信息实例。根据以上分析，本文设计了一个多源信息的多源节点近似选取算法，用该算选可以从Digg数据集中找到多源信息的实例。对于Digg数据集中全部新闻，算法1能找到两个及以上信息源点的信息都是符合要求的多源信息实例。具体的，本文设定Digg数据集中信息初次发布后的5分钟内（即300秒）对其投票的所有非好友关系的用户均为该信息的源点。在3553条新闻中，算法共找到了1433个多源新闻信息实例。下面将通过实验研究这些多源信息在Digg网络中的扩散规律和空间-时间特征。
3多源信息扩散的预测
本节将利用基于文献[6]中的线性扩散模型对Digg数据集中的多源信息扩散进行预测。首先计算Digg数据集中实际扩散结果，然后用线性扩散模型得到预测结果，最后比较两个结果得到模型预测的准确率。多源信息进行有效预测，我们对全部1433个多源新闻实例都进行了预测。表3给出了所有的预测结果：第1列表示多源新闻的分组，第2列、第3列分别表示每个分组中最受关注的新闻事以及对其扩散结果的预测准确率，第4列、第5列表示每个信息分组中包含的新闻条数以及模型对该组中所有信息的平均预测准确率。由表3可见，对于每个信息分组中最受关注的新闻特例，线性扩散模型都能达到90%以上的预测准确率。不仅如此，该模型对于其它所有的新闻实例都能达到较高的预测准确率。如表所示，每个信息分组的平均预测准确率都能达到75%左右。而对于全部的1433个多源新闻，模线性扩散的平均预测准确率为76.25%。这个结果说明，线性扩散模型对于多源信息扩散能够进行有效的预测。
4结束语
随着在线社会网络用户的快速增加，在线社会网络已经成为一种重要的信息传播渠道。在线社会网络对于消息发布、产品推销、甚至到政治选举等社会生活中的多个方面都具有重要的意义和作用。因此，深入研究在线社会网络中信息的传播模式和规律，特别是对在线社会网络中信息扩散的准确预测非常重要。在大量的研究中，只对单源点发出的信息扩散问题进行了的探讨。但在实际情况中，一条信息往往是从多个消息源同时发出的多源信息扩散。在多源信息扩散情形中，消息常常会被多个而不是单个用户同时发布到网络上，然后在网络中迅速传播。本文详细研究了多源点信息扩散问题，主要工作包括：1）提出了多源信息扩散问题原型，并给出了多源信息扩散情形用户间距离度量的定义；2）设计了一种在数据集中选取多源信息实例的算法，该算法不仅可以用在Digg数据集中，扩展后也可适用于用其它数据集；3）利用一种线性扩散预测模型对多源信息实例进行了预测。较高的预测准确率一方面说明了本文的距离定义和多源选取算法的可行性，另一方面则证明了线性扩散模型对于多源信息扩散的预测能力。下一步的工作将尝试对不同的在线社会网网络的信息扩散特征进行研究，并建立新的信息扩散预测模型进行有效预烟草经济论文测。
作者：单位：彭川 李元香 莫海芳 中南民族大学计算机科学学院 武汉大学计算机科学学院
相关专题：内蒙古医学院 南方医科大学学报投稿
