信息扩散与网络协同进化的点过程模型

跟踪：期刊论文WWW 2018，2018年4月23日至27日，法国里昂473COEVOLVE：一个信息扩散与网络协同进化的联合点过程模型MehrdadFarajtabar*乔治亚理工大学mehrdad@gatech.eduShuangLiGeorgiaTechsli370@gatech.eduManuel Gomez-RodriguezMPI for SoftwareSystemsmanuelgr@mpi-sws.org查宏源佐治亚理工zha@cc.gatech.edu王一辰佐治亚理工学院yichen.wang @gatech.edu乐松佐治亚理工学院、蚂蚁金lsong@cc.gatech.edu摘要在线社交网络中的信息传播受到底层网络拓扑结构的影响，但它也有能力改变它。当网络用户接触到新的信息源时，他们会不断地创建新的链接，而这些链接反过来又改变了信息传播的方式。然而，这两个高度交织在一起的随机过程-信息扩散和网络进化-通常被单独研究，忽略了它们的共同进化动力学。在这项工作中，我们提出了一个时间点过程模型，共同发展，这样的联合动力学，允许一个过程的强度被调制的其他。该模型使我们能够有效地模拟交错的扩散和网络事件，并生成遵循在现实世界的网络中观察到的共同扩散和网络模式的痕迹此外，我们开发了一个凸优化框架，从历史扩散和网络演化轨迹学习模型的参数。在合成数据和从Twitter收集的真实数据中的实验表明，我们的模型提供了一个很好的拟合数据，以及比替代品更CCS概念• 信息系统→社交网络;网络→在线社会网络;拓扑分析与生成;网络动力学;关键词社交网络;网络结构;信息扩散;协同演化动力学;点过程霍克斯过程生存过程ACM参考格式：Mehrdad Farajtabar ， Manuel Gomez-Rodriguez ， Yichen Wang ，Shuang Li，Hongyuan Zha，and Le Song.2018. COEVOLVE：信息扩散与网络协同进化的联合点过程模型。 In The 2018 Web ConferenceCompanion，2018年4月23日至27日，法国里昂。ACM，New York，NY，USA，5页。https://doi.org/10.1145/3184558.3186236*Correspondingauthor本文在知识共享署名4.0国际（CC BY 4.0）许可下发布作者保留在其个人和公司网站上以适当的归属方式传播作品的权利。WWW©2018 IW3C2（国际万维网会议委员会），在知识共享CC BY 4.0许可下发布。ACM ISBN 978-1-4503-5640-4/18/04..https://doi.org/10.1145/3184558.31862361引言Facebook、Twitter或微博等在线社交网络已成为人们分享、讨论和搜索个人感兴趣的信息以及突发新闻的大型信息网络[19]。在这种情况下，用户经常向他们的追随者转发他们通过他们的追随者接触到的信息，触发了在网络中传播的信息级联的出现[4]，并不断创建与信息源的新链接重要的是，最近对Twitter数据的实证研究表明，信息扩散和网络演化是耦合的，网络变化通常由信息扩散引发[1，25，32]。虽然最近有许多关于建模信息扩散[4，5，12，13]和网络演化[3，20，21]的工作，但大多数都分别研究这两个随机过程，忽略了一个过程可能对另一个过程产生的影响。因此，为了更好地理解信息扩散和网络演化，迫切需要这两个过程的联合概率模型，这在很大程度上是不存在的。在这项工作中，我们提出了一个概率生成模型，协同进化，信息扩散和网络进化的联合动力学。我们的模型基于时间点过程的框架，它明确地描述了事件之间的连续时间间隔，它由两个相互交织和相互依赖的组件组成：I. 信息传播过程。我们设计了一个使用“多变量霍克斯过程”[ 24 ]来捕获转发事件的相互激励行为，其中用户中的此类事件的强度由来自她的时变关注者集合的先前事件提升。虽然Hawkes过程在[7，10，17，23]之前已被用于信息扩散，但我们方法的关键创新在于明确地对由于特定源节点而引起的激发进行建模，从而揭示源的身份。这种设计反映了信息源被明确承认的现实，并且它还允许特定的信息源根据她的“信息量”以一定的速率获取新的链接II. 网络演进过程。 我们将链接创建建模为“信息驱动”的生存过程，并将此过程的强度与转发事件相结合。 尽管生存过程在[16，30]之前已经用于链接创建，但我们模型中的关键创新是将转发事件作为*这项工作的扩展版本出现在（Farajtabar et al.[8]）。QCode可在https://github.com/farajtabar/Coevolution上获得。跟踪：期刊论文WWW 2018，2018年4月23日至27日，法国里昂474（）下一页（{}）∈×（）•（）下一页（）∈{ }∪∈[]∈∗[]小窗口.（）∈F（）u（）下一页–（）下一页（）（）.ΣΣH（）对于环c关系为γu*s（t）=βsv∈Fu（t）κω1（t）（Auv（t）dNvs（t））dN（t）：tf（t−τ）dN（τ）=ti∈H（t）f（t−ti），我们有ei=（ui，si，ti）|ui=u和si=s（）下一页F（）{}∈[]（）图1：信息传播和网络结构过程如何相互作用的图示这类过程的驱动力由于我们的模型已经捕获了每个转发事件的源身份，因此新的链接将针对信息源，其强度与其激发程度和源的影响成比例点过程已成功应用于社交网络中的不同现象，如社区检测[28]，假新闻缓解[9]，推荐[15]，消息广播[18]，建模人群生成的数据[27]和级联模型。Nus t0Z+，计算由于源s到t的u的转发次数。这些计票过程是“链路的生存过程也表示为每个固定时间点t的大小为m的矩阵At。矩阵中的第u，s个条目Aus t0，1指示u是否直接在s之后，即，Aust=1意味着定向链路之前已经创建t. 生存过程的实例化只有一个事件刻画点过程的一个重要方法是通过条件强度函数λ*（t）。形式上，它是在小窗口[t，t+dt）中观察到事件的条件概率。e. ，λ*（t）dt：=P{在[t，t+dt中的事件）|H（t）}=E[dN（t）|H（t）]，其中我们通常假设dN（t）∈{0，1}，对于DT交织的信息扩散和网络演化过程被表征为E[dN（t）] |Hr（t）∪ Hl（t）]= Γ*（t）dt和E[dA（t）]|Hr（t）∪ Hl（t）]= Λ*（t）dt.其中reΓ*（t）=（γu*s（t））u，s M 且Λ*（t）=（λu*s（t））u，sM.我们对强度Γ*（t.），对于返回事件和Λ（t），我们的模型（Fig.（1）它的设计方式允许且λu*s（t）∫=（1−Aus（t））（μu+α.uκω2（t）dNus（t）。Heref（t）在相同的时间尺度内同时折叠并切除双向互相影响此外，我们通过实验验证了我们的模型可以产生信息扩散和网络演化的协同演化动力学，并生成遵循共同信息扩散模式（例如，级联结构、大小和深度）、静态网络模式（例如，节点度）和时间网络模式（例如，收缩直径）。最后，我们表明，通过建模的协同进化动力学，我们的模型提供了显着更准确的链接和扩散事件的预测比替代品在大规模的Twitter数据[1]。2模型我们将对两种类型的事件的生成进行建模：tweet/retweet事件er和链接创建事件el我们将事件表示为源是u的当前跟随者集合，γuu=ηu，且λuu=0。 项ηu 0是用户u主动发出的原始推文的强度，成为级联的来源，而项βsvtκ ωtAuvt dNvst模拟对等影响在网络中的传播，其中触发核κω1模拟对等体影响随时间的衰减。项1Aust有效地确保链路仅创建一次，并且在此之后，相应的强度被设置为零，项μu 0表示基线强度，其模拟节点u决定自发地跟随源s的时间，并且项αuκω2tdNust对应于由于源S最初发布的推文而引起的节点U的转发，其中，触发内核κω2t对兴趣随时间的衰减进行建模。这里，对应的转发强度越高，u越有可能发现来源s的信息有用，并且将创建到s的直接链接。型号详见[8]er或el：=u，s↓t.目的地↑ 时间m↑e其有效模拟和估计过程。3实验结果对于转推事件，三元组意味着目的地节点u在时间t转推最初由源节点s发布的推文。当u通过另一个节点u’转发消息时，该事件可能发生，其中原始信息源s被确认。给定转发事件的列表er =（u1，s1，t1），. . .直到时间t，3.1合成数据在本节中，我们使用我们的模拟算法[8]模拟了8，000个节点的网络的演化以及信息的传播。对于模拟网络，我们设置外源inten-历史Hr （吨）1u由于源s是Hr（t）=链路和扩散事件的概率为µu=µ=4× 10−6，以及. 反斗城我们的转发.对于链路创建事件，三元组意味着目的地节点u在时间t创建到源节点s的链路，即从时间t开始，节点u开始跟随节点s。我们将自己限制在每个（有向）链接仅创建一次的情况下。我们将链接创建历史表示为It。然后，给定m个用户，我们将使用两组计数过程来记录生成的事件：• 对于每个固定时间t，转发的计数过程被表示为大小为m×m的矩阵N（t）。矩阵中的第（u，s）项ω1=ω2=1。参数µ决定独立增长粗略地说，每个用户在时间T之前自发建立的链接的预期数量为μT。度分布 实证研究表明，在线社交网络和微博网站的度分布遵循幂律[3，19]，并认为这是富人越富现象的结果。网络的度分布是幂律，如果度为d的期望节点数md由md∝d−γ给出，其中γ>0。直观上，值越高0ing[33]。两个过程，信息扩散和网络演化，非ηu = η = 1。5，并且触发内核参数为跟踪：期刊论文WWW 2018，2018年4月23日至27日，法国里昂475数据幂律拟合泊松拟合数据幂律拟合泊松拟合=0=0.05=0.1=0.2直径×个数据幂律拟合泊松拟合410数据幂律拟合泊松拟合410八零八零二、二十十十四零四零010个01100 105 100五一零十十稀疏性−4X 10稀疏性−4X 10(a) α = 0（b）α=0。054十十十(a) 直径，α = 0。1（b）直径，β = 0。10.30.32十十十0.150.15010个10110(c)α =0。102100十十十1个2个十十十(d)α = 0。200 0.10.2(c) CC，α= 0。100.75 1.5(d) CC，β= 0。1图2：当网络稀疏度达到0. 001时，不同α和固定β = 0的度分布。1.一、度分布从随机网络跨越到无标度网络，说明了对真实网络建模的灵活性。图3：不同α值和固定β = 0的叶栅结构、尺寸和深度的分布。2在参数α和β中，所得到的度分布越接近于遵循幂律。这是因为网络在本地增长得更多。有趣的是，它们的值越低，分布越接近Erdos-Renyi随机图[6]，因为边几乎均匀且独立地添加，而不受局部结构的影响。图2通过显示不同α值的度分布证实了这一直觉。级联模式。我们的模型可以产生最常见的级联结构以及重尾级联大小和深度分布，如在历史Twitter数据中观察到的那样[11]。图3总结了结果，并提供了经验证据，即α（β）值越高，叶栅越浅和越宽。小（收缩）直径。 有经验证据表明，在线社交网络和微博网站的直径表现出相对较小的直径，并随着网络的增长而缩小（或变平）[2，3，22]。图4（a-b）显示了最大连通分量（LCC）上的直径与不同α和β值的网络随时间的稀疏性。虽然在开始时，由于小的连接组件的合并，直径有一个短暂的增加此外，较大的α或β值导致较高水平的局部生长，并且因此导致较慢的收缩。聚类系数 三元闭包[14，20，26]经常被认为是一种合理的链接创建机制。然而，不同的社交网络和微博网站呈现出不同程度的三元封闭[29]。重要的是，我们的方法能够生成图4：网络稀疏度为0.001时的直径和聚类系数;（a，b）固定α = 0时，直径与稀疏度随时间的变化。1，并且对于固定的β= 0。（c，d）分别针对β和α的聚类系数（CC）β=0，t=20β= 0，t=35β= 0，t=50β=0。8，t = 20β= 0。8，t = 35β = 0。8，t=50图5：具有值β = 0，0的网络的演化。8具有不同等级的三元闭合的网络，如图4（c-d）所示，其中我们绘制了聚类系数[31]，其与三元闭合的频率成比例。网络可视化。图5显示了两个300节点网络的最大连通分量（LCC），用于我们模型的两个特定实现，在两个不同的网络中。β的值。 在这两种情况下，我们都使用µ = 2 10 −4，α = 1，η =1。5.三个左图对应于β=0并且表示β = 0的一端。光谱，即、Erdos-Renyi随机网络。在这里，网络均匀地演化。右边的三个图对应于β = 0。8并且表示另一端，即、无标度网络。在这里，网络在本地演化，集群作为本地增长的结果自然出现。=0=0.001=0.1 =0.8直径聚类系数聚类系数42跟踪：期刊论文WWW 2018，2018年4月23日至27日，法国里昂476洞穴鹰Top1·0.80.4140700.20.10 50100事件发生时间00 50100事件发生时间110一三五事件数量×105(a) 友情链接：AR800一三五事件数量×105(b) 友情链接：Top-10.30.540 0.150 20 40 60事件发生时间00 20 40 60事件发生时间一三五事件数量×1050一三五事件数量×105图6：真实数据中2个典型用户的链接和转推行为左列示出了他们的链接和转推事件的尖峰序列，右列示出了相同两个用户的估计的链接和转推强度3.2真实数据我们使用一个数据集，其中包含链接事件以及来自数百万Twitter用户的推文和转发[1]。特别是，该数据集包含20天内三组用户的数据;超过650万用户的近800万条推文，转发和链接事件第一组用户（8，779个用户）是源节点s，针对源节点s收集了他们的所有推文时间第二组用户（77，200个用户）是第一组用户的关注者，针对第一组用户收集了他们的所有转发时间（和源身份）第三组用户（6，546，650个用户）是在记录时段期间开始跟随第一组中的至少一个用户在我们的实验中，我们专注于10天期间（2012年9月21日至2012年9月30日的所有事件（和用户），并使用9月21日之前的信息来构建初始社交网络（用户之间的我们使用我们的框架在第二个10天期间的协同进化模型更具体地说，在协同进化模型中，我们在第一层中有5，567个用户发布了221，201条推文。在第二层中，整个77，200个用户在该时间间隔内生成了101，465个转推 在第三层中，我们有198，518个用户，他们创建了219，134个链接到第一层中的1978个用户（共5567个）。最后，我们根据时间将事件分为训练集（覆盖85%的事件）和测试集（覆盖剩余的15%），即，则训练集中的所有事件都比测试集中的事件发生得早。然后，我们使用我们的模型估计过程[8]来拟合越来越多的训练数据中的参数。Retweet和Link Coevolution图6可视化了不同目标之间聚合的转发和链接事件，以及由我们的训练模型为随机挑选的四个源节点给出的相应强度。在这里，很明显，（他的帖子的）转发和（给他的）链接创建在时间上是聚集的，并且经常彼此跟随，我们的拟合模型强度成功地跟踪了它们。链接预测。 我们使用我们的模型来预测每个测试链接事件的源的身份，给定预测时间之前的历史（链接和转推）事件，并将其性能与TRF [1]和WENG [32]进行比较，这是最先进的方法。我们通过使用不同的方法计算所有潜在链接的概率来评估性能，然后计算(i)所有真实（测试）事件的平均排名（AvgRank），以及（ii）真实（测试）事件在所述平均排名中排名的（c）活动：AR（d）活动：Top-1图7：Twitter数据集中的预测性能，通过平均排名（AR）和真实（测试）事件在前1个事件中排名的成功概率（Top-1）。每个测试时间的前1个潜在事件（前1个）。 我们在图7（a-b）中总结了结果，其中我们考虑了越来越多的训练retweet/tweet事件。 我们的模型优于TRF和WENG一致。例如，对于8 - 10 - 4个训练事件，我们的模型实现了SP 2。是TRF和WENG的5倍活动预测。我们使用我们的模型来预测生成每个测试扩散事件的节点的身份，给定的历史事件之前的时间的预测，并比较其性能与基线组成的霍克斯过程没有网络进化。对于霍克斯基线，我们在预测时间之前拍摄网络快照，并使用所有历史转发事件来拟合模型。在这里，我们通过与链接预测任务中相同的两个度量来评估性能，并针对越来越多的训练事件总结了图7（c-d）中的结果。结果表明，通过建模的协同进化动力学，我们的模型的表现显着优于基线。4结论在这项工作中，我们提出了一个信息扩散和网络演化的联合连续时间模型，它可以捕获协同进化动力学，可以模仿在现实世界的网络和信息扩散数据中观察到的最常见的静态和时间网络模式，并且可以比以前的最先进的技术更准确地预测网络演化和信息扩散。使用点过程来建模信息和社交网络中相互交织的事件，为未来开辟了许多有趣的场所。我们目前的模型只是一个展示的情况下，一个点过程框架提供了丰富的可能性，这已经很少探索之前在大规模的社会网络建模。例如，在框架中也可以替代地使用大范围且不同范围的点过程，并且在不改变模拟的效率和参数估计的凸性的情况下增强当前模型。开发一种有效的机制来解释时间分辨率的异质性将提高模型的预测能力。最后，我们可以增强框架以允许时变参数。 模拟不会受到影响，并且时变相互作用的估计仍然可以通过凸优化问题进行[34]。Retweet链路Retweet链路Retweet链路COEVOLVETRF翁Retweet链路COEVOLVETRF翁洞穴鹰尖峰序列强度尖峰序列平均排名强度Top1平均排名跟踪：期刊论文WWW 2018，2018年4月23日至27日，法国里昂477引用[1] D. Antoniades和C.多夫罗利斯社交网络中的协同进化动力学：以Twitter为例。arXiv预印本arXiv：1309.6001，2013。[2] L. Backstrom，P. Boldi，M. Rosa，J. Ugander，and S.豇豆四度分离。在Proceedings of the 4th Annual ACM Web Science Conference，第33[3] D. Chakrabarti，Y.Zhan和C.法鲁索R-mat：一个用于图形挖掘的递归模型计算机科学系，第541页，2004。[4] 成杰湖，澳-地Adamic，P. A.道，J.M. Kleinberg和J.莱斯科韦茨可以预测级联吗？第23届万维网国际会议论文集，第925-936页，2014年[5] N. 杜湖，澳-地宋，M。Gomez-Rodriguez和H.扎。连续时间扩散网络中的可缩放影响估计。 神经信息处理系统进展26，2013。[6] P.Erdos和A.雷尼关于随机图的演化。Publ. Math. Inst.Hungar Acad. Sci，5：17 -61，1960。[7] M. Farajtabar，N.杜，M。戈麦斯-罗德里格斯岛Valera，H.Zha和L.歌通过激励用户来塑造社交活动。 神经信息处理系统进展（NIPS），2014年。[8] M. Farajtabar，Y.Wang，M.Gomez-Rodriguez，S.Li和H.扎。Coevolve：信息扩散与网络演化的联合点过程模型。Journal ofMachine Learning Research，18：1 -49，2017。[9] M. Farajtabar，J.Yang，X.叶，H.许河，巴西-地Trivedi、E.Khalil，S.利湖，加-地歌H. 扎 。 通 过 基 于 点 过 程 的 干 预 缓 解 假 新 闻 。 arXiv 预 印 本 arXiv ：1703.07823，2017。[10] M. Farajtabar，X.叶，S。哈拉蒂湖Song和H.扎。社交网络中的多阶段竞选活动神经信息处理系统进展，第4718-4726页，2016年[11] S. Goel，D. Watts和D. G.戈德斯坦在线扩散网络的结构。在Proceedings ofthe 13th ACM conference on electronic commerce，pages 623[12] M. Gomez-Rodriguez，D.Balduzzi和B.舍尔科普夫揭示扩散网络的时间动态。2011年国际机器学习会议论文集。[13] M. Gomez-Rodriguez，J. Leskovec和A.克劳斯推断扩散和影响的网络。第16届ACM SIGKDD国际知识发现和数据挖掘会议论文集，第1019ACM，2010年。[14] M. 格兰诺维特弱关系的强度美国社会学杂志，1360-1380页[15] S. A. Hosseini、K.阿利扎德，阿-地Khodadadi，A.阿拉布扎德Farajtabar，H.Zha和H. R. 拉比用于时间推荐的递归泊松因子分解arXiv预印本arXiv：1703.01442，2017。[16] D. Hunter，P.Smyth，D.Q. Vu和A.联合亚松森引文网络的动态自我中心第28届国际机器学习会议论文集，第857-864页，2011年。[17] T. Iwata，A. Shah和Z. Ghahramani透过共享级联泊松过程发现线上社交活动在第19届ACM SIGKDD知识发现和数据挖掘国际会议上，第266-274页。ACM，2013年。[18] M. R. Karimi、E.Tavakoli，M.法赖塔巴尔湖Song，M.戈麦斯·罗德里格斯 智能广播：你想被看到吗？arXiv预印本arXiv：1605.06855，2016。[19] H.瓜克角Lee，H. Park和S.月球什么是Twitter，社交网络还是新闻媒体？在 Proceedings of the 19th International Conference on World Wide Web ，pages 591ACM。[20] J. 莱斯科韦茨湖巴克斯特罗姆河Kumar和A.汤姆金斯社交网络的微观演化。 第14届ACM SIGKDD知识发现和数据挖掘国际会议论文集，第462-470页。ACM，2008年。[21] J. Leskovec，D.Chakrabarti，J.克莱因伯格角Faloutsos和Z.Ghahramani 克罗内 克 图 ： 一 种 网 络 建 模 方 法 。 Journal of Machine LearningResearch，11（Feb）：985 -1042，2010.[22] J. 莱斯科韦茨Kleinberg和C.法鲁索随时间变化的曲线图：致密化规律，收缩直径和可能的解释。第十一届ACM SIGKDD国际会议关于数据挖掘中的知识发现的论文集，第177-187页。ACM，2005年。[23] S. W. Linderman和R. P·亚当斯发现点过程数据中的潜在网络结构。2014年国际机器学习会议（ICML）[24] T. J. Liniger. 多变量Hawkes过程博士论文，瑞士苏黎世联邦理工学院，2009年。[25] S. A. Myers和J.莱斯科韦茨twitter信息网络的突发动态。 第23届万维网国际会议，第913-924页，2014年。[26] D. M. Romero和J.克莱因伯格混合社会信息网络中的定向闭合过程，以及对Twitter上链接形成的分析。国际妇女运动会，2010年。[27] B.塔比比安岛Valera，M.法赖塔巴尔湖宋湾，澳-地Schölkopf和M.戈麦斯-罗德里格斯。从数字痕迹中提取信息可靠性和来源可信度arXiv预印本arXiv：1610.07472，2016。[28] L. Tran，M.法赖塔巴尔湖Song和H.扎。 Netcodec：社区检测从个人活动。InSDM，2015.[29] J. 乌干达湖Backstrom和J.克莱因伯格 Subgraph frequencies：Mapping theempirical and extremal geography of large graph collections. 第22届万维网国际会议论文集，第1307 国际万维网会议指导委员会，2013年。[30] D. Q. Vu，D.Hunter，P.Smyth和A.联合亚松森纵向网络的连续时间回归模型。神经信息处理系统进展，第2492-2500页，2011年。[31] D. J.瓦茨和S. H.斯特罗加茨 小世界网络的集体动力学。Nature，393（6684）：440[32] L. Weng ， J.Ratkiewicz ， N. 佩 拉 湾 贡 萨 尔 维 斯 角 Castillo ， F. 邦 奇 河Schifanella，F. Menczer和A.弗拉米尼信息 扩散在社交网络演化中的作 用 第19届ACMSIGKDD知识发现和数据挖掘国际会议论文集，第356-364页。ACM，2013年。[33] A. Zarezade，A.Khodadadi、M.Farajtabar，H.R. Rabiee和H.扎。相关级联：竞争或合作。arXiv预印本arXiv：1510.00936，2015。[34] K. Zhou，H.Zha和L.歌多维hawkes过程的触发核学习。2013年国际机器学习会议（ICML）