4190SIR-Hawkes：将流行病模型和Hawkes过程链接起来，以模拟有限人口中的传播0Marian-Andrei Rizoiu澳大利亚堪培拉ANU和Data61 CSIRO0Swapnil Mishra澳大利亚堪培拉ANU和Data61 CSIRO0Quyu Kong澳大利亚堪培拉ANU和Data61 CSIRO0Mark Carman澳大利亚墨尔本莫纳什大学0Lexing Xie澳大利亚堪培拉ANU和Data61 CSIRO0摘要0在在线信息传播建模的统计工具中，流行病模型和Hawkes点过程都是受欢迎的选择。前者起源于流行病学，将信息视为传播到在线用户群体中的病毒传染。后者源于地球物理学和金融学，将个体行为视为连续时间中的离散事件，并根据事件序列的自激励性质调节事件的速率。在这里，我们建立了这两个框架之间的新颖联系。即，在扩展的Hawkes模型中，事件的速率与易感-感染-康复（SIR）模型中的新感染速率相同，而在Hawkes过程中，康复事件是未观察到的。这个结果为将SIR的工具应用于Hawkes以及反之打开了道路。它还导致了HawkesN，这是Hawkes模型的一个泛化，考虑了有限的人口规模。最后，我们根据随机SIR的方法推导了HawkesN的级联大小分布。这样的分布为受欢迎程度的普遍不可预测性提供了细致的解释：扩散级联大小的分布往往具有两个模式，一个对应于大的级联大小，另一个接近于零。0ACM参考格式：Marian-Andrei Rizoiu，Swapnil Mishra，QuyuKong，Mark Carman，LexingXie。2018年。SIR-Hawkes：将流行病模型和Hawkes过程链接起来，以模拟有限人口中的传播。在2018年WWW会议上，2018年4月23日至27日，法国里昂。ACM，纽约，纽约，美国，10页。https://doi.org/10.1145/3178876.318610801 引言0研究界长期以来一直意识到口碑现象在信息传播和塑造在线和离线环境中的用户行为方面的重要性。本文研究了信息在在线传播中的传播机制，即它是如何从个体传递到个体的。目的是将个体行为与集体层面的度量，如受欢迎程度或名声，联系起来。0本文发表在知识共享署名4.0国际（CC BY4.0）许可下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW2018，2018年4月23日至27日，法国里昂，© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31861080这项工作解决了关于在线传播建模的两类方法的三个悬而未决的问题：流行病模型和Hawkes点过程。第一个悬而未决的问题涉及这两个模型之间的关系。流行病模型起源于流行病学领域，将信息视为在在线用户群体中传播的病毒传染；Hawkes模型主要用于金融和地球物理学领域，将信息的个体广播视为随机点过程中的事件。尽管这两个模型起源于不同的学科，但它们都描述了离散事件的随机序列；它们之间是否存在内在联系？第二个问题是设计更具表现力的传播模型。Hawkes过程是社交媒体过程的事实上建模选择，主要是因为它们可以轻松定制以考虑社交因素，如用户的影响力[14,44]、社交记忆的长度[23,29]和内在内容质量[21]。我们能否借鉴流行病模型的概念来设计一个更适合描述在线传播的Hawkes过程？第三个问题涉及预测级联的最终规模，这直观地反映了底层信息的受欢迎程度。以前的研究[23,28, 29,44]预测了未来受欢迎程度的单一值，然而众所周知，受欢迎程度很难预测。许多随机因素导致预测的高方差[37]。我们能否计算规模分布，以解释高方差和不可预测性？在这项工作中，我们通过首次揭示流行病模型和点过程之间的联系来回答以上三个问题，并在三个大型公开可用的转发级联数据集上进行了理论和实证验证。我们通过研究以前未探索的易感-感染-康复（SIR）流行病模型[18]与Hawkes过程之间的联系来回答第一个问题。连接的关键在于对口碑过程的建模：我们将一个用户向另一个用户的每个新广播视为Hawkes中的一个事件，并类比于SIR中的新感染。从这个观察出发，我们证明了扩展Hawkes模型中的事件速率与SIR模型中的新感染速率相同，这是通过对Hawkes过程中未观察到的康复事件进行期望的结果。这一结果具有重要意义，因为它表明为一种方法开发的工具可以应用于另一种方法。为了回答第二个问题，我们提出了HawkesN，这是Hawkes模型的一个扩展，考虑了有限的人口规模。最后，我们根据随机SIR中的方法推导了HawkesN的级联大小分布。这样的分布为受欢迎程度的普遍不可预测性提供了细致的解释：扩散级联大小的分布往往具有两个模式，一个对应于大的级联大小，另一个接近于零。0主题：社交网络分析和网络图算法，WWW 2018年4月23日至27日，法国里昂λ(t) = µ +tj 1 时，P(Nt+h = n + m | Nt = n) = o(h)0当m = 0时，P(Nt+h = n + m | Nt = n) = 1 - λ(t)h + o(h) (1)0h = 0; N t是与点过程相关的计数过程，即一个随机变量，它计算时间t之前（包括t）的事件数量。Hawkes过程[16]是一个自激励点过程，其中每个先前事件发生在时间t j < t时，在时间t - tj产生新事件的速率为ϕ(t - tj)，也称为Hawkes过程的核函数。Hawkes过程的事件率是一个依赖于先前事件时间的随机函数，定义为：0该模型描述了以下过程[20]：新事件以背景速率µ进入系统；或者它由先前事件以相应核函数的速率生成。02.2 SIR模型0易感-感染-康复（SIR）模型定义了三类个体（也称为隔间）：易感染个体，当前感染个体（因此具有传染性）和康复个体（不再具有传染性）。SIR模型描述了以下过程：当一个易感染个体遇到一个感染个体时，前者以速率β被感染；感染个体以恒定速率γ康复。确定性SIR模型。在确定性SIR模型中，个体及其分配到三个隔间的情况并不被观察到。每个隔间的大小的时间动态由以下常微分方程控制[1]：0S ( t ) , I ( t ) 和 R ( t )是确定性函数，分别表示易感染、感染和康复人群在时间t的大小；N= S ( t ) + I ( t ) + R ( t )是总人口大小。SIR模型做出了一些假设。首先，它假设人口是均匀的，个体与任何其他个体均匀随机相遇。其次，它假设所有速率都是恒定的：感染率β和康复率γ。第三，它假设人口没有出生和死亡，即整个流行病的展开过程中N保持不变。当流行病的速度远远超过人口变化的速度时，这个假设成立，例如，一个平均转发扩散只持续几分钟，而Twitter上用户的预期活动持续数年。0研究方向：社交网络分析和Web上的图算法 WWW 2018，2018年4月23日至27日，法国里昂1230.51,(7)4210随机SIR。已经提出了几种随机形式的SIR模型[1]，它们模拟独立同分布的代理行为。代理的行为由Eq. (3) -(5)中定义的相同一组整体规则描述，并且具有上述相同的假设[4]。SIR的一种随机形式是双变量点过程表示[39]，其中发生两种类型的事件：感染事件和康复事件。SIR过程中的第j个感染个体在时间t I j被感染，并在时间t Rj康复。因此，每个感染事件对应一个康复事件。S t，I t和Rt是取整数值的离散随机变量。它们是S(t)，I(t)和R(t)的随机对应物。Eq. (3) -(5)可以写成随机微分方程，但为了方便起见，我们在本文的其余部分将继续引用Eq. (3)- (5)。我们将定义恢复时间（即个体j的传染性时间）为：τ j = t R j - t I j。根据Eq.(5)，恢复时间服从参数为γ的指数分布，感染平均持续1个单位时间0γ个时间单位。令C t为感染过程的计数过程，Rt为恢复过程的计数过程。注意，C t = N - St是发生的感染总数（无论它们是否仍然具有传染性），它与It（时间t的传染性数量）不同。令Ht为时间t之前的双变量流行病过程的历史，即H t = {t I 1，t I2，...，t R 1，t R 2，...}。可以证明新感染率λ I ( t )和新恢复率λ R (t )为：0λ I ( t ) = β 0N I t ; λ R ( t ) = γI t . (6)0我们对前述陈述进行了概述的证明。Yan [39]推导出给定Ht的时间t的新感染的概率为：0P ( C t + δt - C t = 1 |H t ) = β S t0N I t δt + o ( δt)0P ( C t + δt - C t > 1 |H t ) = 00P ( C t + δt - C t = 0 |H t ) = 1 - β S t0N I t δt + o ( δt ),0根据公式（1），新感染过程是一个强度为β S t的时间点过程0N I t . λ R ( t )的推导类似。图1以双变量点过程的形式展示了SIR的实现：五个感染事件发生在时间t I 1，..，t I5（以红色显示）；五个恢复事件发生在t R 1，.. t R 5（以蓝色显示）。图1的中间面板显示了随时间变化的感染人口It的大小。每个新的感染事件增加了I t ，每个新的恢复事件将I t减少了一个。图1的底部面板显示了相应的新感染和新恢复率。最初，λ I ( t )显著高于λ R ( t )。随着易感个体St的减少，术语S t0方程（6）中的N抑制了λ I ( t )，在第五次感染后变为零（S t = 0，t≥ t I 5）。最后一个感染个体恢复后，新的恢复率也变为零（I t =0，t ≥ t R5）。确定性和随机SIR之间的联系是随机过程的平均行为渐近地接近确定性过程的行为[1，39]。确定性和随机人口规模之间的联系是S (t ) = E H t [ S t ]，I ( t ) = E H t [ I t ]和R ( t ) = E H t [ R t ][1]。我们自己模拟的两种变体的结果在在线补充材料[25]中呈现。0时间0感染过程0恢复过程0传染性数量0时间0时间02 2.5新感染率0新的恢复率0图1：作为双变量点过程的SIR的示例：感染过程和恢复过程。（顶部面板）第j个个体在时间t I j被感染，并在时间t R j恢复0t R j。恢复时间τ j = t R j - t Ij是个体保持传染性的时间段。（中间面板）随时间变化的感染人口I (t )的大小。（底部面板）SIR参数N = 5，β = 2，γ = 0.5的感染率λ I( t )和恢复率λ R ( t )。0正如在第3.2节中将详细阐述的那样，双变量点过程SIR的形式提供了与Hawkes点过程的联系。03将流行病模型与Hawkes过程联系起来0我们首先提出了HawkesN，这是Hawkes过程在有限人口中的推广（在第3.1节中），并展示了HawkesN与SIR流行病模型之间的联系（在第3.2节中）。03.1 HawkesN：有限人口中的过程0我们将Hawkes模型[16]推广到考虑有限人口规模的情况。直观地说，级联不仅遵循自激励的口碑传播，而且还受到相关社区规模的限制。引入有限人口规模N的效果是，时间t的事件率受到可用人口的调节。据我们所知，以Hawkes模型来建模社会过程的先前工作都没有考虑有限的基础人口。HawkesN中的事件率函数定义如下：0λH(t)=�1−Nt0N0� 0µ+0tj t) =�t Ij t).(9)ET�λI (t)� (6),(9)=ETβ StN�t Ij t)=�t Ij t)�=�t Ij t)r(ζ )dζ=�t Ij 0。我们使用指数核函数来描述HawkesN：0ϕ(τ)=κθe−θτ（8）0κ是一个缩放因子，θ是指数函数的参数，用于模拟社交记忆的衰减。指数核函数是文献中的常见选择[2, 8, 11, 23, 29, 43,44]。Hawkes也使用了其他核函数，包括幂律函数[6, 17, 19,23]和瑞利函数[34]。使用非指数核函数的HawkesN留待将来研究。03.2 将HawkesN和SIR联系起来0我们现在介绍我们的主要结果，定理3.1，它将随机SIR和HawkesN过程联系起来。直观上，当建模信息扩散时，SIR和HawkesN都模拟了同样的现象：用户接触到扩散的内容，然后将其进一步传播给其他用户。在HawkesN中，每次新的广播被建模为一个新的事件，在SIR中被建模为一个新的感染。将HawkesN和SIR模型联系起来的关键是HawkesN中的事件和SIR中的新感染之间的概念上的相似性。在HawkesN中，过去的事件以速率ϕ(t)生成新事件，该速率在方程（8）中以指数时间衰减。在SIR中，一个感染个体j以βSt的速率感染易感个体。0在感染期间，N是具有参数γ（在第2.2节中讨论）的指数分布的持续时间τj的人数。0定理3.1. 假设参数为 { β , γ , N }的随机SIR过程中的新感染遵循强度为 λ I ( t ) 的点过程。假设参数为{ µ , κ , θ , N } 的HawkesN过程中的事件具有强度 λ H ( t )（方程7）。设 T = { τ 1 , τ 2 , . . . }是SIR中感染个体的恢复时间集合。 λ I ( t ) 在 T 上的期望等于 λ H (t ) ：0当 µ = 0 ， β = κθ ， γ = θ 。0注意， E T [ λ I ( t )] 和 λ H ( t )都是随机函数，因为它们依赖于随机感染时间 t I j（对于SIR）和随机事件时间 t j（对于HawkesN）。期望只消除了SIR中恢复时间 t R j的随机性。本节的其余部分证明了该定理。预期的新感染率。我们使用感染事件时间和恢复时间的指示函数来表示方程（6）中的 S t 和 I t ：0我们研究仅由感染事件 { t I j }组成的点过程。该过程中的事件率通过边际化恢复时间得到：ET λI (t) = 1 − CtNt Ij 00p ({ s, i - 1 }|{ s, i }) =0β N si + γi 0βs + Nγ, for i > 0. (12)0假设Σ中的状态按照1到|Σ|的顺序排列。我们定义大小为|Σ|×|Σ|的转移矩阵T=[t kl]，其中t kl = p(σ k = {s k, i k}|σ l = {s l, il})是从状态σ l 转移到状态σ k的概率。根据公式（12），我们得到：0t kl =0��0�0βs l + Nγ, s k = s l - 1, i k = i l + 1, i l > 0 Nγ0βs l + Nγ, s k = s l, i k = i l - 1, i l >0 1, s k = s l, i k = i l = 0 0,otherwise0注意，转移矩阵M中每一列j的总和等于1，因为它包含了从σl转移到其他状态的概率。概率状态向量和大小分布。设π为概率状态向量π∈R|Σ|×1，其中π的第l个位置给出了系统当前处于状态σl的概率。设π0=[0,..,0,1,0,..,0]为初始概率向量，其中值为1对应于初始状态˜σ，其他位置都为零。从π0开始，我们计算一次转移后的概率状态向量为π(1)=M×π0。π(2)=M2×π0给出了两次转移后的概率，π(3)=M3×π0给出了三次转移后的概率等等。由于在SIR实现中最多有N-1次感染事件和N次康复事件，系统保证在2N-1步后收敛[1]。在收敛时，除吸收状态外，π(2N-1)中的所有状态概率都为零。我们用P(s)表示π(2N-1)中状态{s,0}的值，其中s=0,1,...,N-I0。从初始状态˜σ开始，系统可以以概率P(s)完成任何吸收状态{s,0}。扩散的最终大小分布是随机变量N'=N-s的分布。0论文: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, FranceET[˜i] = ETl�j=11(tIj + τj > tl)l�j=1e−γ (tl −t Ij )(14)L(κ,θ, N) =n�j=1log λH �tj� −tn0λH (τ)dτ.(15) 0 [ 23]。我们通过最大化点过程的对数似然函数来估计剩余的HawkesN参数 { κ , θ , N } （参见在线补充材料 [ 25 ] 或 Daley 和 Vere-Jones[7, Ch. 7.2]）：0我们进一步详细说明积分项：∫ t n0表1：非有效 N 解的百分比和使用统计量 S 的检测准确性。0观察到的百分比 5% 10% 20% 40% 80%0非有效 N (SIR) 4% 0% 0% 0% 0% 非有效 N (HawkesN)56% 42% 37% 18% 0%0找到的有效N根44 58 63 82 100，使用S < 0 40 5763 82 1000方程（15）是一个非线性目标，对于每个模型参数都有一些自然的约束条件，即：θ > 0，κ > 0和N ≥ n。我们使用数学建模语言AMPL[10]，它提供了与连续优化工具的接口，包括自动梯度计算和求解器。我们选择Ipopt[33]作为求解器，这是文献中用于具有非线性目标的大型问题的常见选择。更多细节可以在在线补充材料[25]中找到。05.2 估计人口大小N0在这里，我们研究了人口大小N是唯一未知数的情况。目的是确定从数据中恢复N的难度。对于使导数为零的N值，是方程（15）中对数似然函数局部最大值的必要条件。我们写出对数似然关于N的导数：0∂L/∂N =0n �0(µ(t) + ∫tj0时，可以保证对数似然函数L随N≥n单调增加，且不存在有效的N解。估计N的困难。我们通过模拟来说明估计N的困难，并且我们表明这取决于级联中观察到的事件数量。从集合开始0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, France●00.10.55.02.03.04.0HawkesNSIRReal N (100)SIR Estimated N (102)N00.115010015020000.11000.20.40.60.81.02550751001254250SIR实现示例0SIRLL0时间0感染过程0康复过程0对数似然0导数对数似然0图4：（顶部面板）模拟的SIR过程实现示例，包含10个感染事件和10个康复事件。（中间面板）HawkesN（红色）和SIR（蓝色）的对数似然作为N的函数。（底部面板）对数似然关于N的导数。对于HawkesN，导数始终为正，对数似然单调增加，没有有效的N解。对于SIR，对数似然在102处达到最大值，接近模拟值N = 100。此实现的统计值S = 13.77。0根据观察到的级联百分比估计的N0观察百分比0估计的N0SIR估计的N 15%/85%置信区间（SIR）HawkesN估计的N15%/85%置信区间（HawkesN）真实N（100）0图5：使用HawkesN（红色）和SIR（蓝色）使用最大对数似然估计N的中位数和15%/85%置信区间。0参数 µ = 0, κ = 5, θ = 0.2, N =100，我们使用随机SIR模拟了100个实现。假设除了N之外的所有参数都固定，我们研究了在每个级联的逐渐增长的前缀上估计N的有效性和质量，其中包含了范围为[5%，100%]的所有事件的百分比。SIR在每个前缀中观察到感染和恢复事件，而HawkesN只观察到感染事件。我们实现了一个数值过程来找到N：我们将范围[0，200]分成1000个区间，并使用R中的uniroot在每个区间中数值搜索方程17的根。这是一个缓慢的过程，它提供了一个与之比较的基准真值统计量S。表1显示了有多少级联存在0表2：数据集概述：级联数量和推文数量；级联大小的最小值、平均值和中位数。0#级联 #推文 最小值 平均值 中位数0ActiveRT [28] 41,411 8,142,892 20 197 41 Seismic [44]166,076 34,784,488 50 209 111 News [23] 20,093 3,252,54950 162 900对于SIR（第一行）和HawkesN（第二行），N没有有效的解决方案。显示了5%、10%、20%、40%和80%的观察百分比。对于HawkesN，在观察到5%的事件后，56%的级联没有有效的N解决方案。我们观察到，当观察到级联的50%以上时，存在N的解决方案。然而，对于SIR，只有10%的级联在级联开始时没有有效的N，一旦观察到超过10%，所有级联都有有效的N解决方案。这表明在HawkesN中估计N比在SIR中更困难。表1的后两行显示了有多少级联有有效的N解决方案，以及其中有多少统计量S为负数。在观察到级联的5%后，S <0只误识别了4个有效解决方案（共44个），并且在观察到的百分比大于10%时识别出了所有有效解决方案。请注意，S是对数似然的下界，并且保证找到所有非有效解决方案。图4显示了一个具有10个感染事件和10个恢复事件的级联的示例。当使用HawkesN时，不存在N的有效解决方案，因为对数似然函数是单调递增的。当在SIR中观察到恢复事件时，N有一个接近真实值的可行解。这表明恢复事件的时间（在HawkesN中未观察到）包含了关于人口规模的信息。图5证实了这个结论，显示SIR即使在级联开始时也能正确估计N，而HawkesN需要观察级联的大约50%才能正确估计N。有关模拟和附加分析的详细信息，请参阅在线补充材料[25]。06 实验和结果0在本节中，我们研究了HawkesN在三个Twitter扩散数据集上的性能（在第6.1节中描述）。我们评估了HawkesN的泛化性能（在第6.2节中），并对级联大小分布进行了分析，并为感知到的受欢迎程度的不可预测性提供了一个新的解释（第6.3节）。06.1 数据集0我们使用了之前的工作中使用的三个Twitter转发扩散级联数据集。对于每个级联中的每个推文，我们都有关于转发的时间偏移和发布转发的用户的关注者数量的信息。ActiveRT数据集是由R
我的内容管理
展开
