Abir De∗IIT Kharagpurabir.de@cse.iitkgp.ernet.inSourangshu BhattacharyaIIT Kharagpursourangshu@cse.iitkgp.ernet.inNiloy GangulyIIT Kharagpurniloy@cse.iitkgp.ernet.in5490在社交网络上划分内生和外生意见扩散过程0摘要0在线社交网络（OSN）中的网络意见扩散受到两种类型的意见的影响-内生意见是由用户之间的社交联系驱动的，外生意见是由新闻、动态等外部影响形成的。这种双重意见动态由属于两个类别的用户引导-有机用户通常发布内生意见，外在用户容易受到外部影响，大多发布外生信息。准确划分内生和外生信息为意见建模提供了重要线索，从而提高了其预测性能。另一方面，准确的用户选择有助于检测外在用户，从而有助于意见塑造。在本文中，我们设计了一种名为CherryPick的新型学习机制，通过解决消息和用户集的联合推理任务，从时间流的情感消息中对意见和用户进行分类。此外，我们从建模和塑造的角度验证了我们提案的有效性。此外，对于后者，我们在随机最优控制的新框架中制定了意见塑造问题，其中选择的外在用户最佳地发布外生信息，以引导他人的意见朝着期望的方向发展。在从Twitter爬取的五个数据集上，CherryPick在意见预测方面显著提高了准确性，超过了几个竞争对手。此外，它可以准确确定一组控制用户的质量，结合所提出的在线塑造策略，始终比几个最先进的基线更有效地引导意见动态。0ACM参考格式：Abir De，Sourangshu Bhattacharya和NiloyGanguly。2018年。在社交网络上划分内生和外生意见扩散过程。在WWW2018：2018年Web会议上，2018年4月23日至27日，法国里昂。ACM，纽约，纽约，美国，10页。https://doi.org/10.1145/30关于理解意见动态的研究，从建模和控制的角度来看，文献中充斥着两种方法[1-15]。第一种方法基于统计物理的概念，几乎没有数据驱动，因此预测性能较差[1-3，7-15]，而第二类模型旨在克服这些限制，通过从瞬态意见动态中学习可操作的线性模型[4-6]。0� 现在隶属于德国软件系统MPI。电子邮件：ade@mpi-sws.org0本文发表在知识共享署名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.31861210除了这些现有方法的个别局限性外，它们都通过天真的假设来研究意见动态现象-即缺乏外部影响或缺乏外部影响，尽管有经验证据证明存在这样的信号[16-20]。因此，现有模型“原样”只能在预测意见动态方面表现平平。由于社交网络是一个鼓励信息的内外流动的开放系统，大量的外部信息通过新闻、动态等渠道传递给用户。因此，涉及连接用户之间广泛互动讨论的网络意见形成过程也受到这些推荐给用户的外部来源的推动。因此，我们首先观察到两种意见家族-由邻居的影响而演变的内生意见和主要由外部因素驱动的外生意见。这种双重动态进一步将用户分为两类：主要表达内生意见的有机用户和主要发布外生内容的外在用户-它们共同在社交网络中有机地引导耦合的意见扩散过程。在大多数实际情况下，帖子（内生或外生）的真实标签以及用户（有机或外在）都不可用。因此，准确的无监督标记用户及其帖子为意见建模提供了复杂的特征-从而提高了广泛应用（如极性预测、品牌情感估计等）的预测性能。除了预测之外，准确的用户分类对意见塑造具有巨大的潜在影响。有效的用户分类技术帮助我们发现外在用户，即容易受到外部帖子影响的人。这些用户可以在意见塑造任务中轻松激活，其中在他们的墙上发布动态或新闻，以引导他人的意见达到给定的状态。最近，[7-14，21]已经开始处理意见塑造任务，但是现有的意见塑造方法都没有旨在识别外在用户，这使得控制策略在实践中无效。此外，[21]中的方法将控制信号分配给每个节点，这本质上意味着每个用户都是控制用户，可以控制他人的意见；因此，他们的提议在任何实际重要性方面都无关紧要。最近的两项工作[22，23]采用了类似的方向，但是它们专注于完全不同的应用，例如智能广播和活动最大化。在本文中，我们的目标是划分内生和外生消息，分类有机和外在用户，并最终从意见建模和特别是意见塑造的观点证明我们提案的实用性，对于后者，我们设计了一种高效的控制机制，以便以有利的方式策划整体意见动态。0研讨会：社交网络分析和Web上的图算法WWW 2018年4月23日至27日，法国里昂5500提出的方法：我们通过使用我们先前提出的模型SLANT[6]，来假设有机意见在外部行动存在的情况下的动态。它允许用户的潜在内生观点随时间变化，并通过邻居的内生和外生观点（表示为情感消息）来调节，即内生和外生观点（第3节）。随后，我们提出了CherryPick，这是一种原则性的学习机制，可以最优地划分内生和外生观点，并对有机和外在用户进行分类。为了将消息以及相应的用户进行分类，我们旨在选择符合高置信度的有机动态的事件集，即影响估计的低方差。为此，我们将这个问题设计为消息和用户类别的联合推理任务。我们发现，这个推理问题可以被形式化为基数约束的多维子模最大化问题的一个实例。为了解决这个优化问题，我们设计了一种新颖的贪婪方法，就像一个普通的贪婪子模最大化算法一样，它具有（1-1 /e）的近似界限（第4节）。为了展示我们的用户选择方法的有效性，我们提出了一个作为新颖随机最优控制问题的观点塑造任务。与之前的工作有所不同，我们通过将所选外生用户的强度解耦为外生（η（t））和内生部分（λ（t））来解决塑造问题，其中外生率与限制控制消息数量的成本相关。我们发现，这个多维控制信号的最优值线性依赖于当前观点，从而为塑造问题提供了一个简单但可扩展的闭环解决方案（第5节）。最后，我们对从Twitter抓取的五个不同数据集进行实验，并展示了通过分类内生和外生消息，CherryPick在预测意见方面取得了显著的性能提升。此外，我们观察到所选的外生用户以及所提出的塑造策略，比几个基线更有效地引导其他人的意见动态（第6节）。贡献：总结起来，我们在本文中的主要贡献有两个方面：1.一种无监督的划分方法：我们的提议提供了CherryPick，一种新颖的无监督学习算法，它在意见动态的场景中联合分类一系列未标记的消息及其用户。原则上，CherryPick是一种贪婪算法，最大化了一个新颖的函数f，这是一个参数方差的逆测量。我们发现f在用户和消息集中都具有联合子模性质，从而为所提出的算法提供了可证明的近似保证。尽管消息流之间存在复杂的相互依赖关系，但存在这样一个重要函数，我们认为这是一个令人惊讶且关键的观察结果。2.通过激活外生用户进行意见塑造：为了证明外生用户识别的效用，我们开发了一种新颖的随机意见控制框架，用于计算外生用户应该发布的最优控制消息强度，以便以期望的方式引导意见动态。与之前的工作有所不同，我们的提议提供了一种闭环反馈控制策略，可以在线计算所需的消息强度。02 相关工作0多年来，意见建模及其应用已经以不同的形式广泛研究。在本节中，我们从三个主要角度回顾了其中一些研究成果，即意见动态建模，意见感知和意见塑造。意见动态建模。对网络上意见流动的演化过程进行建模，主要遵循两种方法，基于（a）统计物理和（b）数据驱动技术。第一类模型，例如Voter，Flocking，DeGroot等，传统上旨在捕捉各种调节现实生活现象，例如共识，极化，聚类，共存等[1-3，24-31]。Voter模型[1]是一种离散的意见模型，其中意见被表示为名义值，并在每一步中从影响邻居那里复制。这个基本原理仍然是许多离散意见模型的主要工具[3，24-29，31]。与这些模型相反，Flocking和DeGroot是连续的意见模型。在Flocking模型及其变体[30]中，具有意见xi的节点i首先选择满足|xi-xj|≤ϵ的邻居j的集合，然后通过对这些意见求平均来更新自己的意见。另一方面，DeGroot模型[2]允许用户使用所有邻居的平均意见更新自己的意见。在这个模型中，底层影响矩阵是行随机的，对于强连通图强制实现共识。第二类模型，例如BiasedVoter，AsLM，SLANT等，旨在从反映瞬态意见动态的时间消息流中学习一个可处理的线性模型[4-6]。虽然BiasedVoter模型[4]统一了DeGroot和Flocking模型的各个方面，但AsLM[5]通过放松影响矩阵的结构来推广DeGroot模型。与这些模型不同，SLANT[6]将意见动态与消息动态相结合，使用随机生成模型。然而，所有这些方法都回避了外部性的影响，这严重限制了它们的预测能力。意见感知：从文本数据中感知意见或挖掘情感传统上依赖于复杂的基于NLP的机器。有关详细信息，请参见[32，33]。这两本专著提供了全面的调查。一般来说，LIWC[34]被广泛认为是从丰富的文本数据中计算情感的基准工具。另一方面，Hannak等人开发了一种简单而有效的方法，用于从短小的非正式文本（如推文）中进行情感挖掘[35]，也被[5，6]使用。最近，一类作品[36-38]设计了简单的监督策略来感知意见垃圾邮件，其中一些[37，38]还提倡意见垃圾邮件的时间信号的作用。请注意，外生意见与意见垃圾邮件根本不同。与垃圾邮件不同，垃圾邮件是未经请求且与讨论无关的，外生帖子通常是相关的，但只是某些外部新闻或信息的知情反映。此外，由于垃圾邮件的属性是其固有属性，它不依赖于之前的消息。然而，当转发外生帖子时，它可以变成内生的（见表3）。此外，意见垃圾邮件检测技术基于监督分类的原则，而监督分类又需要标记的消息。然而，在网络意见动态的背景下，消息（推文）是未标记的，这使得垃圾邮件检测技术在这种情况下实际上不适用。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, FranceAд(t − s)[m(s) ⊙ dN(s) + w(s) ⊙ dM(s)](6)Bκ(t − s)[dN(s) + dM(s)].(7)Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France5510意见控制：意见塑造主要由控制理论家研究[7-14]。这些研究强调共识控制，因此在大多数实际场景中的适用性有限。此外，它们大多数假设控制意见是连续信号，而在实践中，表达的意见只能通过消息或帖子来观察到。只有最近的研究[21]尝试通过将控制信号建模为离散时期来克服这些限制，然而，这提供了一种近似和计算效率低下的解决方案。03 模型制定0在本节中，我们首先重新审视了在没有外生行为的情况下的意见动态模型[6]，然后描述了在存在外生行为的情况下的模型。03.1 问题设置0我们使用两个数据源作为输入：一个用户之间的有向社交网络 G =(V, E)（例如朋友、关注等之间的连接）和在给定时间窗口 [0, T)内这些用户发布的消息的聚合历史U(T)。在本文中，我们仅使用三个组成部分来总结每个消息事件 e_i∈ U(T)，即发布消息的用户 u_i，与消息相关的意见或情感值ζ_i，以及帖子的时间戳 t_i。因此，U(T) := {e_i = (u_i, ζ_i, t_i) | t_i д 1 (0) 和 д 2 (1) < д 2 (0) 可以推导出 f的条件单调性和次模性。 (i)的其余证明重点在于证明 d0dp д 2 ( p ) < 0，这保证了 д 1 (1) > д 1 (0) 和 д 2 (0) > д 2(1)。这种方法在网络可控性分析中被采用[54]，在这里被推广到更复杂的网络动力系统。定理的第二部分的证明直接由定理的第一部分得出。详细的证明在[46]中提供。注意，上述定理的第二部分在隐含一个假设，即 V ( H T ) � O；换句话说，消息集合 H T 的用户属于 O。否则，如果我们假设 v ∈ V ( H T ) 但 v �∈ O ，那么用户 v发布的事件，即向量 ϕ v i 不会对 f ( H T , O ) 有贡献。因此，f (H T \{ e v } , O ) = f ( H T , O )，其中 e v 是用户 v发布的消息。因此，该假设为 f ( H T , O ) 的最小用户集合 O的选择提供了一个选择，并且不具有限制性。0最大化f(H T, O)：由于f在HT和O中是联合次模的，所以它的最大化需要进一步修改传统的贪婪方法，该方法用于最大化单个集合的次模函数[55]。最大化例程在算法1中正式显示。在每一步中，它通过最大化边际增益f(H T ∪ {e}, O∪ {u}) − f(H T, O)（步骤7，算法1）依次贪婪地将事件e添加到HT和用户u添加到O，直到用户总数达到NO（步骤5-11）。一旦|O|达到NO，它不再添加任何其他用户，但继续选择H T中最大化f(H T ∪ {e},O) − f(H T, O)的事件e，直到H T达到NH。也许令人惊讶的是，修改后的贪婪算法也能够达到f(H T,O)最大值的常数(1−1/e)的一部分。0引理5（解决质量）。算法1对f(H T, O)具有(1−1/e)的近似界限。0算法1：Υ = CherryPick(f, N O, N H, V, U T)01：初始化：2：H T ← �，O ← �，I ← V，C T ← U T3：一般子程序：4：当|H T | < N H时执行5：如果|O | < NO，则执行6：选择e和u的贪婪方式7：(e, u) ← arg max e, u f(H T ∪{e}, O ∪ {u}) − f(H T, O)8：C T ← C T \{e}，I ←I\{u}9：更新内生消息集和用户集10：H T ← H T ∪ {e}，O ← O ∪{u}11：结束如果12：用户预算已达到。|O | = NO，所以从现在开始只选择消息。13：e ← arg max e ∈U T f(H T ∪{e}, O) − f(H T, O)14：C T ← C T \{e}15：仅更新内生消息集16：H T← H T ∪ {e}17：结束当18：Υ = (H T, O, C T, I)19：返回Υ。0证明的概述与普通次模函数的证明类似（但不完全相同）。证明的关键是使用算法1中获得的f的联合次模性逐步更新f的下界。这样的下界，在大量更新之后，接近于(1−1/e)。为了简洁起见，此处省略了证明，但在[46]中给出。除了所选有机用户I =V\O之外的其他用户是在第5节中的意见控制期间用于引导他人意见的外在用户。0算法2：参数估计01：输入：N O，N H，G，U T 2：输出：(α�，µ�，A�，B�)3：首先找到内生消息4：(H T, O, C T, I) = CherryPick(f,N O, N H, V, U T) 5：仅在HT上估计参数6：(α�，µ�，A�，B�) = argmax L(α, µ, A, B |HT, O) 7：返回α�，µ�，A�，B�。0因此，所得到的事件集H T将用于通过最大化L(α, µ, A, B |H T,O)来估计所有参数A，µ，α，B（参见算法2）。0e i ∈H T p(m u i | x � u i (ti)) + �0u ∈O00 λ � u (s)ds.0由于L是凹函数，因此可以高效地最大化它。我们采用了[6]中作者提供的方法，该方法可以准确计算参数。05引导意见动力学0在本节中，我们正式陈述在线意见塑造问题，然后从跳跃SDE的随机控制的角度来解决它（方程（16））。首先，我们从控制的角度修改了由方程（10）给出的内生动力学。0d x � (t) = ω(α − x � (t)) dt + Am(t) ⊙ dN(t) + C dM+(t) − CdM−(t)0简而言之，一组用户通过发布正面（+1 意见）和负面（-1 意见）的消息来控制内生意见过程 x � ( t)，这些消息与计数过程 M + ( t ) 和 M - ( t ) 相关联。这里 C 和 D 是大小为 |V|×|I|的矩阵。它们是由选定的控制用户引起的 A 和 B 的子矩阵。即，C = A V , I 和 D = B V ,I。我们的目标是找到控制计数过程 M ± ( t ) 的 η ± ( t ) 的强度，以最优方式引导用户的意见。此外，我们假设 ξ max (B ) << 1。实际上，我们发现大多数数据集都满足这个性质，即时间影响的数值很小。opinion) associated with counting process M+(t) and M−(t). HereC and D are matrices of size |V|×|I|. They are submatrices of Aand B respectively, induced by the selected control users. That is,C = AV, I and D = BV, I. Our objective is to find the intensityof η±(t) of the control counting processes M±(t), that optimallysteer the opinions of the users in a desired way. Additionally, weassume that ξmax(B) << 1. In reality, we actually found that mostdatasets satisfy this property, that is the temporal influences takequite small numbers.ℓ(x∗(t),η±(t))dt].(17)ℓ(x∗(t),η±(t))dt](19)Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France55405.1 在线意见塑造问题0给定一个有向网络 G = ( V , E ) 和一个小的控制用户集合I，我们的目标是找到最优的控制强度 η ± ( t)，以最小化网络整体内生意见的特定损失函数 ℓ ( x � ( t ) , λ � ( t ) , η± ( t
我的内容管理
展开
