一种在线社会网络消息扩散模型

于　婧　王　晶　张校辉

(解放军信息工程大学　河南 郑州 450002)



一种在线社会网络消息扩散模型

于婧王晶张校辉

(解放军信息工程大学河南 郑州 450002)

摘要在线社会网络的消息扩散研究对社会经济、政治等方面都具有较大的现实意义。针对当前在线社会网络消息扩散模型存在的独立、封闭等问题，引入时间、主题以及合作与竞争关系、非封闭世界环境等实际因素，提出一种消息扩散概率计算方法以及消息扩散模型。将此模型应用于实际在线社会网络拓扑进行网络仿真，通过与网络真实消息扩散过程对比，结果表明该模型能够很好地拟合现实在线社会网络的消息扩散过程。

关键词在线社会网络消息扩散主题影响力合作与竞争

AN INFORMATION DIFFUSION MODEL FOR ONLINE SOCIAL NETWORKS

Yu JingWang JingZhang Xiaohui

(PLA Information Engineering University,Zhengzhou 450002,Henan,China)

AbstractResearch on information diffusion of online social networks has a greater relevance in both social economy and politics. In order to solve the problems of being independent and closed existed in current online social network information diffusion, this paper proposes an information diffusion probability calculation approach and information diffusion model by introducing the practical factors such as time, topic, cooperation and competition relationship, and non-closed world environment, etc. Applying the model to actual online social network topology to conduct network simulation, by comparing with the information diffusion process in reality, result shows that the model can commendably fit the information diffusion process in real online social networks.

KeywordsOnline social networkInformation diffusionTopic influenceCooperation and competition

0引言

当前互联网最热的应用无疑当属在线社会网络OSN[1](Online Social Network)。在线社会网络的主体是用户，用户可以创建主页及发布信息，可以与其他用户建立社会关系。可以说在线社会网络是一个用户创建的自由通信及共享信息的内容分发系统。在线社会网络的出现为互联网用户提供了一种新的交互手段，这不仅使得互联网的信息总量以一种前所未有的速度巨大的膨胀，而且极大地提高了消息传播的速度及影响覆盖范围。在线社会网络已经在世界的方方面面发挥了不可忽视的作用，如2010年的Arab Spring等具有影响世界格局的政治活动等都有在线社会网络应用的身影。

近年对在线社会网络的研究日益深入，研究内容包括网络拓扑发现、用户行为分析、用户隐私与安全、系统架构、社团发现以及消息扩散等方面。本文主要研究在线社会网络的消息扩散机制。在线社会网络中的消息扩散研究对于消息的推广、商业营销、网络舆情引导及控制等具有重要的实际意义。

本文首先简要介绍当前在线社会网络消息扩散的研究现状及目前存在的问题，针对问题提出了一种在线社会网络的消息扩散概率的计算方法以及消息扩散模型，并对此模型进行了仿真分析，最后给出了全文总结。

1研究现状及问题引出

在线社会网络是由消息传播路径组成的复杂网络，消息传播反过来又促进在线社会网络结构的变化。消息传播是用户行为活动的表现，在线社会网络中消息的扩散本质上是用户对消息的扩散。用户作为信息接受、消化和传播的主体，由于其特有的社会属性和个人特质，形成了对不同信息内容的不同关注度及信息传播行为模式[2]。通过对用户的属性信息以及信息浏览历史进行归纳、统计和抽象，建立消息扩散模型，对于研究消息的传播及在线社会网络演化机制具有重要的研究意义。

消息扩散模型研究的主要任务是充分考虑各种影响消息扩散的因素，理解、模拟并预测消息扩散过程[3]。针对现实网络提出的经典模型在在线社会网络中有一定的适用性，但在线社会网络之上进行的消息扩散与传统社会网络消息扩散不尽相同，它与在线社会网络的特点及体系架构有密不可分的关系。

消息扩散模型研究中，消息扩散概率的研究是重中之重。社会网络中的消息扩散概率是指消息沿着社会链接从一个用户扩散到另外一个用户的概率，可以直观理解为社会网络中边的权重。最初的文献[4]采用通过节点度来计算边的权重或者随机分配边的权重的方法进行消息扩散的研究，现在看来这些方法过于简单和随意，并不能代表现实中的真实信息扩散机制。另外，虽然很多研究将用户之间的消息扩散概率视为是恒定不变的，但是实际上它是与时间[5]及消息主题[6,7]密切相关的，会随着时间或者主题的变化而变化。

另外，当前对扩散进程的研究都是假定消息传播是独立的，而文献[8]的研究得出，消息的传播是存在合作与竞争的关系。竞争会导致传播的可能性降低，而合作则使得彼此的消息更容易被接纳。

当前对消息扩散的研究是在假定在线社会网络是一个封闭世界的前提下进行的，并没有考虑线下其他因素包括人际交往、电视、报纸等媒体对它的影响，文献[9]研究得出在Twitter中只有71%的消息是由于Twitter内部影响而扩散的，而剩余29%均来自于外部事件的影响。因此，研究消息扩散时需考虑用户身处的多个环境的影响。

因此，本文针对上述问题提出了考虑时间、主题、合作与竞争以及非封闭世界环境下的消息扩散概率计算方法，并提出了消息扩散模型。

2消息扩散模型

2.1基本思想

根据上述分析，我们考虑影响在线社会网络中用户对消息的传播的主要因素包括：1) 消息的发布者与用户的邻接关系；2) 消息的发布者与用户的交往程度；3) 消息所属主题对用户的吸引力；4) 消息的发布者在消息所属主题上的影响力；5) 消息发布的时间；6) 外界对用户的影响。

由此提出消息扩散模型的基本思想：用户只接受邻居节点的消息，即只考虑对邻居节点发布的消息是否进行扩散；OSN之外的媒体、社交等对用户的消息扩散起部分作用；每个消息归属于一定的主题，消息在网络内的流动受消息所属主题及节点主题分布的驱使，用户只对自己感兴趣的主题的消息进行扩散；消息的发布者在消息主题上的影响力直接影响用户对消息扩散的可能性；消息的发布者与用户之间的合作或竞争的关系对消息扩散起关键作用；消息发布的时间也就是消息的新鲜程度也影响消息扩散成功性。

具体扩散流程归结为两个步骤，如图1所示(图中标识Info的用户表示该用户发布了消息Info)：1) 用户从邻居节点接收消息，综合考虑上述因素判断是否进行消息扩散；2) 若消息成功扩散，需对邻居节点进行影响力反馈，提高发布节点的主题影响力。

图1　OSN消息扩散模型示意图

2.2模型描述

1) 定义

定义1在线社会网络可以使用一个有向或者无向图G=(V,E)表示，V是节点集合，E⊆V×V是节点间链路集合。图中节点代表用户，边代表用户之间存在关联。对∀euv=1，若节点u与v之间存在链接，否则euv=0。

定义4定义节点u的对主题T的转发门限值为pu(T)thresh，采用线性阈值模型进行信息扩散，即当计算得到的转发概率大于pu(T)thresh时，对消息进行转发。

2) 转发概率

节点u的邻居节点v转发消息Infor的概率表示为：

pv(Infor|u)=f(Infor,tcurrent,θv,ξ)

(1)

其中θv是节点v的主题分布，tcurrent是当前时间，β是指OSN之外外部环境对转发概率的影响因子。

转发消息的时间间隔对转发概率的影响服从指数分布，即从消息发布到消息转发的时间越长转发概率越低。β从两方面考虑，一是与转发时间间隔的关系符合瑞利分布，即影响力随着时间的增长会迅速出现一个高峰期，然后快速下降，二是消息本身带来的外部影响因子，记作α，0≤α≤1。

根据2.1节中的描述及上述分析，得出pv(Infor|u)的表达式：

(2)

其中，τ代表节点对消息转发时延的平均值，λ是节点转发消息的平均概率，0≤λ≤1，σ是瑞利分布参数。

另外，若节点v有多个邻居节点发布消息Infor，则节点v转发消息Infor的概率需综合考虑这多个邻居节点的影响，则转发概率：

(3)

3) 算法描述

消息扩散算法以节点主题影响力为切入点，计算节点对消息的转发概率，确定消息的传播范围。具体算法描述如下：

输入：网络G初始主题影响力集合E0；

输出：最终主题影响力集合Ef；

1 Initialize：Ef=E0；

2 foreach u∈V do

3 foreach information I in u, do

4 foreach v∈Nb(u) do

5 calculate pv(I);

6 if(pv(I)≥pv(TI)thresh)

7 issue the information I;

8 updateEu(TI);

9 end

10 end

11 end

12 end

13 return Ef;

3实验仿真

3.1实验方法

获取在线社会网络数据，选取关键事件的数据，研究该事件的实际扩散过程。以该网络拓扑为基础，初始化网络中节点初始主题分布及主题影响力分布及消息转发主题门限值，在网络中注入消息，采用本文所述消息扩散模型进行消息扩散，以发布消息的节点个数的变化趋势来描述消息在网络中的扩散过程。

以离散时间模型描述[10]，t0表示初始时刻，t1,t2,…,tn,…表示经过1,2,…,n,…个单位时间后的时刻。定义NI(tn)为tn时刻已发布该消息的节点数，扩散速率r(tn)表示(tn-1,tn]时间段内新发布消息的节点数，则：

NI(tn)=NI(tn-1)+r(tn)

(4)

归一化扩散速率r′(tn)定义为扩散速率r(tn)与网络内节点总数N的比值，即：

(5)

考虑模型中参数的选取对扩散的影响，计算扩散速率，给出扩散速率对时间的曲线，与实际在线社会网络的消息扩散图进行比较，若曲线符合，则说明模型的可用性。

3.2仿真结果及分析

通过运行网络爬虫脚本，获取新浪微博的详细用户数据，具体包括用户名、好友、粉丝、发表的微博及发表时间等信息，整理得到节点数为4039的在线社交网络数据集及网络拓扑。

从中聚焦某焦点事件的所有微博，统计得到该事件随时间的扩散情况如图2所示，横坐标表示时间，以天为单位，纵坐标表示归一化扩散速率。以此数据集为基础，选取模型参数如表1所示，得到模型仿真扩散过程如图2所示。

图2　事件扩散仿真对比图

模拟仿真过程τλσα1100.110.5250.310.53100.310.8

从图2中可以看出，模型仿真结果与实际扩散过程总的扩散趋势是基本相符的，即扩散速率会在一段时间内迅速上升，随后下降至平稳。

虽然从数据集中可以提取用户主题分布等信息，但无法得到用户间的关系信息，仿真时采用随机生成的关系向量替代实际用户关系信息，这在一定程度上影响了仿真的效果。

4结语

本文从消息传播的机理出发，引入主题影响力、节点主题分布等与主题相关的参数，节点间的合作与竞争关系，非封闭世界环境下外部环境影响因子，充分考虑了时间对消息扩散的影响，提出了一种消息扩散模型。仿真实验表明，该模型能够模拟消息的扩散过程，扩散趋势与实际扩散过程相符，对在线社会网络中消息扩散的研究具有一定的借鉴意义。

参考文献

[1] 徐恪,张赛,陈昊,等.在线社会网络的测量与分析[J].计算机学报,2014,37(1):165-188.

[2] 杨士强,孙立峰,崔鹏.Web社会网络分析[J].中国计算机学会通讯,2011,7(2):52-58.

[3] 李栋,徐志明,李生,等.在线社会网络中信息扩散[J].计算机学报,2014,37(1):189-206.

[4] Kempe D,Kleinberg J M,Tardos E.Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD 2003).Washington DC,USA,2003:137-146.

[5] Goyal A,Bonchi F,Lakshmanan L V S.Learning influence probabilities in social networks[C]//Proceedings of the 3rd ACM International Conference on Web Search and Data Mining(WSDM2010),New York,USA,2010:241-250.

[6] Tang J,Sun J M,Wang C,et al.Social influence analysis in large-scale networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD 2009).Paris,France,2009:807-816.

[7] Liu L,Tang J,Han J W,et al.Mining topic-level influence in heterogeneous networks[C]//Proceedings of the 19th ACM Conference on Information and Knowledge Management (CIKM2010).Toronto,Canada,2010:199-208.

[8] Myers S,Leskovec J.Clash of the contagions:Cooperation and competition in information diffusion[C]//Proceedings of the IEEE International Conference on Data Mining (ICDM2012).Brussels,Belgium,2012:539-548.

[9] Myers S A,Zhue C,Leskovec J.Information diffusion and external influence in networks[C]//Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (SIGKDD2012),Beijing,China,2012:33-41.

[10] 赵丽,袁睿翕,管晓宏,等.博客网络中具有突发性的话题传播模型[J].软件学报,2009,20(5):1384-1392.

中图分类号TP3

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.02.026

收稿日期：2014-07-16。国家重点基础研究发展计划项目(2012 CB315901，2012CB315905)。于婧，讲师，主研领域：计算机网络。王晶，讲师。张校辉，讲师。