摘要
为了减少商家在社交网络上进行多轮次商品推广的营销成本，针对多轮次影响力传播过程中的增益节点选择问题展开研究。基于多轮次影响增益传播模型，提出了自适应的增益节点选择策略，该策略在已知种子节点的前提下，能够在近似线性的算法复杂度下，找到最小化达到传播影响阈值所需的营销轮次的近似策略。实验结果表明，相较于现有启发式算法和非自适应算法，所设计的自适应策略能够减少7.3%~ 18.3%达到指定阈值所需的传播轮次，有效减少推广成本。
Abstract
In order to reduce the marketing costs of merchants promoting products over multiple rounds on social networks, this study made a exploration on the selection of boosting nodes during the process of multi-round influence propagation. Based on the model of multi-round influence boosting propagation mode, an adaptive strategy for choosing boosting nodes was designed. Given known seed nodes, this strategy could find an efficient method to minimize the number of marketing rounds needed to reach a certain threshold of social influence, with nearly linear algorithmic complexity. Experimental results show that compared to existing heuristic algorithms and non-adaptive algorithms, the designed adaptive strategy can reduce the promotion rounds required to reach a specified threshold by 7.3%~18.3%, effectively reducing the promotion cost.
近年来，以Facebook、Twitter、微博为代表的社交网络平台发展迅速。社交网络通过互联网连接用户关系，为信息的传播提供了快速便捷的途径。在社交网络上，信息可以通过好友间“口耳相传”的效应进行传播。用户可以通过社交网络平台进行消息的发布和转发。具体来说，发帖人发布新的消息后，他的粉丝在一定概率下会进行转发，新的消息会沿着社交网络上的好友关系传播以获得更多用户的关注，从而产生一定的社会影响力。
舆论信息传播和营销产品推广都能够利用社交网络的传播效应。因此，在线社交网络中的信息传播过程已经吸引了多个领域的广泛研究，包括计算机科学、物理学、流行病学[1]。以广告投送为例，商家或广告商在社交网络上进行广告投送时，通常选择具有大量粉丝的账号作为广告的初始发布人，这些账号发布的消息能够在短时间内被大量用户看到并进一步转发，这种连锁传播效应使得广告信息能够在短时间内达到更多的用户，从而提高产品或服务的知名度和销售量。以微博为代表的社交平台上，广告的转发量可以反映产品在社会上的影响力。选择有“影响力”的初始发布人、提升中间用户的转发积极性都可以扩大广告的影响力。
传播影响最大化和传播成本最小化是信息传播研究中的两个关键问题，它们互为对偶问题。Domingos和Richardson在市场病毒式营销策略的启发下，提出了传播影响最大化问题[2]。假设已知社交网络中的数据，并能够估计用户之间互相影响的概率，商家可以向网络中少数具有“影响力”的用户提供免费试用服务，由他们开始向朋友推荐产品，触发影响级联效应，从而使产品或服务能够被网络中最大期望数量用户所采纳。影响力的传播过程基于特定的传播模型，最为主流的模型包括线性阈值模型、独立级联模型和触发模型等[3]。在这些模型中，最初被选中进行信息发布的用户通常被称为种子节点。在信息传播过程中，受到种子节点影响并进行转发信息的用户则被称为激活节点。在传播的开始阶段只有种子节点处于激活状态。信息从这些种子节点出发根据特定的传播模型规则进行扩散。在这个过程中，成功被激活的节点数量被视为此次信息传播所产生的影响力大小。影响力最大化问题旨在设计种子节点的选择策略，使得传播结束后，激活节点数量的期望值最大化。在大部分传播模型下，影响力最大化问题是一个非确定性多项式时间（nondeterministic polynomial time，NP）难问题，Kempe等[3]在线性阈值模型和独立级联模型上，利用影响函数的单调性和子模性为贪心策略给出了近似性证明。Borgs等[4]通过采样反向可达集优化蒙特卡罗算法模拟传播实例的耗时。Tang等[5-7]在采样反向可达集的基础上进一步缩小了所需采样数量的下界。
但这些工作主要针对单独节点的影响力，没有考虑节点间的助推作用和社群结构的影响。近年来，一些工作基于图上的社群结构检测方法对传统近似算法进行了模型优化和效率优化[8-9]。一部分工作改进了传统的影响力传播模型，对于实际营销过程中可能发生的产品助推[10]、产品竞争[11]、节点助推[12-13]进行了建模。Lin等[12]提出了增益节点的概念。除了与网络中具有“影响力”的用户合作外，商家可以采用发放优惠券或定向推送广告的方式提升一部分用户的消费意愿。这部分用户相比于受到激励前，在收到好友的消费推荐后会更愿意购买并向其他好友推荐这个产品。如何选择激励目标用户成为一个值得研究的问题。可惜的是目前的工作仅考虑了单轮次传播过程中的增益节点选择问题。
在实际的营销活动中，商家会进行多轮次的营销推广。每轮次的推广由不同“有影响力”的用户群发起，商家会向一部分用户发放优惠券，提高他们的消费意愿。当不再有新消费的用户群体增长时，当前轮次的传播过程结束，商家则会开启下一轮的消费激励政策。Sun等[14]对多轮次的病毒式营销过程进行建模，为每轮次的传播选择种子节点集合，以最大化多轮次传播结束后激活节点的期望数量。设计了多轮次触发模型，并采用跨轮次贪心策略和自适应轮次内贪心策略计算多轮次影响最大化的近似解。Tang等[15]观察已选择的种子节点对其他用户的影响，自适应地选择下一轮传播的起始种子节点，解决了自适应种子最小化问题。Niknami等[16]针对多轮次影响竞争问题进行探讨。
由于社交网络的动态性和社交网络传播的不确定性，仅采用单轮次的营销策略可能会浪费资源，重复激励已经购买过商品的用户群，错过未发生消费的潜在用户群。多轮次的营销过程可以根据传播现状动态分配资源选择下一轮次的增益目标，从而更有效地提升传播影响力、节省营销成本。目前针对增益节点的研究主要集中在单轮次的营销活动中，没有充分考虑到在多轮次的营销活动中如何选择增益节点。为了能够最小化多轮次传播过程中所需要的推广成本，对于多轮次增益传播过程进行建模，并采用自适应选择算法根据每次的传播结果，动态选择下一轮的增益节点，从而获得更精确的结果，以避免静态策略产生的重复目标推广成本。这一问题是NP难问题，研究提出了具有近似下界保证的优化选择策略，并且只需要近似线性的时间复杂度。通过在真实数据集[17-19]上的实验，相较于现有启发式算法[12，20]和非自适应算法[12]，所设计的自适应策略能够减少7.3%~18.3%达到指定阈值所需的传播轮次。这种基于动态策略的增益节点成本最小化方法不仅有理论价值，也具有实际应用价值。
1 问题模型与定义
本节针对多轮次影响增益模型（multi-round influence boosting model，MIBM）和传播影响阈值限制下的增益节点成本最小化问题的定义进行说明。
1.1 信息传播模型
多轮次影响增益模型在传统影响增益模型[12]的基础上引入多轮次传播[14]的性质，即每轮从不同种子节点开始传播，提升不同的节点作为增益节点，所有轮次传播结束后的激活节点的数量即为多轮次影响增益模型的传播影响力。
1.1.1 影响增益模型
影响增益模型 [12]是在独立级联模型的基础上提出的，该模型在影响增益最大化问题中被广泛应用。
在影响增益最大化的问题定义中，当一个节点被提升为增益节点后，更容易受到邻居节点的影响。给定社交网络G=（V，F），其中V表示社交网络中的节点集合，F表示社交网络中的边集合，对于网络中的任一边euv∈F存在两个权值 puv和p′uv（p′uv＞puv），其中puv表示节点v受到节点u传播影响的原始概率。当v被提升为增益节点后，受到邻居节点影响的概率会提升。p′uv表示v被提升为增益节点后受到邻居节点u的传播影响的概率。
传播开始前，选定种子集合S和增益节点集合B。初始时刻只有种子节点处于被传播激活的状态，其他节点均未被激活。在每个离散时刻t，如果节点v不属于激活节点集合，且与t-1时刻被激活的节点u存在连接关系euv，那么节点u会尝试将信息传播给节点v，若节点v不属于增益节点集合B，那么被节点u激活的概率是puv，如果v属于增益节点B，节点v被节点u激活的概率提高为p′uv。每个被激活的节点仅有一次激活邻居节点的机会，节点被激活后会保持激活的状态，当没有更多新节点可以被激活时，传播过程停止。信息传播的影响力可以表示为最终处于激活状态的节点数量。
1.1.2 多轮次影响增益模型
多轮次影响增益模型会进行多轮次的传播，每轮次信息会从不同的种子集合开始扩散。在传播开始前给定一个备选种子集合，其中每个节点s∈，都存在一个概率p（s）表示每轮次节点s被选作种子节点传播信息的概率。在第t传播轮次开始前，给定本轮次增益节点集合Bt，按照种子概率分布生成本轮传播种子集合，按照影响增益模型在社交网络上进行传播，定义第t轮次激活节点的集合为ρφ（t）（Bt），φt表示在第t轮次时的传播过程。不同轮次中可能激活相同的节点，这些节点可以作为传播介质，再次将信息扩散到邻居节点，但不重复计入传播影响力。传播过程是随机的，对于一个多轮传播过程φ，经过Tn轮次传播后，最终激活节点的集合可以表示为
(1)
式中，U表示Tn轮次中总共选择的增益节点的集合，Bt表示第t传播轮次中选择的增益节点集合。
定义1 多轮次影响增益模型传播影响力。在已知备选种子集合的情况下，增益节点集合U在传播实例φ上助推传播影响力的定义为
(2)
1.2 MIBM模型下的增益节点成本最小化问题
给定社交网络G=（V，F），同时给定一个初始传播用户备选种子集合和传播影响阈值η∈[1，N]，其中N表示从备选种子集合出发可能影响到的节点数量。每轮次传播开始前，选择b个节点作为这一轮次的增益节点，目标是设计一种多轮次增益节点选择策略，这种策略能够应对任意随机出现的信息传播实例，并在尽可能少的时间轮次内达到预设的传播影响阈值，从而使总体期望的传播轮次最小。
通过公式表示这一过程，增益节点成本最小化期望找到一个策略π，对任一出现的传播实例φ，均有Iφ[U（π，φ）]≥η且使得期望传播轮次最小化，即
(3)
(4)
其中，U（π，φ）表示按照π策略在实际传播实例φ下选择的增益节点总集合，T（π，φ）表示在实例φ下按照策略π选择增益节点达到传播影响阈值时所需要的传播时间轮次。
2 算法设计
针对增益节点成本最小化问题设计，本节提出了自适应贪心增益节点选择策略（adaptive greedy multiply boosting nodes selection strategy，AdaMBTS）和对应的下界选择策略（lower bound of AdaMBTS，AdaMBTS-LB）。
2.1 自适应增益节点集合选择策略
解决增益节点成本最小化问题的一种简单的策略是：在传播开始前，估计每个节点的传播增益，贪心地选择传播增益最大的节点。然而，固定的增益节点选择可能会导致助推的用户群重复，造成不必要的成本浪费。因此，采用自适应增益节点集合选择策略。在每轮传播前，先观察前几轮的传播结果，然后根据这些结果来选择下一轮次的增益节点集合。
2.1.1 符号与定义
由于传播过程是随机的，采用期望传播影响作为衡量增益节点集合传播效果的重要参数。在有阈值限制的问题中，仅要求最终的传播影响大于η即可，首先定义阈值传播影响函数
(5)
为了方便表示，用Bt表示第t轮次选择的增益节点集合，并将（Bt，t）看作一个元组元素，用xt简化表示。用Ut表示前t轮次选择的元组集合，即Ut={（B1，1），（B2，2），···，（Bt，t）}。
定义传播函数的边际增益函数和阈值传播函数的阈值边际增益函数。
(6)
(7)
用Ω表示所有可能传播的实例组成的集合。每轮次选择一个元组后，可以观察得到反馈状态，Ωt∈Ω表示与t轮次传播前观察到的传播状态一致的传播实例所组成的传播子集。定义nt表示在第t轮次传播开始时还未被激活的节点个数，ηt表示第t轮次传播开始时与要求阈值的差值，即ηt=η-（n-nt）。那么易知
(8)
则期望阈值边际增益函数可以表示为
(9)
即在目前传播状态下，选择元组xt在下一轮次可以产生的阈值边际增益的期望值。
2.1.2 自适应贪心算法框架
参考种子节点最小化的自适应处理范式[21]，当自适应算法的优化目标函数满足强自适应子模性[21]和强自适应单调性[21]，每轮次直接利用贪心策略，选择使目标优化函数增益最大化的元组，存在理论近似保证，可以最小化所选择的元组数量以达到阈值。
可以证明，增益节点自适应选择问题的目标函数Γ（U）满足强自适应子模性和强自适应单调性，基于自适应成本最小化近似定理[15]，在第t轮次传播选择增益节点集合时，选择的元组（B°t，t）需要满足。但计算最大期望阈值边际增益函数是一个NP难问题，如果可以找到近似最优解，即选择的元组需要满足，达到阈值时所经过的期望传播轮次不会超过最优策略下期望最少轮次的（ln η+1）2/α[15]。算法1描述了自适应贪心增益节点选择策略的流程。
算法1 自适应贪心增益节点选择策略
Alg.1 Adaptive greedy muti-round boost node selection strategy
2.2 期望阈值边际增益函数最大化
要得到有下界保证的自适应算法近似解，就要计算最大期望阈值边际增益函数。这一问题虽然证明为NP难问题。但一些工作[3-7，12]已经为这一问题提供了有近似保证的处理范式。解决这一问题分为两步：采样足够数量的传播实例，利用传播实例估计给定节点的传播影响；通过贪心策略选择估计值最大节点。估计给定增益节点集合所产生的期望影响增益，通常通过采样潜在反向可达图[12]，但这种方法并不能简单地用来估计阈值下的期望边际增益。在本节中，采用多根潜在反向可达图（k-root potential reverse reachable graph，kPRR-Graph）的采样和截断影响传播最大化（truncated influence maximizing，TRIM）算法[15]选择增益节点使期望阈值边际增益函数最大化。
2.2.1 增益节点的传播影响估计
文献[12]提出了潜在反向可达图的概念，利用潜在反向可达图估计期望影响增益。
对于社交网络G=（V，F）上的边euv∈F，其有puv的概率被激活，有1-p′uv的概率阻塞传播，除此之外还存在p′uv-puv的概率，当且仅当v被提升为增益节点后，它才能变成激活边，否则作为阻塞边存在。定义这类边为待增益边。
一个随机潜在反向可达图对应一个传播实例的子图。生成一个随机潜在反向可达图，从备选种子集合中均匀选择本轮次的种子节点，然后在其他节点中均匀随机选择一个节点r作为根，并从r开始进行反向广度优先搜索。搜索过程中访问到的每条边都按照上述概率保留为激活边、待增益边或阻塞边。由r到达所有种子节点的非阻塞边组成的最小子图就构成了一个随机潜在反向可达图R。
在随机潜在反向可达图R上定义一个二值函数yR（B）。当且仅当从种子节点出发存在激活路径可以到达根节点，或者提升节点集合B为增益节点后存在一条激活路径到达根节点时，yR（B）=1；否则yR（B）=0。假设已经采样了足够数量的潜在反向可达图，用表示这些图集合。在给定的备选种子集合下，增益节点集合B的传播影响期望可以估计为
(10)
2.2.2 期望阈值边际增益函数估计
计算，一种简单的思路是直接利用进行估计，然而当节点数量较多时，这种方法可能会严重偏离实际值。Tang等[15]在种子数量最小化任务中提出，估计阈值边际增益函数时，可以采用将反向可达图拓展成多根的方法，从而得到有效的近似值。假设潜在反向可达图的根节点数量为k，根节点对于阈值边际增益函数的期望贡献可以表示为min（nt/k，ηt），k越接近nt/ηt，准确率越高。
基于这一思路，通过采样k根潜在反向可达图，可以估计给定增益节点在阈值下的期望边际增益。采样生成一个随机的kPRR-Graph，需要从中随机选择k个节点作为根节点，从这些根节点出发构造潜在反向可达图R。定义二值函数，当且仅当种子节点存在激活路径到达任一根节点，或者提升节点集合B为增益节点后，存在激活路径到达至少一个根节点时，=1，否则=0。
定义表示采样的随机kPRR-Graph集合，则期望阈值边际增益函数可以近似计算为
(11)
定理1[15] 定义概率，采样潜在反向可达图时，按照概率r设置根节点数量，按照概率1-r设置，则有
(12)
2.2.3 采样和增益节点选择
在目标函数满足单调性和子模性时，贪心策略可提供严格的近似保证。贪心策略从空集合开始，逐一选择使目标优化函数最大化的节点加入集合。但只满足单调性而非子模性。Lin等[12]提出三明治近似策略为非子模的目标优化函数最大化问题，并提出了一个解决范式。由于直接在非子模函数上使用贪心策略得到的结果是没有近似保证的，可能出现结果偏小的情况。构造满足单调子模性的紧凑下界函数，计算使下界函数最大化的节点集合可以弥补直接贪心导致的结果偏小的情况，从而提供最大化的近似保证。
在多根潜在反向可达图中定义关键点[12]集合。定义（B）的单调子模下界函数。期望阈值边际增益函数的下界函数可以估计为
(13)
由于具有单调子模性，和也具有单调子模性。
TRIM[15]算法框架通常用于解决单调子模的下界函数的期望最大化问题。算法2描述了这一过程。TRIM算法在当前所维护的采样集合上应用贪心策略（算法3）动态计算采样造成的误差，直至误差满足近似性要求。如果不满足则继续扩大采样的规模。
定理2[15] 在1-δ的概率下，通过下界贪心策略可以得到期望阈值边际增益下界函数最大化问题的1-近似解。
可以证明，通过下界贪心策略求得的近似解，与阈值边际增益函数的最优解比例近似小于，其中表示下界函数和估计函数的近似比。
第3节中实验结果展示，直接采用下界贪心策略也可以获得一个逼近最优解的结果。
下界贪心策略会返回一个kPRR-Graph的采样集合，三明治近似策略在采样集合上贪心计算使最大化的增益节点集合，具体来讲，从空节点开始，逐一选择节点加入，直到节点数量达到要求。
算法2 下界贪心策略
Alg.2 Lower bound greedy strategy
算法3 迭代过程中的贪心策略
Alg.3 Greedy strategy on iterative step
对比和，选择使影响力更大的节点集合作为本轮次最终选择的增益节点集合Bsa，即
(14)
算法4描述了这一过程。可以证明，通过三明治近似策略求得的增益节点集合是阈值边际增益函数最大化问题的近似最优解。
算法4 三明治近似策略
Alg.4 Sandwich approximation strategy
2.3 复杂度分析
2.3.1 准确性近似分析
对下界贪心策略和三明治近似策略的理论近似性进行分析。
定理3 在1-δ的概率下，通过下界贪心策略和三明治近似策略求得的近似解BL，与使期望阈值边际增益函数最大化的最优解的比值近似小于。
采用自适应贪心策略π可以得到近似比为（ln η+1）2/α的近似解，其中α为每轮次求解最大阈值边际增益时的近似比例。下界贪心策略和三明治近似策略两种方法中，均有
(15)
综上，采用自适应贪心策略得到的传播轮次与最优解的近似比小于。
2.3.2 时间复杂度分析
下界贪心策略和三明治近似策略的复杂度主要来自三个方面：采样随机多根潜在反向可达图的总数量、生成一个随机多根潜在反向可达图的时间复杂度和节点贪心选择的复杂度。
定理4 第t轮次应用下界贪心策略产生的随机多根潜在反向可达图的数量为Obln ，Ob，t表示选择数量为b的增益节点集合可以产生的最大期望阈值边际增益下界。
定理5 定义Q表示一个随机多根潜在反向可达图的最大期望，在每轮次采用下界贪心策略和三明治近似策略的计算复杂度为
(16)
综上，采用自适应贪心策略的算法总复杂度为
(17)
式中，T为采用自适应贪心策略达到阈值所需要的传播总轮次，采用自适应贪心策略可以达到近似线性的复杂度。
3 实验结果
为了验证AdaMBTS算法的正确性与时间效率，在多个真实数据集上进行实验，采用启发式的增益节点集合选择算法作为基线方法进行对比，实验结果展示AdaMBTS在正确性上具有明显的优势。所有的实验在CPU型号为Intel Xeon Gold 5220R@2.20 GHz，1 T内存的机器上进行。
3.1 实验设置
3.1.1 数据准备
数据集：实验在真实社交网络数据集Digg[17]、Flixster[18]和Twitter[19]上进行。采用数据集中提供的图结构建立社交网络G=（V，F）。图结构中每个节点代表一个用户，在Digg数据集上，若两个用户之间存在发帖和回帖的关系，则存在一条边。Flixster数据集上的边表示用户之间的好友关系。Twitter中的边表示用户主页之间的关注关系。实验仅在这些数据集的最大弱联通分量上进行。
估计传播概率：实验前，需要学习图上每条边的影响概率puv和增益概率p′uv。利用Lin等[12]提出的方案构建影响增益模型。实验采用Goyal等[22]提出的影响概率模型学习社交网络上每条边的影响概率，采用计算结果的2倍作为边上的传播影响概率。各数据集点、边统计如表1所示。定义增益参数β，对于社交网络上的边euv，若这条边的影响概率为puv，那么提升后的影响概率为。
表1数据集点、边统计
Tab.1 Statistics of points and edges in the dataset
备选种子集合：采用基于鞅的影响力最大化（influence maximization via martingales，IMM）算法[6]选择500个传播影响最大的节点作为备选种子集合，从这些种子出发可以得到有效的传播。设定种子节点成为各轮次传播的种子节点的概率为0.1。
3.1.2 基线算法
采用启发式算法和非自适应的增益节点集合选择策略作为基线算法与AdaMBTS进行对比。实验时，预先生成了20组传播120轮次的传播实例，统计在20组传播实例上到达阈值时所进行的传播轮次的平均值，在设计传播阈值时，约束了传播轮次不超过120。
基线算法采用最大化节点度数（Degree）[12]、PageRank和非自适应的基于单轮次增益节点选择策略（single round based multiply boosting nodes selection，S-MBTS）[12]。
Degree[12]：在每轮次中，最大节点度数启发式算法迭代选择有权度数最大的节点加入增益节点集合，直到增益节点集合数量达到要求。参考文献[12]的节点度数权重定义，实验中采用5种权重度数，节点u的权重度数定义为：①所有出边传播概率的总和；②不包括终点在增益节点集合中的出边的传播概率总和；③所有入边提升概率与原传播概率差的总和；④不包括起点在增益节点集合中所有入边提升概率与原传播概率差的；⑤不包括终点在已经激活节点集合中的出边的传播概率总和。实验结果采用5种不同有权度数定义中平均传播轮次最少的结果。
PageRank[20]：在每轮次中，选择PageRank分数最大的b个节点加入增益节点集合。
3.2 结果分析
在Digg[17]、Flixster[18]和Twitter[19]数据集上进行测试，实验结果表明，在不同阈值与不同参数下，基于AdaMBTS和AdaMBTS-LB的增益节点选择策略相比于最大化节点度数[12]、PageRank[20]、非自适应增益节点选择策略[12]3个基线算法表现出了明显的优势。达到阈值所需的期望传播轮次远低于其他基线方法。从时间效率上，AdaMBTS的复杂度近似线性，AdaMBTS-LB采用下界贪心策略估计期望边际增益最大解。在保持相当的正确率的情况下，相比于采用三明治近似策略的AdaMBTS，AdaMBTS-LB在时间效率有显著提升。
3.2.1 性能对比
在不同传播影响阈值下，采用自适应选择策略所需的期望最少传播轮次始终优于其他基线算法。设置增益系数β=3，每轮次增益节点数量b=50，改变不同数据集上的影响传播阈值与节点数量的比例η/n，计算采用不同增益节点选择策略所需的期望传播轮次T。实验结果如图1所示。可以观察到，在3个数据集上采用AdaMBTS和AdaMBTS-LB要优于其他启发式节点选择策略[12，20]，相比于S-MBTS[12]也存在相当大的优势。图1中PageRank和Degree的期望传播轮次远大于通过AdaMBTS选择增益节点所需的传播轮次。在Digg数据集上，Degree和PageRank平均需要44.8和47.7轮次才能到达25%的影响阈值；而AdaMBTS和AdaMBTS-LB仅需要33.65和35.15轮次即可达到阈值。在Flixster数据集上，Degree和PageRank平均需要77.15和82.9轮次才能达到50%的影响阈值；而AdaMBTS和AdaMBTS-LB仅需要48.65和50.05轮次即可达到指定传播阈值。在Twitter数据集上，Degree和PageRank都平均需要87轮次才能达到35%的影响阈值；而AdaMBTS和AdaMBTS-LB仅需要60.8和62.2轮次即可达到指定传播阈值。而S-MBTS在3个数据集上分别需要36.3、53.6、74.4传播轮次达到阈值。采用AdaMBTS比采用S-MBTS在3个数据集上分别减少了7.3%、9.2%、18.3%的时间轮次，而采用AdaMBTS-LB比采用S-MBTS在3个数据集上分别减少了3.2%、6.6%、16.4%的时间轮次，两种方法都表现出了明显的优势，而这一优势将随着传播轮次的增加而增大。
图1β=3，b=50时不同η/n下所需的传播轮次
Fig.1The required spread rounds at different η/n when β=3, b=50
图2分别展示了不同数据集上AdaMBTS和AdaMBTS-LB的平均每轮次运行时间，线条上的数值为AdaMBTS-LB相对于AdaMBTS的加速比。虽然AdaMBTS-LB算法准确率略差于AdaMBTS，但在运行时间上有着显著优势，在精确度需求不高的时候可以采用AdaMBTS-LB算法提升效率。随着传播影响阈值的提高。AdaMBTS算法在Digg数据集和Flixster数据集上平均每轮次运行时间呈现上升的趋势，这是由于采样数量提升。而在Twitter数据集却先上升而后下降。这是由于随着η的增长，传播轮次增长，在早期传播轮次中每轮次采样的kPRR-Graph数量增多，但kPRR-Graph的根的数量减少，根的数量直接与kPRR-Graph的最大期望大小有关。而Twitter数据集的规模最大，kPRR-Graph的期望大小对运行时间的影响更大，随着η的增长，总传播轮次数量增长，增长的尾部传播轮次带来的传播影响增益相对减少，导致对应的ηi较小，运行时间较短，从而使得整体的平均每轮次运行时间变小。
图2β=3，b=50时不同η/n下的平均每轮次运行时间
Fig.2Average time per round at different η/n when β=3, b=50
3.2.2 参数调整
为了测试不同参数对于算法准确性的影响，分别在β=3以及b=50，100，150的情况下进行对比实验。实验证明AdaMBTS在不同参数的设置下，达到传播影响阈值所需要的传播轮次远小于基线算法，始终保持一个较高的准确率。
由于不同数据集的规模和结构不同，在不同的数据集设置了不同的阈值限制，从而能够在实验预生成的传播轮次中达到阈值。Digg上设置 η/n=0.25，Flixster上设置η/n=0.5，Twitter上设置η/n=0.35。
图3展示了在不同数据集上β=3时，设置不同的增益节点集合数量b，采用不同的增益节点选择策略时，达到阈值所需的传播轮次T的变化。可以观察到，随着增益节点数量的增加，期望传播轮次逐渐减少，但减少幅度逐渐变小，增加增益节点集合的数量对于传播轮次的减少起到的效果有限。基于AdaMBTS和AdaMBTS-LB选择的增益节点集合相比于基线算法，能够有效减少阈值要求下必需的传播轮次。
图3β=3时不同增益节点集合数量下达到阈值所需的传播轮次
Fig.3The required spread rounds at different boosting node set quantity when β=3
图4同时展示了AdaMBTS和AdaMBTS-LB的平均每轮次运行时间，AdaMBTS-LB在准确性上略低于AdaMBTS，但在时间效率上相对于AdaMBTS有较大的提升， AdaMBTS-LB的时间效率受到增益节点数量的影响相对较小，能始终保持高效的状态。
基于2.3节中的分析，AdaMBTS和AdaMBTS-LB的算法复杂度与ε2成反比，图5展示了AdaMBTS和AdaMBTS-LB在不同误差参数ε下的运行耗时与基线算法[12，20]的对比，其中Degeree与PageRank的平均每轮次运行时间曲线几乎重合。实验在Digg数据集下进行，设置增益节点集合数量b=50，增益系数β=3。虽然AdaMBTS和AdaMBTS-LB的运行速度相较于基线算法较慢，但通过调整误差参数，可以在结果准确率和运行效率之间取得一个均衡。即使设置较大的误差参数，在大部分情况下，AdaMBTS和AdaMBTS-LB相比于基线算法仍然有效减少了达到阈值所需的轮次。
图4β=3时不同增益节点集合数量下平均每轮次运行时间
Fig.4Average time per round at different boosting node set quantity when β=3
图5不同ε时平均每轮次运行时间和达到阈值所需的轮次
Fig.5Average time per round and the required spread rounds at different ε
4 结论
提出了多轮次传播影响增益模型下的增益节点传播成本最小化问题。采用自适应的增益节点动态贪心选择策略和相应的下界策略，使得产品可以用最少的传播轮次达到传播影响阈值，并从理论上论述了AdaMBTS和AdaMBTS-LB与最优策略的近似性。在真实数据集上的实验结果表明，AdaMBTS和AdaMBTS-LB能够高效地计算得到使期望传播轮次最少的有效近似解。
