病毒营销对在线社交网络舆论动态影响的新模型

1570基于病毒营销的在线社交网络中的意见动态模型摘要涂思静瑞典斯德哥尔摩皇家理工学院sijing@kth.se斯特凡·诺依曼瑞典斯德哥尔摩皇家理工学院neum@kth.se1引言在线社交网络为公民提供了一个就不同社会问题形成意见的媒介，并为公众讨论提供了一个论坛它们还使用户接触到病毒式内容，如突发新闻文章。 在本文中，我们研究了这两个方面之间的相互作用：意见形成和在线社会网络中的信息级联。 我们提出了一个新的模型，使我们能够量化用户如何改变他们的意见，因为他们接触到病毒内容。 我们的模型是一个流行的Friedkin-Johnsen模型的意见动态和独立的级联模型的信息传播的组合。我们提出了模拟我们的模型的算法，我们提供了近似算法优化某些网络指数，如用户意见或分歧-争议指数的总和，我们的方法可以用来获得洞察到多少病毒内容可以增加这些指数在线社交网络。最后，我们在真实世界的数据集上评估我们的我们的实验表明，营销活动和极化内容对网络有着截然不同的影响：前者对网络中的极化影响有限，而后者可以增加极化高达59%，即使只有0.5%的用户开始分享极化内容。 我们相信，这一发现揭示了当今在线媒体中日益严重的隔离现象。CCS概念• 信息系统→社交网络;数据挖掘;·计算理论→图算法分析。关键词在线社交网络，舆论动态，信息传播ACM参考格式：涂思静和斯特凡·诺依曼。2022年基于病毒营销的在线社交网络中的意见动态模型。 在ACM WebConference 2022（WWW '22）的会议记录中，2022年4月25日至29日，虚拟活动，法国里昂。ACM，New York，NY，USA，9页。https://doi.org/10.1145/3485447.3512203允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用。必须尊重作者以外的其他人拥有的本作品组件的版权。允许使用学分进行摘要 以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。 请求权限请发邮件至permissions@acm.org。WWW©2022版权归所有者/作者所有。授权给ACM的出版权ACM ISBN 978-1-4503-9096-5/22/04。. . 十五块https://doi.org/10.1145/3485447.3512203在线社交网络是现代社会中无处不在的一部分除了将用户与他们的朋友联系起来之外，许多人还将它们用作内容聚合器，通过关注媒体或阅读同行分享的文章。显然，参与社交网络可能会影响一个人对社会问题的看法：用户可能会在基于同行争论的讨论中调整自己的观点;或者他们可能会根据他们阅读的新闻文章中揭示的新事实调整自己的观点。由于意见形成和信息传播之间的这种强烈联系，在线社交网络已成为病毒式虚假信息活动的目标。流行的例子包括像QAnon这样的团体，他们传播关于疫苗接种等主题的阴谋论和假新闻，或者试图影响敌对国家选举结果的国家行为者。 虽然病毒式内容如何通过社交网络传播已得到充分研究，但此类模型并未考虑病毒式内容如何影响用户意见。因此，了解新信息如何影响用户意见，并能够量化这种信息失真活动的影响是非常可取的。量化社会网络中的意见动态的一个突出模型是FJ模型规定，每个用户都有一个表达的意见，用户公开透露，是网络依赖的，和一个固有的意见，是固定的，网络无关的。然而，它没有考虑用户如何基于新信息改变他们的意见（例如，病毒内容）在网络中传播此外，研究人员还研究了与优化某些基于意见的网络指数相关的问题，例如，最大化平均意见[17]或极化[9，16]，或最小化极化和分歧[10，25，27]。在这方面的工作中，优化是通过将一组种子用户表达的或固有的意见推向某个方向来实现的。然而，现有的作品并没有具体说明如何发生这种轻推，也没有考虑在一个更现实的信息级联设置的意见轻推的相互作用。因此，目前的研究要么允许我们量化用户意见并优化基于意见的网络指数，而不考虑病毒式内容，要么允许评估病毒式内容的传播，而不需要对用户意见进行推理。这一限制导致我们提出以下问题：(1) 我们能否量化病毒式内容如何影响在线社交网络中的用户意见(2) 我们能否研究信息级联和舆论动态？(3) 我们能否通过考虑病毒式内容的传播来优化基于意见的网络指数WWW涂思静和Stefan Neumann1571（− / −）我们的贡献。 我们通过提出一个结合Friedkin-Johnsen模型[ 15 ]和Kempe等人的影响最大化框架的新模型来肯定地回答上述问题。[21 ]第20段。 据我们所知，我们的模型是第一个允许量化病毒式内容对用户意见的影响的模型。与vanilla FJ模型（其中固有的用户意见是“固定的”，但表达的意见会随着时间的推移而变化，基于用户交互）相比，我们的模型考虑了网络中共享的病毒内容，并且假设对于暴露于此内容的用户，他们的固有意见可能会发生变化。 这可能是这样的情况，例如，当用户阅读一篇文章，使他们重新考虑他们对某个主题的立场。当一部分用户改变了他们固有的观点时，他们表达的观点也会被修改，这反过来又会通过FJ观点动态对整个网络产生影响。因此，少数用户的固有意见的改变可能会对整个网络产生影响：即使用户的固有意见不会因病毒式内容而改变（因为他们忽略了它或内容从未到达他们），他们仍然可能由于“同伴压力”而改变他们表达的意见。我们的模型将这两种现象联系起来：它使我们能够理解病毒式内容如何影响个人用户，同时也使我们能够研究个人行为如何在网络中传播并影响整体讨论。我们考虑两种不同类型的内容：非极化和极化。对于非极化内容，例如营销宣传片，用户的固有意见只能增加。对于极化内容，我们考虑了逆火效应[28]：与对立内容的交互可能会导致用户先天观点的减少。情况可能是这样，例如， 在政治竞选中，一个政党的广告使其支持者作出积极反应，而反对者作出消极反应。从算法的角度来看，我们提出了模拟我们的模型的方法此外，我们考虑优化某些基于意见的网络索引的问题。我们提出一个贪婪的图11示出了用于最大化非极化内容的用户意见 我们还提出了最大化非极化内容的争议和分歧-争议指数[ 27 ]的算法;我们的算法具有数据依赖的近似比。最后，我们提供了最大限度地提高其他指标，如极化和分歧，非极化和极化内容的算法。为了获得我们的优化算法，我们建立在反向可达集框架[6，31，32]上。一个挑战是，在我们的设置中，所产生的优化问题是基于二次型，因此，我们必须将反向可达集框架扩展到这个更一般的设置。我们在真实世界的数据上评估我们的方法我们的实验揭示了非极化和极化内容之间的显着差异。一方面，非极化内容可以显著增加用户意见的总和，但它对极化的影响有限，有时甚至会减少它。极化内容的情况正好相反：它几乎没有增加用户意见的总和，但它可以显着增加极化。我们看到，即使只有0.5%的用户开始分享极化内容，网络极化也会增加20%以上。平均值，最高可达59%。 我们相信，这一发现为现代网络媒体中日益增长的两极分化提供了解释。我们在完整版中提出了我们主张的证据[33]。2相关工作我们的目标是量化病毒式内容如何影响社交网络中的用户意见。当然，我们的方法建立在现有的意见动态和信息级联模型的基础上。舆论动力学已经在不同的研究领域进行了研究，包括心理学，社会科学和经济学[7，20]。在这里，我们建立在流行的已经提出了许多FJ模型的扩展例如，Amelkin et al.[1]假设固有的用户意见基于所表达的意见而随时间改变。对于其他相关模型，我们参考[1]中的讨论然而，这些作品并没有考虑到基于对病毒内容的阐述而产生的固有观点的变化最近的工作使用这些模型来理解意见动态的属性，并制定自然优化问题。Bindel等人[5]分析FJ模型中的Gionis等人 [17]最大化网络用户意见的总和。 其他作品研究了在FJ模型中测量和减少意见极化或其他分歧指数的问题[12，25，27，36]，同时也考虑了对抗性设置，旨在量化试图在模型中引起不和谐的对手的力量[9，10，16]。为了对信息级联进行建模，我们建立在流行的独立级联模型Kempe等人。[21 ]第20段。已经提出了这个模型的许多扩展和变体例如，Sathanur et al. [30]结合基于外部来源的内在用户激活。另一个流行的扩展是Barbieri等人的主题感知级联模型[4]，并具有包括社交广告在内的各种应用[2，3]。 虽然这种模型允许对信息传播进行建模，但它们不允许量化这些如何改变用户意见。逆火效应，即个人在面对事实修正时坚持自己信念的倾向，在政治科学中已经观察到[28]，但在计算社会科学中尚未得到广泛研究。这些都是Chen et al.[11]，他们将逆火纳入偏见同化的意见动力学模型[13]，Hirakura等人。[19]，他提出了一个融合了移情和排斥的两极分化模型我们的优化算法依赖于反向可达集，引入Borgs等人。[6]，并通过随后的技术[31，32]进行了改进 我们将这些想法扩展到我们的设置，以获得包括二次项的目标的算法。我们注意到，王等人定义的活动最大化任务。[34]这是一个特殊的情况下，我们的设置。我们应用为了有效地计算我们的目标函数，我们使用Xu等人的方法[35]基于Laplacian解算器。据我们所知，这是第一个研究用户意见如何因在线社交网络中的病毒式信息而改变的工作。基于病毒营销的在线社交网络中的意见动态模型WWW1572（）下一页∈[]∈[]∈[]∅∈•（−）•−是n×n对角矩阵，其中Du，u=−v∈N（u）w（u，v），对所有1nu∈Vzu是平均值。用户意见;其固有的意见（如下所述），并分享内容，表1：不同指数的矩阵索引符号矩阵p紫外线更新固有意见偏振−111⊺−11 −puv1−δ δP（L）（I+L）（I-n）（I+L）不一致D（L）（L+I）−1L（L+I）−1内部冲突I（L）（L+I）−1L2（L+I）−1无效忽略确认扩展控制器C（L）（L+I）−2Disagre对于固定的用户意见，Monti et al.[26]研究了级联如何状态状态转移节点暴露于来自邻居顶点u的病毒内容的概率状态转移路径行动1−δpuvδpuv分享病毒内容根据用户意见和内容的主题，3预赛设G =（V，E，w）是一个无向赋权图，n = |V|节点和边权重w：E → R>0。 设N（u）表示u∈V的近邻集. G.是L=D-W，其中D图1：关于状态转换和对单个节点v执行的操作的扩展确认模型的图示。在初始轮中，k个种子节点处于扩展状态，而其余节点处于不活动状态。无效、忽略、确认或扩散。我们命令各州u∈ V，W是n × n矩阵，且对任意u，v ∈ V，Wu，v = wu，V.Friedkin–Johnsen 在FJ模型中，我们给出一个n结点的加权无向图G = V，E，w. 每个节点u对应于社交网络的用户每个用户u都有一个表达意见zu 0，1，这取决于网络，和一个固定的固有意见su 0，1。我们写s0，1n和z0，1n表示先天和表达意见的向量。所表达的意见将逐轮更新。更具体地说，设s为固有观点的向量，z（t）为在时间t表达的观点的向量。更新规则由下式给出：z（t +1）=（D + I）−1（Wz（t）+s）。（3.1）取极限t→∞，所表达的观点收敛于z=（I + L）−1s。（3.2）我们在我们的模型中研究了以下流行的网络指数，其中二次型的矩阵如表1所定义• 用户意见的总和，由Ss=1s给出，并且很好-当用户改变他们的状态时，他们只能选择相对于该排序更高的图1中提供了关于针对单个节点v执行的状态转换和动作的模型的图示。我们的模型在轮中进行最初，在第0轮中，有k个用户的状态是分散的，所有其他用户都是不活动的;在以后的轮中，用户可能会改变他们的状态。我们将其初始状态被传播的用户称为种子节点。每轮t> 0有两个阶段：1在第一阶段，用户更新他们表达的意见。 在第二阶段，病毒内容通过网络传播，用户可能会改变他们的状态和他们的固有观点。我们在下面描述这两个阶段第一阶段：更新用户意见。用户如在FJ模型中那样更新他们表达的意见，即，根据Eq.（3.1）。第二阶段：信息传播。 考虑轮t> 0。令U表示已将其状态更改为扩展的用户集t-1的整数如果U=0，我们认为第二阶段已经结束。否则已知Ss=1<$z;• po。[27]第二十七话.u∈V（zu<$−z<$）2=s<$P（L）s，其中z<$=（U）），每个用户uU与其所有邻居共享病毒式内容。当u的邻居v暴露于病毒内容时，（2）在任何情况下，• [27]第27话，我是你的女人 .（1）A（1）A（2）A（3）A（• 争议[10，25]CG，s=u∈V（zu∈）2=s<$C（L）s;以及如果v处于inactive或ignore状态，则如下所示• 内部冲突[10]IG，s=.u∈V（su−zu<$）2=s<$I（L）s;G，s• 随着概率δpuv，用户v切换到状态扩展;v调整• disagreeement-dogsoversy[27，35]Idc=sIdc（L）s=CG，s+DG，s。4病毒内容对用户意见我们在SEC中正式介绍我们的模型 4.1并展示如何在第二节中模拟。4.2.4.1传播-认知模型根据独立级联模型[21]，我们假设下一轮的比赛在概率为1δpuv的情况下，用户v切换到状态确认;v调整其固有的意见（如下所述），但在下一轮中不与其邻居共享内容在概率为1puv的情况下，用户v切换到忽略状态;v不执行任何动作（即，v不试图分享内容，v也不调整其固有的观点）。如果v处于确认状态，则它以概率δpuv切换到状态扩展，值pu，v∈ [0， 1]编码用户v对con作出反应的概率1δpuv.最后，如果v处于spread状态，那么v总是保持在这个状态，状态在这两种情况下，v都不会再次调整它的意见从用户u接收帐篷;我们允许pu，vpv，u。此外，我们引入参数δ，δ>0，如下所述根据FJ模型，每个用户u具有表达意见zu和固有意见su。此外，每个用户都有一个状态，[1]我们注意到，对于我们的模型和我们的分析，没有必要考虑两个阶段，我们只是为了更好地说明而做出这个假设我们也可以假设这两个阶段是交错的，同时发生通过<<<它转换到一个新的状态，并可能调整其固有的意见。如果WWW涂思静和Stefan Neumann1573--[客户端]{−}--∈[]≥∈−（）下一页∅（）下一页（）下一页M（）[M（）]上述过程确保在状态切换期间遵守之前定义的状态排序，并且每个用户最多调整一次其固有意见最后，请注意，如果δ=1，我们的模型是独立级联模型的推广。调整固有的意见。 现在，我们描述用户在接触病毒式内容时如何改变他们的固有观点。考虑用户u处于非活动状态或忽略其新状态是确认或传播。然后，固有的意见su转变为新的价值su。我们考虑两种情况：营销活动：用户的意见变得更加积极后，看到的内容，即。例如， su=minsu+，1，参数> 0。在这里，我们使用最小运算来确保新的意见s_u在整数0，1中。适得其反的两极分化活动：在两极分化的活动中，我们认为，虽然一些用户接受的内容，其他人会发现它排斥。 更具体地说，我们假设存在阈值τ 0，1，使得：（1）如果suτ，则u包含内容并将其意见调整为su=minsu+τ，1;（2）如果su<τ，则u找到内容的对应并调整su=max0，su-是的请注意，在我们的模型中，用户仍然可以分享他们不喜欢的内容虽然一开始这看起来不直观，但我们认为这是一种现实的行为：反对某个内容的用户通常会将其与反论点一起我们注意到我们的模型可以修改以避免这种情况。最后，观察到s是一个随机向量，它取决于信息传播的结果然而，一旦我们确定了信息传播的随机性，信息传播就变得确定了。这将是一个有用的属性在下面。可能的模型扩展。 我们注意到，我们的模型是相当通用的，可以以各种方式进行扩展。首先，我们通过独立级联模型对信息级联进行建模[21]。然而，如果我们使用线性阈值模型[21]，独立级联和线性阈值模型的主题感知版本[4]以及内在用户激活[30]，我们的模型和引理4.1的结果也成立。特别是，使用线性阈值模型可以深入了解通过复杂接触传播的内容[8，18]。其次，上面我们考虑了两个相对简单的设置，用于调整用户的固有意见。然而，我们注意到，引理4.1below推广到了当su是su的任何用户定义函数时的设置。4.2与两阶段模型的等效性虽然传播-认知模型很容易解释，也很容易被现实世界的场景所激励，但如何有效地模拟它还不清楚。 如果我们按照上述方式实现模型，我们将不得不在每一轮中更新已表达的意见，这可能是昂贵的。为了避免这种情况，我们现在引入一个新的模型，可以更有效地模拟，我们表明，它产生了一个相同的分布在先天和表达的意见。两阶段模型。 我们的简化模型也进行轮，但它执行的信息传播和更新的用户意见在两个连续的阶段。更具体地说，在第一阶段的每一轮中，我们执行上述第二阶段中描述的信息传播过程（我们不执行第一阶段中表达的意见的更新）。在这个过程中，用户的一些固有的意见和他们的变化 当一轮之后没有新用户将他们的状态改变为传播时，我们开始第二阶段。在第二阶段的每一轮中，我们都会像上面第一阶段中描述的那样对表达的意见进行更新（我们不运行第二阶段）。模拟两阶段模型。接下来，我们讨论为什么两阶段模型非常适合有效的模拟。首先，观察到当没有节点在前一轮中改变其状态以扩散时，第一阶段停止，即，当U=因此，第一阶段最多可以有O n轮（因为n个用户中的每一个最多可以有四个不同的状态，并且因为我们假设用户只根据状态的排序来增加他们的状态）。此外，在第一阶段的每一轮中，我们可以通过迭代作为节点u U的邻居的所有节点v来更新节点的状态，然后用阶段II中描述的概率更新v的状态。 由于每个用户只能成为一次传播者，因此执行第一阶段的所有回合的时间为O m，其中m是图中的边数。第二，我们认为，调整后的主观意见的产生仅仅依赖于信息传播过程中的随机性。因此，在第一阶段完成之后，固有意见就被固定下来了。因此，我们可以假设向量s_u是已知的，并且经验均衡意见由z_u=I+L−1s_u给出。第二阶段的时间复杂度是求解z的时间要求。观点分布的等价性 这还有待证明，两种模型在固有观点和表达观点上都得出了相同的分布。 为了证明这种等价性，我们假设两个模型都使用相同的输入图、相同的种子节点和相同的（未调整的）固有观点s运行。现在，让我们来表示由S. S. S. S.U的spread-ackn owl dge模型和由S.S.U的two-stage模型产生的调整后的固有意见。我们称之为bothsweetu和sweetu是随机向量，它们只依赖于信息传播过程的结果下面的引理证明了这两个模型的等价性。证明在[33]中给出。引理4.1. 对于所有的a ∈ [0，1]n，Pr [s= a]= Pr [s= a]. 此外，令z=（I+L）−1s和z=（I+L）−1s是均衡观点。 则对所有b ∈[0，1] n，Pr[z=b]=Pr[z=b].5算法我们提出的算法，最大限度地提高了定义在第二节的指数3. 我们给出了近似指数的算法（Sec. 5.1）。然后，我们提出了我们的算法，以最大限度地提高用户意见的总和（第二节）。5.2）和最大化的争议和分歧-争议指数（第5.2节）。5.3）。 我们在[33]中提供了证据。5.1估计指标设L是表1中的矩阵之一，它为我们希望研究的每个指数导出了二次型。 回想一下，s是先天观点的非调整向量，而s是调整后的先天观点的随机向量。在下文中，我们的目标是计算Es我是。设s =s是随机向量，表示用户改变了他们的看法。然后观察，E[sM（L）s]=sM（L）s+E[2 sM（L）s+sM（L）s]。··基于病毒营销的在线社交网络中的意见动态模型WWW15741（）[客户端].（）下一页（）∈（）|≤|≤|R|n（）∈（）下一页[（）]R（）（）M（）[][M（）][M（）]（）下一页.||（）下一页国家v。例如，如果v将其状态更改为确认，则2克伦克1）（n ln n+ ln 2 + ln n）.如果θ≥ λ则公式（5.2）成立。S在下文中，我们设置su∈ [−，]来表示u∈VuS（）我们可以最大化F（S）：u∈V1u（S）<$su，如下所示。由于和中的第一项是确定的，因此我们将其丢弃并关注E[h（s）]，其中reh（s）：=2sM（L）s+sM（L）s。我们表明，计算E[h（εsε）]是#P-哈，因为我们的模型推广了如果u调整了固有的观点，否则1u（S）=0。设1（S）是由每个u∈V组成的1u（S）的向量。注意，1（S）是一个随机向量，而ε s是确定性的。观察到，S=S，独立级联模型引理5.1. 如果S不存在，则计算E[h（s）]是#P-ha rd。这里是Hadamard乘积。为了简化我们的符号，我们设置wu=（2sM（L））u∈u，令mu，v=（su）<$M（L）u，v<$sv. 然后我们得到：蒙特卡罗模拟因为引理5.1表明，h（s）=.wu1u（S）+mu，v1u（S）1v（S）=：F（S）.精确地计算是困难的，我们求助于近似。一种选择是用蒙特卡洛模拟我们的模型具体来说，我们可以模拟我们的模型，如第2节所述4.2获得多个样本的s。现在，一个E的界意味着我们可以以很高的概率计算出E的近似值然后，我们可以使用Xu等人的算法在近线性时间内计算Eh的近似。[35]这是基于拉普拉斯求解器。u，v∈Vn给定这些定义，我们设Ru和Rv是随机rr-集，分别为u和v，我们设ωRu，Rv（S）=]wu+，（Rv]nmu，v，对于随机集合R，我们定义（Ru，Rv）∈RωRu，Rv（S）这种方法是有效的，当种子节点集的数量FR（S）=.（5.1）|R|我们希望计算的E[h（εsε）]是小的。反向可达集。然而，在我们的优化算法中，我们证明了FR（S）是E[F（S）]的无偏估计。我们将需要针对大量不同的种子节点集合来评估Eh_s_n，并且因此使用蒙特卡罗方法太低效。因此，我们使用反向影响采样[6，31，32]，这使我们能够减少模型的模拟次数我们的反向可达集的概念如下。假设我们想在图G=V，E上模拟我们的模型。一个可能世界是G的一个拷贝，它的边上有标签，我们生成标签如下。 对于每个边u，vE，我们假设u具有状态扩展，v具有状态非活动。 现在，我们按照上面阶段II中所述对v的状态进行采样，并将（u，v）标记为新的引理5.2. 设R是随机rr -集对的样本集.则E[F（S）]= Eu，<$G[n F R（S）].由于前面的引理只在期望中成立，我们现在考虑以高概率成立的近似。 设θ> 0是一个误差参数，θ=是rr-集的个数，并假设我们知道OPT = max S k E F S（我们稍后将展示如何使用统计检验来获得OPT的界）。我们的目标是选择足够大的θ，PR [|n F R（S）− E[F（S）]|≥ 1000PT] ≤1。（5.2）确认u、v的标签对于所有边缘u，v，E重复该过程，并且我们始终假设u具有状态扩展，v具有状态不活动，而不管先前样本的结果如何。现在考虑一个可能的世界。我们说存在着一种因为联合界意味着对于任何大小为k的种子集S，EF S是FSw.h.p.的良好估计。我们证明，如果我们选择足够大的θ，则满足方程（5.2）引理5.3. 设χ= max|w + nm|且λ=8n χ（λ+从u到v的路径，如果存在一条路径，其中所有边都有承认或传播。请注意，当用户. u，v∈V uKOPTu，vϵ23在我们的模型中改变他们的意见：用户v调整其意见，当且仅当存在从种子节点到v的活动路径。接下来，设<$是一个随机生成的可能世界，u是G中的一个随机节点。一个随机的rr-集合R对于u在<$in是一个节点在<$in的集合，使得存在一个到u的活路径。估计指数。 现在我们转向估计E h s。 现有的信息传播方法可用于估计2 E sεLε sε，因为ε s ε是该传播中唯一的随机量。然而，我们还需要应用最优化E_s_l_我们的主要观察结果是，在每个可能的世界中，它保持，当且仅当存在从种子节点到u和v的活路径时，对（u，v），在图中存在边;在这里，我们有5.2最大化网络索引现在我们考虑表达意见之和问题，其中我们给定一个无向加权图G=V，E，其边概率为pu，v和一个正整数k。 目标是找到一 组 基 数 最 大 为 k 的 种 子 节 点 ， 使 e 个 经 验 意 见 的 总 和E[Ss]=E[1z]最大化。 我们的主要成果如下。定理5.4. 存在一种贪婪近似算法，它以高概率计算（1 −1/e − 1）-近似。事实上，在[33]中，我们证明了我们的模型比FJ模型更强大，在FJ模型中，我们可以增加k个先天用户意见。为了得到定理，我们最大化调整后的p.A rtsofth.einnateopinions E[usu]，sinc e. 众所周知，Wang等人[34]他也有过类似的经历，但只考虑了uzu=usu，因此we可以最大化E[usu]。等效地，.对所有对（u，v）∈V2执行此操作。引理5.5。argmax.z（S）= arg max F（S）一旦用户u达到确认状态，则调整其意见传播. 请注意，由于间隔的原因，我们在上面的第二阶段中描述的级联接下来，设S是一组种子节点，设1u（S）是一个指示符，其中1u（S）=1引理5.5的主要好处是，为了最大化F S，我们不必从等式（3.2）计算稀疏矩阵逆这非常昂贵。注意，如果对于所有u∈V，F（S）简化为影响最大化问题[21]。然而，在这方面，.除了可能有标号的与v相关联的边之外的标号扩展WWW涂思静和Stefan Neumann1575G，sICe（）R（）e–（）（）LU∈{（）}LU（）下一页（）（）（）（）[M（）M（）]（）≤（）≤（）R（≥/（）下一页L并随机选择使FR（S）最大化的节点。该算法µ0（S）≥maxµ0（SU），µL（S）（1 − 1 −）µ0（S）。L2Kϵ2算法1：RR-贪婪表2：数据集的统计，其中n是n是节点数，m是边数。输入：R，Datasetn mDatasetn m输出：输出������˜���←∅而|���˜���|≤���do���←argmax���������������������������˜���←���˜∪{���};���返回顶部���算法2：采样Convote 219 521Netscience 379 914WikiTalkHT 404 734维基投票889 2914Reed98 962 18812电邮：1133 5451粤ICP备16097666号-1USFCA722672 65244NipsEgo 2888 2981PagesGov 7057 89429HepPh 11204 117619电话：12645 49132CondMat 21363 91286Gplus 23613 39182Brightkite 56739 212945WikiTalk 92117 360767输入：G，���������2，���，Δs，���，LB0输出：RR ←L，LB← LB0;对于���= 1，. . . ，log 2���− 1do5.3夹心法现在，我们提出一种算法，用于找到最多k个种子节点，使Dis-ConIndexIdc和Cont roversyIndexCG，s最大化。��� ��� ������←而|R|≤������doR<$R<$GenerateRR-Set;X_r_r←RR-G_r_e_y（R，R）;由于这些优化问题不是子模的，我们不能使用上面的贪婪算法然而，索引的矩阵dcL和L只包含非负项，这允许我们定义子模上界和下界。���如果n（X）≥（1B）B，则LB<$BR（XB），break;���目标函数因此，我们应用三明治方法[24]来R 2←1 2获得数据相关的近似保证。我们得到我们的上限和下限如下。设M（L）∈而|R|≤���doR<$R<$GenerateRR-Set;{Idc（L），C（L）}. 设M（L）U是对角矩阵，其中返回R;M（L）U是M（L）的第i行中所有条目的总和让IIµ0（S）[2sM（L）s+sM（L）s]，μ（S）=E[2sM（L）s]，如果对于某些u，su为零，则解可能不同。<该定理的近似结果源于以下引理。引理5.6. 函数E[F（·）]是单调的亚模函数。 因此，贪婪算法实现了1 - 1的近似比。最大化网络索引。 为了估计F S，我们定义F类似于公式（5.1）。不同之处在于，我们去掉了二次项<$[（Ru<$S）<$$>，（Rv<$S）<$$>]nmu，v，并设置wu=<$su。我们的算法工作如下。我们采样一个集合R的rr-集RµUS=E2sLs+sLUs. 由于所有这些矩阵的元素都是非负的，我们得到了我们想要的关系式μLS μ0S μUS。由于µS和µS都是单调的和次模的，贪婪算法可以在因子11的范围内近似它们。在我们的三明治算法中，我们分别选择最大化µLS、µUS和µ0S的节点SL、SU和S0然后，我们在µ0S上评估每个集合，并返回具有最高目标值的集合，即，我们返回arg maxS S0，S，Sµ0S。我们得到以下近似保证。定理5. .8（LUet al.[24]）。 设S = arg max|S |≤k µ0（S）。然后不断添加RR-集，直到统计测试断言我们找到了OPTs的下限更具体地说，我们继续µU（SU）µ0（S）e采样，如果nF S估计的值不是OPT（见引理5.7中的（1）），并且当我们停止采样时，我们获得足够好的下界LB（见引理5.7中的（2））。然后我们可以应用引理5.3和θ λ LB来获得我们的近似保证。我们给出了算法2中的采样和算法1中的贪婪子程序的伪代码我们运行我们参数为L B0=ma xu的算法|我们|且β=n（4<$2+6实验我们进行实验评估。我们的实验是在Intel Xeon E5 2630 v4上进行的，频率为2.20 GHz，内存为128 GB。我们的代码是用Julia编写的，可以在github上找到2数据集。我们使用公开可用的社交网络的真实世界数据集[22，23，29]。对于每个网络，我们提取了最大2）（ lnln log 2ln. n/2。3连接组件数据集统计见表2。参数对于每个网络，我们设置每个网络的固有意见su引理5.7。令X表示算法1的输出，并假设用户u在[0， 1] [35]中均匀随机分布我们设定参数βn−εpu，v如加权级联模型[21，31，32]中，即，pu，v =d1，|= θ ≥ y。|=θ≥y. 则概率至少为1−log2（n）：（1）如果OPT 50，000时，抽样5 nrr-集. 这在实践中给出了很好的估计（通常误差为1%<我们用LinDiscon、LinPol、LinIntCon和LinDis来表示算法。我们将我们的优化算法与三个基线进行比较：MaxInflu选择影响最大化的种子节点;HighDegree选择度最高的种子节点; Random均匀随机地选择种子节点。由于随机是唯一的随机基线，我们报告10次运行的平均值由于这些方法为我们提供了固定的种子集，因此我们使用Monte来自SEC的Carlo模拟5.1评价结果。此外，我们还比较了Chen和Racz [9]的贪婪启发式FJ，该启发式FJ在香草FJ模型下最大化表1中的指数FJ被允许任意改变k个固有的用户意见，但是，与我们的模型不同，没有信息传播;我们为FJ提供与所有其他算法相同的参数k。与其他方法不同的是，我们不采用FJ返回的种子集并在我们的模型中计算其得分，但我们报告了香草FJ模型中FJ的相对增加;这将使我们能够评 估 信 息 传 播 是否使 我 们 的模 型 更 强 大 。 我 们还将 包 括Gaitonde，Kleinberg和Tardos [16，Thm. 3.4]，其给出了关于在FJ的设置中可实现的分析上限;我们注意到该上限可能是宽松的（即， 它可能太大）。请注意，如果我们的算法实现的值大于FJUpp，则我们的模型严格地比没有信息传播步骤的普通FJ模型中可实现的更强大。评价我们报告的指数从第二节的相对增加。3. 也就是说，对于L是表1中的矩阵，s是未调整的先天意见，s是调整后的先天意见，我们输入（sM（L）s−sM（L）s）/（sM（L）s）。病毒式营销如何改变指数？首先，让我们考虑在传播-认知模型下，我们的基线如何影响用户意见。在图2中，我们报告了当我们选择2%的节点作为种子时极化指数的变化我们重复实验5次，并给出平均值和方差。 在图2（a）中，我们看到营销活动对网络中的极化指数几乎没有影响，并且增加了不到0.1%。然而，当我们考虑带有逆火的极化运动时，情况就大不相同了（图2（b））：极化增加到60%，通常至少增加20%图2：不同数据集上极化指数的相对变化，其中k=2%n种子节点。该图显示（a）营销活动和（b）两极分化活动。如果最有影响力的用户分享两极分化的运动。 使用随机种子节点对极化的影响很小。分析的可扩展性和准确性在[33]中，我们证明了算法在图的大小上线性缩放，并且比贪婪算法快三个数量级，同时具有相似的质量。因此，接下来我们将关注仅考虑线性项并扩展到更大数据集的算法。营销活动的实验接下来，我们评估k= 0的营销活动的方法。5%n种子节点。在表3中，我们报告了所有先前提到的方法的结果，不包括行为与MaxInflu非常相似的HighDegree。我们将考虑求和指数和极化指数，并评估这些指数如何根据具有不同目标的算法的解决方案而变化。虽然这可能看起来违反直觉，但这种方法揭示了我们考虑的不同方法和我们优化的指数之间的有趣联系。 对于FJ，我们使用两个相应的版本，分别最大化求和指数和极化指数;对于两个大型数据集，FJ和FJUpp超时了。让我们来看看指数。方法Sum、LinDiscon和MaxInflu通常可以获得最高值，并且它们都具有相似的质量。毫不奇怪，这表明对于营销活动来说，最大化用户意见本质上与最大化影响力是一样对于九个数据集，总和指数增加不到5%，但对于一些数据集，它增加了高达18.75%。 非常有趣的是，只有在两个数据集上LinPol将Sum Index增加了1%以上，这表明LinPol和其他方法的解决方案非常不同。此外，我们观察到FJ的解决方案几乎没有增加Sum Index。然而，对于极化指数，情况是完全不同的在这里，LinPol显然实现了最大的增长，其次是