NT-EP：一种无拓扑结构的社交消息传播范围预测方法

刘子图 全紫薇 毛如柏 刘 勇 朱敬华

(黑龙江大学计算机科学技术学院 哈尔滨 150080)

近年来随着社交网络的快速发展，越来越多的用户使用新浪微博、Twitter、Facebook等社交网站分享自己的生活.据统计Facebook截至2018年12月31日每月的活跃用户超过23亿[1].由此可见社交网已经成为许多人生活的一部分.与此同时各大社交平台也在促进着各种消息的快速传播.例如在新浪微博上平均每天有几亿条微博产生，在每天产生的微博中会包含很多重要信息.用户更新一条微博可能包含着用户对某消息的态度和观点[2]，也可能是分享身边的新鲜事[3].预测消息的传播范围在病毒营销、舆情监控、商品推荐等诸多领域都有广泛的应用，因此受到了数据挖掘领域的广泛关注.

目前对消息传播范围进行预测所使用的方法主要有2种：1)根据消息特征或者消息的特定类型进行传播范围预测.例如：可以根据发布的Twitter是否带有标志性的图片从而预测它在Facebook上的传播范围[4]；也可以通过分析发布的Twitter是否包含对消息传播有利的内容来预测它的传播范围[5].然而使用消息特征预测消息传播范围显然不能推广到不同的平台.2)使用社交网络中用户的拓扑结构[5-7]或消息的转发结构[8]来预测消息传播范围.然而在很多实际应用中，我们很难获得消息的传播结构以及用户的拓扑结构，通常只能获得消息的传播序列.例如在豆瓣网中，对于电影的影评只显示用户在什么时间评价了电影，而没有表明用户因为受到哪些用户影响才评价该电影.因此，只利用消息的传播序列而不考虑用户的拓扑结构来预测消息的传播范围具有更广泛的应用场景.

本文研究了无拓扑结构条件下的消息传播范围预测问题，提出了一种无拓扑结构的消息传播范围预测方法NT-EP.该方法由4部分构成：1)利用消息传播随时间衰减的特性为每个消息构造一个加权的传播图，在传播图上使用随机游走策略获取多条传播路径，再使用Word2vec方法计算每个用户的特征向量；2)把目标消息的传播路径替换成用户的特征向量序列输入到双向门控制循环神经网络(bidirectional gated recurrent unite, Bi-GRU)，结合注意力机制计算出目标消息的传播特征向量；3)考虑到不同消息传播可能存在的相互影响，利用目标消息发生前的其他消息，使用梯度下降方法计算出其他消息的影响向量；4)将目标消息的传播特征向量和其他消息的影响向量结合在一起，使用多层感知机(multilayer perceptron, MLP)拟合出目标消息的传播范围.与其他方法相比，NT-EP方法具有2个明显的创新：1)首次考虑了消息之间的相互影响；2)利用消息传播随时间衰减特性为每条消息构造加权传播图，抽取传播路径.

NT-EP方法充分考虑了消息之间的相互影响.这是因为在消息的传播过程中，消息与消息之间必然会产生影响.例如在公布个人所得税起征点改革消息之后的一段时间内，用户会增加对包含具体税率改革内容的消息的关注.因此个人所得税起征点改革消息对有相关内容的消息传播产生了影响.消息传播中的相互影响来自于2方面：1)来源于消息本身的内容，也就是消息本身是否为热点消息，是否会被普遍关注；2)来源于已经参与消息传播的用户对于其他消息传播的影响.在一段时间内，用户使用社交网络的时间上限是固定的.用户浏览某些消息的时间更多意味着用户浏览其他消息的时间会减少.因此本文方法NT-EP考虑了目标消息发生前后其他消息对目标消息可能存在的各种影响，构造了其他消息的影响向量，结合目标消息的传播特征向量来预测目标消息的传播范围.本文实验部分比较了利用消息影响与不利用消息影响NT-EP方法的2种变体，证明了消息影响对范围预测的重要性.

NT-EP方法根据传播序列构造加权传播图，来模拟接近真实传播轨迹的传播路径.在无拓扑结构的条件下，我们只有用户的动作序列.但是用户在接受消息过程中必然会受到之前接受相同消息用户的影响，而且影响强度依赖于接受消息的时间差.假设在消息a传播过程中用户V1接受了消息a，在用户V1之前用户V2和用户V3也接受消息a，并且用户V2接受的时间早于用户V3,那么直觉上用户V3对用户V1接受消息影响更大.根据消息传播随消息衰减的特性，我们构造有向边V2→V1和V3→V1，V3→V1边上的权值大于V2→V1，边上的权值代表了影响强度，权值依赖于2个用户接受消息的时间差.NT-EP方法按照这种方式为每个消息构造一个随时间衰减的传播图，然后使用随机游走策略抽取多条传播路径，这些传播路径更接近于真实的传播轨迹.本文实验部分构造了NT-EP方法的2种变体，一种利用时间衰减构造传播图，另一种不利用时间衰减构造传播图，比较了这2种变体的性能，再次证明了消息传播符合时间衰减特性.本文的贡献有4个方面：

1) 提出了一种新的无拓扑结构条件下的消息传播范围预测方法NT-EP.

2) NT-EP利用了消息之间的相互影响，提高了消息传播范围预测的准确性.

3) NT-EP利用了消息传播随时间衰减的特性为消息构造加权传播图，使得抽取的随机游走路径更接近真实的传播轨迹，提高了消息传播范围预测的准确性.

4) 实验结果表明，NT-EP能对无拓扑结构条件下的消息传播范围进行准确预测，并且预测效果明显优于现有的方法.

本文源码和数据可以从https://github.com/Vimotus/NT-EP下载.

1 相关工作

在社交网中消息的传播范围包括微博或Twitter在一定时间内的转发数[4-5,9-11]、照片的被浏览数[2]、视频被点赞的次数[12-14]、学术论文在一定时间内被引用的次数[15]等多种情况.相关工作大致可以分为3类：1)利用消息本身的特征进行预测；2)利用消息的传播序列和用户的社交关系进行预测；3)只利用消息的传播序列进行预测.

消息特征或者消息的特定类型可以帮助预测消息的传播范围.例如文献[4]根据发布的Twitter是否带有标志性的图片来预测它在Facebook上的转发次数；文献[12]分析视频在规定的时间段内观看人数的增长量来预测消息被观看的次数.然而消息的传播范围除了消息本身的特征，更多依赖发布消息或者转发消息用户的影响力，因此此类方法预测效果一般，而且不易推广到其他平台.

目前的绝大多数研究都是利用消息的传播序列和用户的社交关系进行预测.该类方法又可分为2种：1)将消息传播预测视为分类问题，通过预测传播范围是否会超过某个阈值来预测某个消息是否会变成流行消息[7,12,14];2)将消息传播范围预测看作回归问题，预测消息的最终传播范围或者截止到某一时刻的传播范围.此类研究通常使用确定的时间属性[12]、早期消息传播的拓扑结构[6,15-16]以及用户的拓扑结构[17]，来进行传播范围预测.文献[18]学习多数消息传播过程中的普遍拓扑结构预测消息传播范围.此类方法需要消息的传播结构或者用户的拓扑结构，但实际应用中这些信息不易获得.

目前在无拓扑结构(用户社交关系)条件下，对消息传播范围预测的研究相对较少.2010年Gomez-Rodriguez等人[19]利用用户被影响的时间特征推断消息传播的路径，然后累加路径上的用户数计算传播范围.2012年Simma等人[20]提出了基于连续时间和霍克斯进程的随机过程范围预测模型.2014年Bourigault等人[21]提出了基于学习映射观察动态时间对连续空间的影响，将参与扩散的节点投射到潜在的表达空间,然后计算用户向量的相似性判断用户是否会被另一个用户影响.2016年Bourigault等人[22]使用用户表达空间，将用户的影响能力映射到一个多维空间中，通过计算多维空间中2个向量的距离来计算是否会被影响.

现有方法并没有考虑消息在传播过程中会存在相互影响的情况.本文利用了消息之间的相互影响，提出了一种无拓扑结构的传播范围预测方法NT-EP,该方法具有5个优势：1)是一种端对端的学习框架；2)适用于无拓扑结构；3)考虑了消息传播过程中的相互作用；4)抽取的随机游走路径更接近真实的传播路径；5)结合目标消息的传播向量和其他消息的影响向量，同时利用注意力机制预测传播范围，使预测结果更准确.

2 问题定义

3 NT-EP传播范围预测框架

对于无拓扑结构下社交消息传播预测问题，本文提出了一种新的社交消息传播范围预测方法NT-EP，其框架如图1所示.方法NT-EP首先根据消息动作日志中的传播时间差为每个消息构造一个加权的传播图，如图1的①②所示.传播图边上的数字代表用户之间的影响概率.在传播图构造完成之后，使用随机游走方式从传播图中提取若干条该消息可能的传播路径，如图1的③所示，然后使用Word2vec方法计算出每个用户的初始的特征向量.传播路径上的每个用户获得初始的特征向量后，再将消息的传播路径送入Bi-GRU中得到用户的最终向量表示，如图1的④所示.传播路径上的每个用户获得最终的特征向量后，再结合注意力机制计算出每个消息的传播特征向量，如图1的⑩所示.

在消息传播过程中，不同消息之间会存在相互影响.因此我们也必须计算目标消息发生前其他消息的可能影响.如图1的⑤～⑧所示，使用和目标消息类似的方式，构造加权传播图、随机游走、Word2vec等方法计算其他消息参与用户的特征向量，然后构造其他消息的传播向量.

此后，使用梯度下降方法计算出其他消息的影响向量，如图1的⑨所示.最后NT-EP方法将目标消息的传播特征向量和其他消息的影响向量结合在一起，使用MLP拟合出目标消息的增量传播范围，如图1的所示.

Fig.1 NT-EP method framework图1 NT-EP方法的框架

3.1 传播路径选取

给定的动作日志通常对每个消息的动作按照传播时间排序，如图2的①所示.用户V1在时间1接受了消息A1，用户V2在时间2接受了消息A1,….从给定的动作日志中我们无法获得消息真实的传播轨迹.因为真实的情况可能是：用户V3在时间3接受了消息A1可能是因为用户V3和用户V1是朋友，并且用户V3看到了用户V1接受了消息A1，从而影响用户V3也接受了消息A1.用户V3不认识用户V2，V3接受了消息A1从来没有受到用户V2的影响.这样的真实传播轨迹在没有用户社交关系的条件下是无法获得的.

根据社交网上消息传播呈指数衰减特性[13]，我们有理由认为当用户V3接受消息A1的时候，用户V2影响的概率大于用户V1影响的概率，因为V2接受消息A1的时间离V3接受消息A1的时间更近.因此，我们根据2个用户接受消息的时间差来刻画2个用户的影响.假设用户Vi和Vj接受消息的时间分别为ti和tj，并且ti

w(ti,tj)=e-μ(tj-ti)，

(1)

其中，μ为调整时间差影响的超参数，实验中给出了该参数的选择过程.计算出每个消息中用户之间的影响概率后，我们可以根据影响概率为每个消息构造一个加权图来模拟该消息的真实传播轨迹.如图2的②所示，如果在消息A1中用户V1接受消息A1的时间早于用户V2接受消息A1的时间，则从用户V1引出一条边指向用户V2，边上的权值表示用户V1对用户V2的影响概率，由式(1)计算.在得到加权图后，我们再对加权图归一化，使得每个节点出边的概率和为1，如图2的③所示.为了模拟真实的传播路径，我们在归一化的加权图上根据边上的概率进行随机游走.每次游走的开始节点都是接受消息的第1个用户，例如图2的③中的V1.针对每个消息，我们采样K条路径，并且每条路径的长度为T.当游走过程中遇到某条路径长度小于T的时候，在后面若干补充位，让每条路径长度都等于T.在抽取了所有消息的传播路径后，我们使用词向量方法Word2vec计算每个用户的初始特征向量，细节见3.3节.

Fig.2 Constructing a weighted graph of message propagation图2 构造消息传播的加权图

3.2 其他消息影响向量

社交网中消息与消息之间存在着不同程度的联系，一个消息的传播可能促进或者抑制另一个消息的传播.例如国家个人所得税更改方案公布时，短时间内对税率信息查询有促进传播的作用.此外，用户上网浏览消息的时间有限，对于某些消息的关注增加，对其他消息的关注就会降低.

下面介绍其他消息对目标消息的影响能力.该影响能力通过一个影响向量来刻画.设当前的目标消息为a，a发生时间为ta.如果消息A1在消息a之前发生，并且消息A1的发生时间与消息a的发生时间距离较近，那么消息A1的传播很可能会对消息a的传播产生影响.基于这一思想，我们获取在ta之前很短的时间段τ内发生的消息集合Sa={A1,A2,…,Am}，该集合内每个消息对消息a传播的影响都需要考虑.假设影响消息集合Sa={A1,A2,…,Am}中每个消息截至时刻ta的传播范围分别为n1，n2，…，nm，发生时间分别为t1，t2，…，tm，并且满足t1

(2)

消息Ai的传播能力pi来自于参与消息Ai的用户传播能力，因此消息Ai的传播能力pi可以表示为

(3)

其中，pi表示影响消息Ai的传播向量，xj是使用Word2vec的skip-gram模型从传播路径上得到的用户向量，因为消息ei的传播范围为ni，所以有ni个不同的用户向量xj.对于消息ei的影响向量qi，本文使用梯度下降算法求解，使式(2)的目标函数最小化，具体算法如算法1所示.在得到影响消息集合Sa={A1,A2,…,Am}中每个消息的影响向量{q1,q2,…,qk}后，我们计算整个消息集合Sa对当前目标消息a的影响向量qSa.

(4)

算法1.计算其他消息影响向量.

输入:其他消息的传播向量pi(i=1,2,…,m)、其他消息的当前传播范围ni(i=1,2,…,m)、学习率λ;

输出:其他消息的影响向量qi(i=1,2,…,m).

① Initqi(i=1,2,…,m)；

② repeat

④qi←qi-λΔg；

⑤ until convergence.

3.3 目标消息传播向量

在抽取了所有消息的传播路径后，我们将每条传播路径当作一个句子，路径上的每个用户当作句子中的单词，输入到Word2vec[16]的skip-gram模型中，得到每个用户初始的特征向量.假设用户特征向量的维度为H.

为了知道消息在传播过程中会被哪些用户影响，我们使用相同的方法再从后向前处理路径上的每个用户.因此本文使用的是双向GRU(Bi-GRU)，拼接隐藏状态的输出得到对应用户的最终向量表示.具体通过式(5)对用户向量进行更新:

(5)

其中j表示传播路径中第j个节点，模型输入的用户节点向量xj和隐藏状态hi-1一起作为输入，并通过GRU的公式计算更新.其中W和U作为训练期间学习的GRU参数.

如图1的④所示，每条传播路径经过GRU处理后，会得到该路径上每个用户的最终向量表示h1,h2,…；然后我们使用注意力机制合并这些用户的最终向量表示h1,h2,…，计算该传播路径的向量表示；最后对所有传播路径的向量表示累加求和，得到目标消息传播向量pa：

(6)

3.4 传播范围预测

目标消息a的传播范围依赖于目标消息a的传播向量pa和其他消息的影响向量qSa，因此我们将目标消息a的传播向量pa和其他消息的影响向量qSa融合为一条向量la，即：

la=pa+αqSa，

(7)

其中，α为其他消息影响向量的权重，实验部分给出了参数α的选择过程.将融合后的向量la作为一个多层感知机的输入，输出预测的传播范围f(a)=fMLP(la)，其中MLP为一个多层感知机，f(a)为消息a的预测传播范围.

4 实验结果及分析

4.1 实验数据

本文中我们使用2套无拓扑结构的传播数据进行实验并对结果评估.数据描述如表1所示：

Table1 Dataset Statistics表1 实验数据描述

1) 微博[18].微博是基于用户关系的信息分享、传播的社交媒体.我们从论文中提供的数据中选取在2012-09-28—2012-10-29之间发生的1 280个消息的动作日志.截取的数据中包含261 839个用户、1 280个消息以及933 683条传播记录.

2) Flixster[11].Flixster是一个电影社交网站，可以让用户分享电影的评分，讨论新的电影.我们使用1 000个消息的动作日志.其中包含109 816个用户和581 202条传播记录.

实验中预测消息传播范围时通过调整时间长度t和Δt来选择预测的时间区间.t表示消息从发生开始到当前时刻所经过的时间，也就是消息已经发生了多久；Δt表示在时间t之后的时间长度.实验中我们选择t与Δt的大小分别为12 h,24 h,36 h来对消息的传播范围进行预测.实验中需要进行其他消息影响向量和用户特征向量占用空间存储.实验中将数据按7∶1∶2的比例分为训练集、验证集、测试集.数据集中每个消息的全部动作日志只出现在训练集、测试集、验证集中的一个.我们在训练集中训练模型，在验证集中调整超参数，在测试集中测试方法的性能.

4.2 评估指标

本文使用均方误差(mean squared error, MSE)来评估传播范围预测效果.这是回归任务中常见的评估指标.它是由预测值与真实值差的平方和求平均得到，定义为

(8)

本文使用精确率、召回率、F1_score来评估消息热点预测效果.在热点消息预测时，我们只进行采样12 h的传播并预测消息的最终传播范围.实验中设置一个阈值，超过阈值会被认为是热点消息，实验中选择的阈值为1 000.具体如下：

1)TP(真正例).TP表示预测传播范围大于阈值，并且实际传播范围大于阈值的消息数.

2)FN(假负例).FN表示预测传播范围大于阈值，但实际传播范围小于阈值的消息数.

3)FP(假正例).FP表示预测传播范围小于阈值，但实际传播范围大于阈值的消息数.

4)TN(真负例).TN表示预测传播范围小于阈值，并且实际传播范围小于阈值的消息数.

5) 精确率P(precision).P表示在所有被预测为热点的消息中，实际为热点的消息所占的百分比,即：

(9)

6) 召回率R(recall).R表示在所有实际为热点的消息中，被预测为热点的消息所占的百分比，即：

(10)

7)F1分数(F1_score).F1_score是统计学中同时兼顾精确率和召回率的一种指标，即：

(11)

4.3 对比方法

1) Embedding-IC[19].它是一种嵌入版本的独立级联模型，充分考虑用户之间的相互影响，把用户嵌入到隐藏投影空间中，借助EM(expectation-maximization)算法求发送方和接收方的嵌入向量，推测传播概率.根据计算出的传播概率计算最终消息传播范围.

2) Deepcas[6].它是一种消息传播范围预测方法.通过随机采样获得消息扩散的路径，使用GRU网络将路径转换为路径的表达向量.最后通过注意力机制来预测消息的传播范围.

3) NT-EP-T.它是NT-EP的一种变体.通过时间衰减游走采样传播路径，不利用消息的相互影响.

4) NT-EP-R.它是NT-EP的一种变体.不使用时间衰减游走(使用传统的随机游走)采样传播路径，但是利用消息的相互影响.

实验中，传播序列的选择算法使用C语言编写，在VS环境下编译运行，对比算法也使用C语言编写.NT-EP中神经网络部分使用python语言和tensorflow框架编写，在Anaconda3环境下编译运行.评价标准也使用python语言进行处理.所使用的台式机环境为Intel®Core i7-7700K 4.2 GHz CPU，16 GB RAM，操作系统为Windows10.

4.4 参数选择

Fig.3 Influence of different d of user vector on MSE图3 用户向量不同维度d对MSE的影响

我们在验证集中调整模型的超参数，包括用户向量维度d、其他消息影响向量的权重α、时间差的影响参数μ、学习率λ、消息抽取的路径数K、路径长度T等.实验中设置算法1中计算消息影响向量的学习率λ=0.000 5.

参数选择均使用微博数据进行实验，采样12 h传播序列，预测未来12 h传播范围，图3～7为不同参数下NT-EP方法的MSE值.我们先随机固定其他参数来考察用户向量维度d对MSE的影响，实验结果如图3所示.随着维度d的增加，MSE的值在逐渐减小，表明预测效果越来越好；但当维度超过50时，预测效果改善并不明显.为了平衡预测效果和运行时间，本文后面的所有实验都采用用户向量维度d=50.

Fig.4 Influence of different α of selection on MSE图4 α选取对MSE的影响

Fig.5 Influence of μ value selection on MSE图5 μ值选取对MSE的影响

Fig.6 Influence of K value selection on MSE图6 K值的选择对MSE的影响

Fig.7 Influence of T value selection on MSE图7 T值的选择对MSE的影响

其他参数的选取也采用上述类似的处理方式.在选取其他消息影响向量的权重α时，我们固定用户向量维度d=50.图4为α选取过程，我们选取α时在0到1之间每0.2取值，其中α=0.8时MSE的取值最优，因此本文后面的所有实验都采用α=0.8.图5给出了参数μ的选择过程，先固定用户向量维度d=50和α=0.8，其他参数随机选择，观察参数μ对MSE的影响，在μ=1时MSE值最小.因此后续实验选择μ=1时作为时间衰减游走采样的参数值.传播路径数量K与传播路径长度T的选择过程如图6和图7所示，因此后续实验中我们固定K=200和T=10作为传播路径数量和传播路径长度.

4.5 实验结果

不同方法对传播范围的预测效果如表2和表3所示.其中表2为微博数据上的实验结果，实验中分别采样12 h,24 h,36 h，然后对未来12 h,24 h,36 h的传播范围预测.表3为Flixster数据集的实验结果，实验中分别采样10 d,20 d,30 d，然后对未来10 d,20 d,30 d的传播范围预测.从表2和表3可以看出，本文方法NT-EP及其变体NT-EP-R和NT-EP-T的预测效果均优于对比方法Deepcas和Embedding-IC.表3中的实验结果好于表2中的结果，其原因在于Flixster数据比微博数据的消息数更多、每个消息的传播范围更广，能让各种模型学习得更充分.

Embedding-IC方法所在行只有一个实验结果，因为Embedding-IC方法和时间长度Δt无关.Embedding-IC把所有用户映射到一个向量空间中，通过距离计算用户之间的影响概率.该方法考虑所有用户对当前用户的影响，导致许多无关的用户也进行计算，但实际上激活时间上相近的用户才可能产生影响,所以Embedding-IC方法很容易导致过拟合，预测效果较差.Deepcas使用传统随机游走采样传播路径，没有考虑时间差对传播消息的影响，而且Deepcas也没有考虑消息之间的相互影响，因此预测效果并不理想.

Table 2 MSE Result of Weibo Dataset表2 微博数据传播范围预测MSE结果

Notes:tis the sampling time, Δtis the future sampling time, the best results are in bold.

Table 3 MSE Result of Flixster Dataset表3 Flixster数据集传播范围预测结果

Notes:tis the sampling time, Δtis the future sampling time, the best results are in bold.

NT-EP方法的变体NT-EP-T是通过时间衰减游走采样传播路径，不利用消息的相互影响预测时间传播范围.从表2和表3可以看出，NT-EP-T优于Deepcas，说明时间差对消息的传播起重要作用，消息之间确实存在相互影响.NT-EP的变体NT-EP-R利用消息的相互影响，但不使用时间衰减游走采样传播路径.从表2和3可以看出，NT-EP方法同时考虑消息的相互影响与时间差对消息传播的作用，预测效果明显优于Deepcas,NT-EP-T和NT-EP-R.

为了进一步验证本文方法的有效性，我们也对热点消息进行了预测，实验结果如表4所示.实验中我们使用微博数据采样12 h，对未来12 h,24 h,36 h是否会成为热点消息进行预测，我们在实验中设置的阈值为1 000.如果传播范围预测值大于阈值，则预测为热点消息.实验结果再次表明本文方法NT-EP优于现有方法，也再次证明了消息之间的相互影响确实存在以及消息传播具有时间衰减等特性.

Table 4 Precision,Recall,F1_score Results of Weibo Data表4 微博数据精确率、召回率、F1_score结果

Notes:tis the sampling time, the best results are in bold.

5 结 论

本文研究了无拓扑结构条件下的消息传播范围预测问题，提出一种社交消息传播范围预测方法NT-EP.NT-EP首次利用消息之间的相互影响来提高范围预测的准确性.实验结果表明：NT-EP在多个评价指标上优于现有的方法Deepcas和Embedding-IC.未来研究我们准备加入用户兴趣向量和用户基本属性进行范围预测，以及增加多层注意力机制尝试改善预测性能.