社交网络中信息扩散的非线性动力学

+Ⓧ社交网络中信息扩散的非线性动力学松原康子，熊本大学，JST PRESTOYasushi Sakurai，熊本大学B. Aditya Prakash，弗吉尼亚理工大学李磊，今日头条实验室卡耐基梅隆大学最近搜索引擎和博客、推特等新媒体的使用激增，加快了新闻和谣言的传播速度。一条新闻在这些媒体上传播的速度有多快？它的受欢迎程度是如何随着时间的推移而下降的？上升和下降的模式是否遵循一个简单的普遍规律？在这篇文章中，我们提出了SPIKEM，一个简洁而灵活的分析模型的上升和下降模式的信息扩散。我们的模式具有以下优势。第一，统一的力量：它解释了早期的经验观察和概括的理论模型，包括SI和SIR模型。我们提供了SPIKE M的起飞与消亡条件的阈值，并讨论了我们的一般性。通过将其应用于任意图形拓扑来建立模型。第二，实用性：它符合观察到的行为11各种各样的真实数据。第三，简约性：它只需要少数参数。第四，实用性：通过对感兴趣的系统参数（新闻的质量、感兴趣的博客作者的数量等）进行逆向工程，使得可以执行诸如预测、发现异常和解释的分析任务。我们还介绍了一个高效和有效的算法，实时监测的信息扩散，即SPIKE STREAM，它确定了多个扩散模式在一个大的收集在线事件流。在真实数据集上的大量实验表明，SPIKE M准确而简洁地描述了社交网络中上升和下降尖峰的所有模式。类别和主题描述符：H.2.8 [数据库应用程序]：数据挖掘通用术语：算法，实验，理论附加关键词和短语：信息扩散，社交网络，非线性建模ACM参考格式：松原靖子，樱井靖，B. Aditya Prakash，Lei Li，and Christians Faloutsos. 2017.社交网络中信息扩散的非线性 动 力 学 ACMTrans.Web11 ， 2 ， Article11 （ April2017 ） ， 40pages.DOI ：http://dx.doi.org/10.1145/3057741这项工作得到了JSPS KAKENHI Grant-in-Aid for Scientific Research（JP 15 H 02705、JP 16 K12430、JP26280112和JP 26730060）、PRESTO JST和MIC/SCOPE（162110003）的支持。这种材料也是基于陆军研究实验室（合作协议W 911 NF-09- 2-0053）和国家科学基金会（IIS-1017415）支持的工作，并 得 到 国 家 科 学 基 金 会 （ IIS-1353346 ） ， 国 家 人 文 基 金 会 （ HG-229283-15 ） 和 ORNL （ 任 务 订 单4000143330）的部分支持，以及马里兰采购办公室（H98230-14-C-0127）和Facebook的教师礼物。作者松原，熊本大学高等科学技术学院，2-39- 1 Kurokami，Chuo-ku，Kumamoto 860-8555，Japan;电子邮件：yasuko@cs.kumamoto-u.ac.jp; Y.Sakurai; email：yasushi@cs.kumamoto-u.ac.jp; B.Aditya Prakash;电子邮件：badityap@cs.vt.edu; L.电子邮件：lileicc@gmail.com;C. Faloutsos;电子邮件：christian@cs.cmu.edu。允许制作部分或全部本作品的数字或硬拷贝供个人或课堂使用，不收取任何费用，前提是复制品不以营利或商业利益为目的制作或分发，并且复制品在第一页或显示器的初始屏幕上显示此通知以及完整的引用。本作品的版权归ACM以外的其他人所有，必须予以尊重。允许使用学分进行摘要复制，再版，张贴在服务器上，再分发到列表，或在其他作品中使用本作品的任何组成部分，需要事先特定的许可和/或费用。可向出版部索取，ACM，Inc.2 Penn Plaza ， Suite 701 ， New York ， NY 10121-0701 USA ， 传 真 ： 1 （ 212 ） 869-0481 ， 或permissions@acm.org。c 2017 ACM 1559-1131/2017/04-ART11 $15.00DOI：http://dx.doi.org/10.1145/3057741ACM Transactions on the Web，卷。号112、第十一条，公布日期：2017年4月十一Y. Matsubara等人1. 国际合作在线社交媒体正在以新的方式传播新闻和谣言，搜索引擎极大地促进了这种操作，创造了爆发和峰值。一些谣言（或模因、标签）开始缓慢，并徘徊不去;另一些则提前出现，然后衰减;另一些则表现出更复杂的行为，如图1所示。真实的上升和下降模式之间是否存在质的差异？他们组成不同的阶级吗？如果有，有多少个，什么种类？早期关于YouTube数据的工作声称有四个类[Crane and Sornette2008]。 实证研究发现了六类[Yang and Leskovec 2011]。到底有多少个班？我们的答案是一。我们提供了一个非线性分析模型，SPIKE M，1，只需要少数参数，我们表明，它可以生成所有的模式，发现在实际数据中，只需通过改变参数值。预览我们的结果。图1显示了来自K-SC [Yang and Leskovec2011]的在线媒体（模因）的六个代表性尖峰，作为灰色圆圈，我们的拟合模型作为实线红线。请注意，拟合非常好，尽管我们的SPIKE M模型只需要7个参数，时间序列跨越120个间隔。我们要解决的问题是如何建模/预测在线活动（例如，博客帖子的数量）作为时间的函数，在给定时间给出一些突发新闻。为了简洁明了，我们将使用一个博客示例，但也可以对许多其他过程进行建模，例如热门关键字的搜索量，Twitter上的谣言传播以及计算机病毒感染机器[Papalexakis et al. 2013]。因此我们存在以下问题。PROBLEM 1（WHAT-IF）。 给定一个博客（/主机/用户）网络，一个冲击（例如，事件）、事件的兴趣/质量以及立即（=时间nb）对事件进行博客的博主的计数Sb，发现博客活动将如何随时间演变。一个密切相关的问题是开发一个简约的模型，可以使其适合过去观察到的几个尖峰（如图1所示），如下所示。PROBLEM 2（MODEL DESIGN）. 考虑到过去几个尖峰的行为，找到一个方程/模型，可以用尽可能少的参数来解释它们。更重要的是，如果参数有一个直观的解释（“博客数量”，“新闻质量”等），那就太好了与自回归模型（AR/ARIMA）的a1、a2相反1.1. 与竞争对手表1说明了我们方法的相对优势。只有SPIKE M符合所有要求。K-SC [Yang and Leskovec2011]（如图1所示）中的六组上升和下降模式是非参数的，无法进行预测。C-S方法[Crane and Sornette2008]可以捕获幂律衰减模式，但无法生成指数增长模式或周期性用户活动。易感染（SI）模型及其变体（例如，SIR、SIRS、SEIR模型）是非线性模型，导致指数衰减，而不是我们在实际数据中观察到的幂律衰减（我们将在后面的图2中讨论）。逻辑函数[Brauer and Castillo-Chavez2001]、 WTA [Prakash et al.2012 a]和其他方程[Jackson1992; Nowak2006; Matsubara et al.2014 b]是非线性动力系统，Bass模型[Bass1969]（即，新产品的市场渗透率），产品生命周期模型[Klepper1996; Chang etal.2014年]，1可查阅http://www.cs.kumamoto-u.ac.jp/www.software.html。ACM Transactions on the Web，卷。号112、第十一条，公布日期：2017年4月社交网络十一Fig. 1. SPIKE M的建模能力：六种类型的尖峰（K-SC）显示为点，我们的模型拟合由红色实线显示。数据序列跨越超过120个时间刻度，而SPIKE M只需要7个参数。拟合非常好，以至于由于遮挡，红线通常不可见。表I.方法的能力（只有我们的方法符合所有规格）K-SCC-SSI/SIR离散小波变换/离散傅立叶变换AUTOPLAITSARIMAS派克 M领域知识-√√---√√信息扩散√√√----√幂律衰减-----√非线性-√√-√--√√周期性----√缺失值--√√-√-√-√离群点检测---√分割----√-√网上办理------√预测-----√投入-产出模型[Leontief1986]，以及其他相关经济模型都包含了决策知识。然而，这些方法并不旨在捕获长的重尾模式或周期性的用户活动。小波变换（DWT）和傅立叶变换（DFT）等时间序列分析的基本工具可以检测突发和典型模式，但它们无法检测社交网络中信息扩散的AutoPlait [Matsubara et al.ACM Transactions on the Web，卷。号112、第十一条，公布日期：2017年4月十一Y. Matsubara等人图二、图1中图案C1的S PIKE M与SI的拟合结果。 原始序列（灰色圆圈）和我们的模型（红线）具有指数上升部分和幂律下降部分。SI模型（蓝色虚线）对于两个部分都是指数的，因此是不现实的。顶行：全区间;左列：仅上升部分;右列：仅下降部分。2014]、SWAB [Keogh et al.2001]和pHMM [Wang et al.2011]能够捕获序列的动态并执行分割;然而，它们不旨在捕获信息扩散的长距离非线性演变。所有传统的线性时间序列方法从根本上都不适用：AR、ARIMA、SARIMA和衍生物，包括AWSOM [Papadimitriou et al.2003]、 TBATS [Livera et al.2011]，PLiF [Li etal.2010]和TriMine [Matsubara et al.2012 a]都是基于线性方程，因此无法对由非线性方程控制的数据进行它们导致指数衰减，而不是现实似乎遵守的幂律，它们不能包含领域知识。我们还应该注意到，所有这些线性模型都可以随着时间的推移而趋于无穷大。我们提出的模型SPIKE M能够成功地复制早期的模式，并且可以轻松地适应大量不同的真实数据集。它非常直观，基于扩散和影响传播。此外，作为一个简洁的模型，它提供了所有相关的好处：它可以实现压缩和异常检测，也能够预测。1.2. 贡献本文提出了一个统一的模型SPIKE M来解决上述两个问题.我们的模式具有以下优势：ACM Transactions on the Web，卷。号112、第十一条，公布日期：2017年4月社交网络十一==∗−(1) 统一能力：它包括早期的模式和模型作为特例（例如， SI和SIR模型，以及K-SC中的模式[Yang和Leskovec 2011; Leskovec等人2009]）。我们的模型也可以推广到一个任意的图形拓扑结构，以及团网络。(2) 实用性：它匹配众多，多样，真实数据集的行为，包括幂律衰减。(3) 简约性：它只需要少数参数。(4) 准确性：我们提出的模型可以回答我们还提供了一个可扩展的算法，即SPIKESTREAM，它是为实时监控信息扩散而设计的（见第4.4节）。我们的模型是通过精心的设计，包括（a）幂律衰减的传染性，（b）有限的人口，（c）适当的周期性。早期的模型无法处理上述一个或多个问题。由于SPIKE M的实用性，我们可以实现预测，分析假设情景，以及检测扩散尖峰和异常，如我们在第5节和第6节中所示。1.3. 纲要文章的其余部分组织如下。第2节介绍了相关工作的概述，第3节描述了所提出的模型。在第四节中，我们分析了我们的模型，并讨论了SPIKE M的一般性和扩展。第5节和第6节显示了我们对各种数据集的实验结果我们在第7节描述了相关的工作，并在第8节总结了文章。2. 阿格罗和本节介绍基本概念。2.1. 流行病学基础最基本的流行病模型是SI模型。每个对象/节点都处于两种状态之一：易受感染（S）或感染（I）。每个被感染的节点都试图以概率β独立地感染它的每个邻居，这反映了病毒的强度。一旦被感染，每个节点将永远被感染。如果我们假设底层网络是一个由N个节点组成的集团，并使用我们的符号（dB（t）dt=β<$（N-B（t））B（t），（1）其中时间t被认为是连续的，dB/dt是导数，初始条件反映了外部冲击（例如，B（0）b外部感染的人）。理由如下：β是病毒的强度--也就是概率感染者（B）和未感染者之间的接触会导致感染--我们有B（N B）次这样的接触。B（）的解是S形的，它的导数围绕峰值对称，有指数上升和指数下降（我们稍后在图2中讨论）。在那里，我们还显示了SI模型的弱点：实际数据有一个幂律2.2. 自激Hawkes过程Crane 和 Sornette[2008] 使 用 了 自 激 Hawkes 条 件 泊 松 方 程 ，cess [Hawkes andOakes1974]对每天的YouTube浏览量进行建模，显示活动的峰值具有幂律上升模式和幂律下降模式，具体取决于ACM Transactions on the Web，卷。号112、第十一条，公布日期：2017年4月十一Y. Matsubara等人=.=模型参数。霍克斯过程是一个泊松过程，其瞬时速率不是常数，而是取决于先前事件的计数，其影响随着事件的年龄τ而换句话说，如果最近有很多事件（观看/博客），我们今天就会有很多这样的事件。基本模型指出，感染的传播速率取决于（a）外部源S（t）和（b）自激励-即，在较早感染的节点（i 1，. . ）;这些节点以衰减的病毒强度φ（τ）传播感染，它们的年龄τ增长，乘以某个常数μi。常数μi等价于被感染节点i的度。dB（t）dt=S（t）+μiφ（t-ti）（2）i，ti≤t该模型通常假设μi值相等，即所有节点具有相同的度（在一定条件下，该模型提供了幂律上升和幂律下降模式。接下来，我们提出了我们提出的模型，SPIKE M，它避免了SI和Hawkes模型的缺点，并具有其他几个理想的属性。3. 该方法在本节中，我们为读者提供了几个有趣而重要的观察结果，并介绍了我们提出的模型，即SPIKE M。为了简单起见，我们首先关注最基本的情况：集团网络，其中所有节点（即，博客作者）潜在地通过无向和未加权的边彼此连接。3.1. SPIKE M的设计理念基本上，我们的模型试图捕捉以下行为，这是我们在几个真实数据中观察到的，-P1：幂律坠落模式-P2：周期性，与此同时，我们希望-P3：避免发散到无穷大其他型号可能有的。为了处理P3（发散），我们强制我们的模型具有有限的种群并相应地调整方程。为了处理P1（幂律下降模式），我们假设节点的感染力（博客文章的受欢迎程度）随影响指数p衰减。3.3节讨论了周期性的处理。我们以增加复杂性的步骤来描述我们的模型，我们从基本模型开始。我们假设有N个博客，他们中没有一个人还在写关于感兴趣的话题的博客在时间nb，发生事件（例如，2004年的印尼海啸或一个有争议的政治演讲，如我们的模型还需要一些参数：第一个是新闻的质量/趣味性，我们将其表示为β，因为这是流行病学文献中病毒传染性的标准符号。如果β为零，则没有人会关心这条特定的新闻;值越高，就会有越多的博主在博客上谈论它。最后，我们有一个衰减函数f（τ），它模拟了一个博客帖子在τ岁时的感染力/影响力。标准的流行病学模型假设f（）是常数（一旦患病，你感染他人的概率相同）;最近的分析表明，随着年龄的增长，影响力下降，遵循幂律。ACM Transactions on the Web，卷。号112、第十一条，公布日期：2017年4月社交网络十一∗表II.符号和定义符号定义N可用博客ndn序列持续时间时间刻度（n= 0，...， n d）U（n）B（n）B（n）不知情的博客数量已通知b记录器Delta：在时间n时f（τ）β在τ感染强度S（n）国家b‹时间n时的外部S爆料开始时间出生时的外部冲击强度（时间nb）背景噪声PaPpPs周期性强度周期（例如，Pp=24小时）周期性以上是基本模型的参数。在我们列出方程之前，我们想简要地提到一个导出量βN;这个量大致对应于流行病学文献中的R0（这告诉我们“第一次爆发”的大小2总之，我们模拟的场景如下：什么都没有发生，直到一个新闻事件出现，在出生时间nb。-SB 博主们立即对此发表博客。- 其他博客访问最初的SB（或后续）博客，偶尔也会我们还假设：- 每个博客最多只写一次关于这个事件的博客- 没有其他相关事件发生-也就是说，冲击函数S（）只有一个尖峰。在不失一般性的情况下，我们还假设，一旦一个不知情的博主看到一个受感染/知情的博客，他或她总是写关于这个事件的博客（如果他或她写博客的概率为ρ1，我们可以在感染因子β中吸收ρ）。我们的目标是找到一个方程来描述在时间tickn时写博客的人的数量B（n），作为n的函数，当然还有系统参数（博客总数N，感染强度β等）。表二列出了主要符号及其定义。3.2. 基本型号：SPIKE M-BASE我们提出的模型有两种状态的节点（=博客）-U：Uninformed of the rumor-B：通知了，B记录了这件事。对于那些在时间tickn时刚刚被告知的人，我们将使用符号B（n），我们假设一旦被告知，一个人会立即在博客上发布谣言设U（n）为在时间n时不知情的人数，设WAB（n）为在时间n时发现谣言并立即在博客上发表的人数。[2]是的，它应该是N-1，但我们为了直觉而牺牲了准确性ACM Transactions on the Web，卷。号112、第十一条，公布日期：2017年4月十一Y. Matsubara等人.+.S（n=n）b b=MODEL 1（SPIKE M-BASE）。我们的基本模型由以下方程控制n<$B（n+1）=U（n）·（<$B（t）+S（t））·f（n+1−t）+<$（3）t=nbU（n+1）=U（n）−B（n+1），（4）哪里和初始条件f（τ）=β·τ−p（5）B（0）= 0，U（0）= N。此外，我们添加了一个外部冲击S（n），即在出生时间nb产生的尖峰。数学上，其定义如下：S（n）=. 0（n/=nb）。（六）模型的合理性。我们采取以下步骤：- 术语CQB（t）S（t）捕获了在时间tickt激活的博主和外部来源的数量;它们的感染性由f（）感染性函数调制，因为我们假设来源/博主的感染性随时间衰减求和是对自电击的诞生时间nb- 传染性函数f（）严格遵循指数为p的幂律。我们设定p 1。[5]正如早期关于阅读数据的工作所发现的：真正的博客[Leskovec et al. 2007 b]以及爱因斯坦和达尔文对邮件的回复[Barabasi 2005]。- 求和的含义是在时间tickn时的可用刺激;可用目标是不知情的博主U（n），乘积给出了新感染的数量- 我们添加了一个噪音术语<$来处理诸如meme“是的，我们可以“的情况这是巴拉克·奥巴马的口号）。经常，0。这就完成了我们基本模型的论证我们还提到了我们的模型所遵循的一些规则根据定义，nB（n）= B（t），t=0当然我们还有不变式B（n）+U（n）=N，其中N是人/博客的总数。3.3. 有周期性：SPIKE M博客可以调整他们的活动后，每天的周期（或每周，或每年）。例如，在时间n，U（n）个不知情的博主中的一小部分没有注意（比如说，因为他们累了或睡着了）。那么，我们如何在方程中反映这一点呢我们在下面提出一个答案，然后我们提供理由。MODEL 2（SPIKE M）.我们可以用下面的公式来捕捉博客的周期性行为ACM Transactions on the Web，卷。号112、第十一条，公布日期：2017年4月社交网络十一··==−−=--=关于我们.2Pp<$B（n+1）=p（n+1）·U（n）· <$B（t）+S（t）·f（n+1−t）+<$.n..ΣΣ（七）t=nbp（n）=1−1Pa.sin。2π（n+Ps）π+1π，（8）其中U（n）、S（t）和f（n）在模型1中定义。理由。该模型与SPIKE M-BASE相同，但增加了周期因子p（）。这反映了博客作者们降低了他们的活动的事实（例如，在晚上）甚至完全停止这个想法是U（）是可用于感染的受害者的计数在正常情况下，每个受害者-攻击对都会导致一个新的受害者;然而，由于受害者没有完全注意（累了/睡着了），攻击就不会那么成功，因此我们用p（）周期函数来按比例分配它们：-P p代表周期（例如24小时）。-Ps 代表相移：如果活动高峰在中午，周期为Pp24小时，则Ps18。Pa取决于波动的幅度，具体地说，它给出了非工作时间（比如午夜）与高峰时间（比如中午）的相对值。因此，如果P为0，我们就没有涨落。3.4. 分析：指数上升和幂律下降图2显示了图1中模式C1的SPIKE M的行为分析结果。具体而言，它显示了原始时间序列数据（以灰色圆圈显示）以及SPIKE M（红线）和SI（蓝色虚线）的拟合结果。我们可以观察到其上升模式是指数的，而下降模式服从幂律。这是可取的，因为这种行为似乎在真实数据中普遍存在令n模式表示波A_B（）达到其最大音量的时间滴答（即，nmodeargmax B（n））。n上升图是指从出生时间n b到n模式（以及反转时间abs（n n模式））的值的图。下降图的定义类似：活动Δ B（）与从峰值n开始的延迟n模式。如图2所示，下降部分存在幂律，上升部分的指数形状然而，传统的SI模型，如预期的那样，表现出指数行为的上升和下降部分。3.5. 学习参数我们的模型由一组七个参数组成：θN，β，nb，Sb，<$，Pa，Ps。给定在时间tick n（n1，...，nd），我们使用Levenberg- Marquardt（LM）方法[Levenberg1944]来最小化误差之和LM算法可以在最小二乘意义下解决非线性函数极小化问题为了学习模型参数集θ，我们最小化由原始活动量和预测活动量之间的欧几里得距离测量的预测误差ndθ←arg minD（X，θ），D（X，θ）=（X（n）−θ B（n））2，（9）其中，X是持续时间nd的原始序列，并且WEB（n）是给定一组参数θ的时间n处的估计感染计数。ACM Transactions on the Web，卷。号112、第十一条，公布日期：2017年4月θn=1十一Y. Matsubara等人====·=··=-4. 模型分析和扩展在本节中，我们从理论上分析了我们提出的模型，并提供了几个重要的观察和扩展。4.1. 关于SPIKE M正如我们在第1节中提到的，SPIKE M最重要的性质之一是统一的力量。具体地，SPIKEM（即，SPIKE M-BASE）包括几个基本的非线性流行病学模型（例如，SI和SIR）作为特殊情况。我们的想法是，我们改变感染概率f（τ）β τ−p与感染后的时间τ。例如，典型的SI模型具有恒定的传输（即，感染）速率β，然后所有节点最终都将被感染。因此，我们有以下引理。4.1. blog 如果影响指数p = 0，则S PIKE M与SI模型相同，其中我们具有随时间的恒定传输概率（即， f（τ）= β·常数）。易感染-感染-恢复（SIR）模型具有感染率β和治愈率δ，其中的每一个描述了每个状态的转移概率（即，从易感到感染，以及从感染到康复）。更具体地说，愈合率δ定义了每个时间刻度愈合的恒定概率，每个受感染的节点都暴露于此例如，如果δ0，则没有人会恢复，并且模型对于每个时间滴答具有恒定的传输速率β（即，它与SI模型相同）。如果δ1，每个被感染的节点都会立即恢复--也就是说，模型对每个节点都有一个单脉冲传输β·pulse（1），与我们的传染性函数完全相同其中指数p=∞（即，f（τ）=β·τ−∞=β·pulse（1））。4.2.如果影响指数p=∞且愈合率δ= 1，则S PIKE M表现出与SIR模型相同的行为，其中我们在时间tick τ = 1处具有单个脉冲传输（即， f（τ）= β·脉冲（1））。4.2. SPIKE M的阈值条件给定一个社交网络和一个全新的谣言（例如，（一部新上映的电影），我们能确定谣言会消失还是很快消失吗？换句话说，如果有一个新的、未知的谣言，我们怎么能猜测整个社区会立即陷入一片哗然，还是只是把它当作毫无意义的信息而忽略呢？我们现在提供SPIKE M起飞熄灭条件的阈值THEOREM 4.3（SPIKEM TAKE-OFF条件）。 给定一个由N个博主组成的网络，传染性衰减函数f（τ）β τ −p的指数为p（p <1），其中β是感染的强度，如果SPIKEM满足以下条件，它将起飞：s= Nβ·n（p）≥ 1。0，（10）其中，f（p）是黎曼zeta函数。P屋顶。考虑一个人/博客在时间τ0被感染。在时间τ1（即，第一次爆发），这个博主会感染Nβ1−p个相邻的博主。类似地，在时间τ2，他或她感染了Nβ2−p个博主。3因此，被第一个博主感染的博主总数为s= Nβ·1 −p+ Nβ·2 −p+ Nβ·3 −p+···+Nβ·τ −p+.（十一）3更具体地说，在时间τ=2时，它是（N-Nβ）β·2-p，但当β1时，我们可以丢弃O（β2ACM Transactions on the Web，卷。号112、第十一条，公布日期：2017年4月社交网络十一.p==≥=≥=-==-=·≤ ≤ =∞===·=∞ ∞ =={··}==τp图3.SPIKEM起飞条件的图示：它显示了我们阈值的散点图（即，Nβ·N（p））与足迹（即，每个尖峰的最大值，即，maxB（n））。我们改变条件0 ≤Nβ·n（p）≤ 2，影响指数p= 1。五二0，...，∞.请注意，每个点对应于每个尖峰，临界点完全符合我们的条件：s = Nβ·n（p）= 1。0.换句话说，把前面所有的计数加起来，我们有∞s=Nβ·τ−=Nβ·τ（p），（12）τ=1其中，ε（p）是Riemannzeta function（i. 例如， （p）=.∞τ11）。 如果s小于1，则为e。0,这意味着第一博客作者不能感染足够多的人（即，在他或她的社区中，不止一个人，因此新闻/谣言消失了，没有受到任何关注。类似地，如果在时间τ=0时有多个受感染的博主，则每个博主需要感染多于一个邻居（即， s≥ 1。0）满足起飞条件。行为分析。图3显示了阈值分析模拟结果。它显示了阈值与足迹的散点图，即起飞条件（即，sNβ（p））与每个尖峰的峰值位置（即，maxB（n））。我们改变感染率β与固定的人口N104，使我们有条件0s2，有几个影响指数p 1。五二0，...，。例如，红点对应于斜率为p1的尖峰。5.在图3中，正如我们预期的那样，所有尖峰中的感染足迹在s1处突然跳跃。我们还应该注意到，这个条件涵盖了基本SIR模型的条件。众所周知，传统的SIR模型存在一个流行阈值Nβ/δ1 [Hethcote2000]。 在图3中，绿点显示了影响指数为p的封装（此处为p（）1. 0），这相当于具有愈合率δ 1的SIR模型。0.此外，请注意，SI模型没有固有的流行阈值，因为所有节点最终都会被感染。在图4中，我们给出了特定参数设置（N）的几个结果 两千约，β2 10−4左右）。该图显示了线性-线性（左列）和对数-对数（右栏）刻度。我们固定了其余的参数，即nb0、< $0、Pa0，B（0）1，p 1。5.图4（a）显示了S PIKE M的行为，其中我们将总种群N从2，000变化到5，000，具有固定的感染强度β，而图4（b）显示了β的结果210 - 4，...，510 −4，人口N固定两千。应该注意的是，如果条件成立（即，s 1。0）;否则，它会很快消失，如图4（a）中的蓝色箭头所示。ACM Transactions on the Web，卷。号112、第十一条，公布日期：2017年4月十一Y. Matsubara等人=≥·=图四、 行为分析：特定设置的几个峰值。我们将总人口N从2000变化到5000，将感染率β从210−4变化到510−4，其中nb0、 <$0、Pa 0、B（0）1的值保持不变我们尝试用固定的β（a）改变N，用固定的N（b）改变β，以及改变N和β（c）以固定条件s2。3.如果条件成立，SPIKEM总是起飞（即，s1）;否则，它会很快消失，如（a）和（b）中的蓝线所示ACM Transactions on the Web，卷。号112、第十一条，公布日期：2017年4月社交网络十一. ..Σ.=t=1t=1j=1- 我们假设新事件在时间tickn发生，并且Si=1blogger（s）立即−B和（b）中的至少一种。图4（c）显示了另一种特殊情况，其中我们改变参数N和所以我们有固定的条件s = 2。3.4.3. 模型扩展：一般任意图到目前为止，我们已经看到了SPIKE M在团网络中的行为，其中所有节点（即，博客作者）潜在地连接到所有其它节点。下一个问题是：给定一个由N个博客组成的任意图，博客活动将如何随着时间的推移而演变？设A是任意N个节点的图的邻接矩阵（即，博客），让i（n）是节点i在时间n被感染/通知的概率。我们引入了一个新的模型，SPIKE M-G，它可以描述任意图中的信息扩散动力学MODEL 3（SPIKE M-G）。我们可以用以下等式在任意图网络A中生成博客的峰值：n NIi（n+1）=（1−Ii（n））·Aji·t=1j= 1NB（n+1）=i=1U（n+1）=U（n）−B（n+1）（15）在初始条件n_id（n b）= 1。0，U（0）=N，其中sid是起始节点/blogger的索引。理由。我们有以下内容：- 邻接矩阵A代表每个节点/博客对之间的连接这里，如果邻接矩阵A是团（即，Jiang，jiang. -Ii （n）描述节点i在时间n被感染的累积概率，即，Ii（n）=.n其中0≤Ii（n）≤Ii（n）≤1。- 项（1Ii（n））示出了节点i保持未被通知的概率（即，可用于感染）。- 这是总结n .N （Aji·<$Ij（t） ·f（n+1−t））表示累积刺激，其中N在时间tickn来自邻居节点的传播效应的强度，并且其被设置为[0， 1]。- 我们可以计算出blog B（n）（在时间tickn）通过求和每个节点的概率（即，例如， B（n）=.N I（n））。这里，sid是节点/blogger ID，在时间tick北湾4.4. 实时监控信息扩散在许多基于Web的服务中（例如，博客、新闻和Twitter），我们观察到每次滴答时大量例如，Twitter生成数百万个事件条目（例如，标签）每小时。从这个庞大的在线事件集合中，网站所有者可以监控日常活动模式，发现信息传播的爆发或峰值，并预测接下来的一周，以帮助设计广告。ACM Transactions on the Web，卷。号112、第十一条，公布日期：2017年4月对于节点i节点/博客。在这里，累积的刺激显示了十一Y. Matsubara等人=--关于我们关于我们图五. 图为SPIKE STREAM。给定事件流X，其仅需要单次扫描来检测SPIKE M段并报告每个切割点（即，起始位置：nm，子序列长度：lm）和模型参数集θm。这里，Xc=X（ns：ne）是长度为lc的当前窗口的子序列。分析这些日志时的一个大挑战是以非常高的日志记录率处理如此大量的数据。此外，在实践中，现实生活中的事件流包含不同持续时间的各种类型的扩散模式，例如哈利波特电影系列的多个尖峰，正如我们稍后在图18（d）中看到的那样。换句话说，我们需要识别事件流中的任何突然中断，并立即识别当前的时间序列模式，以便我们可以在任何时间自适应地预测/理解当前的扩散动态。那么，我们如何处理这个问题呢我们的SPIKE M模型能帮助我们解决这个问题吗？理想情况下，我们希望解决以下问题。问题3（实时监控信息融合）。 给定数据流在线用户活动：X X（1），X（2），...，X（n），.. . ，其中n是当前的时间刻度，找到具有信息扩散过程特征的片段，增量和快速-也就是说，我们希望- 识别X中与SPIKEM模型匹配的所有序列，- 找到切割点（即，起始位置nm和长度lm），以及- 估计每个子序列的模型参数集θm我们方法背后的主要思想。我们提出了一个快速，单路径算法，即SPIKE STREAM。假设我们有一个活动量X的半无限序列（例如，博客帖子/主题标签的数量），例如，X X（1），X（2），.，X（n），.. . ，其中n是最近的值。 给定一组新到达的事件，每个时间刻度1，2，.，n，...，我们的算法报告所有合格的连续性（即，SPIKE M段），同时丢弃冗余信息（例如，背景噪声）。此外，请注意，我们可能会检测到非常短且意义不大的尖峰序列（例如，不到半天的持续时间），但这通常不足以用于许多实际应用。因此，我们引入子序列匹配的最小长度lc，使我们能够忽略这样小的连续性。图5说明了算法的工作原理。给定一个事件流X，它提取最近到达的事件集X cX（ns：n e）的窗口大小l c。在这里，ns和ne表示子序列Xc的开始和结束位置，我们将Xc称为当前窗口。对于每个不相交的窗口Xc，SPIKE STREAM尝试拟合SPIKE M模型，然后找到最佳段（如红线所示）。最后给出了最优解nm，lm，θm，（即，其起始位置、子序列长度和模型参数集）。ACM Transactions on the Web，卷。号112、第十一条，公布日期：2017年4月社交网络十一==--===− +θ=−θm==联系我们--==-==-‹N≤‹‹=N|‹‹算法1：SpikeStream1：输入：（a）在时间tickn的新事件X（n）和（b）先前状态sc2：输出：限定子序列n m，l m 及其参数集θm（如果有）3：如果（nmodlc）0，则4：/* 对于窗口长度lc的每个不相交子序列Xc */5：n snl c1;//ns：起始位置6：n en;//ne：结束位置7：XcX（ns：ne）;//Xc：当前窗口8：/* 计算Xc的似然值 */9：//（1）视为背景噪声，从ns10：L<$= N（X c|μ <$，σ 2）;//<$={μ <$，σ 2}：μ <$=均值（X c），σ 2=方差（X c）11：//（2）将其视为新生穗，从ns12：{θ，θB}=SPIKEM-FIT（Xc，θB）//θB：初始SPIKEM参数集13：L c=N（X c−B|μθ，σ2）;//θ的Likewise值14： 如果scSpikeM，则15：θm，θBSPIKEM-FIT（X（nm：ne），θm）; //使用X（nm：ne）进行16：lm ns nm;//lm：当前SPIKEM窗口的长度17：//（3）Xc属于连续尖峰θm，从nm开始18：L m=N（X c−N B（l m：l m+l c）|μθm，σ2）;//θm的可能值19：如果Lc>Lm或L<$>Lm，则20：//背景噪声或新生尖峰-终止当前尖峰21：报告nm，lm，θm; //报告最优子序列22：如果L<$>Lc，则23：scbackground noise; //切换到背景噪音24：其他25：nm ns;θmθ; //新生儿尖峰转换为尖峰M26：如果结束27：如果结束28：其他29：如果Lc>L<$，则30：// New-born spike-switch到SpikeM31：scSpikeM;nm ns;θmθ;32：如果结束33：如果结束34：如果结束SPIKE STREAM假设事件流中的每个不相交窗口都有两个隐藏状态，即，(a) background_noise：独立的活动趋势（例如，随机噪声或小于Ic持续时间的短尖峰，如图5中的蓝线所示）。我们将此状态视为高斯分布<$（即，（μm，σ2））。(b) SpikeM：具有SPIKEM的特征的子序列/片段（即，口碑现象，如图5中的红线所示）。如果当前窗口Xc属于SpikeM，则算法保持当前子序列的起始位置nmnm ns）。如果当前窗口状态从SpikeM切换到background_noise，或者有一