摘要
现有的序列广告推荐研究主要关注用户对广告的偏好，未充分考虑广告间的正向关系。从广告间的关联出发，将广告网络和用户网络同时纳入考量，构建了基于触发模型的多轮广告序列推荐影响力最大化模型。提出了基于广告边的多轮反向影响力采样贪心策略，以提升广告平台收益，并证明了这一方法具有严格的理论下界保证。实验表明，与现有最优方法相比，该方法的广告传播影响力收益平均提升了35%，显著增强了广告推荐效果，为广告序列推荐提供了新的解决方案。
Abstract
Existing research on sequential ad recommendations mainly focuses on user preferences for advertisement, insufficiently considering positive relationships between ads. Starting from the associations between ads, incorporates both ad networks and user networks into consideration, a multi-round social advertising influence maximization model based on triggering model was constructed. An ad edge based greedy strategy based on multi-round reverse influence sampling was proposed to enhance platform revenue, with theoretical proofs of its strict lower bound guarantee. Experiments show that compared to existing optimal methods, the proposed method increases the average ad propagation influence revenue by 35%, significantly enhancing ad recommendation effectiveness, providing a new solution for ad sequence recommendations.
随着移动设备的普及和信息网络的飞速发展，人们上网越来越便利，在社交网络中的沟通交流因打破了时间和空间的限制而备受欢迎。相比于传统广告，社交广告可以通过用户的“点赞”和“转发”等行为快速获得大量曝光。因此在社交网络上投放广告成为社交平台的一个重要盈利方式，广告序列推荐方向吸引了一系列研究。一些相关研究注重用户对广告的兴趣[1-2]，假设用户之间彼此独立，在浏览广告序列的过程中，用户根据对广告的兴趣有概率停止浏览，这些工作倾向于把更能吸引兴趣的广告排在前面，让用户持续浏览以获取更多收益。Shi等[3]的另一部分研究则假定用户会浏览到平台推荐的所有广告，且认为广告之间有正向联系，两个有关联的广告被用户接受会有额外收益。
然而，这些工作忽略了社交网络中用户传播的影响。在社交广告的背景下，用户并非孤立，用户接受广告的行为也会进一步暴露给其他的用户，从而影响其他用户的选择。因此也需要考虑社交网络中用户间的信息传播作用，这一点在影响力最大化领域有着广泛的研究。社交网络影响力最大化（influence maximization，IM）问题[4]针对市场营销过程中的“口碑效应”（word-of-mouth）和“病毒营销”（viral marketing）等传播原理进行研究，Kempe等[5]将其模型化为算法问题，即在用户网络中选取一个最多k个节点的种子集合，向它们投放广告，通过网络传播，最大化受影响的用户数量。Kempe等引入了广泛使用的独立级联（independent cascade，IC）模型[6]、线性阈值（linear threshold，LT）模型[7]和触发（triggering model，TR）模型，证明了影响力最大化问题在这三种模型上都是NP-hard的，并给出了近似比为1-1/（e-ε）的贪心算法。后续的工作针对贪心算法中的采样开销进行优化。一部分研究[8-9]利用模型的性质，通过减少模拟计算次数来提升模拟效率；另一部分研究采用启发式算法进行针对性优化[10-11]，但缺乏效率和精度保证。主流的方法基于Borgs等[12]提出的反向影响力采样（reverse influence sampling，RIS）进行加速。在此基础上Tang等提出了TIM/TIM+[13]和IMM[14]算法，将时间复杂度优化到O（（k（m+n）logn）/ε2）。为了进一步减少采样次数，优化处理效率，最新工作采用动态调试策略确定反向传播次数[15]。
以上工作都只考虑了单轮次的影响传播过程，Sun等[16]首次考虑实际生活中的多轮传播过程，建模了多轮影响力传播模型，Lozano-Osorio等[17]在此基础上提出智能邻域搜索策略进一步提高了多轮IM问题的可扩展性。
影响力最大化问题虽然利用社交网络上的用户传播提升商品推广的影响力，但大多都默认用户一定会接受推荐给他们的广告，也不会考虑广告推荐顺序的差异。为解决这一挑战，Tang[18]首次将社交广告序列推荐和影响力最大化问题结合起来，假定用户逐个按顺序到来，为每一个到来的用户都推荐一组序列广告，用户会根据自己的兴趣可能接受部分广告，也有可能停止浏览。他们将广告先按用户在网络上传播的期望收益与用户放弃继续浏览概率的比值进行排序，然后使用动态规划算法选取最终的广告序列，综合考虑了用户兴趣和网络传播。这一工作也是考虑影响力最大化的广告序列推荐问题目前比较好的解决方案。
目前的研究工作大多忽略了广告之间的关联，没有考虑到用户对广告的接受程度很可能也受其他广告的影响。产品之间的关联可能会激发用户对广告内容的兴趣。例如，一个用户看到了羽毛球拍的广告并且购买了它，这个用户接受羽毛球广告的概率会大大提升。可以利用广告的这种关联增益效应，提升用户兴趣，并利用社交网络传播连锁反应，促进广告在社交网络上产生更高的效益，避免在同等成本下推送无关广告。
在广告序列推荐问题上首次将广告网络和用户网络同时纳入模型，在已有的影响力最大化问题和广告推荐问题的基础上，综合用户对广告的偏好、广告之间的促进作用以及用户网络的信息传递，并考虑到广告推荐不是一次性过程，加入多轮推荐的模式，建立能够同时为一组用户服务的多轮广告序列影响力最大化问题模型。提出基于边的贪心算法，取得了更好的推荐效果，使得平台的收益最大化。真实数据集上的对比实验验证了算法的有效性，提出的算法较现有最优算法平均提升了35%的广告收益。
1 问题描述
多轮广告序列影响最大化问题的最终目标为，对于一组具有相似特性的特定用户，基于广告之间的关联，向他们推荐相同的多轮序列广告，经过社交网络传播，达到广告收益的最大化。
1.1 符号表示
用US表示需要推送广告的这组特定用户的集合。定义广告网络N=（V，W），其中V代表可推荐的广告集合；为广告边，即广告和广告之间的有向边，自环代表广告本身的接受概率，其他边代表两个广告之间具有促进关系。例如，在同一个广告序列中先后向用户u推荐了两个不同的广告v1和v2，并且v1和v2之间有一条有向边，那么如果用户接受了v1，则会有更大的概率接受广告v2。但不同用户对于广告的接受程度，以及接受了一个广告对接受另一个广告的促进程度可能不尽相同，使用函数来衡量这一程度。对于US×W中的每个元素（u，（v1，v2））都有函数值w（u，（v1，v2））：
1）当v1=v2时，w（u，（v1，v2））表示无其他广告影响时用户u接受广告v2的概率；
2）当v1≠v2时，w（u，（v1，v2））表示用户u接受了广告v1再看到广告v2时接受概率提高的倍数。
例如，用户u接受广告v1和广告v2的概率分别为w（u，（v1，v1））和w（u，（v2，v2）），如果用户已经接受了v1，并且v1和v2之间存在一条有向边（v1，v2），那么用户u接受广告v2的概率就会增加w（u，（v1，v2））×w（u，（v2，v2））。当v2有多个入边邻居被接受时，真实的增益难以计算，但多个广告增益的结果最差也不会差过单个广告的增益，因此采用一种较为保守的假设，即v2只会被增益幅度最大的边增益一次。这要求函数w至少满足以下两个性质：①u，v，0≤w（u，（v，v））≤1；②u，v1，v2，w（u，（v1，v2））≤1/w（u，（v2，v2））-1。
1.2 传播模型
在影响力传播的研究中，IC模型和LT模型是较为常用的两种模型，都是触发模型的一种特例[5]。为保证本方法的全面性，将使用更为通用的触发模型作为传播模型的基础。定义社交网络G=（U，E），其中U代表用户集合，为用户与用户之间的有向边集，每条边关联一个概率bu1，u2。信息的传播会在离散时刻上进行。初始时刻，种子集合S中的节点会被激活，每个节点u会根据其入边概率选择一个触发集合T（u）。如果在某时刻，未被激活的节点的触发集合中有节点已被激活，则该节点将会被激活。传播会持续到没有新的节点被激活。种子集合S的影响力为最终被激活点的期望数量。
触发模型可以用活跃边图（live-edge graph）上的方法等价表示。给定一组触发集合{T（u）}u∈U，可以构造一个活跃边图L=（U，E（L）），其中E（L）={（u1，u2）u2∈U，u1∈T（u2）}，每条边（u1，u2）都被称为一条活跃边（live-edge）。令Γ（G，S）代表图G中可以被S到达的点的集合。由于触发模型和活跃边图的等价性，触发模型中种子集合S的影响力等价于，该期望值取决于生成的活跃边图L的分布。
1.3 问题定义
定义1 多轮广告序列影响最大化问题是指，给定用户网络G=（U，E）、生成触发集合的概率分布、广告网络N=（V，W）、用户组US、函数w: 、轮数T、序列长度限制k、广告被接受的收益函数r: ，推荐T轮广告序列，每轮至多k个广告，使得平台推荐广告的总收益最大化，即：
(1)
其中，ρ（σ）代表平台推荐广告带来的总收益。
定义如下符号来方便描述：σt，i表示一组解σ中第t轮广告序列中的第i个广告。使用符号E（·）来表示广告序列中生成的边集，即
(2)
(3)
其中，E（·）表示序列的生成边集。则ρ（σ）可以等价地转化为边的函数:
(4)
其中：r（v）为每有一个用户接受了广告v，平台可以获得的广告收益；f（E（σ），v）代表经过T轮推荐和传播后，用户网络中接受广告v的人数期望值，即
(5)
其中：Lt为在用户网络上随机生成的活跃边图；Sv，t为US的子集，代表第t轮时用户组US中接受了广告v的用户集合。f（E（σ），v）的值取决于L1，L2，···，LT和Sv，1，Sv，2，···，Sv，T的分布。
为了得到Sv，t的分布，需要计算US中用户对于被推送的广告序列σt中每个广告的接受概率，用pu，v，t代表用户u在第t轮接受广告v的概率，则：
(6)
其中：的含义为如果满足括号内条件值为1，否则值为0；代表（v′，v）对v的增益是所有v的入边中最大那条的概率；pu，v，t为用户u自身愿意接受v的概率与其他广告对v的增益之和。如果多个广告同时对v有增益，则选择增益最大的广告。Pmax可以表示为
(7)
即入边（v′，v）对v产生最大增益的概率。（v′，v）能对v造成最大增益的前提是v′被用户u接受，并且与v有连接关系的其他增益大于（v′，v）的广告没有被u接受。通过上述过程可以获取Sv，t的分布，进而求得h（E（σ）），即在选定广告序列σ后产生的期望收益。
多轮广告序列影响最大化问题的目标为找到最佳的σ使得推荐广告总收益ρ（σ）最大化。由于ρ（σ）可以等价地转化为边集合函数h（E（σ）），且为了边贪心策略的需要，接下来将使用h作为需要最大化的目标函数。
2 算法设计
针对多轮广告序列影响最大化问题，本节提出了基于广告边的贪心策略。算法框架如图1所示。算法会进行T轮推荐，每轮使用边贪心策略结合前面的推荐结果将广告序列扩充至长度k，使用三明治算法选出每轮最优的序列，结合T轮推荐序列形成最终结果。相比已有算法，算法的创新之处在于：①使用边贪心策略利用广告间正向关系；②使用多轮反向影响力采样方法以快速估计边际收益；③提出三明治算法解决目标函数不具备子模性的挑战。
图1算法框架
Fig.1Algorithm framework diagram
2.1 基于边的贪心策略
对于多轮广告序列影响最大化问题，算法1给出了基于边的贪心策略。在进行每一轮的广告选择时，相较于其他直接对广告节点进行选择的算法[1-2，18]，算法1所示的边贪心策略更加注重广告边（即广告间的促进关系）的作用，在广告之间具有强增益作用的广告网络中，边贪心的算法可以有效挖掘出广告边的价值。同时，算法将用户对广告本身的接受程度设置为自环边的边权，与其他边一起竞争，也不会忽略掉节点本身的价值，即用户对广告的偏好。
算法1将从空集开始，逐轮选择每一轮的广告序列。用σt表示第t轮推荐的广告序列，初始使σt为空。用ε来表示尾部不在σt中的边的集合，用h（（vi，vj，t）|E）=h（E∪{（vi，vj，t）}）-h（E）表示广告边（vi，vj，t）在经过用户网络传播后的边际收益。每次贪心地选择边际收益最高的一条边（vi，vj）∈ε，如果边的头部vi不在σt里，或者vi=vj，即该边是自环，则只把vj加入σt的末尾，否则就把vi和vj按顺序依次加入σt的末尾，第11行和第13行中的⊕代表将该符号右边的节点连接到左侧序列的末尾。将每轮选择的σt合并到σ中得到最终的结果。该结果具有合理的下界保证。
算法1 边贪心算法
Alg.1 Edge greedy algorithm
定理1 用σ*表示多轮社交广告序列影响力最大化的最优解。如果函数h具有单调性和子模性，边贪心算法满足：
(8)
其中，din为广告网络中节点的最大入度。
证明:算法可以从轮次的层面，看成对每个时间轮t，都贪心地选择一个σt来最大化ρ（{σ1，σ2，···，σt-1，σt}）-ρ（{σ1，σ2，···，σt-1}）。每一轮内部再选择边际收益最大的边加入进来最终形成σt。如果h是单调子模的，那么每一轮内的目标函数ht（E′）=h（E′|E（{σ1，σ2，···，σt-1}））也是单调子模的。对于目标函数为单调子模函数的边贪心算法，可证明其近似比[19]至少为。
2.2 多轮反向影响力采样
为了快速估算广告边在社交网络G中造成的影响力，即算法1的步骤8，即计算（vi，vj）的边际收益，设计了多轮反向影响力采样方法。
对于社交网络G中的每条边（u1，u2），将以的概率被保留，以的概率被删去，这样生成得到的子图g被称为G的一个采样。
选择G中的一个节点u作为起始节点，g中所有能够到达u的点集被称为一个反向可达集，在多轮的情况下，每一轮都独立地随机生成一个u的反向可达集。定义多轮反向可达集，其中代表第t轮中u的反向可达集中的节点与时间t的二元组的集合。
定义一个随机多轮反向可达集为随机选择一个u作为起始节点的多轮反向可达集。对于一个广告网络N以及一组广告序列σ，用Sv={（u，t）|u∈Sv，t}来表示每个时间轮t中会接受并转发广告v的那些特定用户，其中Sv，t为上文提到的第t轮时用户组US中接受了广告v的用户集合。Sv的影响力f（E（σ），v）计算方法如下：
(9)
由式（9）可见，f（E（σ），v）的值取决于Sv和的分布。需要注意的是，对于f来说，f（E（σ），v）中的E（σ）并不需要一定是σ的生成边集，可以替换为任意满足拓扑性质的边集，例如在算法进行过程中，需要计算E（σ）的某些子集的期望收益，后文中使用E′来表示这一参数，即：
(10)
用多轮反向影响力采样方法估计h值的过程如算法 2所示。Sv的分布可以通过pu，v，t得出。如步骤12所示，对于生成的每一个多轮反向可达集，可以直接计算出Sv∩=Ø的概率，进而得出Sv∩≠Ø的期望。
算法2 多轮反向影响力采样方法
Alg.2 Multi-round reverse influence sampling method
引理1 对于任意的ε＞0，＞0，如果，则
(11)
其中，，代表每个采样值的上界。h（E′）是所求，不能精准获取其值，但是可以找到一个尽可能大的下界，使得在保证1-1/（）的置信度的同时，采样的次数尽可能少，提升时间效率。对于US中的用户，至少能计算没有传播的情况下接受广告v的人数期望，即
(12)
在算法中，使用LB作为h（E′）的一个下界计算θ，并进行θ次反向采样，结合对Sv分布的计算，最终有1-1/（）的概率，得出函数h估计值的偏差与真实值相比不超过ε。
由引理1可知，使用多轮反向影响力采样方法计算边际收益的边贪心算法对于每一轮t，都有至少1-1/（）的概率找到一个近似比为的近似结果。那么将所有轮合并起来，有至少1-1/的概率，算法在每一轮得到的答案都能满足该近似比。
2.3 三明治算法
满足定理1的一个重要前提条件是函数h必须同时满足单调性和子模性[20]。函数具有单调性是指如果一个集合函数f: ，对于任意的集合和元素v∈V\A（其中，“\”表示V和A的差集），都有f（A）≤f（A∪{v}）。函数具有子模性是指如果一个集合函数f: ，对于任意两个集合和元素v∈V\B，都有f（A∪{v}）-f（A）≥f（B∪{v}）-f（B）。
引理2 前文定义的关于边集的函数h具有单调性。
直观上，加入一条边（v1，v2，t0）后，只会改变第t0轮中广告v2被US中用户接受的概率，而且边的作用只会使该广告被接受的概率增加，至少不会减少，并且不会对其他广告的接受程度产生影响。US中用户更愿意接受v2并分享出去，更有可能被更多的人看到，至少不会使平台的收益降低。因此函数h显然是单调的。但是函数h（E′）并不满足子模性，这很容易通过举反例得到。
h虽然满足单调性，却不满足子模性。图2展示了h不满足子模性的一个具体实例。节点A、B、C代表广告，自环边的数字代表用户愿意接受该广告的概率，非自环边代表用户接受边的头部节点对尾部节点的增益倍率。先把问题简化为只有一个轮次t，并且用户网络中只有一个用户节点u，所有广告单次点击收益均为1。在此例中，为了方便，用图中边上的小写字母代表边两侧的节点和时间的三元组，如a表示（A，A，t）。
图2函数h不满足子模性举例
Fig.2Example of the non-submodularity function h
图2（a）计算边e的边际收益h（e|{b}）=h（{b，e}）-h（{b}）=0.2。图2（b）中的图结构与图2（a）中完全一致，但是多选择了两条边a、d，同样地，计算边e的边际收益为h（{a，b，d，e}）-h（{a，b，d}）=1.4-1.1=0.3。 h（e|{b}）≤h（e|{a，b，d}），显然不满足子模性。
对于满足单调性不满足子模性的目标函数，为了保证算法具有合理的近似比，需要引入文献[22]中提到的三明治算法来解决，令：
(13)
(14)
(15)
在每一轮t，找到两个与h定义在同样定义域上的子模函数和，满足对于定义域上的任意，都有。即处处是Δht的下界，处处是Δht的上界，并且如果将原问题中的h替换为和，每一轮得到的结果近似比至少不差于原问题。
定义函数和，除计算第t轮的pu，v，t以外，其余部分与函数h一致，只需重新定义用户在第t轮对所推荐广告的接受概率计算部分，即：
(16)
(17)
直观地理解函数和限制了当前轮在边的增加导致的某些边对其他点增益增大且其余条件都相同的情况下，函数在计算某个广告被接受的概率时，不考虑边的增益，只计算每个节点本身的价值，相当于去除了边的增强作用，最终得到的结果一定小于原函数值。函数则是默认前面的广告被接受的概率均为1，增大了前序广告对该广告增益的概率，最终得到的结果一定大于原函数值，因此有。
引理3 函数和在其定义域上都是单调并子模的。
如算法3所示，每一轮分别使用、h和替换原来的h来运行三次贪心算法，得到三个结果σμt，σρt和σvt，然后在其中选择一个原目标函数值最大的作为最终结果σsandt。在每一轮中使用三明治算法并将结果加入答案，得到整体的σ。
算法3 三明治算法
Alg.3 Sandwich algorithm
定理2 三明治算法保证对任意1≤t≤T，使用多轮反向影响力采样的边贪心算法有：
(18)
其中，代表Δρ在第t轮的最优解，证明见文献[22]。
2.4 准确性与复杂度分析
定理3 对任意的ε＞0和＞0，使用多轮反向影响力采样和三明治算法的边贪心算法得到的σ至少有的概率满足：
(19)
证明：结合定理1、引理2、引理1和引理3可得，有至少1-1/概率每一轮都能得到近似比为的近似结果。易知，对将每个σt作为元素的集合函数ρ，该问题仍然是单调子模的，套用定理1证明中提到的1-e-α的结论，即可得定理3。
纵观算法过程，使用了多轮反向影响力采样方法和三明治算法的边贪心时间复杂度为，其中mv=|W|代表广告网络的边数，mu=|E|代表用户网络的边数，nu=|G|为用户网络节点数，ns=|US|为特殊用户集合大小，R与LB的含义与引理2中一致，LBmin代表可能的LB的最小值。算法需进行T轮，每轮k次选边，选边需遍历大小为mv的广告边集，在估算一条边的边际收益时，需要遍历θ个多轮反向可达集，统计采样结果需要计算已经被选择的广告，不会超过Tk个，只要统计有哪些特殊用户在该广告出现的那一轮接受了这个广告即可，因此统计其结果的时间为Tkns，总复杂度为。对于生成采样的部分，沿用上一次生成过的采样结果不会影响其估算的准确性，故只需按照最大的θ生成一次即可。生成一个采样的时间是Tmu，这部分时间复杂度为O（θTmu）。综上，根据引理2，代入θ，总时间复杂度即为：。
3 实验结果
3.1 实验数据与设置
实验在Amazon评论数据集[23]上进行。该数据集主要记录了用户对已经购买的商品的评论信息。对于网络结构不可见的图，文献[24]提供了一种生成近似网络的方法，商品网络和用户网络的生成遵循该方法。如果买过商品i后又买了商品j的人数超过特定阈值，就在商品网络中加入一条由i到j的有向边，并对每个商品加入自环；如果两个用户购买相同商品的次数超过特定值，就在用户网络中为他们增加有向边。在TR模型中，为每条边在[0，1]中生成一个随机权重。对于每一个商品v，在{0.01，0.02，0.03，0.04，0.05}集合中取一个随机值作为r（v）。用户u对商品v的接受程度用在[0，1]范围内随机生成的w（u，（v，v））表示。对非自环边，v1对v2的促进程度用在[0，1/w（u，（v2，v2））-1]范围内随机生成的w（u，（v1，v2））表示。对于特殊用户集合US，现实中用户的影响力可能存在巨大差距，为了体现用户区分度以及算法对用户网络传播的考虑，分别从用户网络中度数较大和度数较小的节点中随机选择5个，取其并集作为US。
Amazon评论数据集对于不同的商品类别分开统计。按照用户网络和广告网络的稠密程度以及节点与边的规模挑选不同类别，生成了4个不同大小的数据集，数据集的具体参数见表1。
表1数据集参数
Tab.1 Parameters of the data set
实验在操作系统Ubuntu 18.04.6 LTS下运行，CPU型号为Intel（R）Xeon（R）Gold 6254 CPU @ 3.10 GHz，运行内存为314 G。
实验任务是在给定的用户网络和商品网络中为用户推荐多轮广告序列。基于此任务设计的实验，算法的目标是为用户组推荐T轮长度至多为k的广告序列，最大化目标函数ρ（σ），即广告平台的期望收益。最后会对结果序列进行10 000次推荐过程和影响力传播过程的蒙特卡罗模拟，取平均值作为评价结果的标准。通过与已有算法对比验证提出方法的有效性。本次实验中设置T=5，k=10。为兼顾实验效果和效率，除探究θ对结果的影响实验外，设置θ=1 000，即在估计边际收益时进行1 000次多轮反向影响力采样。
3.2 对比实验结果
选择两种已有方法和一种平凡算法作对比。
边贪心：使用多轮反向影响力采样估计边际期望收益，并使用三明治算法取三个结果中最好的序列作为最终结果。
点贪心：不考虑广告之间的促进作用。使用多轮反向影响力采样估计点的边际期望收益。将影响力最大化领域中经典的贪心算法[5]应用于广告网络中，作为广告节点的选择方法。
动态规划：目前该领域最优秀的算法[18]之一，该算法将影响力最大化和广告序列结合起来，将所有广告节点按照期望收益排序，采用动态规划选择广告序列。由于该算法没有考虑多轮情况，实验时将使用多轮反向影响力最大化采样方法为该算法估计广告收益。
随机选择：平凡算法，随机选择广告推荐。
实验证明了边贪心算法能够更有效利用广告之间的促进作用，比已有的最优动态规划方法在Amazon评论数据集上平均提升35%。如图3所示，点贪心算法和动态规划算法基本重合，因为在不考虑广告边收益的情况下，广告节点的收益基本不受其他节点影响，因此无论是动态规划算法还是点贪心算法对于该问题都会按照节点收益从大到小选择节点序列，从而导致结果基本一致。两者都没有考虑广告边对结果的影响，因此在广告网络较为稠密的三个数据集上边贪心算法明显更优，期望收益高出至少40%。而在广告网络较为稀疏的Magazine Subscriptions数据集上，两者与边贪心算法的效果比较接近，边贪心算法只领先10%，但也远远优于平凡算法。广告网络稀疏时，广告之间的联系较弱，广告节点的权重相对提升。这也说明边贪心算法在稠密广告网络上更加适用。但边贪心算法会综合考虑广告之间的联系和广告本身的权重，并且三明治算法的下界函数也相当于进行了点贪心，所以即使在广告网络稀疏的情况下至少不会差于点贪心算法。
图3对比实验结果
Fig.3Comparative experimental results
3.3 参数实验
算法中多轮反向影响力采样部分有两个参数ε和，可以通过调整这两个参数来控制算法的准确度和运行效率。ε越小，越大，算法在估计每条边的边际收益时就越准确，同时运行时间也会越长。观察算法的流程，可以发现调整ε和的最终效果都只是改变了θ的大小，因此分别设置θ=10 100、θ=1 000、θ=10 000、θ=100 000运行边贪心算法，记录分析其多轮反向采样得到的目标函数估计值，对结果进行10 000次蒙特卡罗模拟得到期望收益以及算法总运行时间。如图4所示，随着θ的增大，最终得到的蒙特卡罗模拟期望收益变化并不明显，说明即使是较小的θ，也能得出比较好的效果。但θ过小时，多轮反向采样的结果与蒙特卡罗模拟结果可能相差较大，θ达到1 000以上后，两者基本持平，并且推荐的广告序列基本没有发生变化，结果数据波动较小。而算法的运行时间会随着θ的增大线性增长。因此在实验中，为了兼顾算法的效果、稳定性和运行效率，使用了θ=1 000作为反向采样次数。在实际应用中，也可以根据需求牺牲部分置信度进一步缩小θ的大小来满足效率要求。
图4参数实验结果
Fig.4Parameter experiment results
3.4 消融实验
考虑用户网络传播的影响、广告边的关联、多轮传播等因素，除边贪心和点贪心之外，额外增加三组对比方法进行消融实验：
边贪心（无传播）：去除边贪心算法中多轮反向影响力采样部分，不考虑用户网络的信息传播。
点贪心（无传播）：去除点贪心算法中多轮反向影响力采样部分，不考虑用户网络的信息传播。
每轮相同：第一轮使用边贪心算法选取广告序列，后续每一轮推荐与第一轮相同的广告序列。
如图5所示，每轮推荐相同广告在开始的两个时间轮还比较有竞争力，这侧面说明了边贪心算法选出的序列比较优秀。但由于不能在后面的轮次推荐更高价值的新序列，期望收益只有微小增长。点贪心忽略了广告边的促进作用，期望收益也不如边贪心算法。
图5中两条虚线展示了不考虑用户网络影响力传播的情况。类似地，在用户网络较为稠密的三个数据集上，无传播的算法都表现较差。而在用户网络较为稀疏的Software数据集上，无传播的边贪心算法与有传播的边贪心算法效果较为接近。无传播的算法不考虑传播结果，就无法区分影响力大的用户和影响力小的用户，可能部分用户虽然对广告序列的接受程度很高，但无法造成大量影响导致最终结果较差。在用户网络稀疏的图上，用户影响力差距较小，会降低影响力传播对结果的贡献，但无法完全消除。有传播的算法还是优于无传播的算法。用户网络越复杂，用户之间的影响力区别越大，有传播的算法越有优势。
图5消融实验结果
Fig.5Ablation experiment results
4 结论
将广告序列推荐问题和影响力最大化问题结合，提出了多轮广告序列影响力最大化问题。综合考虑了用户对广告的偏好、广告之间的关联对用户接受广告程度的促进作用和用户网络上的信息传递，建立了新的多轮广告序列推荐影响力最大化问题模型以及解决该问题的贪心算法，使用多轮反向影响力采样技术提升算法效率，用三明治算法解决了目标函数不具有子模性的问题，并证明了算法的近似性和时间复杂度。基于现实数据集的实验表明，基于多轮反向影响力采样的贪心算法能够帮助平台推荐收益更大的多轮广告序列，较现有最优方法平均提升35%，为多轮广告序列推荐影响力最大化问题提供合理的近似解。
