英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
回到过去：部分观察的级联扩散网络中的源识别
摘要：当一条恶意信息在信息传播网络中泛滥成灾时，我们能否确定最初将其引入网络的源节点并推断出该恶意信息产生的时间？这样做对于减少恶意信息的传播并减少潜在的损失至关重要。这是一个十分具有挑战性的问题，因为通常只能观察到不完整的传播轨迹，根据不完整的传播轨迹展开，回溯到过去来查明源头。在本文中，我们通过开发一个两阶段的框架来解决这个问题，该框架首先学习基于历史扩散迹线的连续时间扩散网络模型，然后通过最大化所学知识下迹线的可能性来识别不完整扩散迹线的来源。在对大型综合数据和真实数据进行实验后表明，我们的框架可以有效地“回到过去”，并且比以前的最新技术更准确地精确定位源节点及其启动时间。
- 引言
2014年9月，在网上发布了数百种来自各行各业的名人的私人照片，这些照片主要由女性组成，并且经常包含裸露内容，后来由用户在网站和社交网络（例如Imgur1、Reddit2和Tumblr3 [Kedmey,2014]）上进行传播。经过在发散路径上的手动追踪上的一番努力后，调查人员发现，图像板4chan4是罪魁祸首，最初在其在8月31日发布这组照片，即使照片在发布不久就已从网站上删除。私人图片的泄漏引发了全球范围内有关互联网上隐私和公民自由状况的广泛讨论和辩论[Isaac,2014]。
1http://imgur.com/
2http://www.reddit.com/
3https://www.tumblr.com/
4http://www.4chan.org/
考虑到历史上不完整的扩散痕迹，我们是否可以自动查明此类恶意信息源的身份以及它们首次发布恶意信息的时间？ 在许多场景中，解决这一源识别问题引起了人们的极大兴趣[Lappas等，2010]。 例如，找到引起谣言的人可以减少虚假信息，识别疾病传播中的患者零点可能有助于理解和控制流行病，或者推断特洛伊木马或计算机蠕虫最初发布的位置可以提高计算机网络的可靠性。
相关工作：直到最近才研究了寻找扩散迹线的来源（也称为级联）的问题[Lappas等，2010； Shah和Zaman，2010； Aditya Prakash等，2012； Pinto等，2012]。但是，大多数以前的工作都假设观察到了级联的完整稳态快照，换句话说，我们知道哪些节点被感染，但不知何时被感染。 此外，先前的工作使用离散时间顺序传播模型，例如独立的级联模型[Kempe等，2003]或SIR模型的离散版本[Bailey，1975]，这些模型很难应用于真实世界的数据[Gomez -Rodriguez等，2011，Du等，2012，2013b，Zhou等，2013a，b]。
直到最近，Pinto等人[2012] 考虑一个相当一般的连续时间模型，并假设只观察到一小部分稀疏放置的结节，如果被感染，则观察到它们的感染时间。不幸的是，它们的方法要求观察到的节点之间的距离较大，因为它们使用中心极限定理通过高斯分布来近似感染时间。由于这在实际的社会和信息网络中很容易被违反[Backstrom等，2012]，因此我们发现其在此类网络上的性能不高，如第5节所示。
难题：先前的方法虽然失败了，但成功指出了源识别问题的几个挑战，接下来我们将通过一个玩具示例来说明这些挑战，如图1所示。
图1：谣言在社交网络中传播。 每个边缘的权重是谣言通过边缘所花费的时间。 实线的磁体边缘指示谣言传播的实际路径。 绿色虚线边缘是谣言传播的替代方式。 观察到了索菲娅和利亚姆的感染时间（红色正方形）；其余结节的感染时间被隐藏了（黄色正方形）。 算法如何发现雅各布是发起谣言的人？
-部分观察到的感染。即便不是不可能，也很难收集完整的传播轨迹，并在在线社交和信息网络中跟踪每个个体感染。由于需要开发可以（几乎）实时提供输出的方法而使该问题更加严重。例如，Spinn3r5只会定期抓取一部分博客； Twitter的流API提供了全部推文的一小部分（1％）[Morstat-ter等，2013]； Facebook用户通常保持其活动性和个人资料私密性[Sadikov等，2011]。因此，有必要开发出对丢失数据具有鲁棒性的方法[Chierichetti等，2011； Kim和Leskovec，2011； Sadikov等，2011]。我们的玩具示例通过考虑要观察的利亚姆和索菲亚的感染时间以及所有其他感染时间（隐藏或未观察到）来说明这一挑战。
-未知感染开始时间。在大多数现实世界场景中，恶意信息开始传播的确切时间是未知的，因此观察到的感染时间仅具有相对意义。在我们的玩具示例中，我们知道利亚姆被感染的时间比索菲亚晚了5，但实际上我们没有观察到雅各布的感染引发了传播，而雅各布的感染引发了传播，这段时间已经过去了多少时间。
-不确定的传输延迟。信息在社会和信息网络上的传播是一个随机过程。因此，我们需要考虑概率传输模型来捕获不确定性。例如，我们的玩具示例说明了特定谣言的传播，因此考虑了一组固定的边缘延迟（例如，谣言从Sophia传播到Ethan花费了5个时间单位）。但是，边缘延迟是随机的，并且可能对每个特定的边缘延迟都是不同的 谣言（例如，不同的谣言从Sophia传播到Ethan所花费的时间可能不超过5倍）。 边缘延迟密度或传输密度可能取决于诸如谣言的内容或用户的影响之类的参数。
5http://spinn3r.com/
—未知的感染路径。在大型的现实世界网络中，我们经常会遇到大量潜在的路径，这些路径可能解释了来自源节点和网络中任何其他节点的谣言的传播。实际上，潜在路径集随网络规模和网络密度成指数增长，甚至简单地计算路径数量也需要非平凡的方法[Gomez-Rodriguez和Scholkopf，2012a，b，Du等，2013a]。 例如，在我们的玩具示例中，利亚姆可以通过奥利维亚（Olivia）或艾玛（Emma）来了解谣言。
我们的方法：为了解决这些挑战，我们提出了一个两阶段的可扩展框架：我们首先学习基于历史扩散迹线的连续时间扩散网络模型，然后通过在学习模型下最大化其可能性来确定不完整扩散迹线的来源。我们框架的关键思想是从图形模型的角度来看问题，并将问题转化为最大似然估计问题，为此，我们可以通过对目标的重要采样近似和利用该问题的结构优化程序来非常有效地找到最佳解决方案。此外，对于具有指数分布的边缘传输密度的网络（以前用于信息传播建模）[Gomez-Rodriguezet 等。2011]，我们证明目标是关于源的感染时间的分段单峰函数，并开发出更有效的方法搜索程序。
对于合成数据和真实数据，我们都显示出框架可以有效地“追溯过去”，并且比其他方法更准确地指出源节点及其感染时间。
- 我们的框架
我们解决源识别问题的框架包括两个主要阶段：首先学习基于历史扩散迹线的连续时间扩散网络模型，然后在学习的模型下通过最大化扩散迹线的来源及其起始时间来识别源扩散问题。我们通过回顾在Gomez-Rodriguez等人[2011]，Du等人[2013a]中引入的社交网络中级联数据的连续时间生成模型来开始我们的展示。
2.1级联的连续时间模型
给定定向联系网络, G =(upsilon;,ε),有N个节点，扩散过程始于受感染的源节点s，最初在时间 开始某种传播（想法，谣言或恶意信息）。传播从源头沿着它的外向边缘传播到它的直接邻居。每次通过边缘传输都需要随机发散时间tau;，该时间由密度随时间(tau;;alpha;ji)得出，该参数由传输速率alpha;ji设定。 然后，被感染的邻居将感染传播给他们各自的邻居，然后继续进行该过程。假设传输时间是独立的并且是非负的，换句话说，节点不能被后来被感染的节点感染; 如果tau;lt;0，(tau;;alpha;ji)=0。 此外，在整个扩散过程中，受感染的节点仍保持感染状态。 因此，如果一个节点被多个邻居感染，则只有第一个感染该节点的邻居才是真正的父节点。
扩散过程留下的时间轨迹通常称为级联。 一个级联的N维向量t：=（t1，...，tN）记录节点被感染的时间，这样，isin;[0，infin;]，其中T是观察窗口的截止点，infin;表示节点在观察窗口期间没有被感染。 但是，如上所述，在许多情况下，我们仅观察到感染节点的子集O，而所有其他节点H的状态却未发现（我们假设源节点为sisin;H）。 然后，我们的目标是从被感染节点O的子集的感染时间 中找到级联的来源。图1说明了观察到的数据。
2.2级联似然
根据级联连续时间模型中提出的条件独立性关系，级联的完全似然性（对于观察到的节点和隐藏节点而言）分解为：
（1）
其中pi;i是由有向图G定义的i的父节点的集合。对于受感染的节点s，Gomez-Rodriguez等人[2011] 表明可能性可以进一步写成：
,
其中 是分布函数， 是累计函数， 是风险函数，或者说是瞬时感染率，我们将重点研究魏布尔分布 ，因为它们已被证明可以很好地拟合现实世界的扩散数据[Duet al。，2013b]。在这种情况下， ，其中是控制密度形状的超参数。该族包括许多众所周知的特例，例如指数分布或瑞利分布，它们也已被用来对信息网络上的信息传播进行建模[Gomez-Rodriguez等，2010，Du等，2013b]。
不幸的是，要使用等式1，必须完全观察到级联中的所有感染节点。 如果仅观察受感染节点的子集 ，则不完全级联的可能性计算如下：
（2）
它们实质上使乘积空间 上所有隐藏节点H的时间边缘化。 为了简化符号，在本文的其余部分中，我们将省略积分的域。
2.3学习扩散网络
我们的框架基于这样的假设：有可能记录足够多的历史级联C，以便发现网络中所有节点的存在，以推断网络结构以及模型参数,{}。我们注意到没有必要记录覆盖所有节点和边缘的级联，但是每个级联必须充分观察到足够长的时间段。此外，所有级联共同需要覆盖整个扩散网络。 在[Daneshmand等 ，2014]所述的精确条件下，可以使用 正规化的最大似然估计程序来推断连续时间模型的参数。
2.4级联源识别问题
给定一个学习的扩散模型，我们的目标是找到一个不完整级联的源节点，以使不完整级联的对数似然性最大化。 因此，我们旨在解决：
，（3）
其中 在等式2中定义，我们假设 。如果我们观察到几个独立不完全的级联D，全部由同一源节点触发，我们将最大程度地提高它们的联合可能性：
，（4）
- 近似目标函数
要使我们的框架在实践中有用，还需要解决两个技术挑战。 首先，由等式2给出的不完全级联的可能性是连续域上的一个困难的高维积分问题，我们通过基于重要性采样的近似算法克服了这一困难，这将大大简化积分。 其次，等式4中源时序上的内环最大化是非凸的。我们通过设计一种有效的算法来解决此问题，该算法通过利用问题的分段结构来找到全局最大值。
3.1重要性
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[235731]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
