制作和主办：Elsevier沙特国王大学学报社会网络影响力最大化框架、绩效、挑战与方向：一项理论研究Shashank ShesharSingh，Divya Srivastva，Madhushi Verma，Jamarra Singh印度大诺伊达贝内特大学计算机科学与工程系阿提奇莱因福奥文章历史记录：收到2021年2021年8月8日修订2021年8月9日接受2021年8月18日网上发售保留字：影响力最大化社会影响力信息扩散影响力评价社交网络A B S T R A C T影响力最大化（Influence Maximization，IM）问题识别出网络中有影响力的用户子集，从而为诸如疫情检测、病毒式营销等现实问题提供解决方案。因此，许多评论和调查，其中大多数主要集中在经典的IM框架的单网络，避免了其他IM框架。在这种情况下，IM问题仍然有一些重要的设计方面，以及一些新的挑战的问题。受这些事实的启发，的最先进的IM算法的方法。为了给IM问题的研究奠定基础，首先讨论了信息扩散模型。其次，基于IM算法的接下来讨论IM方法关于性能度量的相对分析最后，对该领域研究面临的挑战和未来的展望进行了讨论.版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。内容1.第7571页1.1.与现有调查的差异75722.初步75722.1.定义75732.2.我们需要什么？............................................................................................................................................................................................................................... 75732.3.扩散模型75742.4.问题硬度75762.5.问题定义75772.6.贪婪算法75773.影响最大化框架75773.1.基本框架75773.2.经典IM框架75793.3.跨多个网络的影响最大化（IM2）框架75833.4.多重影响最大化（MIM）框架75843.5.跨多个网络的多重影响最大化（MIM2）框架75843.6.上下文感知IM框架7584*通讯作者。电子邮件地址：itbhu.ac.in（S.S.Singh），divyalknw@gmail.com（D.Srivastva），madhushi. bennett.edu.in（M.Verma），Jumarra.bennett.edu.in（J. Singh）。沙特国王大学负责同行审查https://doi.org/10.1016/j.jksuci.2021.08.0091319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comShashank Sheshar Singh，D.Srivastva，M.Verma等人沙特国王大学学报75713.7.其他扩展75883.8.讨论75884.性能分析75895.研究挑战和未来方向75945.1.传统IM框架下的挑战75945.2.IM2框架下的挑战5.3.MIM框架下的挑战5.4.MIM2框架下的挑战5.5.情境感知IM框架下的挑战75966.未解决的问题75977.结论意见75988.遵守道德标准7598竞争利益声明附录A.缩写7598参考文献75991. 介绍如今，人们花费大量时间在互联网上，60- 70%的时间花费在社交网络平台上，如Facebook，Instagram，Twitter等，这些社交网络已经成为几乎每个人生活中必不可少的一指数这些网络使用的增长已经吸引了研究人员对信息扩散的关注（Richardson等人，2002; Kempe等人，2005; Kempe等人， 2003），社区检测（ Biswas 和 Biswas ， 2018; Mishra 等人 ， 2021; AbdAl-Azim 等人，2020）、链接预测（Kumar等人，2020; Kumar等人，2019年;Kumar等人，2019 年; Singh等人，2020 a; Berahmand 等人，2021）等。信息扩散模型通过口碑传播信息或创新（Brown和Reingen，1987;Goldenberg等人，2001a）传播。这具有广泛的应用潜力，如病毒式营销（Domingos和Richardson，2001;Singh等人，2019 a; Singh 等人，2019 b; Singh 等人， 2019 c; Tang 和Yuan，2020; Saxena和Saxena，2019），收入最大化（Teng等人， 2018），谣言控制（Peng和Pan，2017; Chen等人，2010d）、社会推荐（Ye等人，2012年; Jindal和Sardana，第一个是如何对扩散过程建模，以由于随机性而在社交网络中传播来自种子用户的信息，这将严重影响最大化问题中非种子用户的产品的适应性（Kempe等人，2003; Guille等人， 2013年）。一般来说，影响最大化问题在理论上是复杂的。Kempe等人证明，在经典扩散模型下，种子用户的识别是NP困难的。此外，还观察到，对于给定的种子，2020年）等。受病毒式营销的启发，佩德罗和马特（多明戈斯和Richardson，2001）引入影响最大化（IM）作为优化问题。IM问题确定了一组最有影响力的用户在社会网络中，以最大限度地提高预期采用的产品。Kempe等人（2003年）提出了一种病毒式营销的场景，其中社交网络被赋予影响力权重，该权重近似于彼此影响的程度。社交网络平台为广告和营销提供了一个互动渠道，keting。广告商的目标是最大限度地提高产品采用考虑-从网络中提取一些个人作为种子用户。这些种子用户负责通过传播产品信息来推广产品。广告商过去常常向这些种子用户提供免费的产品样品，广告广告商希望口碑的影响将吸引其他用户使用该产品，并将有助于最大限度地扩大影响力。挑战和问题。系统在社会学、计算机科学、生物学等领域经常被表示为网络，和物理学中影响最大化起一个至关重要的角色已经开发了许多用于影响最大化的技术，但是该问题没有得到令人满意的解决（Li等人，2018年d）。随着影响最大化问题出现了几个挑战，其中一些如下（Li等人，2018年d）。Fig. 1. 调查概述。●●Shashank Sheshar Singh，D.Srivastva，M.Verma等人沙特国王大学学报7572集合（Barbieri等人，2012; Li等人，2018年d）。因此，对于大规模的社交网络，要实现影响最大化问题和规模的近似最优解是相当困难的大多数信息扩散模型和影响最大化算法是随机的（Guille等人，2013; Li等人，2018年d）。在同一网络的不同算法执行在性能评估期间，在算法的不同执行中获得的输出的累积随着影响力最大化问题的出现，也出现了几个问题，其中一些如下：有效种子的识别是影响最大化问题中的一个主要问题。为了减少这个问题，上下文特征如位置（Guo等人，2017年; Li等人，2014 d，时间Gomez-Rodriguez等人，2016，2012，topic Li et al.，2015年a; Shuo Chen例如，2015a，和竞争性Zhu等人，2016; Lin等人，2015）等被用于提出若干上下文感知影响最大化。这些上下文感知方法产生具有较低效率和可扩展性的有效种子。在大型网络的情况下，大多数影响最大化算法是时间效率低下和不可扩展的。因此，算法需要减少迭代次数，提高迭代复杂度，减少搜索空间，有效地识别种子集。为了减少这个问题，已经提出了许多算法，例如基于Chen等人的启发式度量，2009; Wang和Feng，2009; Kundu等人，2011），基于影响路径（Kimura和Saito，2006; Chen等人，2010 e; Kim等人，2013），基于社区 （ Wang et al. ， 2010; Li 等 人 ， 2015 b ） ， 基于子 模 块 化（Sviridenko，2004; Leskovec等人，2007; Goyal等人， 2011年，质量仍然是一个问题。在选择种子节点期间，有效性和效率的保证是一个重要问题（Arora等人， 2017年）。有效性的测量包括拓扑和上下文信息，而效率的测量涉及迭代的数量和复杂性。这两种措施之间的根本区别导致了效率和效力之间的权衡。这种权衡是影响最大化算法性能评估过程中的一个重要问题。在现实世界中，公司可能打算在同一社交网络中同时鼓励几种竞争性和非竞争性产品（Carnes等人，2007; Bharathi等人，2007; Sun等人，2016年）。通常，在社交网络中，对于不同的用户，对不同产品的兴趣不同，因此，来自他们的社交网络朋友的促销的接受概率相应地不同。因此，与传统的影响力最大化问题相比，该问题的主要问题是形成种子用户，在给定的m个项目中确定每个产品的数量，然后进一步确定影响力最大的k个在现实世界中，已经有相当多的用户同时维护多个帐户，这允许他们跨不同的网络传播信息（Zhang等人，2016; Wang等人，2016 b;Erlandsson等人，2017年）。此外，现实世界的系统是复杂的，因为它们覆盖更全面的方面，例如多重关系、组织层次、方向关联等，（Zhang，2015）。因此，用单一算法在这些多样化和多特征的网络中识别种子节点是具有挑战性的。应用. IM具有广泛的基于实时上下文的功能应用，例如，招聘、谣言控制、社交推荐、社交媒体、人口筛选、分析和销售预测、竞选活动、流行病学、博客圈、收入最大化和网络监控等。贡献本文提供了一个广泛的审查影响最大化算法有关他们的网络。调查概况见图。 1通过广泛关注基于各自框架的影响最大化算法。本调查文件主要侧重于以下方面。1. 简要介绍了传统的扩散模型的特点比较。2. 在算法框架的基础上，对IM算法进行了简要分类，并对各种算法进行了比较分析3. 比较分析现有的IM算法及其使用的各种性能指标。4. IM问题的挑战和未来的研究范围涉及他们的框架。5. 最后讨论了影响最大化问题中的一些开放性问题。1.1.与现有调查的虽然许多调查（Guille等人，2013; Sun和Tang，2011;Zhang等人，2014 a; Chen等人，2013; Arora等人，2017;Tejaswi等人，2016年; Li等人，2018 d; Li等人，2017 d; Razaque等人，2019 a;Chang等人，2018; Sumith等人， 2018）存在于信息扩散分析中。这次调查在以下几个方面有所不同。Guille等人，2013; Razaque等人，2019 a;Razaque等人，2019年b）提出了一个讨论的信息扩散过程，组件和模型的社会网络分析。本研究不局限于特定的社会网络领域，如影响力传播和即时通讯问题。Changet al.（2018）阐明了信息扩散模型在三个社交网络应用中的有用性：信息源检测、影响力评估和影响力最大化。Sun和Tang（2011）讨论了衡量网络中社会影响力的方法。他们还讨论了分析用户生成数据的社会影响的模型。虽然一些工作（Zhanget al.，2014 a; Chen等人，2013; Tejaswi等人，2016年;Li等人，2017 d; Singh等人，2019 d）描述了IM的影响传播模型和近似算法。然而，这些研究都是不完整的，因为它们只关注传统的影响力最大化.这些研究没有提供关于最近进展的见解，如IM跨多重（Zhang et al. ，2016; Wang等人，2016 b; Erlandsson等人，2017年; Li等人，2012年; Zhan等人，2015 a）、上下文感知（ Singh 等 人 ， 2019; Lee 和 Chung ， 2015; Tejaswi 等 人 ，2017;Barbieri等人，2012; Zhuang等人，2013; Wang等人，2017a;Wang，2016; Tong等人，2017; Bozorgi等人，2017），软计算方法（Gong等人，2016; Wang等人，2017 b; Ge例如，2017;Singh等人，2019 d; Wang等人， 2020年）等。Arora et al.（2017）提供了对一些知名IM方法的深入基准研究。本研究是基于实验分析而非理论分析。Li et al.（2018 d）专注于基于算法设计的单个网络IM算法的理论分析。作者还提供了上下文感知IM算法的详细描述。然而，IM算法的审查是不完整的，因为它们不包括IM方法的性能指标。我们的工作重点是在算法框架的基础上对单网和多网IM算法进行理论分析。此外，特征的比较涵盖了更广泛的方面。本调查讨论了研究●●●●●●●●●●Shashank Sheshar Singh，D.Srivastva，M.Verma等人沙特国王大学学报7573ðÞðÞ联系我们吉吉22ðÞ¼ ðÞ图二.信息扩散分析概述。每个框架的挑战和方向而不仅仅是经典的IM（Li等人，#20182;的问题，以及开放的？与现有的调查相比，这项工作提出了一个研究的信息扩散模型和现有的IM算法为单一和多个网络。本文重点对现有的影响力最大化技术进行了有了这个，它还专注于上下文感知IM方法。此外，据我们所知，这是同类调查中的第一次，其中包括IM算法比较有关的性能指标以及研究挑战和未来的工作。本调查还列出了IM中一些有待探讨的问题。2. 初步信息传播分析研究可以分为四类：1）信息传播过程的建模，2）影响力的评估，3）影响力最大化算法设计，以及4）有影响力的用户识别，如图2所示（Chang等人，2018年）。本研究的重点是影响力最大化和信息扩散的公式、框架和算法。IM作为一个优化问题的概念是由Pedro和Matt（Domingos和Richardson，2001）在2001年从病毒式营销中获得灵感而提出的。2003年，Kempe等人给出了IM问题的形式化定义。他们假设一个社交网络可以用一个图来表示G V;E;W，它将用户及其在网络中的关系与特定的关系强度相结合。IM问题的目标是确定初始的种子用户表示为k谁创造最大的影响。此外，可以基于扩散模型来计算活动节点的影响力传播。 在形式化IM问题的定义之前，为了更好地理解IM问题，给出了一些定义.缩写列表基本定义和IM问题形式化如下。2.1. 定义定义1（社交网络）。也被称为影响图的社交网络可以由具有N个用户和M条边的加权有向图G V;E;W表示。这里，V表示网络中的用户集合，并且E表示诸如友谊、关注者、转发、提及、合著等的关系关系的类型是依赖网络的。边权重W表示对等体之间的关系强度。定义2（邻居）。给定一个节点a，它的邻居Na可以表示为用户b的集合，使得b2Na当且仅当9a;b2E和b2V。a的内邻居和外邻居可以分别指定为N in_a_n和N out_a_n。边集是有序节点对的集合，即，a; b;c; a; b;c; d; e; b; c;方向边缘a;b 说明节点a对在节点B上，而不是相反。定义3（度中心性）。给定节点上的链接数D a N a。传出链接的数 量 被 认 为 是 节 点 a 在 有 向 社 交 网 络 中 的 中 心 度 ， 即D_a_n_j_N_out_a_j。定义4（种子节点）。参与社交网络的信息传播过程并充当传播源的一组节点被定义为种子节点或种子集（S），使得S2V和jSj ^k。定义5（活动节点）。活动节点b V是属于种子集S或已经拾取由已经激活的节点a VA使用扩散模型传递的信息的一旦它们的邻居激活节点b，它将被添加到活动节点VA的集合，即，V A← fV A[bg.定义6（影响扩散）。在使用扩散模型实现扩散过程之后获得的活跃用户的数量表示种子集S的影响扩散IS_S_S_，并且可以表示为ISS jVASj。定义7（信息扩散模型（IDM/DM））。描述了S对G的影响传播的随机过程，其中G V;E;W为影响图，SV为种子集。2.2. 我们需要什么？为了解决IM问题，需要执行三个步骤。1. 形成或采用影响力模型来传播信息，思想，创新等，在社交网络中。Shashank Sheshar Singh，D.Srivastva，M.Verma等人沙特国王大学学报75742¼P2ð Þ图三. 信息扩散模型的组成部分。2. 获取关于特定网络的拓扑信息，以估计人际影响以及影响和激活概率。3. 最后，设计一个种子选择算法，以最大限度地扩大影响力。2.3. 扩散模型在社交网络、数据挖掘、流行病学、数据库等领域都有大量的文献因此，调查扩散模型是至关重要的，扩散模型在调查基于IM的算法的各个方面中起着至关重要的作用。 图 3展示了扩散模型的组成部分（Razaque等人，2019年a）。本文讨论了IM在网络中的经典扩散模型框架。框架中的每个节点u，V具有与两个状态中的任一个相关联的时间戳t，即，活跃或不活跃。非活动节点是不受其邻居影响的节点。在初始状态下，除了种子节点之外，所有其他节点都是不活动的。在t0时，种子节点是活动的（SV），这开始了扩散过程。该过程从种子节点开始，并且进一步传播影响以使其邻居活跃。然后，这些活动节点影响它们的邻居，并且该过程继续，直到没有新的节点可以被激活。一般来说，每个模型都有自己的机制来根据邻居的行为从非活动状态捕获活动状态。一些流行的扩散模型是（Guille等人，2013; Li等人，2018 d; Qiang等人，2019）如下。阈 值 模 型 （ TM ） 。 阈 值 模 型 首 先 由 Schelling （ 2006 ） 和Granquartter（1978）提出。TM是任何模型，其中单个阈值或一组阈值，用于区分模型预测行为的值范围。线性阈值模型（LTM）是最常用的阈值扩散模型。这个模型背后的想法是，节点y变得活跃当且仅当x2NayWxyPTy，即传入邻居的影响必须大于阈值Ty。在线性TM中，用户阈值的值遵循[0，1]上的均匀分布。在文献中存在一些其他阈值模型，通过它们的阈值来区分，如大多数TM（Ty1/2D）（Richardson等人，2002; Bhagat等人， 2012）、小TM（Ty是一个小常数）（Kermelt和Laporte，1989）、分离TM（具有单独竞争性级联的线性TM）（Kermack和McKendrick，1927; Borodin等人，2010年b），和一致TM（Ty¼Dy）（Richardson et al.，2002年），其中D y表示节点y的度中心性。通过用任意函数替换线性TM的激活函数，提出了一些通用的阈值模型（Pathak等人，2010; Bhagat等人， 2012年）。 Bhagat等人（2012）提出了一种扩散模型，该模型考虑了用户对产品的体验，并捕获了产品采用率而不是影响力，并将其命名为具有颜色的线性阈值。Banerjee等人 （Pathak等人， 2010）进一步扩展线性TM以处理用户的意见改变，并允许用户在活动和非活动状态之间切换回来。级联模型（CM）。受概率论和相互作用粒子系统的启发（1989年粒子系统和渗流讲义），引入了扩散的动态级联模型。Goldenberg etal.（2001 b）和Goldenberg and Muller（2003）的作者首先将级联模型引入营销领域。独立级联模型（ICM）在病毒营销中被充分研究并且最受欢迎（Goldenberg等人，2001年b）。如果一个节点x在某时刻变为活动的，●●Shashank Sheshar Singh，D.Srivastva，M.Verma等人沙特国王大学学报7575P2¼ð ÞP第四季第2集一PAPþ1/11/1我我2ðÞ\A.x;y营销Q1/1 ð-yvj[dt dtdtDTDTdt dtdt表1扩散模型特性的比较扩散模型激活条件性质应用Linear TM（Kermack和McKendrick，1927）在LTM下，目标函数r∈S∈是次模的，IM问题是NP-难的谣言与疾病控制多数TM（Richardson等人，2002;Bhagat等人， 2012年）TyIM问题在MTM分布式计算下是NP难问题，投票系统小TM（Elmelt和Laporte，1989年）x2Na b cSTM下的NP-困难UnanimousTM（Richardson等人，（2002年）X Na y W xyPT y; T yd v2-近似算法，IM是NP难的网络安全和脆弱性分离的TM（Kermack和McKendrick，1927; Borodin等人，（2010年b）Px NA Yut-1wAyPTA目标函数是单调的但不是次模的，IM是NP-难的具有竞争力来源的网络加权比例TM（Kermack和McKendrick，1927）P½y 2utjy2utnut-1]¼x2utwx;yx2utwx;yrS既不是次模的也不是单调的IM是NP难的。应对两种竞争影响独立CM（Kempe等人，（2003年）1-Py[1]-Pyv;jS[M; rS是次模的，IM是NP-难的。集体行为，病毒性Opinion CM（Zhang等人， 2013）x2NayW xyP T yrS函数既不是次模也不是单调的，IM是NP-难的政治运动和纳入用户意见ICM-NO（Chen等人，（2011年） 1-Py1P;S 在概率P的情况下，每个新的活动节点ii变成正数的概率是1-P。政治运动和纳入负面意见降低CM（Kempe等人， 2005）Py xjS 6 Py xjM目标函数是次模的，IM在DCM下是NP-难的集体行为，信息传播SIR（Kermack和McKendrick，1927;Kermack和McKendrick，1991）–dS¼ -bSI，dI¼bSI-cI，dR¼cI流行病学SIS（Kermack和McKendrick，1927;Kermack和McKendrick，1991）–dS¼-bSII-cI，dI¼bSI-cI流行病学SIRS（Kermack和McKendrick，1927; Kermack和McKendrick，1991）-表2扩散模型特性的比较- II.扩散模型网络子模激活引导加权递减单调多时间返回激活方面Linear TM（Kermack和McKendrick，1927）UUUU多数TM（Richardson等人，2002; Bhagat等人， 2012年）UUUUU小TM（Elmelt和Laporte，1989年）UUUUUnanimousTM（Richardson等人，（2002年）UU分离的TM（Kermack和McKendrick，1927; Borodin等人，（2010年b）UU加权比例TM（Kermack和McKendrick，1927）UU独立CM（Kempe等人，（2003年）UUUUOpinion CM（Zhang等人， 2013年度）UUUUICM-NO（Chen等人，（2011年）UUUU降低CM（Kempe等人，（2005年）UUUUSIR（Kermack和McKendrick，1927; Kermack和McKendrick，1991）UUUSIS（Kermack和McKendrick，1927; Kermack和McKendrick，1991）UUUUSIRS（Kermack和McKendrick，1927; Kermack和McKendrick，1991）UUUUt时，它只有机会以在时间戳t = 1处的激活概率pxy激活其不活动邻居y。节点的激活过程类似于抛硬币。如果节点y在t1时变为活动的，那么它将来将永远不会是不活动的独立级联模型有一些扩展，存在于类似ICM的文献中，具有负面意见（Chen等人，2011 年 ） ， ICM 与 积 极 和 消 极 的 意 见 （ Nazemian 和Taghiyareh，2012年）。触发模型（TRM）。触发模型是由Kempe等人（2003）提出的TM和CM的一般化形式。作者还证明了TM和CM中的触发模型是等价的。在触发模型中，每个节点x与阈值Tx和分布函数f x相关联，该分布函数fx以概率（子集可以影响节点x的可能性）映射到其邻居的子集Sx该模型在用户x的扩散过程的每个实例中独立地选择邻居的随机子集。有两个Gen-基 于 TM 和 CM 扩 散 行 为 的 一 般 化 触 发 模 型 。 Kempe 等 人（2005）提出了一个比触发模型更一般的模型，称为递减级联模型。该模型将节点x对y的影响概率重新定义为py<$x;Sx<$，其中Sx表示活动的x的邻居降低CM会强制执行pyx;SPyx;T;ST获取收益递减的财产流行病模型（EM）。流行过程对传染病的传播、政治运动以及谣言和新闻等信息传播产生了至关重要的影响（Kumar和Sinha，2021）。在流行病模型中，固定种群可分为三类：易感者（S）、感染者（I）和康复者（R）。Kermack和McKendrick（1991）根据模型级联的性质提出了三种流行病模型：易感传染病恢复（SIR）、易感传染病易感（SIS）和易感传染病恢复易感（SIRS）。●●Shashank Sheshar Singh，D.Srivastva，M.Verma等人沙特国王大学学报7576ð Þ见图4。 现有扩散模型在各种特征上的频率分布。时间感知模型（TAM）。上面讨论的扩散模型是时间未知的。当没有更多的节点被激活时，这些模型终止扩散过程。然而，一些传播活动需要最大化特定于固定时间段的社会影响的传播，即，传播的收敛取决于时间周期而不是迭代的次数。为了满足时间关键需求，引入了时间感知的信息扩散模型TM分为两类：离散时间模型和连续时间模型。Chen et al.（2011）、Chen et al.（2012）和Lee et al. （2012）通过扩展独立CM提出了DTAM模型。这些模型遵循不同时间戳上的离散随机变量 为了处理这种情况，当节点x在连续时间内影响其他节点时，CTAM（Lee等人，2012;Gomez-Rodriguez等人，2011年）推出。表1（Guille等人，2013; Singh等人，2019 d）和2（Sumith等人，2018）总结了每个扩散模型的特点和属性。“列扩散模型”给出了算法名称并引用。列激活条件描述将状态从非活动更改为活动的条件。“属性”栏和“应用”栏分别提供属性及其应用的信息。列网络和子模表示网络类型和扩散函数性质。U和表示属性的存在和不存在。现有的扩散模型的频率分布在不同的特征，如子模块化，网络的适用性，和活跃，过程如图4所示。这也有助于总结IM算法中不同特征的流行程度。2.4. 问题难度本节将研究TM、CM、TRM、EM和TAM下影响最大化问题的影响传播函数的计算难度定理1. 在独立级联模型（ICM）下，病毒式营销环境下的IM问题是NP难问题（Kempe et al.，2003，定理2.4）。定理2. 在经典线性阈值模型（LTM）下，具有病毒式营销设置的IM问题是NP难的（Kempe等人，2003，定理2.7）。定理3. 在连续时间感知（CTAM）扩散模型下，具有病毒式营销设置的IM 问题是NP 难的（GomezRodriguez等人，2012，定理3）。定理4. 在触发（TRM）扩散模型下，病毒式营销应用上的IM问题是NP难的（Kempe等人，2003年）。定理5.在独立的ICM传播模型下，给定的活跃用户S的子集的预期影响扩散r S的计算是困难的（Chen等人，2010a，定理1）。●Shashank Sheshar Singh，D.Srivastva，M.Verma等人沙特国王大学学报7577ð Þð Þkωω111K1ð Þð Þð Þð Þð Þð Þ- -定理6. 在LTM传播模型下，给定的活跃用户子集的预期影响扩展r S的计算是困难的（Chen等人，2010b，定理1）。基于对这些定理的观察，我们可以总结出，文献中不存在这样的算法，其可以在多项式时间内识别有影响力的用户的子集，除非P/4NP。通讯器-种子社会影响力传播的归因过程最大边际增益（第3行）。然后算法将节点x添加到种子集S（第4行）。最后，该算法返回k个不同的节点作为结果种子集。贪婪算法产生的解的理论近似保证取决于目标函数r S次模性质，这在定理7至10中所述的经典DM中成立。算法1. 贪婪算法（Kempe等人，（2003年）节点S 在任何扩散模型下也是复杂的。因此，我们认为，现有的研究集中于开发近似的和有效的IM算法。2.5. 问题定义定义8（影响最大化（IM）（Kempe等人，2003年））。G中的影响扩散可以通过使用信息扩散模型来最大化，该信息扩散模型考虑正整数k和i个流的子集，i个流的子集是SωV;jSωj <$k <$h，i个流的子集是SωV;jSωj<$k<$h，i个流的子集是S ω v; j S ωj <$k <$k <$k <$sω j，其中，G/V;E;W/V是影响图。虽然IM问题是NP难的，并且找到最优解是不可行的。因此，可以找到一个近似的解决方案，如果预期的影响扩散函数rS是submodular。任何函数称为次模函数当且仅当该函数同时满足单调递增和单调递减的性质。性质1（单调增加（Singh等人， 2019年））。 客观定理11. 最优种子的期望影响扩散与贪婪算法生成的种子之间的关系满足r<$S<$P<$1- k<$1-k<$r <$S <$，其中S和S 分别表示最优和贪婪种子（Nemhauser等人，1978，定理2.2）。一般来说，近似比被认为是1-1=e，而不是功能说 rðSÞis说到被 单调增加森林论坛比2001-2001K-k在现有作品因为1-1=e0。 此外，为了性质2（收益递减（Singh等人，2019年））。目标函数比如说，rS是说到被递减返回当且仅当rS[u-rSPrT[u-rT;8u2T和ST.单调性表明，在有影响力的用户集中增加更多节点不会减少其整体预期影响力，相反，它可以增加，而递减收益意味着节点u与种子集子集的边际增益总是大于或等于种子集的边际增益。定理7. 在ICM信息传播模型下，影响函数r S的预期传播是次模的（Kempe等人，2003，定理2.2）。定理8. 在LTM信息传播模型下，影响函数r S的预期传播是子模块化的。2003，定理2.5）。定理9. 在TRM信息传播模型下，影响函数r S的预期传播是次模块化的（Kempe等人，2003，Theorem 4.2）。定理10. 在CTAM信息传播模型下，影响函数r S的预期传播是次模的（GomezRodriguez等人，2012，Theorem4）。2.6. 贪婪算法大多数基于模拟的最先进的方法是基于贪婪的框架提出的Kempe等人。（2003年），在算法1中演示。该算法从取空集作为种子集（第1行）开始，并迭代地标识节点x考虑到采样算法中的采样误差，引入了附加项S，即，抽样方法的近似比为ε 1- 1 =e-s ε。3. 影响力最大化框架虽然贪婪框架保证了1 1=es的近似比，但在IM框架中估计期望的影响仍然是具有挑战性的定理5和6指出，即使在经典扩散模型下，给定种子的社会影响r S的计算也是P-困难的。这种理论上的困难创造了一个机会，进行广泛的研究，开发有效的方法来解决IM问题。现有的研究工作可以基于IM算法如何考虑网络、产品、上下文特征等而被分成不同的类别（Arora等人，2017年; Li等人，2018 d;Singh等人，2019年f）。 表3示出了现有IM技术的分类（Singh等人，2019年f）。3.1. 基本框架Arora等人（2017）对一些流行的IM算法进行了实验研究，并提出了一个基本的基准框架，如图5所示。IM问题的基本框架由四个部分组成：经验设置、种子选择策略、评价和洞察力。除了种子选择之外，每个框架的所有组件都相同。种子选择组件根据算法设计和框架的不同而有不同的发展.经验设置配置设置并收集数据集、扩散模型、算法等信息， 这是解决IM问题所需要的。种子选择过程基于算法设计识别有影响力的用户。评估过程估计不同的性能指标，如影响传播、运行时间、内存占用等。最后，洞察组件分析算法的结果以及有效性、效率、可扩展性和鲁棒性。表3IM框架的分类及其参考。框架类别问题解决视角代表影响大化古典基于仿真#MC模拟的最小化MC的复杂性改进（Leskovec等人，2007; Goyal等人，2011; Zhou等人，2 0 1 5 年a）（Wang等人，2010; Jiang等人，2011年; Chen等人，2014; Sheng和Zhang，2018; Singh等人，2019 e; Zhang等人，（2016年）基于启发混合第一千一百零六章等级提升模型缩减快照采样（Freeman，1978; Page等人，1999; Liu等人，2014; Chen等人，2009; Jung等人，2012; Singh等人，2020 b; Tsai和Liu，2019）（Kimura和Saito，2006; Chen等人，2010 e; Kim等人，2013年; Chen等人，2010 c; Goyal等人，2011; Galhotra等人，2016;Vega-Oliveros等人，2020; Banerjee等人， 2019年度）（Chen等人，2009; Cheng等人，2013; Cheng等人，2013年; Ohleman等人，2014; Cohen等人， 2014年度）方法反向可达（Borgs等人，2014; Tang等人，2014; Tang等人，2015; Wang等人，2017 a; Nguyen等人，（ 2016年）IM2基于仿真#MC模拟的最小化MC的复杂性改进（Saito等人，2012; Zhang，2015）（Zhang等人，（2016年）基于启发混合秩精化模型约简反向可达（Erlandsson等人，2017; Wang等人，2016 b）（Zhang，2015）（Wang等人，（2016年b）MIM方法模拟-MC的复杂性改进（Sun等人，（2016年）MIM2基于基于启发第一千一百零六章等级提升（Singh等人，（2019年f）上下文感知空间局部位置主题相关目标（Li等人，2014年a、2015年b、2016年、2017年b、2018年、2017年、2018年a、b）（Guo等人，2013; Li等人，2015 c; Lee和Chung，2015; Nguyen等人，（2016年）时间主题相关扩散离散时间感知IM连续时间感知IM（Shuo Chen等人，2015 b; Aslay等人，2014; Chen等人，2015; Singh等人，2019; Barbieri等人，2012）（Chen等人，2012; Lee等人，2012; Liu等人， 2014年度）（Gomez-Rodriguez等人，2011; Gomez Rodriguez等人，2012; Du等人，2016; Xie等人，2015年; Tang等人，二〇一五年;竞争已知竞争对手Mohammadi等人，（2015年）（Carnes等人，2007; Bharathi等人，2007; Borodin等人，2010 b; Ceren Budak等人，2011; He等人， 2012年）动态未知竞争对手比较基于探测的采样别人
我的内容管理
展开
