社交网络中基于成本的广告投放策略

曹玖新 崔桂旗 冯雪艳 闵绘宇

(东南大学计算机科学与工程学院，南京 211189)

依托社交网络[1]产生了一种全新的营销模式——“病毒营销”，该营销模式将找出的最有影响力的若干用户作为信息的源头，并利用口头传播的方式使得信息最终覆盖大部分网络，这就是影响最大化问题的原型．Domingos等[2]最早将影响最大化问题归纳为一个算法问题．Kempe等[3]首次把影响最大化问题形式化为一个离散最优问题．

商家利用有限的成本在社交网络中选择种子用户投放广告，以达到尽可能好的广告效应，其本质是一个影响最大化问题．文献[4]指出，预算有限时，将所有节点的成本视为一个相同的值不能得到较好的影响效果．Leskovec等[5]最先将成本效益这一概念用于影响最大化问题的研究中，考虑到不同节点的成本不同，提出CEF(cost-effective forward selection)算法，文献[6]证明了该算法可以达到的近似比约为最优解的0.394．文献[7]基于CELF提出了优化算法CPP-SNS．Li等[8]提出了带标签的影响最大化问题．文献[9]研究表明，用户自身的兴趣爱好决定其对信息的偏好程度以及与相邻用户间的亲密程度，这导致不同主题的信息在同一社交网络中的传播影响效果不同．Barbieri等[10]在传统的影响力传播模型基础上提出了带有主题意识的影响力传播模型．文献[11]提出了目标影响最大化算法Targeted-MIA，以此来找到能够最大化影响特定用户的可靠用户集合．Aslay等[12]提出了带有主题意识的影响最大化查询问题．Chen等[13]基于带有主题意识的独立级联模型，使用预处理方法来解决带有主题意识的影响最大化问题．Chen等[14]基于MIA模型提出了Best-effort算法．Li等[15]针对在线定向广告提出了基于关键词的定向影响最大化问题．

在广告预算有限的情况下，已有的大部分算法并没有同时考虑节点成本和节点主题属性这2个因素，因此在新问题下原有的一些算法并不能给出较好的解决方案．

本文在选择初始种子节点时，不仅考虑了节点成本，而且还考虑了节点主题属性．在影响力传播模型中，引入了覆盖距离，并设计了一种AvePA算法来选择初始种子节点，以达到在广告预算有限的情况下广告效应尽可能好的目的．

1 基于成本的广告投放问题

同时考虑节点成本和节点主题属性的广告投放问题，可形式化定义为给定一个带主题属性的社交网络G(V,E,T)，其中V为节点集合，E为边集合，T为节点主题属性的集合，选择一个初始种子节点集合S，在集合S的总成本C(S)不超过预算B时，使得最终的广告效应R(S)最好．这里，cost(v)表示节点v的成本，广告效应R(S)是指广告投放结束时处于活跃态的节点Active(v)对广告AD的兴趣度之和．本文采用最终处于活跃态的节点主题属性vtag与广告主题ADtopic间的相似度Sim(vtag，ADtopic)来衡量兴趣度．形式化描述如下：

(1)

(2)

(3)

2 模型建立

2.1 节点成本建模

文献[4]指出当预算有限时，不考虑节点的成本差异难以得到较好的影响效果，且与事实不符．因此，本文在选择初始种子节点时认为不同节点在被选择时的代价不同．大部分社交网络是以关注关系构建的.参考已有研究和实际情况，以节点的出度(即节点关注者数)表示节点的成本，定义如下：

cost(v)=degreeout(v)v∈V

(4)

2.2 节点间的关注度

令blog(u)表示u的微博数，通过节点v转发节点u的微博数vtran(u)和评论节点u的微博数vcom(u)来衡量节点v对节点u的关注度Fvu，其计算公式为

(5)

为了使Fvu的取值范围在0～1之间，对其分母进行了归一化处理．

2.3 节点间影响概率建模

节点u对节点v的影响概率puv受节点v对节点u的关注度Fvu以及节点v的属性vtag与广告主题ADtopic间的相似度Sim(vtag, ADtopic)共同影响．故puv计算公式为

puv=FvuSim(vtag, ADtopic)

(6)

3 基于平均概率的种子节点选择算法

3.1 节点间影响概率建模

本文提出新的度量节点影响力的指标，即平均概率AvePro(u)，其表示单位成本下节点u对其邻居节点的影响概率．

式中，Nout(u)为节点u的出度邻居节点集合．

考虑到2个节点的影响范围可能存在重叠区域，本文引入覆盖距离d使种子节点间保持一定的距离，以有效应对影响重叠问题．

3.2 基于平均概率的AvePA算法思想

已有的利用独立级联模型的影响最大化问题研究中，通常假设节点间的影响概率是常量，因此在使用度中心性、介数中心性和核数这3个指标选取影响力节点时可取得较好的效果[3,16-17]．但实际情况下，人与人之间的关系有强弱之分，并且会影响节点间的影响概率，因此仅基于度中心性或核数选取初始种子节点的算法不尽合理．文献[18]对独立级联模型进行改进，提出了一种拓展独立级联模型，其与独立级联模型唯一的区别是节点间影响概率是不相同的．本文在拓展独立级联模型基础上进行实验．

AvePA算法选择节点时，根据综合考虑了节点平均成本、节点对其出度节点的影响及节点与所投放广告的相似度的AvePro指标来选择种子节点，因此与其他算法相比，选择的种子节点有一定差距．例如，一个节点集合中出度最大的节点与所要投放的广告相似度趋近于0，那么在Degree算法中该节点会被选中，而在AvePA算法中该节点不会被选中．模型中节点有覆盖和未覆盖状态，处于未覆盖状态的节点有可能会被选作种子节点，而处于覆盖状态的节点则不能被选为种子节点．起初所有节点均处于未覆盖状态，每轮选择未被覆盖的平均概率最大且度数大于平均度数的节点.若该节点成本不超过预算，就将其加入到初始种子集合S中，并在广告预算B中减去该节点成本；若节点u为种子节点，则将与u距离小于等于d的所有节点设为覆盖状态．

3.3 AvePA算法

算法1 AvePA算法

输入：社交网络G(V,E,T)，覆盖距离d，广告预算B．

输出：种子节点集合S．

1S=∅

2 for eachv∈Vdo

3 COv=false

4 计算平均概率v

5 end for

6 whileB>0

8 if cost(w)≤Bthen

9S=S∪{w}

10B=B-cost(w)

11 for eachvin {vdw,v≤d,v∈V} do

12 COv=true

13 end for

14 end if

15 else then

16 COw=true

17 end else

18 end while

19 returnS

算法中，AvePro(u)为节点u的平均概率；COu表示节点u是否被覆盖，若节点未被覆盖为false，否则为true；dw,v为节点w和节点v的距离，即2个节点间的最短跳数．

对AvePA算法的分析如下：第1行初始化种子节点集合为空；第2～5行计算每个节点的平均概率，并设置每个节点的覆盖状态为未覆盖状态；第6～18行表示在预算内选取种子节点，每轮选取1个种子节点；第7行选取当前未被覆盖的平均概率最大且度数大于平均度数的节点作为种子节点；第8～14行表示如果该节点成本不超过预算，就将其加入种子节点集合S，并在预算B中减去该节点成本，同时，根据覆盖距离d，以节点w为中心，设置与其距离小于等于d的所有节点为覆盖状态；第15～17行表示若该节点成本超过预算，就直接将其设置为覆盖状态．此外，处于覆盖状态的节点在传播过程中仍可以被其他节点所激活．

3.4 AvePA算法时间复杂度

假设社交网络G(V,E)中节点数目为n，则第2～5行的时间复杂度为O(n)，第6～15行的时间复杂度为O(n)．因此，算法总时间复杂度为O(n)．

4 实验设计与分析

4.1 实验数据集

利用新浪微博提供的API接口抓取新浪微博的真实数据作为数据集，对网络拓扑进行预处理，得到2个较完整的由活跃用户组成的拓扑．一个是有向网络拓扑，由68 243个节点和1 013 164条关注关系组成；另一个是无向网络拓扑，由44 514个节点及162 398条互粉关系组成．

4.1.1 节点主题属性预处理

用户标签可以表征节点主题属性[19]，标签信息可以反映用户的兴趣爱好，在获取节点主题属性后，采用基于《知网》的词汇语义相似度计算方法[20]计算节点主题属性与广告主题间的相似度．对于没有标签信息的用户而言，根据社交网络同质性特点[21]，其微博关注者和粉丝的标签能一定程度上反映该用户的特征．对于关注者和粉丝均很少的用户而言，除了利用关注者标签、粉丝标签外，还要利用用户发布的微博信息进行人工标注．

4.1.2 社交网络数据集获取

对采集到的用户的所有标签出现频次进行统计，将频次大于1 000次的标签可分为吃喝玩乐几个方面，所以选择吃喝玩乐类的广告进行投放比较有代表性，故最终确定选取旅游、饮食、娱乐3类广告进行投放．因此，结合2种拓扑关系和3类广告共获得6个不同的社交网络数据集，如表1所示．

表1 社交网络的网络拓扑信息

4.1.3 节点主题属性与广告主题间的相似度

计算平均概率需要先求出各节点主题属性与广告主题间的相似度．本文对所有用户的所有标签词进行统计，得到73 523个不重复的标签词，并与旅游、饮食和娱乐3个词进行词语相似度计算并统计．根据实验结果，词语相似度的值处于 0.6～1.0 范围的密度较小，处于0～0.4 范围的密度较高，处于 0.4～0.6 范围的密度居中．因此，将词语相似度的值划分为如下区域：[0, 0.4)，[0.4, 0.6]，(0.6, 1.0]，依次记为区域ζ1，ζ2，ζ3．

假设节点主题属性为Wtag1,…,Wtagi,…,Wtagm，广告主题词为Wtopic1,…,Wtopicj,…,Wtopicn，单个标签词Wtagi与单个广告关键词Wtopicj的词语相似度为Sim(Wtagi,Wtopicj)，节点主题属性vtag与广告主题ADtopic间的相似度Sim(vtag,ADtopic)的具体计算过程如下：

首先计算某节点的各个标签与广告主题词的词语相似度，得到c个词语相似度Sim(Wtagi,Wtopicj)，再将这c个Sim(Wtagi,Wtopicj)根据定义好的3个区域划分为3部分：处于区域ζ1，ζ2，ζ3中的Sim(Wtagi,Wtopicj)个数分别为c1，c2，c3，和分别为S1，S2，S3．其中，c=c1+c2+c3．

1) 当ci=c(i=1或2)时，

2) 当c1+ci=c(i=2或3)时，

3) 当c2+c3=c时，

4) 当c1+c2+c3=c时，

为减弱低相似度词语对高相似度词语的影响，低词语相似度对应低权值，高词语相似度对应高权值．在实验过程中将权重设置如下：φ1=3/4，φ2=1/4，η1=2/3，η2=1/4，η3=1/12．其中，φ1+φ2=1，η1+η2+η3=1．

4.2 实验设计

在6个真实社交网络数据集和拓展独立级联传播模型上进行实验．为验证有效性，将AvePA算法与代表性的算法进行对比，通过影响效果和时间效率2个指标对各个算法进行评价．实验对比算法及其参数设置如表2所示．出于成本考虑，本文在蒙特卡罗模拟过程中，步进间隔设为50，依次获取成本从50到5 000时的各个算法的影响效果，在初始种子节点集合选择过程中不再循环k次，而是在过程中每选一个节点加入到初始种子节点集合中时，就在预算中减去该节点的成本，直到预算耗尽得到初始种子节点集合．

为便于阅读，根据广告预算为5 000时算法的影响效果好坏对算法排名．

表2 实验对比算法

影响最大化算法X和Y在广告预算为B时的差异定义为

(7)

式中，σ(X,B)为算法X在广告预算为B时的影响效果；σYX(Y,X,B)=σ(Y,B)-σ(X,B)．

影响最大化算法X和Y的平均差异定义为

(8)

在本文的实验分析中，算法间影响效果的差异是指广告预算从50增加到5 000时，2种算法之间影响效果大小的平均差异．其中，差异性比较以AvePA为基准，即在式(7)、(8)中算法X为AvePA．

4.3 评价指标

评价指标主要有：① 时间效率，即算法的时间复杂度，用有限的广告预算选择初始种子节点集合S的时间尽可能短；② 影响效果，用有限的广告预算选择初始种子节点集合，通过它们对网络中其他节点的影响，使得最终处于活跃态的节点对广告的兴趣度之和最大．

5 实验结果及分析

本文中影响效果的表征量为最终处于激活态的节点对广告的兴趣度之和．通过蒙特卡罗仿真模拟10 000次传播过程并取平均值，来获得一个较为精确的影响效果，其中三度影响力覆盖距离d分别取0～3以进行纵向比较，证明覆盖距离的有效性，再选取拥有较好覆盖距离的算法与其他算法进行比较．

投放在旅游、饮食和娱乐类上的广告在2种拓扑结构上的实验结果类似，因此本文仅选取投放在旅游类广告上的实验结果进行分析．

5.1 无向拓扑图下各算法效果分析

图1是AvePA算法在数据集1上覆盖距离d取0～3时的比较．其中，AvePA(d=1)是指算法的覆盖距离d设置为1，以此类推．由图可见，AvePA(d=1)算法的影响效果最好．当广告预算小于2 700时，AvePA(d=3)的影响效果稍好于AvePA(d=1)和AvePA(d=2)，AvePA(d=0)的影响效果最差；当广告预算大于2 700时，AvePA(d=2)和AvePA(d=3)的影响效果增长缓慢，说明广告预算越大，选取到的种子节点越多，d太大会覆盖掉部分影响力大的节点；当广告预算大于4 500时，AvePA(d=0)的影响效果大于其他三者的影响效果．由此判断，引入覆盖距离d是有效的．

图1 无向拓扑图下AvePA算法d取0～3时的比较

图2是在数据集1上，分别选取基于最优覆盖距离的其他算法与在数据集1上影响效果较好的AvePA(d=1)算法的对比．

图2 数据集1上各算法影响效果比较

总体上, AvePA(d=1)在几种算法中影响效果最好；从图中也可看出，Degree，DegreeDiscount，IRIE和PageRank这4种算法随着广告预算的增加，影响效果增长缓慢，因为它们在选择种子节点时未考虑节点主题属性在影响力传播过程中的重要作用．

表3是在数据集1上根据式(8)计算的AvePA(d=1)与其他算法的影响效果的差异，差异为负数表示该算法的影响效果比AvePA(d=1)差．从表中可看出, 与AvePA(d=1)差距最小的是SoPCA(d=1)，因为SoPCA算法在选择种子节点时也考虑了节点主题属性对影响概率的影响.AvePA(d=1)算法优于其他算法．

表3 数据集1上各算法的影响效果对比 %

图3是各算法在数据集1上的运行时间对比．AvePA(d=1)算法的运行时间略大于10 s，在可接受范围之内．

图3 各算法在数据集1上运行时间比较

5.2 有向拓扑图下各算法效果分析

图4是AvePA算法在数据集4上取不同覆盖距离时影响效果的比较，可看出AvePA(d=1)和AvePA(d=2)曲线交替上升．整体上，AvePA(d=1)算法的效果最好．

图4 有向拓扑图下AvePA算法d取0～3时的比较

图5是在数据集4上，分别选取基于最优覆盖距离的其他算法与在数据集4上影响效果较好的AvePA(d=1)算法的对比．从图中可看出，AvePA(d=1)的性能优于其他算法且较为稳定；Page-Rank，SoPCA(d=3)和IRIE这3种算法的影响效果整体上处于振荡状态；SoPCA(d=3)算法振荡幅度最大，这是因为SoPCA算法衡量节点影响力的指标是节点的概率和，忽略了节点成本大小．

图5 数据集4上各算法影响效果比较

表4是在数据集4上根据式(8)计算的AvePA(d=1)与其他算法的影响效果差异．

表4 数据集4上各算法的影响效果对比 %

图6给出了各算法在数据集4上的运行时间对比，可看出AvePA(d=1)算法的时间效率最高．

图6 各算法在数据集4上的运行时间比较

6 结论

1) 本文综合考虑节点的成本及出度大小、节点对其粉丝的影响力以及节点与所投放广告之间的相似度这3个因素，提出了平均概率指标．Ave-PA算法依据该指标选择种子节点，相比于将所有节点成本视为同一个值或者不考虑节点和广告主题相似度的种子节点选择算法考虑更加全面，且有针对性．

2) AvePA算法通过引入覆盖距离可有效应对影响范围重叠问题，提高算法性能.但覆盖距离太大会使得部分影响力大的节点被覆盖，导致算法性能下降，且最佳覆盖距离对于不同数据集的取值是不同的．

3) AvePA算法的性能整体上优于其他对比算法且相对稳定，随着广告预算的增加，性能优势更加明显.AvePA算法的时间效率也相对较好.

4) 综合考虑影响效果和时间效率，AvePA算法的性能最优．