Rumor Containment by Spreading Correct Information in Social Networks

 Abstract

  谣言可以通过社交网络快速传播并造成重大损失。为了控制谣言传播，传播正确的信息来抵消谣言的影响似乎比简单地通过审查或网络中断来阻止谣言更为合适。本文提出了一种竞争扩散模型，即单向状态转移线性阈值模型（LT1DT），用于对同一网络中两种不同类型的竞争信息传播进行建模。与其他个人信念一旦采用就不会改变的竞争性扩散模型不同，LT1DT 可以模拟一个人的行为，尽管最初受到谣言的影响，但在收到正确信息时可以改变他/她的想法。探讨了最大限度地减少社交网络中谣言传播的问题。提出了使用四种启发式方法对两个现实世界数据集进行的多次模拟。

I. INTRODUCTION

  随着过去二十年信息和通信技术的快速发展，人们积极利用网络获取信息、交流思想，甚至采用新产品。因此，大量的研究致力于分析信息、观点、社会行为、创新等的传播。此类研究可以帮助人们了解信息或观点如何在社交网络中传播以及如何说服个人遵循新想法或购买新产品。为了模拟这种传播，Kempe 等人。 [10]首先提出了两种主要的离散扩散模型，即独立级联模型（ICM）和线性阈值模型（LTM）。两种模型都由 G = (V, E) 表示的有向图组成，其中的弧与影响权重 wuv ∈ (0, 1] 相关联。在网络中，每个节点代表一个人或一个用户（因此在本文中，我们将可以互换使用节点、用户和个人），并且在给定时间可以是活动的（如果它已经采用了创新）或不活动的（如果它没有采用创新）

  最初，所有节点均处于非活动状态。在时间步 t = 0 时，节点的子集 S ⊆ V 被激活以启动扩散过程，而其他节点保持不活动状态。在 LTM 中，每个节点 v 被分配一个阈值 θv ∈ (0, 1]，该阈值代表节点被激活的不同倾向（如果其邻居激活）。一个不活动的节点 v 在时间 t 变得活跃，如果它的权重总和活跃邻居在时间 t − 1 时至少为 θv。

  最初，所有节点均处于非活动状态。在时间步 t = 0 时，节点的子集 S ⊆ V 被激活以启动扩散过程，而其他节点保持不活动状态。在 LTM 中，每个节点 v 被分配一个阈值 θv ∈ (0, 1]，该阈值代表节点被激活的不同倾向（如果其邻居激活）。一个不活动的节点 v 在时间 t 变得活跃，如果它的权重总和活跃邻居在时间 t − 1 时至少为 θv。

  影响力最大化：影响力最大化问题旨在识别社交网络中一小部分早期采用者，以在给定的扩散模型下最大化影响力传播。这首先由 Kempe 等人正式确定。 [10] 作为一个优化问题。作者表明该问题在 ICM 和 LTM 下都是 NP 困难的，并提出了一种可以达到良好次优解的贪心算法。后来，提出了几种改进算法[14]、[11]、[17]，通过平衡算法的运行时间和影响力传播来解决影响力最大化问题，试图使它们可扩展到大型数据集。

   竞争影响力最大化：影响力最大化问题是在网络中仅传播一项的假设下定义的。然而，实际上，不同的项目，例如不独立的信息、创新、产品，可能会同时在同一网络中传播。它们要么是竞争的，要么是互补的。已经提出了几种竞争扩散模型[3]、[4]、[5]、[8]、[13]、[21]。它们的不同之处在于描述当两个竞争性项目同时到达他时个人如何选择要采用的项目的机制。在竞争扩散模型的框架下，一个有意义的问题是找到一组合适的种子节点来采用某个项目，从而最大化该项目的影响力传播。

  在本文中，我们还考虑了两种类型的信息之间的竞争传播，例如谣言和真相（从现在开始，为了简单起见，我们将在某个主题或活动上使用“真相”而不是“正确信息”）。我们不是研究竞争影响力最大化问题，而是通过选择一组合适的节点来最初传播真相来解决最小化谣言传播的问题。类似的工作已在[5]和[8]中完成。具体来说，在[5]中，在 ICM 的扩展下研究了最小化谣言传播，其中假设当坏信息和好信息同时到达个体时，好信息就会生效。在[8]中，He等人。在竞争线性阈值模型（CLT）的框架下形式化了影响阻止最大化问题，其中如果个体可以同时被两种信息激活，则不良信息占主导地位。上述两种模型在两个方面受到限制：（1）当谣言和真相同时到达用户时，用户接受真相的概率要么是0，要么是1。然而，在现实情况下，人们相信谣言的概率是1。真相因许多社会因素而异。例如，有时他/她可能会怀疑事实的来源； (2)此外，所有提到的竞争扩散模型都假设个体一旦被一种信息激活，他/她将永远坚持这种信息，永远不会改变他/她的想法。这种假设适用于与通常不易逆转的购买行为相关的产品采用，但不适用于信息传播或意见形成，因为人们对政治活动或新闻事件的态度会根据从网络收集的新信息而变化。

   本文提出了一种单向状态转移的线性阈值模型来克服上述两个缺点。 （1）我们为每个个体引入两个阈值：影响阈值和决策阈值，它们在激活不活跃节点或说服谣言激活节点将其信念转变为事实时的不同阶段生效。 （2）它允许对已经接受谣言的节点进行重新考虑，但不允许对已经接受事实的节点进行重新考虑。这样的模型与我们许多人亲自观察到的行为模式是一致的：人们无意中促成了谣言的传播，后来又为错误道歉。考虑一个人受到谣言影响而相信谣言并可能将其传播给其他人的情况。然而，随着谣言和真相的传播，当越来越多的朋友接受真相时，他会重新考虑自己的态度，并可能改变自己的信仰。另一方面，一个首先接受事实的人很可能会忽视谣言[18]

   本文提出了一种单向状态转移的线性阈值模型来克服上述两个缺点。 （1）我们为每个个体引入两个阈值：影响阈值和决策阈值，它们在激活不活跃节点或说服谣言激活节点将其信念转变为事实时的不同阶段生效。 （2）它允许对已经接受谣言的节点进行重新考虑，但不允许对已经接受事实的节点进行重新考虑。这样的模型与我们许多人亲自观察到的行为模式是一致的：人们无意中促成了谣言的传播，后来又为错误道歉。考虑一个人受到谣言影响而相信谣言并可能将其传播给其他人的情况。然而，随着谣言和真相的传播，当越来越多的朋友接受真相时，他会重新考虑自己的态度，并可能改变自己的信仰。另一方面，一个首先接受事实的人很可能会忽视谣言[18].

II. LINEAR THRESHOLD MODEL WITH ONE DIRECTION STATE TRANSITION

  在本节中，我们一般介绍单向状态转移的线性阈值模型（简称LT1DT）来描述两个项目（例如，两个具有不同质量的相似产品、对某个主题的两个相反信念等）的竞争影响力传播。 ，比如说 R 和 T，在同一个网络中。

A. Network Structure

  LT1DT 网络 N 是一个 5 元组 (V, E, θ, θR, W )，其中 V = {1, 2, ..., n} 是节点集，E ⊂ V × V 是弧集，即当从节点 i 到 j 存在一条弧时，(i, j) ∈ E。函数 θ, θR : V → (0, 1] 是为每个节点 i ∈ V 分配影响阈值 θi ε (0, 1] 和决策阈值 θR i ε (0, 1] 的映射。函数 W : V ×V → (0, 1] 是一个映射，它将权重 W (i, j) ε (0, 1] 分配给每个弧 (i, j) ε E，使得 W (i, j) j) = 0 如果 (i, j) / ε E 并且对于所有 j ∈ V 则有 Σ i2V W (i, j) = 1。

  影响阈值 θi 直观地代表节点 i 在其邻居参与某项活动或采用某种产品或创新时受到影响的倾向[10]（θi 越小，节点 i 越容易受到影响），决策阈值θR i 表示节点i受到影响后采用项目R的倾向（θR i 越小，节点i越容易采用项目R）。我们将节点 i ∈ V 的内邻居集定义为 N in i = {j|(j, i) ε E} ，将外邻居集定义为 N out i = {j|(i, j) ε E}。网络中的弧(i,j)表示节点j可以受到节点i的影响。

  在本文中，我们假设网络的参数是给定的。事实上，从真实的社交网络数据中学习它们可能并不容易。这个识别问题超出了本文的范围，但我们参考[6]关于学习网络参数的研究。

B. Diffusion Dynamics

  在LT1DT模型中，每个节点在每一步都有三种可选状态：非活动、R-活动（采用R）和T-活动（采用T）以及一种瞬态：受影响。令 SR 为 R 的种子集，它表示在步骤 t = 0 时最初采用 R 的一组节点。种子集的采用以离散步骤传播到网络。我们将 φtR 表示为在步骤 t 中采用 R 的节点集。在步骤 t 处 R-active 的节点集合，即区间内采用 R 的节点[0, t] 表示为 tR = ∪t k=0 φR k 。符号 ST 、 φtT 和 tT 将类似地用于项目 T。直到时间 t 为止激活的节点集（无论是 R 活动还是 T 活动）表示为 t = tR ∪ tT 。根据定义，我们有 0 = SR ∪ ST 。

   与LTM不同的是，LT1DT中的每一步，每个节点都使用自己的节点级自动机来决定要过渡到哪个状态。状态转换取决于其当前状态以及它收到的影响并与其阈值进行比较。节点级自动机如图 1 所示，其中每个状态都由带标签的圆圈表示，虚线框出的受影响状态是瞬态的。准确地说，在步骤 t = 1, 2,···，两个过程同时发生，即激活过程（对于每个非活动节点 i ∈ V \ t 1）和重新考虑过程（对于除种子节点 i 之外的 R 活动节点） tR 1 \ SR) 。

1）激活过程：激活不活动节点的过程分为两个阶段：取决于影响阈值的影响阶段和取决于决策阈值的决策阶段。在影响阶段，如果不活跃节点 i 的活跃邻居权重总和至少为 θi，则不活跃节点 i 会受到影响而参与活动，即 ∀i ∈ V \ t 1，

  在决策阶段，节点的决策取决于其决策阈值 θR i 。如果节点 i 的 R 活跃邻居的权重之和与其活跃邻居的权重之和大于或等于 θR i ，则节点 i 将采用 R，即：

否则，将采用T，即i ∈ φtT 1

 2) 重新考虑过程：在每一步，R-活跃节点 i ∈ tR 1 \ SR) 由于其邻居的影响而重新考虑其活动状态。如果来自其 R 活跃邻居的权重总和与其活跃邻居的权重总和的比率大于或等于 θR i ，即，等式 1，则它保持 R 活跃。 (2) 持有。否则，它会变成T-active。这种进化一直持续到没有人能够受到影响或重新考虑他的决定为止。在这种情况下，网络进入稳定状态。 R-最终采用者和 T-最终采用者的集合分别用 R(SR, ST ) 和 T (SR, ST ) = ∪1 t=0 φtT 表示。包括R-最终采用者和T-最终采用者的最终采用者集合用(SR, ST ) 及其基数| 表示。  （SR，ST）|称为采用函数。类似地，R 最终采用者的基数，即 |  R(SR, ST )|，称为R-采用函数，并且|  T（SR，ST）|称为T-采用函数。当只有一种类型的项目通过网络传播时，LT1DT可以直接简化为简单的LTM模型。

图 1：LT1DT 模型：节点级自动机。活动一；   一个;乙； c； d;   d代表不同可能的状态转换。当节点处于非活动状态时，如果式（1）成立，则发生事件 a（该节点受到影响）。 (1) 成立，否则事件a（保持不活动）发生。当一个节点受到影响时，若式（1）成立，则发生事件b（该节点采用R）。 (2)成立，否则发生事件c（节点采用T）。当节点处于 R-active 状态时，事件 d（节点保持 R-active）发生，如果 Eq. (2)成立，否则发生事件d（节点改变主意为T-active）。

C. Analysis of the System’s Dynamics

  LT1DT模型中两项的传播是一个复杂的现象，可能会发生竞争和互补。让我们首先考虑瞬态阶段的定时演化。网络中的总传播是渐进的，因为任何活动节点都不会切换回不活动状态。 T 的传播也是渐进的，因为 T-active 是宿状态。然而，R 的传播是非渐进的，因为在某个步骤中处于 R 活动状态的节点可能会在未来的步骤中切换到 T 活动状态。

  对于最终稳态，采用函数和 T-采用函数显然都是单调非递减的。 ST赋予SR，R采用函数|  R（SR，ST）|不是单调非增 w.r.t. ST给定SR，也就是说，为T增加预算可能并不总是会减少其竞争对手R的传播。我们通过举个例子来证明它的非单调性。考虑图 2 中的网络。假设 SR = {1}，θ2, θ3 ∈ (0.5, 1], θ5 ∈ (0, 0.2)，且 θR 2 , θR 3 ∈ (0, 0.5), θR 5ε (0.2, 1]。在没有与T竞争的情况下，即只有R在网络中传播，R(SR, ∅) = {1, 2, 5}。通​​过从节点 6 传播 T（即 ST = {6}），节点 5 将重新考虑采用 T 的决定，从而导致 R = {1, 2} 且 T = {5, 6}。这样添加 ST 会减少 R 的扩展。但是，如果设置 ST = {4}，则 R = {1, 2, 5, 3}，并且节点 3 = {4}。一个节点 4 的额外影响，但根据其决策阈值采用 R，这意味着为 ST 添加节点可能会增加 R 的传播。

  此属性意味着，在这种情况下，如果目标是最小化项目 R 的采用者数量，则需要特别考虑项目 T 的种子集的选择。在某些情况下，这种现象无法避免，因为传播竞争性产品会提高对此类产品或创新的认识，但是采用的产品类型取决于人类的决策。

图 2：单调性的反例。

III. PROBLEM DEFINITION

  LT1DT 模型是一种竞争扩散模型，允许从 R 激活状态转换到 T 激活状态，但不允许向相反方向转换。我们相信这个模型可以用来描述许多不同的实际案例，例如产品采用、谣言传播等。

  例如，在产品采用中，项目R和T可以分别解释为低质量和高质量的两种相似产品。采用低质量产品的用户在进行比较时可能会改变主意并转向高质量产品。然而，很难影响使用高质量产品的用户采用低质量产品。 Macdonald和Sharp[12]发现，经过一系列产品选择后，消费者在一组完全不知名的品牌中进行选择时，更有可能选择优质品牌。

  同样，在谣言传播的情况下，R代表谣言，T代表真相。接受谣言的人可能会重新考虑自己的信仰，而接受真相的人将对谣言免疫[18]。

 下面我们重点讨论谣言传播的应用，即谣言遏制的问题。谣言可能会引起恐慌或导致人们做出错误的决定。因此，研究如何控制谣言的传播就显得至关重要。我们不是切断网络中的某些联系或审查个人表达的意见，而是确定个人来传播真相，以减少人们受到谣言影响的脆弱性。在LT1DT的框架下，本节我们研究最小化谣言传播的问题。

A. Minimizing rumor spread

 谣言遏制的问题是选择一组合适的节点来传播真相，以最小化接受谣言的节点数量。我们将问题形式化如下。
 问题 3.1：（MRS：最小化谣言传播）考虑由网络 N = (V, E, θ, θR, W ) 和谣言种子集 SR 表示的 LT1DT 模型。给定一个整数 k，在 V \ SR 中找到基数小于或等于 k ​​的真值 ST = X 的种子集，使得 R 最终采用者的基数最小化，即

 MRS 问题具有组合性质，寻找最优解需要穷举搜索。下面我们展示 MRS 问题的难度。

 定理3.1：在具有单向状态转移的线性阈值模型下，MRS问题是NP困难的。证明：我们只是给出证明的草图。为了证明MRS问题的NPhardness，只需证明已知为NP-hard的经典最大覆盖问题（MCP）可以简化为LT1DT下的MRS问题。为此，可以使用类似于 [21] 中提出的方法来构建捕获任意 MCP 的 MRS 实例

IV. HEURISTIC SOLUTIONS FOR THE MRS

  鉴于 MRS 问题是 NP 难题，我们提出了一些启发式方法来解决它。根据选择真值种子的搜索空间，它们可以分为两类：无约束和约束。我们首先提出两种不同的无约束启发式方法，然后给出它们的约束版本，其中我们将搜索空间限制为子网络而不是整个网络。

A. Unconstrained

  无约束方法可以根据具体判断选择集合V\SR中的任意节点作为真值种子。 1) PageRank：在网络科学中，确定网络中节点的相对重要性很有趣，可以通过中心性得分来衡量[2]。有多种中心性得分（例如，度中心性、特征向量中心性、页面排名中心性等）被广泛用于解决社交网络中的影响力最大化问题[10]。在本文中，我们采用pagerank中心性，这是一种流行的网页排名算法。我们使用式（1）所示的隐形传态模型[9]。 (3)计算各个pagerank值，将pagerank的重启概率γ设置为0.15。令 p 表示 pagerank 向量，pi 表示节点 i 的 pagerank 值，即

其中 p ∈ (0, 1)n 且 Σn i=1 pi = 1，并且 ^ A 是缩放邻接矩阵，其中 ^ A(i, j) = A(i, j)/1T A(:, j)其中 A 是给定图的邻接矩阵。

  为了遏制谣言的传播，PageRank 选择 V​​\SR 中 pagerank 值最高的 k 个节点作为真相种子.

由于缩放后的邻接矩阵 ^ A 是一个稀疏矩阵，每行平均有 d 个非零元素（所谓的网络平均度），因此矩阵和向量的乘法可以在 O(nd) 时间内完成。因此，计算 pagerank 值需要时间 O(n(d + 1)I)，其中 I 是 p 收敛到合理近似值的迭代次数。选择 V \ SR 中具有最高 pagerank 值的前 k 个节点需要时间 O(kn)。总体而言，PageRank 的时间复杂度为 O(In(d + 1) + kn)。

  2) ContrId：PageRank，无论所考虑的扩散模型的扩散动态如何，仅取决于网络结构。在这里，我们提出了一种新颖的启发式 ContrId（贡献者识别的缩写），它基于谣言传播的动态，并尝试识别哪些节点对谣言传播贡献最大（称为贡献者）。

  下面提出的衡量节点对谣言传播贡献的方法是由 LTM 模型下的观察激发的。谣言的传播是离散的步骤直到没有更多的节点可以被激活。在时间 t 激活的节点立即将其影响传播到可能在后续步骤中激活的外围邻居。因此，在时间 tv 激活的节点 v 的贡献可以定义为在任意时间 t > tv 激活的其外邻居的数量。

   我们首先用 ST = ∅ 模拟从 SR 开始的谣言传播，并记录从步骤 1 到步骤 Ts 的每一步激活的节点集合，此时网络进入稳定状态，即所有 t = 1, 2,·· 的 φtR ·，Ts。设 L 表示网络中最长简单路径的长度。然后我们有 Ts ≤ L，因为扩散过程最多需要 L 个时间步。现在，对于每个节点 v ∈ φtR，其贡献表示为 Ctr(v) 可以形式化为

 为了节点贡献定义的完整性，我们将所有不活跃节点的贡献设置为 0。ContrId 根据对谣言传播 Ctr(v) 的贡献排名，选择前 k 个贡献者，这可以在 O(kn) 时间内完成。模拟 SR 的谣言传播需要计算时间 O(nd)。因此，ContrId的时间复杂度为O(n(d + k))。

B. Constrained

  在前面的部分中，我们提出了两种在 V \ SR 中选择 k 个真值种子的启发式方法。在这一部分中，我们还通过将搜索空间限制在谣言种子集附近来考虑它们的约束版本（称为 ProxPageRank 和 ProxContrId）。我们将此空间称为 SR 邻近空间，并将其表示为 N out(SR) = (∪v2SR N out v ) \ SR。这个想法是阻止从谣言种子到剩余网络的有影响力的路径。我们将从下一节中提供的实验结果中看到，约束版本不仅在计算速度方面而且在谣言遏制方面都比无约束方法表现得更好。

1）ProxPageRank：ProxPageRank选择N out(SR)中pagerank值最高的k个节点作为真值种子，时间复杂度为O(In(d + 1) + k|SR|d)。

2）ProxContrId：ProxContrId选择N out(SR)中贡献最高的k个节点作为真值种子，时间复杂度为O(nd + k|SR|d)。

   由于搜索空间较小，受约束方法的时间复杂度低于无约束版本。所有上述四种提出的方​​法都具有相同水平的时间复杂度，且时间复杂度随 n 线性增长。将搜索空间限制为 SR 邻近空间的想法也可以应用于将搜索空间限制为任何可能的节点子集，例如，可以轻松说服采用事实的节点集。

V. EVALUATIONS

A. Experimental set up

  我们在两个现实世界网络上进行了一系列实验，以比较在所提出的 LT1DT 下启发式解决 MRS 问题的有效性。网络 Astro-Ph 和 NetScience 是来自电子打印 arXiv 不同部分的科学论文作者的两个协作图：该数据源通常用于社交网络分析的文献中 [5]、[8]、[10] ，[19]。两位作者之间的弧线代表共同的出版物。表I总结了数据集的精确统计信息。在数据集上测试的算法是PageRank、ProxPageRank、ContrId和ProxContrId。

  请注意，在文献中，即使所考虑的网络不一定代表物理问题，通常也会考虑基准网络来测试所提出的解决方案的有效性[14]。

  为了更好地估计算法的效率，我们在 100 个不同的随机生成的 LT1DT 网络上运行每个实验，这些网络具有相同的网络结构和影响权重，但在 (0, 1] 中随机选择的阈值 θi 和 θR i 不同。影响权重通过以下方式生成。我们首先给每个有向弧一个在 [1, 10] 中随机选择的整数，然后采用归一化值来保证对于所有 j ∈ V 都具有 Σ i2V W。 (i, j) = 1。然后我们取 100 次运行中 R-最终采用者或 T-最终采用者集合的平均大小。此外，我们让谣言从度数较大的节点传播，并设置 |SR。 | = 10（对于网络 Astro-Ph）和 |SR| = 30（对于网络 NetScience） 所有实验均在 2.5 GHz Intel(R) Core(TM) i5-6300U CPU 和 8GB 内存上进行。实验代码是用C++编写的。

B. Experimental results

    图 3：Astro-Ph 和 NetScience 网络中的影响力传播。 (a) 和 (b) 中的柔和蓝线显示每个数据集中给定谣言种子集的大小。

在所提出的启发式方法下，谣言传播、真相在网络 Astro-Ph 和 NetScience 上的传播如图 3 所示。参照图3a和3b，我们得到以下观察结果。

  ProxPageRank和ProxContrId在谣言遏制方面优于其无约束版本，这很好地体现了邻近效应的良好特性。具体来说，在 Astro-Ph（分别为 NetScience）中，ProxPageRank 和 ProxContrId 分别比 PageRank 和 ContrId 好 35.1%（分别为 54.7%）和 29.6%（分别为 8.3%）。   PageRank 的表现不如 ContrId，甚至有时无助于遏制谣言传播。这是因为PageRank直接利用网络结构而忽略了谣言种子的位置。具有高pagerank值的节点有时距离谣言种子很远，然后谣言和真相在网络的不同部分传播。 ContrId 的表现比 PageRank 好得多，即 Astro-Ph 中的 17.5% 和 NetScience 中的 48.1%，因为它试图针对谣言传播中发挥重要作用的节点。

  在网络 Astro-Ph 中，从 ProxContrId（分别为 ProxPageRank）选择的 30 个节点传播真相可以减少约 83%（分别为 70%）的谣言传播。在网络 NetScience 中，至少需要 78 个（分别为 88 个）真相种子才能完全包含 ProxContrId（分别为 ProxPageRank）传播的谣言。

  从无花果中传播的真相来看。如图 3c 和 3d 所示，从 PageRank 选择的节点传播真相会产生采用真相的最大节点集，这反映了 PageRank 在解决影响力最大化问题方面表现良好的事实。但请注意，我们研究的目标不是真相最大化，而是谣言最小化。

VI. CONCLUSIONS AND FUTURE WORK

  在本文中，我们提出了简单线性阈值模型的竞争性和通用版本，该模型捕获了谣言和真相在同一网络中竞争的实际情况。在我们的广义模型下研究了最小化谣言传播的问题。不幸的是，MRS 问题在 LT1DT 模型下被证明是 NP 困难的。我们首先提出两种不同的启发式方法，然后给出它们的约束版本以突出解决 MRS 问题的邻近效应。模拟是在两个现实世界的社交网络下进行的。

探索 LT1DT 模型的一些理论特性，例如子模性分析，是一个有趣的话题。