基于边际性价比的收益影响力最大化算法

王思诚，孔 兵**，包崇明，周丽华，王崇云

(1. 云南大学 信息学院，云南 昆明 650500；2. 云南大学 软件学院，云南 昆明 650500；3. 云南大学 生态与环境学院，云南 昆明 650500)

随着微博、微信、Facebook 等社交媒体日渐崛起，在线社交已成为当前人类重要的社交方式. 社交网络中信息快速传播的特点，使线上产品推广成为一种重要的营销方式. 为向人群营销自己的产品，商家首先在社交网络中挑选部分影响力较大的用户作为初始用户，然后通过初始用户的口碑效应尽可能多地影响其他用户，继而提升用户购买产品的机会. 这种营销方式与病毒传播相似，被称为病毒式营销.

Richardso 等[1]首先研究病毒式营销，并形式化定义影响力最大化问题. 经过多年研究发展，影响力最大化问题已经在群众思想传播、热门话题预测、谣言分析控制等领域有着广泛的应用[2]，是社会网络分析和数据挖掘领域的热门研究方向[3].

病毒式营销是影响力最大化在商业中的主要应用. 当前大多数病毒式营销模型只关注影响力的传播范围[4]，很少考虑营销中的商业投入产出效益.在现实营销中，有3 个问题是商家所关注的：①产品目标用户，针对高价值目标用户进行营销才产生高收益，对非目标用户而言，扩大的传播范围不会带来任何收益；②节点代价，商家选取不同的初始节点将花费不同代价. 例如，商家想要在Facebook推广自己的产品，可以选择费用高粉丝多的明星人物作为初始节点，也可以选择费用低粉丝少的社区达人作为初始节点；③营销预算，厂商资金有限，营销投入受到限制. 商家如何使用有限的预算，快速选取符合要求的种子节点，获取最大的推广收益，这被称为收益影响力最大化问题.

为了建模更复杂的商业应用场景，在影响力最大化问题中引入约束条件已成为一种研究趋势[5].收益影响力最大化问题引入目标节点、预算、节点收益和代价作为约束条件. 现有的文献资料中，已经有针对引入预算和节点代价约束问题的解决方案. Nguyen 等[6]提出基于有向无环图的算法，迭代缩小候选种子范围，直到找出预算范围内的种子集. Han 等[7]提出平衡种子集选择的启发式算法，快速选取最有影响力的节点和最有效益的节点作为种子节点. Güney 等[8]从统计学角度出发，将问题建模为一个混合整数线性程序，然后利用样本平均近似方案求解问题. 上述研究中假设所有节点都有相同的收益，忽视现实营销中商家更关注目标节点，导致以上方法用于解决收益影响力最大化问题时效果不佳. 另一方面，引入目标节点约束的影响最大化问题也受到学者关注. Li 等[9]研究广告投放过程中的带目标节点的影响力最大化问题，提出一种反向影响集的求解方法. Song 等[10]研究时间状态约束的目标节点影响力，提出一种基于采样的算法. Wen 等[11]为了在特定子集中影响更多的目标节点，采用预先建立用户集群信息索引的方法，以加快种子节点的选择. 但以上的研究只注重捕获目标节点的影响力，没有考虑到节点的收益和选择成本，不能直接用于收益影响力最大化问题.

最近，Banerjee 等[12]同时考虑目标节点、预算和节点收益成本约束，提出IGAIP（Incremental Greedy Algorithm with Improve Performance）算法和HBH（Hop-Based Heuristic）算法. IGAIP 是改进贪心算法，使用资源消耗巨大的蒙特卡洛模拟计算获得用户节点等级的自洽序列，在此基础上选择种子节点，虽然能够取得 (1-1/e)的近似收益保证，却面临着巨大的时间消耗. HBH 启发式算法则是简单选择最具效益的节点，存在严重的收益重叠，在种子集较大的情况下，算法效果表现一般.

现有的研究工作中，单独引入目标节点约束或是引入预算和节点代价约束，并不能对收益影响力最大化问题完整的建模，而同时引入三项约束的IGAIP 和HBH 又分别面临着如下不足：(1)蒙特卡洛模拟的计算量大，导致算法运行效率低；(2)种子节点间存在收益重叠，算法最终效果不佳. 针对以上问题，本文受IMRank[13]启发，利用数值在网络中传递的策略，同时引入三项约束，提出一种不使用蒙特卡洛模拟，还能避免种子节点收益重叠的MCPR（Marginal Cost Performance Ranking）算法. 本文的贡献如下：

(1)定义节点边际性价比作为评价节点重要性的指标，避免了种子节点之间的收益重叠；

(2)证明贪心算法所选取的节点序列为一个自洽序列，提出MCPR 算法，经过10～15 次迭代就能从任意初始序列寻找一个近似自洽序列，有效提高了算法效率；

(3)采用性价比向前分配策略，估计边际性价比，放弃对节点收益的模拟计算，加速MCPR 迭代；

(4)设计实验验证MCPR 算法的性能和效率，结果表明，MCPR 取得近乎贪心算法的性能，同时算法有较高的时间效率.

1 收益影响力最大化问题定义

社交网络G(V,E,P) 表示为有向加权图，其中节点集V(G)={v1,v2,······,vn} 中的节点代表社交网络中的用户，边集E(G)={e1,e2,······,em} 中的边代表社交网络中不同用户之间的联系，边权函数P:E(G)→(0,1]为每一条边分配传播概率. 对于边(vi,vj) 而言，传播概率Pvi→v j表示用户vi影响用户vj的能力.

选取图中节点需要花费一定代价，节点的代价由代价函数C:V(G)→R+确定. 一部分节点将被标记为目标节点，构成目标节点集D，目标节点能够获取的收益由收益函数b:D→R+确定. 节点vi的代价和收益可以分别表示为C(vi) 和b(vi). 如果vi∉D， 那b(vi)=0. 预算B用于选择种子集，每选择一个种子节点，都会从预算中扣除这个种子节点对应的代价. 收益获取函数 β(S) 表示种子集S所能够获取的收益，收益影响力最大化问题可以形式化定义为：对于网络G(V,E,P)，目标节点集D，代价函数C，收益函数b，以及预算B，目标是找到一个种子集S，使得它对于任何其他的种子集S′式(1)均成立.

Kempe 等[14]分析影响力最大化问题存在的性质，收益影响力最大化问题也有相同性质：

(1)收益影响力最大化问题在独立级联模型和线性阈值模型下是NP 难问题；

(2)收益获取函数 β(·) 在独立级联模型下具有子模性. 当 ∀u∈V(G),∀S⊆T⊆V(G)，式(2)恒成立.

2 收益影响力最大化问题启发式算法

本节阐述MCPR 算法的核心思想和主要步骤.首先，定义边际性价比，证明贪心算法选取的节点序列为一个自洽序列；其次，提出算法的整体框架，从任意初始序列开始，利用节点等级与边际性价比之间的关系，迭代的寻找一个近似自洽序列；最后，使用性价比向前分配策略估计边际性价比，加速迭代. 算法的整体结构如图1 所示.

图1 MCPR 算法整体结构Fig. 1 Structure of MCPR algorithm

2.1 边际性价比自洽序列 收益影响力最大化问题选取种子节点时，希望节点的代价低，获取的收益多，同时与其他种子节点之间的收益重叠小. 据此，本文定义边际性价比作为衡量节点重要性度量指标，利用边际特性避免种子节点的收益重叠.

定义 1 边际性价比. 给定种子集S和一个节点v，节点v在种子集S上的边际性价比为：M(v|S)=(β(S∪{v})-β(S))/C(v).

为了准确的描述算法，先对节点等级序列及其符号进行解释. 节点集V(G)={v1,v2,···,vn}，其中n=|V(G)|. 索引序列 {r1,r2,···,rn}，ri为节点的下标索引，ri∈{1,2,···,n}. 将节点集V(G) 的原始下标替换为索引序列中对应的索引得到r={vr1,vr2,···,vrn}，r表示一个节点等级序列，靠前的节点拥有更高的等级和重要性. 例如，节点集 {v1,v2,v3,v4,v5}，索引序列 {5,4,3,2,1}，对应的节点等级序列表示为{v5,v4,v3,v2,v1}，v5拥有最高的等级. 在r的基础上，节点vri的边际性价比Mr(vri)=M(vri|{vr1,vr2,···,vr(i-1)}).

贪心算法在解决收益影响力最大化问题中能取得优异的效果，它在选择种子节点时，首先计算所有非种子节点的边际性价比，然后选择边际性价比最大的节点加入种子集，并且每次迭代中所选取节点的边际性价比呈现逐步降低的趋势. 将每次迭代选择的节点组成一个节点等级序列，那么排前的高等级节点拥有更多的边际性价比，靠后的节点仅有少量的边际性价比，节点的等级与节点的边际性价比正相关.

定理 1 贪心算法每次迭代所选取节点的边际性价比单调递减.

贪心算法得到的节点等级序列，节点等级和节点边际性价比呈正相关，高等级的节点意味着高的边际性价比，事实上构成一个自洽序列.

定理 2 贪心算法得到的节点等级序列是一个自洽序列.

使用自洽序列时，只需要依次选择高等级的节点加入种子集，如同贪心算法选择种子节点的过程，最终种子集也具有近似贪心算法的性能. 然而通过贪心算法寻找自洽序列，需要进行大量蒙特卡洛模拟，时间花销巨大.

2.2 边际性价比排序算法 在节点等级序列中，节点等级与节点边际性价比之间存在相互作用. 节点等级越高，拥有的边际性价比越多，如果一个高等级节点只有少量的边际性价比，可以通过计算边际性价比重新调整节点的等级. 同理，利用节点的等级，也能计算节点的边际性价比. 本文受此启发，提出MCPR 算法，从任意初始节点序列出发，不断迭代调整节点的等级和边际性价比，将每个节点调整到合理的等级，最终逼近一个自洽序列，时间消耗远远低于基于模拟的方法.

MCPR 具体步骤见算法1.

算法 1 边际性价比排序算法(MCPR)

输入G(V,E,P)，代价函数C，收益函数b，预算B，初始序列r，迭代次数t.

输出 种子集S.

步骤 1 开始对序列r进行t次迭代.

步骤 2 一次迭代开始，首先根据序列r，估计所有节点的边际性价比Mr， 然后将Mr按照降序排名，得到新序列r′. 新序列r′用于下一次迭代，令r=r′，完成一次迭代.

步骤 3 结束所有迭代，最终迭代得到的序列r为近似自洽序列.

步骤 4 初始化种子集S为空集.

步骤 5 对序列r从头遍历，准备选取种子节点.

步骤 6 每次遍历节点，如果预算B大于当前遍历节点的代价C(vri)， 将当前遍历节点vri加入种子集S，同时预算B减去代价C(vri)，否则跳过当前遍历节点.

步骤 7 遍历结束，种子节点选取完毕，返回种子集S.

其核心步骤是根据节点当前等级对边际性价比进行估计，再根据边际性价比更新节点等级序列. 反复迭代多次，当所有节点等级不再变化时，就成为一个自洽序列. 但是，找到一个自洽序列通常要经过大量的迭代，这会增加算法时间成本. 事实上，进行少量迭代得到的近似自洽序列，也能够取得很好的效果. 为了证明这一结论，本文在第4.1节中设计实验并分析算法迭代过程，结果表明通常只需要10～15 次迭代，MCPR 就能够找到一个优异的近似自洽序列.

2.3 估计边际性价比 MCPR 每次迭代需要对节点的边际性价比进行近似的估计，为了加速算法迭代，本节将IMRank 中的网络数值传递策略改进应用到包含多个约束条件的收益影响力最大化问题中.

独立级联模型中，每一个节点只有一次被激活的机会. 当一个节点被激活时，该节点有且仅有一次机会去激活它的邻居节点. 对于一个节点v而言，它的性价比来源于等级低于它的节点，而节点v本身也会向等级高于它的节点传递性价比. 假设当所有等级低于vri的节点都完成了自身性价比的传递.在计算Mr(vri)时，需要遵循两条基本的规则：①根据所给出的节点等级，任何节点都只能够被高于自己等级的节点激活；②当一个节点能够被多个节点激活时，它总是会优先被等级最高的节点激活.

根据这两项规则，提出了一种基于节点等级的性价比向前分配策略，用于估计节点的边际性价比，伪代码见算法2. 值得注意的是，不同于IMrank 中固定的影响力，由于每个节点代价的不同，性价比在传递的过程中不是恒定的，每次传递都会发生变化，总体上是一个增长的过程.

算法 2 性价比向前分配策略

输入G(V,E,P)，代价函数C，收益函数b，初始序列r.

输出 边际性价比Mr.

步骤 1 对序列r从后向前遍历，即从第n个节点遍历至第2 个节点，当前受遍历节点为vri.

步骤 2 按式(3)初始化所有的节点的性价比Mr.

步骤 4 如果vri高于自身等级的邻居节点中，还存在节点没有完成性价比的传递，则跳转到步骤3.

步骤 5 完成所有节点遍历，返回估计的边际性价比Mr.

图2 是一个含有 {v1,v2,v3,v4,v5}5 个节点的小型网络. 将网络中所有边的传播概率设置成为p=0.1，节点的代价设置为{11,12,13,14,15}，节点的收益设置为{16,17,18,19,20}，初始序列r={0,4,1,2,3}.

图2 一个示例网络Fig. 2 An example network

在图2 中运行性价比向前分配策略和蒙特卡洛模拟方法计算节点边际性价比，其中蒙特卡洛模拟进行了10 000 次，结果如表1 所示. 实验表明，性价比向前分配策略所得到的结果同蒙特卡洛模拟方法所得到的结果非常接近，尽管不能得到精确的边际性价比，时间消耗却显著减少.

表1 两种算法所取得边际性价比对比Tab. 1 Comparison of marginal cost performance between the two algorithms

3 实验与分析

实验采用算法运行时间和收益作为评价算法效率和性能的指标. 算法获取的收益通过以下步骤计算：①算法使用一定预算，在网络中选取种子节点加入种子集；②模拟种子集在网络中的影响传播，计算所有受影响目标节点的总收益；③重复步骤②1 000 次，取平均值作为算法获取的收益.

3.1 实验数据集与基线算法 Email-Eu-core 数据集是欧洲某大型研究机构的电子邮件通信数据，这些数据由研究成员之间传入和传出的电子邮件信息构成. CollegeMsg 数据集是加州大学欧文分校的在线社交网络上的静态关系网络. Facebook 数据集是从使用Facebookappp 的参与者那里收集的，主要包含Facebook 的朋友圈子. 以上数据集均来自于斯坦福大学SNAP 项目官网，广泛用于社会网络分析和影响力最大化问题研究，具体细节如表2所示.

表2 社交网络数据集Tab. 2 The social network dataset

本文选用5 种常用算法与MCPR 进行实验对比. MAX_DEG 每次选择度最大的节点加入种子集，是一个广泛使用的基线方法. DEG_DIS[15]选择节点加入种子集后，会对邻居节点进行度折扣，能够一定程度减少收益覆盖问题. PAGERANK 用PageRank 中心性作为衡量节点收益的指标. HBH是Banerjee 提出用于解决收益影响力最大化问题的启发式算法，通过计算目标节点周围h跳节点的预期收益选择种子节点，本文中h=2. IGAIP 是改进并提升效率的贪心算法，采用类似于CELF++[16]的改进方式. 本文提出的基于边际性价比排序的启发式算法MCPR，实验中使用基于Random 的序列作为初始序列，迭代10 次.

3.2 实验中的参数设置

（1）传播概率 实验中采用均匀设置（Uniform Setting，简写U）和三价设置（Trivalency Setting，简写T）两种常用的传播概率设置. 均匀设置认为节点影响能力相同，图中每条边的传播概率均为0.1.三价设置认为节点影响力能力存在差异，图中每条边的传播概率从{0.1，0.01，0.001}中随机选取.

（2）目标节点 从所有节点中选取20%的节点作为目标节点[17]，具体步骤参考文献[17].

（3）代价和目标节点收益 本文使用了两种节点代价设置方式：①随机设置（Random Setting，简写R）. 节点的代价从区间(1，50)中随机选取；②度比例设置[18]（Degree Proportional setting，简写D），现实营销中，节点的代价与节点影响力相关，商家选择影响力更大的种子节点需要支付更多的薪金.因此，节点vi的代价C(vi)可以根据节点度进行衡量，计算公式如下：

其中，d(vi) 表示节点vi的度，m表示网络所有节点度之和，n表示节点总个数，t表示节点期望代价，t取25. 目标节点的收益从区间(50，100)随机选取.

（4）预算设置 用同样的预算在不同规模的社会网络中营销是不合理的，大型社会网络理应花费更多的预算. 实验中将按照网络中所有节点总代价的相应比例来设置对应的预算B，比例选取从0.1到0.7，间隔为0.1，下文中用到的预算均以比例表示. 例如，总代价 为1 000时，预算0.1 代表100.

实验中的算法均使用Python3 编写，编程环境为VScode，操作系统为ubuntu5.4.0，硬件配置为3.60 GHz Intel i7-7820x 处理器，64 GB 内存.

3.3 不同算法的收益分析 实验运行设置两种组合：①UR 设置，传播概率使用均匀设置、节点代价使用随机设置；②TD 设置，传播概率使用三价设置、节点代价使用度比例代价. 实验主要目标是在不同的基线算法中进行收益对比分析.

图3 是UR 设置下的实验结果. 3 个数据集中IGAIP 贪心算法取得最多的收益，MCRP 取得的收益略低于贪心算法，在Facebook 数据集，预算为0.7时，MCPR 取得的收益为IGAIP 的98.4%，HBH 取得的收益比MCPR 分别少29.8%、35.7%、33.6%.PAGERANK 取得的收益略优于剩余的算法，MAX_DEG、DEG_DIS 的性能最差.

图3 不同算法在UR 设置下的营销收益Fig. 3 Marketing benefits with different algorithms in UR setting

图4 是TD 设置下的实验结果. 在Email-Eucore、CollegeMsg 和Facebook 数据集，IGAIP、MCPR、HBH 算法取得的近似效果，IGAIP 与MCPR的收益曲线几乎完全重合. 而HBH 在Facebook 数据集性能非常差，算法的效果不稳定.可能的原因是，在数据集节点平均度比较大，或者传播概率较大的时候，每个种子节点都会影响到大量的目标节点，导致HBH 的种子集存在巨大的收益重叠，这会显著降低HBH 算法的性能. PAGERANK、MAX_DEG、DEG_DIS 获取的收益非常有限，与HBH 仍然存在较大的差距.

图4 不同算法在TD 设置下的营销收益Fig. 4 Marketing benefits with different algorithms in TD setting

实验结果表明，本文提出的MCPR 算法相较于现有算法，能够取得与IGAIP 贪心算法近似的收益，并且有着不错的稳定性. 而像HBH 这样的启发式算法，表现不够稳定，总体的收益也低于MCPR.

3.4 不同算法的时间效率分析 表3 展示不同算法的运行时间. 虽然IGAIP 能够取得最好的效果，但相比于其他启发式算法，时间消耗过高. MAX_DEG 仅仅只考虑节点的度，运行时间最少.DEG_DIS 在选择节点时对邻居节点进行度折扣，是MAX_DEG 花费时间的3～5 倍.

表3 不同数据集上算法运行时间对比Tab. 3 Comparison of algorithm running time on different datasets s

PAGERANK 需要花费时间求PageRank 中心值，相对于MAX_DEG 算法，运行时间高了两个数量级. HBH 作为为收益影响力最大化设计的启发式算法，和PAGERANK 在运行时间相差不大. 本文提出的MCPR 算法，在运行速度上相较于IGAIP快近百倍.

在病毒式营销商业场景中，商家需要在合理的时间内完成种子节点选取任务，获取尽可能多的收益. 从实验对比的结果来看，在所有已经提出的方法中，MCPR 在性能和效率上取得平衡，优于现存的算法.

4 MCPR 算法分析

4.1 迭代分析 本节分析MCPR 算法迭代过程，证明MCPR 有较高的迭代效率，能快速找到一个近似自洽序列. 算法分析实验选用Facebook 数据集，其中网络传播概率分别使用均匀设置Uniform和三价设置Trivalency. 通过20 次迭代，选取等级最高的Top100 节点序列分析研究.

节点相似比例代表本次迭代与上一次迭代中Top100 节点相似个数的比例. 图5(a)中，在4 次迭代以后，节点相似比例超过90%，这表明最重要的节点已经被选出，仅有少数节点产生波动. 相似收益比例代表将Top100 节点作为种子节点时，本次迭代收益与最终迭代收益的比例. 图5(b)中，当迭代1 次后，已经能够取得95%以上的最终收益，这是因为迭代1 次后，Top100 节点已经包含大量重要节点. 继续在Uniform 设置下迭代10 次，Trivalency设置下迭代15 次后，获取的收益基本不再变化，接近最终的收益. 序列相似度代表每次迭代中Top100 节点序列与最终自洽序列的节点重合程度.图5(c)中，迭代15 次后，Top100 节点序列达到自洽序列97%的相似度. Uniform 设置比Trivalency设置需要更多的迭代才能达到高序列相似度，这是由于Uniform 更大的传播概率导致更多的收益重叠，序列需要更多的调整次数.

图5 MCPR 算法迭代效率分析Fig. 5 MCPR algorithm iteration efficiency analysis

实验结果表明，MCPR 在首轮迭代中，已经选出大量重要的节点，随后的迭代中不断逼近一个自洽序列，迭代10～15 次得到一个近似自洽序列.

4.2 算法初始序列分析 MCPR 算法从一个初始的序列开始迭代，因此有必要分析算法初始序列对算法性能的影响. 本文选取5 种不同的初始序列，在Facebook 数据集中运行实验，其中传播概率使用均匀设置，节点代价使用随机设置. 实验对不同初始序列获取的益进行比较分析.

如图6 所示，不同的初始序列下，MCPR 算法最终的收益不同. 基于Degree 的初始序列（按节点的度由大至小排列）总能够取得最高的收益. 基于InversCost 的初始序列获取收益最少，说明节点代价与节点重要性无关. 基于Random 的初始序列，对所有节点都是公平的，它不偏爱任何的节点，但也不提供任何节点的重要性，能够取得适中收益.基于InverseDegree 和PageRank 的初始序列并无特别表现，也只能取得中等程度的收益. 综上，基于Degree 的初始序列最适合MCPR 算法.

图6 MCPR 在不同初始排序下的营销收益Fig. 6 Marketing benefits of MCPR under different initial rankings

5 结束语

收益影响力最大化问题能够更好地建模现实中的病毒式营销任务. 为了解决此问题，本文基于边际性价比排序提出MCPR 算法. 在大量的实验对比中，MCPR 能够取得和贪心算法相近的性能，时间消耗远低于贪心算法，在效率和性能上达到良好的平衡，是一种高效的启发式算法. 此外，还对MCPR 算法的迭代效率和初始排序进行实验分析，MCPR 仅需要10 到15 次迭代就能得到一个的优异近似自洽排序. 病毒式营销作为一种商业行动，不可避免会存在商业竞争，在未来的工作中，准备研究收益影响力最大化中的博弈竞争模型.