社交网络中影响最大化的算法研究

0Array 16 (2022) 1002640e under the CC BY-NC-ND license(http://creativecommons.org/licenses/by-nc-nd/4.0/).0ScienceDirect 提供的内容列表0Array0期刊主页：www.elsevier.com/locate/array0社交网络中的影响最大化：理论、方法和挑战0叶宇鑫，陈云亮�，韩伟0中国地质大学（武汉）计算机学院，430078，中国0文 献 信 息0关键词：社交网络 信息传播社会影响 影响最大化0摘 要0影响最大化（IM）是从社交网络中选择一组种子节点，以便最多的个体受到它们的影响的过程。计算给定种子集的社会效应，并确定最大化社会影响的最小种子集，是IM问题中的两个理论挑战，因此当前大多数研究项目都集中在寻找这两个问题的解决方案上。本文对IM算法的高级方法进行了比较研究，特别关注以下关键方面：（1）建立IM问题的基础，首先回顾了三种扩散模型，并比较了它们的特点。基于经典扩散模型，总结了基于上下文感知的扩散模型和基于深度学习的扩散过程模拟的研究成果；（2）使用IM算法的算法框架，对经典IM算法和上下文感知IM算法进行了全面分析和比较；（3）探讨了该领域的关键挑战和未来研究方向。对于新手研究IM领域的研究人员，我们的研究提供了该领域最新的进展，更深入地了解IM问题，并为进一步开展该领域的工作奠定了坚实的基础。01. 引言0在社交网络中最大化影响可以从更广泛的意义上解释。首先，将社交网络视为具有用户节点和它们之间连接的有向图。通过口碑效应在整个社交网络图中推广该产品，口碑效应是人与人之间传播的效应。推广可能导致迅速下降或迅速增长。这两种结果取决于三个关键问题。第一个问题是如何选择最初获得尝试产品权利的人。这就是后面提到的种子节点集S。第二个问题是，这一小群人如何让其他人受到影响而购买产品？实际上，这个过程是不同扩散模型的能力。最后一个问题是如何估计受到这一小群人影响的用户数量，即最具影响力的人。这实际上是估计给定种子集的传播影响的问题。根据上述三个问题，社交网络中的影响最大化问题可以定义为在社交网络中找到由最小数量的节点组成的种子集，以便它们可以影响社交网络中最多的用户；即影响最大化。影响最大化最常用于社交网络病毒营销；即，为营销目的识别潜在客户，目标是最大限度地降低营销成本并最大化利润。病毒营销试图利用“口碑效应”找到0� 通讯作者。电子邮件地址：yyx0000605@cug.edu.cn（叶宇鑫），chenyunliang@cug.edu.cn（陈云亮），weihan@cug.edu.cn（韩伟）。0在让更多人使用之前，让一小群知名人士尝试产品[1,2]。影响最大化首先被[3,4]作为算法问题考虑，他们使用马尔可夫场来解决IM问题，并使用概率模型来定义它。然而，用户如何相互沟通以及在选择了一定群体的用户后扩散过程将如何继续仍不清楚。因此，Kempe等人[5]首次将问题定义为离散优化问题，指定了两种扩散模型，并在理论上证明了在这两种扩散模型下IM问题是NP难的。最后，提出了一种贪婪方法，可以近似得到最优解，近似比为1−1∕�。它利用了影响函数的次模性。他们还在实验中表明，他们的贪婪算法在影响传播方面明显优于经典的度和基于中心性的启发式方法。然而，这种基于模拟的方法[5]非常耗时，因此出现了许多基于贪婪算法的优化方法。从那时起，影响最大化问题已经跳出了营销或商业领域，专注于问题表述和模型学习。本综述旨在从算法角度全面研究现有先进的IM算法，重点关注图1所示的四个领域。0https://doi.org/10.1016/j.array.2022.100264收稿日期2022年10月6日；修订稿收稿日期2022年11月15日；接受日期2022年11月17日20Array 16 (2022) 1002640Y. Ye等0图1. 综述概览。0•IM问题（第2节）。从数学层面正式定义了IM问题，并更详细地介绍了估计扩散影响和在扩散模型下最大化影响的两个主要理论困难。•扩散模型（第3节）。作为影响最大化问题的重要部分，提出了三种扩散模型，即经典扩散模型、上下文感知模型和基于深度学习的扩散模型。•IM算法（第4节）。为了解决第3章提出的IM问题的困难，本章更详细地阐述了现有研究解决方案。首先回顾了贪婪方法，然后将现有的IM算法分为四类：基于模拟的、基于启发式的、基于抽样的和基于元启发式的，并进行了彻底的理论比较。•基于上下文感知的IM算法（第5节）。在本节中，我们回顾了IM问题的扩展问题，通过考虑用户的位置、兴趣、信息传播的主题、传播时间等，使得最终获得的种子集更加高效。由于在这一部分有更多的分类，本综述侧重于三个主要类别：位置、时间和主题。0已经存在大量关于社交网络影响分析的综述。尽管这些综述[6-8]侧重于IM算法，但它们已经过时，缺乏最新的IM算法。[9]是对最新IM算法的全面实验研究，没有进行任何理论分析，[10]对此实验提出了质疑。尽管[11]首次考虑了基于上下文感知的IM问题，并对当前IM算法进行了详细的理论分析，但他们只使用了贪婪0用于分类IM技术的算法。[12]不是基于贪婪算法进行分类，而是完全新的IM方法分类。[13]侧重于基于单变量和多变量网络的理论分析的算法框架。此外，还有大量工作用于比较特征。[14]从算法优化到IM算法的角度介绍了IM算法。[15]专注于基于位置驱动的影响最大化问题，不是对影响最大化问题的全面介绍。[16]考虑用户的行为或态度，并总结了用户行为感知的影响最大化方法。经典IM问题的变体，即基于上下文感知的IM问题（即结合传播时间限制、用户地理位置限制、传播消息的主题等），对IM问题的实际意义和种子节点的有效性做出了重大贡献。[11]首次总结了基于上下文感知的IM问题和相关算法，介绍了共计六个模块：位置感知、时间感知、主题感知、动态感知、竞争和其他因素。尽管本综述对此方面也进行了总结，但不如[11]全面，仅侧重于时间、位置和主题，但我们在时间和位置两个部分有显著差异。首先，本部分时间感知的IM算法部分进行了更详细的分析，而[11]的算法部分的阐述基本类似于扩散模型部分，仅侧重于离散时间感知模型和连续时间感知模型，并没有具体涉及本部分的算法思想。其次，对于位置感知部分，我们将其分为两部分：在线位置感知影响最大化（OLIM）问题和离线广告牌3𝜎 𝑆𝑆hard [18].0数组16（2022）1002640叶Y等。0影响最大化（OBIM）问题，用于阐述OBIM问题，该问题在[11]中不存在。0除了上述差异，这篇综述有三个主要的0不同于其他综述的三个主要贡献，包括[11]。具体的三个主要贡献如下：0•  除了经典扩散模型外，我们提出了0第一次提出了两个主要类别的上下文感知扩散模型和基于深度学习的扩散模型。并且比较了三类扩散模型的特征，如表1（经典扩散模型），表2（上下文感知扩散模型）和表3（基于深度学习的扩散模型）。0•  IM问题的理论困难分为0更详细，两个主要的困难，影响最大化问题和传播影响问题，更清晰和明确地总结了。影响最大化问题是找到最小的种子集，以最大化社会影响。传播影响问题是指解决IM问题的过程，需要克服估计给定种子集的社会影响的问题。0•  除了0经典三大分类：基于模拟的、基于启发式的和基于抽样的，本综述首次增加了解决NP-hard问题的强大工具，即基于元启发式的方法。对于上下文感知IM算法，首次添加了离线广告牌IM（OBIM）到位置感知IM算法，而在线位置感知IM（OLIM）像经典IM算法一样分类。当然，最后，我们对所有IM算法进行了理论比较分析，如表4、表5和表6所示。02. 影响最大化问题02.1. 问题定义0定义1（影响最大化（IM）[5]）。影响最大化问题是找到一组有影响力的用户（种子集）A�A，由i < |A|个节点组成，给定一个社交网络A=（A，A）和一个正整数i，可以通过扩散模型的传播最大化A中受影响用户的数量。其中A是A中的节点集（即用户），A是A中的（有向/无向）边的集合（即用户之间的社交连接）。该问题可以用以下方程描述：0�� �（�，�）= argmax ���，|�|=�  � �（�，�）（1）0其中σ是一个函数，用于计算给定节点集的影响传播，并表示通过激活e中的节点集实现的影响传播。02.2. 问题难度0从问题定义来看，解决IM问题是明确的0首先需要估计给定种子集A的传播影响σ（A），然后使传播影响最大化。但是这两个步骤在理论上都很困难。我们将估计给定种子集A的传播影响σ（A）的理论困难称为传播影响问题，将最大化传播影响的理论困难称为IM问题。0•  传播影响问题。关于理论上的困难-0估计给定种子集A的传播影响σ（A）的困难，[17]表明该问题是#p-hard。0定理1.在独立级联模型（ICM）下，对于已激活用户集合A，给定传播影响的估计σ（A）是#P-hard [17]。0定理2. 在线性阈值模型（LTM）下，估计的传播影响  � ( � )  是NP难的。0根据上述定理，除非N =NP，否则我们无法在多项式时间内找到最优解，因此很多研究致力于克服这一理论难题。例如，基于模拟的、基于启发式的、基于抽样的等。详情可参见第4章第2节，现有IM算法的分类。0•  影响最大化问题。Kempe等人[ 5 ]已经证明了传播影响  � ( � )  对于给定的激活用户集  �是0定理3. 影响最大化问题的一个重要部分是理论上难以最大化传播影响  � ( � )。0定理3. 在独立情况下，IM问题是NP难的。0级联模型（ICM）、线性阈值模型（LTM）和触发模型（TRM）[ 5 ]。03. 扩散模型的分类0作为影响最大化问题的重要部分，0扩散模型解决的问题是如何在社交网络中在节点之间传播信息。在扩散模型中，任何时间点  � ，任何节点  �  ∈  �  都有两种状态，活跃和不活跃。在初始状态  �  = 0时，除了种子集  � � �  外，  �中的其他节点都处于不活跃状态。随后的过程从种子节点开始。每个扩散模型根据自己的规则和邻居节点的行为使种子节点的邻居节点失活。这些被激活的节点继续影响它们的邻居，直到没有新的节点可以被激活为止。激活结束了传播过程。扩散模型的研究分为以下三类：（1）经典模型；（2）上下文感知模型；（3）基于深度学习的扩散模型。03.1. 经典模型0经典扩散模型通常分为阈值模型，0级联模型、触发模型和流行病模型。这些扩散模型是随机模型。它们根据一些概率规则在每个时间点将传播信息从一个节点流向其邻居。表1总结了本节中的分析，详情将在以下小节中解释。03.1.1. 阈值模型（TM）0阈值模型首次由[ 19 ]提出。任何阈值模型0模型具有一个或一组用于区分模型预测行为的值范围的阈值。在阈值模型中，最常用的模型之一是线性阈值模型（LTM）。在LTM中，每条边  �  = ( �, � ) ∈  �都有一个权重 � �,� ，它是节点  �  在所有入度邻居节点中的重要百分比。每个节点  �也有一个影响阈值 � � ，它遵循 [0 ,  1] 的均匀分布，并且一旦确定就不会改变。在�  = 0 时，种子节点集首先被激活为初始节点，所有其他节点都是不活跃的。在  �≥  1  的某一时刻，每个不活跃的节点  �需要将所有活跃的入度邻居节点加到其线性加权和中，然后检查它是否已经达到其受影响的阈值  � � ，即 ∑ � ∈ � ( �,� ) � �,� ≥  � � 。如果是，节点  �  就被激活了。0时间  � 。在某一时刻，不再有新的节点被激活，然后传播过程结束。0根据阈值值的不同，其他阈值模型可以被分类为以下几种：(1) 多数TM [ 4 , 20 ]，其中 ( � �0被分类为02 � ( � ) ) ; (2) small TM [ 21 ]，其中阈值值  � �  是一个非常小的常数; (3) 分离的TM [ 22 , 23]，除了独立维护每种方法的阈值和扩散过程外，这个模型与LTM模型相当；(4) 一致的TM [ 40非常小的常数；（3）分离的TM [ 22 , 23]，除了独立维护每种方法的阈值和扩散过程外，这个模型与LTM模型相当；（4）一致的TM [ 4 ]，其中 ( � �  =  � ( � ) ) ，上述方程中的  � ( � )  表示节点  �的度中心性。[ 20]提出了LT-C（带颜色的线性阈值），它关注的不仅是用户之间的影响，还有产品的采纳率。4inanetworks can be considered as a disease in the epidemic transmissionprocess [32]. In accordance with the characteristics of the modelcascade, three epidemic models have been proposed: susceptible toinfectious disease recovery (SIR), susceptible to infectious disease sus-ceptible (SIS), and susceptible to infectious disease recovery susceptible(SIRS) [23]. The susceptible–infected (SI) model is the simplest. It saysthat each node can be in one of two states: susceptible or infected.When a node is in the vulnerable state, it can be infected. Once a node𝑢 is infected, it will always be infected and spread on its own, sinceit only has one chance to affect a neighboring node 𝑣 that is in thesusceptible state. susceptible–infected–susceptible (SIS) model [33] issimilar to SI, except that it considers that an infected node 𝑢 can returnto the susceptible state with The susceptible infected recovered (SIR)model [23] is roughly the same as SI, but it assumes that nodes havethree states: susceptible, infected, and recovered. It assumes that aninfected node 𝑢 can restore health and develop immunity to diseasewith a certain probability, which means that node 𝑢 will never beinfected again, and the rest is the same as SI. recovered susceptible(SIRS) extends the SIR model by assuming that an infected node 𝑢will recover health with a certain probability and then may becomesusceptible again.0Array 16 (2022) 1002640Y. Ye et al.0表1经典扩散模型属性比较0经典扩散模型类别社交网络子模块化激活0有向加权递减回报单调时间约束多重激活0阈值模型(TM)0线性TM(LTM)√√√√××多数TM√√√√√×小TM√√√√××一致TM√√××××分离TM√√××××LT-C√√√√××0级联模型(CM)0独立CM(ICM)√√√√××权重CM√√√√××DICM√×√×√×意见CM√√√×√√0ICM-NO√√√√××0触发模型(TRM) 递减CM√√√√××0流行病模型(EM)0SIR√√×√××SIS√√×√×√0SIRS√√×√×√03.1.2.级联模型(CM)0Goldenberg等人[ 24 , 25 ]首次引入级联模型到0病毒营销领域中最广泛使用的模型是独立级联模型(ICM)。该模型中的每条边�=(�,�)∈�都有一个激活概率��,�∈[0,1]，激活概率公式为��,�=1−(1−�)���，其中���是]。0节点和所有其他节点都是非活动状态。在某个时刻�≥1，非活动节点�仅在�时由所有上一时刻激活的入射邻居以��,�的激活概率激活一次且仅一次，即节点�的每个上一时刻激活的入射邻居只能独立激活它，并且这些入射邻居将保持活动状态并在之后停止激活。当一个节点在其激活尝试中失败且节点�的其他入射邻居在时刻�未成功激活节点�时，节点�在时刻�仍然处于非活动状态。传播过程仅在某个时刻不再有新节点被激活时结束。0WCM(加权级联模型)[ 27 ]是级联模型的扩展0传统的IC模型也遵循上述规则，但增加了节点属性的概念。也就是说，除了每条边的激活概率��,�之外，每个节点都有一个非负值��的权重，该权重是根据其属性独立于网络结构计算的。[ 28]提出了动态独立级联模型(DICM)中的每个节点�都有一个遵循伯努利分布的随机变量��。当��=1时，意味着节点�已成功激活。此外，还有一些基于ICM的扩散模型，例如带有负面意见的ICM-NO[ 29 ]，带有正面和负面意见的Opinion CM[ 30 ]。03.1.3.触发模型(TRM)0此外，[ 5 ]建议了触发模型，强调了TM0和CM是TR的例外。触发模型中的每个节点�都有一个阈值��和一个分布函数��。该分函数转移到其邻居子集的概率表示邻居子集能够影响节点�的程度。根据节点�的邻居子集的分布，TR模型为扩散过程的每个示例选择一个随机的‘‘触发集’’。在�=0时刻，种子节点集首先被激活为初始节点，其他节点处于非活动状态。在某个时刻�≥1，如果非活动节点�在选择触发集中的上一时刻已激活的邻居节点，则在时刻�节点�将被激活。在某个时刻，不再有新节点被激活，则传播过程结束。0在触发模型的位置，[31]提出了递减级联（DC）模型，这是一个更全面的模型。影响捕捉0（DC）模型，这是一个更全面的模型。影响0节点�对节点�的概率现在由该模型定义为��(�,��)，其中��表示节点�的活跃邻居的子集。0捕捉递减，DC强制��(�,�)≥��(�,�)，对于���。03.1.4. 流行病模型（EM）0流行病传播与信息传播有密切相似性03.2. 上下文感知模型0然而，节点之间的激活不仅仅取决于两个节点之间的激活概率，以及以这种方式找到的种子集合没有一定的有效性。因此，在传播过程中需要考虑用户的地理位置、信息传播的时间、信息传播的主题、用户的兴趣、群体效应、产品竞争等因素。对于不同的上下文感知IM问题，相应的扩散模型也是不同的。本文重点关注三个主要的上下文感知IM问题（见第5节），即位置、时间和主题。对于主题部分，主要是对经典扩散模型进行了扩展，而对于位置和时间部分，则是对经典扩散模型进行了改进或提出了新的扩散模型。因此，本节主要介绍了位置感知模型（LAM）和时间感知模型（TAM）。表2总结了本节的分析，详细内容将在接下来的小节中进行分析。Array 16 (2022) 10026450Y. Ye 等0表2 上下文感知扩散模型的属性比较。0上下文感知模型 类别 扩散模型 社交网络 子模块化 激活0有向加权递减回报单调时间约束多重激活0位置感知（LAM）0在线位置感知 ICM √ √ √ √ × × LTM √ √ √ √ × ×0离线广告牌 OI √ – × × × × MI √ – – − × × LI √ – – − × ×0时态感知(TAM)0离散时间 IC-M √ √ √ √ √ × CTIC √ √ – − √ × LAIC √ √ √ √ √ ×0连续时间 TV-IC √ √ √ √ √ × TV-LT √ √ √ √ √ × DynaDiffuse √ √ √ √ √ ×0基于经典扩散模型提出了改进或新的扩散模型。因此，本节主要介绍了位置感知模型（LAM）和时间感知模型（TAM）。表2总结了本节的分析，详细内容将在接下来的小节中进行分析。03.2.1.位置感知模型（LAM）0基于位置感知上下文的问题分为两类0类别：在线位置感知影响最大化（OLIM）和离线广告牌影响最大化（OBIM）。其中，OLIM问题使用经典扩散模型，最常见的扩散模型是独立级联模型（ICM）、线性阈值模型（LTM）和最大影响树模型（MIA）[18]。OBIM问题提出了新的扩散模型，即一次印象（OI）模型[34]、多次印象（MI）模型[35]和逻辑影响（LI）模型[36]。0• 0这些规定了给定轨迹数据库  �  包括一组轨迹  �  = { � 1 , � 2 ,  …  , � | � | }，一个具有位置0轨迹  � ，如果  � � �  ∈  � 使得 Distance ( � � ,  b.loc ) ≤  � ，即，从  � �  到 b.lo的距离小于或等于阈值 � ，那么可以说这个轨迹  �  受到了广告牌  �  的影响。0• 0这些规定了给定轨迹数据库  �  包括一组轨迹  �  = { � 1 , � 2 ,  …  , � | � | }，广告牌的集合0�  = { � 1 , � 2 ,  …  , � � } ，  size  ( � � )  是广告牌  � �  的面板大小。0pr ( � � , � ) 为均匀值，其中  pr ( � � , � ) = size ( � � )  ∕ � ，  �  =0max � � ∈ �  size ( � � ) 。最后，[35]给出了广告牌对轨迹的影响的公式0广告牌集合  � � �  对轨迹  � 的影响： pr( �, � ) = 1 − � � � ∈ � ( 1 − pr  ( � � , �0• 0规定了给定轨迹数据库  �  包括一组轨迹  � = { � 1 , � 2 ,  …  , � | � | }，一组广告牌  � = { � 1 , � 2 ,  …  , � � }  和伯努利随机变量  �  ( � � , � ) ，0指示广告牌  �  是否影响轨迹�的状态。当  � ( � � , � ) = 1时，表示影响很大。逻辑影响模型通过基于逻辑函数的方程来评估一组广告牌  � � �  对轨迹  �  的有效影响P(S, t)。03.2.2.时间感知模型（TAM）0经典扩散模型是与时间无关的，这意味着0由于传统扩散模型中没有新节点被激活，扩散过程就结束了。然而，扩散过程往往是有时间限制的，因此有必要考虑时间因素。目前的研究大致分为两类：（1）离散时间模型；（2）连续时间模型。0• 离散时间模型。离散时间模型本质上是模拟0类似于IC和LT，因为它们仍然处于离散时间步骤中。因此，这种类型的模型主要是将节点之间的扩散过程建模为不同时间步骤的离散随机变量，以达到扩展IC模型的目的。基于传统ICM模型，引入了IC-M模型[37]。在IC-M模型中，节点  �  有一次机会以概率  � �,�  去除节点  � ，节点y有多次机会以概率  �( �, � )  接触节点  � 。在该模型下，选择种子集S，使得在  �时间步骤内种子集的预期影响最大。[38]通过将时间约束和连续激活的两个属性添加到传统ICM模型中，提出了连续激活和时间限制的IC（CT-IC）。该模型与IC模型的区别在于：（1）每个激活节点可以重复激活其邻居；（2）激活过程直到给定时间  �才会停止。CT-IC模型满足影响传播的单调性和次模性，因此可以保证在CT-IC模型下的贪婪算法具有近似比  (1 − 1∕ � ) 。首先，每个种子节点在时刻0  被激活，并在时刻  �  = 1 ,  2 ,  3 ,  …  激活邻居节点。 � �是时刻�激活的节点集合，其中  � 0  =  � 。每个激活的节点  �  ∈  � �  以概率  �� �− � � ( �, � )  激活其邻居节点  � ，其中  � � 为激活邻居节点  �的时间。激活概率定义如下：  �� � ( �, � ) =  �� 0 ( �, � )  �  exp ( − � � � ) ，其中  � �表示节点u对其邻居的影响减小的速率。与[38–40]提出的延迟独立级联（LAIC）模型具有相同的概念，该模型将影响传播延迟的信息纳入IC模型。在该模型中，当节点  �  在步骤  �  首次被激活时，它以概率 � �� � ��� � ( � � )  在步骤  �+  � �  激活当前非活动的邻居节点  � 。此外，0一个节点只能被激活一次。如果一个节点受到多个邻居的影响，它将在最早的激活时间被触发；其他激活将被忽略。0•连续时间模型。连续时间模型更0与现实世界的情景一致，因为节点之间的扩散过程在本质上是连续的。给定预定义的停止时间 � > 0，如果在停止时间 �之前没有更多的节点被激活，则扩散过程停止。并且给定节点 � 的激活时间�，节点 � 在任何时间段 � > � 时激活节点 � 的概率是 �（� ∣ �; ��,�），其中0��,� 用于确定节点 � 对节点 � 的影响以及节点 �的影响强度。[41]首次提出了连续时间独立级联模型，该模型将扩散过程建模为发生在不同速率的离散时间过程的连续网络。他们仅使用了时间相关的传播概率来建模扩散60Array 16（2022）1002640Y. Ye等人0表3深度学习扩散模型属性比较0算法年份贡献可比算法0基于特征的节点嵌入图核IEDP [45] 2017提出了信息嵌入式模型IEDP来预测信息扩散过程0ICMGDM模型CSDK0Topo-LSTM [46] 2017提出了表示学习方法，用于探索级联结构，从而进行扩散预测0EmbeddedICDeepCasDeepWalkIC-SB0Embedded-IC [47]2016提出了嵌入级联模型Embedded-IC，将社交网络的用户嵌入到潜在空间中，以提取比传统图学习方法定义的更健壮的扩散概率0ICMNetrateCTIC0节点对之间的传播速率和感染时间，而不使用依赖于未知外部因素的先验感染概率。[42]引入了瞬时变量独立级联（TV-IC），这是一种更广泛的基于时间的扩散模型，基于ICM。该模型假设节点 � 在时间步 �1处处于活跃状态，并通过边（�, �）与节点 � 进行通信。在时间步 �2处，传播影响到达节点y，但此时节点 � 尚未激活。节点 � 是否在 �2时间步激活取决于时间差（�2,�1）。[42]同样提出了基于LTM的第一个时态模型，称为时变线性阈值（TV-LT）。由于这两个模型的扩散函数的次模性，该算法可以提供可证明的近似保证。[43]提出了一种用于动态扩散网络的连续时间动态扩散模型（Dy-naDiffuse），能够在估计给定时间范围内的影响传播时考虑一组节点的影响。他们假设在该模型中，一旦节点受到影响，该状态就会持续到结束。当没有剩余未受影响的节点或已经经过给定时间 � 时，该过程结束。03.3.基于深度学习的扩散模型0早期的工作假设扩散模型已经给定，例如0独立级联模型（ICM）和线性阈值模型（LTM）。一些研究尝试通过构建有价值的变量（如网络结构和时间信息[17]，用户节点的社交角色[48]和节点的用户互动[49]）从现有级联数据中开发扩散模型，以预测节点激活概率。即使机器学习技术明显提高了扩散预测的准确性，但创建特征仍需要大量的人工劳动和特定领域的专业知识。随着神经网络领域的快速发展，最近的研究[44-47]开始使用深度学习进行扩散建模，从而避免了繁重的特征工程。表3总结了本节的分析，详细内容将在下面的小节中进行分析。0李等人[44]提出了端到端深度学习方法Deep-0Cas用于预测信息级联的未来大小。在每个时间间隔内活跃节点上诱导的子图用于最初模拟级联。然后将子图分成几条随机行走路径，并学习其嵌入向量0使用门控递归单元（GRU）。因此，通过这个子图的嵌入向量来投影即将到来的级联的大小。端到端预测器DeepCas优于替代节点嵌入和图嵌入技术以及基于特征的机器学习技术。0高等人[45]建议采用信息嵌入...0基于传播预测（IEDP）模型，而不是显式基于图的方法来提取社会结构以了解扩散的时间动态。他们将时间传播预测的挑战转化为在嵌入空间中学习空间概率的目标，并通过在可能的嵌入空间中嵌入扩散内容和用户的相对位置来计算IEDP中扩散传播的概率。还建议在预期嵌入空间中估计信息扩散，并提出了一种有效的基于边界的优化过程。0[46]提出了Embedded-IC，这是独立级联的嵌入版本...0独立级联模型，用于预测在线社交网络中的信息传播。他们对节点进行分类，以便在扩散级联中，活跃节点可以向休眠节点传递信息。它为每个角色获取一个向量作为节点的嵌入。然后，根据非活跃节点的接收者嵌入向量与活跃节点的发送者嵌入向量之间的接近程度构建了一个激活模型。但是，无论网络结构如何，启用时间使得时间戳t之间的非活跃节点和所有现有活跃节点的激活时间为t。因此，每个发送者（或活跃节点）的嵌入都是独立于扩散拓扑的学习。0[47]提出了一种表示学习方法，用于预测...0信息扩散并设计拓扑长短期记忆（Topo-LSTM）方法。Topo-LSTM专门用于预测节点激活，是一个用于处理扩散拓扑的动态有向无环图（DAG）结构。动态DAG作为其输入，其输出是由每个DAG节点创建的具有拓扑意识的嵌入。04. IM算法概述04.1. 贪心方法0尽管IM问题是NP难的，但找到最优解是不可行的0问题的最优解。但是，如果预期影响扩散函数�（�）是次模的，则问题可以被解决7

下载后可阅读完整内容，剩余1页未读，立即下载