社交網(wǎng)絡(luò)中基于成本的廣告投放策略

曹玖新 崔桂旗 馮雪艷 閔繪宇

(東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 211189)

依托社交網(wǎng)絡(luò)[1]產(chǎn)生了一種全新的營銷模式——“病毒營銷”，該營銷模式將找出的最有影響力的若干用戶作為信息的源頭，并利用口頭傳播的方式使得信息最終覆蓋大部分網(wǎng)絡(luò)，這就是影響最大化問題的原型．Domingos等[2]最早將影響最大化問題歸納為一個(gè)算法問題．Kempe等[3]首次把影響最大化問題形式化為一個(gè)離散最優(yōu)問題．

商家利用有限的成本在社交網(wǎng)絡(luò)中選擇種子用戶投放廣告，以達(dá)到盡可能好的廣告效應(yīng)，其本質(zhì)是一個(gè)影響最大化問題．文獻(xiàn)[4]指出，預(yù)算有限時(shí)，將所有節(jié)點(diǎn)的成本視為一個(gè)相同的值不能得到較好的影響效果．Leskovec等[5]最先將成本效益這一概念用于影響最大化問題的研究中，考慮到不同節(jié)點(diǎn)的成本不同，提出CEF(cost-effective forward selection)算法，文獻(xiàn)[6]證明了該算法可以達(dá)到的近似比約為最優(yōu)解的0.394．文獻(xiàn)[7]基于CELF提出了優(yōu)化算法CPP-SNS．Li等[8]提出了帶標(biāo)簽的影響最大化問題．文獻(xiàn)[9]研究表明，用戶自身的興趣愛好決定其對(duì)信息的偏好程度以及與相鄰用戶間的親密程度，這導(dǎo)致不同主題的信息在同一社交網(wǎng)絡(luò)中的傳播影響效果不同．Barbieri等[10]在傳統(tǒng)的影響力傳播模型基礎(chǔ)上提出了帶有主題意識(shí)的影響力傳播模型．文獻(xiàn)[11]提出了目標(biāo)影響最大化算法Targeted-MIA，以此來找到能夠最大化影響特定用戶的可靠用戶集合．Aslay等[12]提出了帶有主題意識(shí)的影響最大化查詢問題．Chen等[13]基于帶有主題意識(shí)的獨(dú)立級(jí)聯(lián)模型，使用預(yù)處理方法來解決帶有主題意識(shí)的影響最大化問題．Chen等[14]基于MIA模型提出了Best-effort算法．Li等[15]針對(duì)在線定向廣告提出了基于關(guān)鍵詞的定向影響最大化問題．

在廣告預(yù)算有限的情況下，已有的大部分算法并沒有同時(shí)考慮節(jié)點(diǎn)成本和節(jié)點(diǎn)主題屬性這2個(gè)因素，因此在新問題下原有的一些算法并不能給出較好的解決方案．

本文在選擇初始種子節(jié)點(diǎn)時(shí)，不僅考慮了節(jié)點(diǎn)成本，而且還考慮了節(jié)點(diǎn)主題屬性．在影響力傳播模型中，引入了覆蓋距離，并設(shè)計(jì)了一種AvePA算法來選擇初始種子節(jié)點(diǎn)，以達(dá)到在廣告預(yù)算有限的情況下廣告效應(yīng)盡可能好的目的．

1 基于成本的廣告投放問題

同時(shí)考慮節(jié)點(diǎn)成本和節(jié)點(diǎn)主題屬性的廣告投放問題，可形式化定義為給定一個(gè)帶主題屬性的社交網(wǎng)絡(luò)G(V,E,T)，其中V為節(jié)點(diǎn)集合，E為邊集合，T為節(jié)點(diǎn)主題屬性的集合，選擇一個(gè)初始種子節(jié)點(diǎn)集合S，在集合S的總成本C(S)不超過預(yù)算B時(shí)，使得最終的廣告效應(yīng)R(S)最好．這里，cost(v)表示節(jié)點(diǎn)v的成本，廣告效應(yīng)R(S)是指廣告投放結(jié)束時(shí)處于活躍態(tài)的節(jié)點(diǎn)Active(v)對(duì)廣告AD的興趣度之和．本文采用最終處于活躍態(tài)的節(jié)點(diǎn)主題屬性vtag與廣告主題ADtopic間的相似度Sim(vtag，ADtopic)來衡量興趣度．形式化描述如下：

(1)

(2)

(3)

2 模型建立

2.1 節(jié)點(diǎn)成本建模

文獻(xiàn)[4]指出當(dāng)預(yù)算有限時(shí)，不考慮節(jié)點(diǎn)的成本差異難以得到較好的影響效果，且與事實(shí)不符．因此，本文在選擇初始種子節(jié)點(diǎn)時(shí)認(rèn)為不同節(jié)點(diǎn)在被選擇時(shí)的代價(jià)不同．大部分社交網(wǎng)絡(luò)是以關(guān)注關(guān)系構(gòu)建的.參考已有研究和實(shí)際情況，以節(jié)點(diǎn)的出度(即節(jié)點(diǎn)關(guān)注者數(shù))表示節(jié)點(diǎn)的成本，定義如下：

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

(4)

2.2 節(jié)點(diǎn)間的關(guān)注度

令blog(u)表示u的微博數(shù)，通過節(jié)點(diǎn)v轉(zhuǎn)發(fā)節(jié)點(diǎn)u的微博數(shù)vtran(u)和評(píng)論節(jié)點(diǎn)u的微博數(shù)vcom(u)來衡量節(jié)點(diǎn)v對(duì)節(jié)點(diǎn)u的關(guān)注度Fvu，其計(jì)算公式為

(5)

為了使Fvu的取值范圍在0～1之間，對(duì)其分母進(jìn)行了歸一化處理．

2.3 節(jié)點(diǎn)間影響概率建模

節(jié)點(diǎn)u對(duì)節(jié)點(diǎn)v的影響概率puv受節(jié)點(diǎn)v對(duì)節(jié)點(diǎn)u的關(guān)注度Fvu以及節(jié)點(diǎn)v的屬性vtag與廣告主題ADtopic間的相似度Sim(vtag, ADtopic)共同影響．故puv計(jì)算公式為

puv=FvuSim(vtag, ADtopic)

(6)

3 基于平均概率的種子節(jié)點(diǎn)選擇算法

3.1 節(jié)點(diǎn)間影響概率建模

本文提出新的度量節(jié)點(diǎn)影響力的指標(biāo)，即平均概率AvePro(u)，其表示單位成本下節(jié)點(diǎn)u對(duì)其鄰居節(jié)點(diǎn)的影響概率．

式中，Nout(u)為節(jié)點(diǎn)u的出度鄰居節(jié)點(diǎn)集合．

考慮到2個(gè)節(jié)點(diǎn)的影響范圍可能存在重疊區(qū)域，本文引入覆蓋距離d使種子節(jié)點(diǎn)間保持一定的距離，以有效應(yīng)對(duì)影響重疊問題．

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

已有的利用獨(dú)立級(jí)聯(lián)模型的影響最大化問題研究中，通常假設(shè)節(jié)點(diǎn)間的影響概率是常量，因此在使用度中心性、介數(shù)中心性和核數(shù)這3個(gè)指標(biāo)選取影響力節(jié)點(diǎn)時(shí)可取得較好的效果[3,16-17]．但實(shí)際情況下，人與人之間的關(guān)系有強(qiáng)弱之分，并且會(huì)影響節(jié)點(diǎn)間的影響概率，因此僅基于度中心性或核數(shù)選取初始種子節(jié)點(diǎn)的算法不盡合理．文獻(xiàn)[18]對(duì)獨(dú)立級(jí)聯(lián)模型進(jìn)行改進(jìn)，提出了一種拓展獨(dú)立級(jí)聯(lián)模型，其與獨(dú)立級(jí)聯(lián)模型唯一的區(qū)別是節(jié)點(diǎn)間影響概率是不相同的．本文在拓展獨(dú)立級(jí)聯(lián)模型基礎(chǔ)上進(jìn)行實(shí)驗(yàn)．

AvePA算法選擇節(jié)點(diǎn)時(shí)，根據(jù)綜合考慮了節(jié)點(diǎn)平均成本、節(jié)點(diǎn)對(duì)其出度節(jié)點(diǎn)的影響及節(jié)點(diǎn)與所投放廣告的相似度的AvePro指標(biāo)來選擇種子節(jié)點(diǎn)，因此與其他算法相比，選擇的種子節(jié)點(diǎn)有一定差距．例如，一個(gè)節(jié)點(diǎn)集合中出度最大的節(jié)點(diǎn)與所要投放的廣告相似度趨近于0，那么在Degree算法中該節(jié)點(diǎn)會(huì)被選中，而在AvePA算法中該節(jié)點(diǎn)不會(huì)被選中．模型中節(jié)點(diǎn)有覆蓋和未覆蓋狀態(tài)，處于未覆蓋狀態(tài)的節(jié)點(diǎn)有可能會(huì)被選作種子節(jié)點(diǎn)，而處于覆蓋狀態(tài)的節(jié)點(diǎn)則不能被選為種子節(jié)點(diǎn)．起初所有節(jié)點(diǎn)均處于未覆蓋狀態(tài)，每輪選擇未被覆蓋的平均概率最大且度數(shù)大于平均度數(shù)的節(jié)點(diǎn).若該節(jié)點(diǎn)成本不超過預(yù)算，就將其加入到初始種子集合S中，并在廣告預(yù)算B中減去該節(jié)點(diǎn)成本；若節(jié)點(diǎn)u為種子節(jié)點(diǎn)，則將與u距離小于等于d的所有節(jié)點(diǎn)設(shè)為覆蓋狀態(tài)．

3.3 AvePA算法

算法1 AvePA算法

輸入：社交網(wǎng)絡(luò)G(V,E,T)，覆蓋距離d，廣告預(yù)算B．

輸出：種子節(jié)點(diǎn)集合S．

1S=?

2 for eachv∈Vdo

3 COv=false

4 計(jì)算平均概率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)為節(jié)點(diǎn)u的平均概率；COu表示節(jié)點(diǎn)u是否被覆蓋，若節(jié)點(diǎn)未被覆蓋為false，否則為true；dw,v為節(jié)點(diǎn)w和節(jié)點(diǎn)v的距離，即2個(gè)節(jié)點(diǎn)間的最短跳數(shù)．

對(duì)AvePA算法的分析如下：第1行初始化種子節(jié)點(diǎn)集合為空；第2～5行計(jì)算每個(gè)節(jié)點(diǎn)的平均概率，并設(shè)置每個(gè)節(jié)點(diǎn)的覆蓋狀態(tài)為未覆蓋狀態(tài)；第6～18行表示在預(yù)算內(nèi)選取種子節(jié)點(diǎn)，每輪選取1個(gè)種子節(jié)點(diǎn)；第7行選取當(dāng)前未被覆蓋的平均概率最大且度數(shù)大于平均度數(shù)的節(jié)點(diǎn)作為種子節(jié)點(diǎn)；第8～14行表示如果該節(jié)點(diǎn)成本不超過預(yù)算，就將其加入種子節(jié)點(diǎn)集合S，并在預(yù)算B中減去該節(jié)點(diǎn)成本，同時(shí)，根據(jù)覆蓋距離d，以節(jié)點(diǎn)w為中心，設(shè)置與其距離小于等于d的所有節(jié)點(diǎn)為覆蓋狀態(tài)；第15～17行表示若該節(jié)點(diǎn)成本超過預(yù)算，就直接將其設(shè)置為覆蓋狀態(tài)．此外，處于覆蓋狀態(tài)的節(jié)點(diǎn)在傳播過程中仍可以被其他節(jié)點(diǎn)所激活．

3.4 AvePA算法時(shí)間復(fù)雜度

假設(shè)社交網(wǎng)絡(luò)G(V,E)中節(jié)點(diǎn)數(shù)目為n，則第2～5行的時(shí)間復(fù)雜度為O(n)，第6～15行的時(shí)間復(fù)雜度為O(n)．因此，算法總時(shí)間復(fù)雜度為O(n)．

4 實(shí)驗(yàn)設(shè)計(jì)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)集

利用新浪微博提供的API接口抓取新浪微博的真實(shí)數(shù)據(jù)作為數(shù)據(jù)集，對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行預(yù)處理，得到2個(gè)較完整的由活躍用戶組成的拓?fù)洌粋€(gè)是有向網(wǎng)絡(luò)拓?fù)?，?8 243個(gè)節(jié)點(diǎn)和1 013 164條關(guān)注關(guān)系組成；另一個(gè)是無向網(wǎng)絡(luò)拓?fù)洌?4 514個(gè)節(jié)點(diǎn)及162 398條互粉關(guān)系組成．

4.1.1 節(jié)點(diǎn)主題屬性預(yù)處理

用戶標(biāo)簽可以表征節(jié)點(diǎn)主題屬性[19]，標(biāo)簽信息可以反映用戶的興趣愛好，在獲取節(jié)點(diǎn)主題屬性后，采用基于《知網(wǎng)》的詞匯語義相似度計(jì)算方法[20]計(jì)算節(jié)點(diǎn)主題屬性與廣告主題間的相似度．對(duì)于沒有標(biāo)簽信息的用戶而言，根據(jù)社交網(wǎng)絡(luò)同質(zhì)性特點(diǎn)[21]，其微博關(guān)注者和粉絲的標(biāo)簽?zāi)芤欢ǔ潭壬戏从吃撚脩舻奶卣鳎畬?duì)于關(guān)注者和粉絲均很少的用戶而言，除了利用關(guān)注者標(biāo)簽、粉絲標(biāo)簽外，還要利用用戶發(fā)布的微博信息進(jìn)行人工標(biāo)注．

4.1.2 社交網(wǎng)絡(luò)數(shù)據(jù)集獲取

對(duì)采集到的用戶的所有標(biāo)簽出現(xiàn)頻次進(jìn)行統(tǒng)計(jì)，將頻次大于1 000次的標(biāo)簽可分為吃喝玩樂幾個(gè)方面，所以選擇吃喝玩樂類的廣告進(jìn)行投放比較有代表性，故最終確定選取旅游、飲食、娛樂3類廣告進(jìn)行投放．因此，結(jié)合2種拓?fù)潢P(guān)系和3類廣告共獲得6個(gè)不同的社交網(wǎng)絡(luò)數(shù)據(jù)集，如表1所示．

表1 社交網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)湫畔?/p>

4.1.3 節(jié)點(diǎn)主題屬性與廣告主題間的相似度

計(jì)算平均概率需要先求出各節(jié)點(diǎn)主題屬性與廣告主題間的相似度．本文對(duì)所有用戶的所有標(biāo)簽詞進(jìn)行統(tǒng)計(jì)，得到73 523個(gè)不重復(fù)的標(biāo)簽詞，并與旅游、飲食和娛樂3個(gè)詞進(jìn)行詞語相似度計(jì)算并統(tǒng)計(jì)．根據(jù)實(shí)驗(yàn)結(jié)果，詞語相似度的值處于 0.6～1.0 范圍的密度較小，處于0～0.4 范圍的密度較高，處于 0.4～0.6 范圍的密度居中．因此，將詞語相似度的值劃分為如下區(qū)域：[0, 0.4)，[0.4, 0.6]，(0.6, 1.0]，依次記為區(qū)域ζ1，ζ2，ζ3．

假設(shè)節(jié)點(diǎn)主題屬性為Wtag1,…,Wtagi,…,Wtagm，廣告主題詞為Wtopic1,…,Wtopicj,…,Wtopicn，單個(gè)標(biāo)簽詞Wtagi與單個(gè)廣告關(guān)鍵詞Wtopicj的詞語相似度為Sim(Wtagi,Wtopicj)，節(jié)點(diǎn)主題屬性vtag與廣告主題ADtopic間的相似度Sim(vtag,ADtopic)的具體計(jì)算過程如下：

首先計(jì)算某節(jié)點(diǎn)的各個(gè)標(biāo)簽與廣告主題詞的詞語相似度，得到c個(gè)詞語相似度Sim(Wtagi,Wtopicj)，再將這c個(gè)Sim(Wtagi,Wtopicj)根據(jù)定義好的3個(gè)區(qū)域劃分為3部分：處于區(qū)域ζ1，ζ2，ζ3中的Sim(Wtagi,Wtopicj)個(gè)數(shù)分別為c1，c2，c3，和分別為S1，S2，S3．其中，c=c1+c2+c3．

1) 當(dāng)ci=c(i=1或2)時(shí)，

2) 當(dāng)c1+ci=c(i=2或3)時(shí)，

3) 當(dāng)c2+c3=c時(shí)，

4) 當(dāng)c1+c2+c3=c時(shí)，

為減弱低相似度詞語對(duì)高相似度詞語的影響，低詞語相似度對(duì)應(yīng)低權(quán)值，高詞語相似度對(duì)應(yīng)高權(quán)值．在實(shí)驗(yàn)過程中將權(quán)重設(shè)置如下：φ1=3/4，φ2=1/4，η1=2/3，η2=1/4，η3=1/12．其中，φ1+φ2=1，η1+η2+η3=1．

4.2 實(shí)驗(yàn)設(shè)計(jì)

在6個(gè)真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)集和拓展獨(dú)立級(jí)聯(lián)傳播模型上進(jìn)行實(shí)驗(yàn)．為驗(yàn)證有效性，將AvePA算法與代表性的算法進(jìn)行對(duì)比，通過影響效果和時(shí)間效率2個(gè)指標(biāo)對(duì)各個(gè)算法進(jìn)行評(píng)價(jià)．實(shí)驗(yàn)對(duì)比算法及其參數(shù)設(shè)置如表2所示．出于成本考慮，本文在蒙特卡羅模擬過程中，步進(jìn)間隔設(shè)為50，依次獲取成本從50到5 000時(shí)的各個(gè)算法的影響效果，在初始種子節(jié)點(diǎn)集合選擇過程中不再循環(huán)k次，而是在過程中每選一個(gè)節(jié)點(diǎn)加入到初始種子節(jié)點(diǎn)集合中時(shí)，就在預(yù)算中減去該節(jié)點(diǎn)的成本，直到預(yù)算耗盡得到初始種子節(jié)點(diǎn)集合．

為便于閱讀，根據(jù)廣告預(yù)算為5 000時(shí)算法的影響效果好壞對(duì)算法排名．

表2 實(shí)驗(yàn)對(duì)比算法

影響最大化算法X和Y在廣告預(yù)算為B時(shí)的差異定義為

(7)

式中，σ(X,B)為算法X在廣告預(yù)算為B時(shí)的影響效果；σYX(Y,X,B)=σ(Y,B)-σ(X,B)．

影響最大化算法X和Y的平均差異定義為

(8)

在本文的實(shí)驗(yàn)分析中，算法間影響效果的差異是指廣告預(yù)算從50增加到5 000時(shí)，2種算法之間影響效果大小的平均差異．其中，差異性比較以AvePA為基準(zhǔn)，即在式(7)、(8)中算法X為AvePA．

4.3 評(píng)價(jià)指標(biāo)

評(píng)價(jià)指標(biāo)主要有：① 時(shí)間效率，即算法的時(shí)間復(fù)雜度，用有限的廣告預(yù)算選擇初始種子節(jié)點(diǎn)集合S的時(shí)間盡可能短；② 影響效果，用有限的廣告預(yù)算選擇初始種子節(jié)點(diǎn)集合，通過它們對(duì)網(wǎng)絡(luò)中其他節(jié)點(diǎn)的影響，使得最終處于活躍態(tài)的節(jié)點(diǎn)對(duì)廣告的興趣度之和最大．

5 實(shí)驗(yàn)結(jié)果及分析

本文中影響效果的表征量為最終處于激活態(tài)的節(jié)點(diǎn)對(duì)廣告的興趣度之和．通過蒙特卡羅仿真模擬10 000次傳播過程并取平均值，來獲得一個(gè)較為精確的影響效果，其中三度影響力覆蓋距離d分別取0～3以進(jìn)行縱向比較，證明覆蓋距離的有效性，再選取擁有較好覆蓋距離的算法與其他算法進(jìn)行比較．

投放在旅游、飲食和娛樂類上的廣告在2種拓?fù)浣Y(jié)構(gòu)上的實(shí)驗(yàn)結(jié)果類似，因此本文僅選取投放在旅游類廣告上的實(shí)驗(yàn)結(jié)果進(jìn)行分析．

5.1 無向拓?fù)鋱D下各算法效果分析

圖1是AvePA算法在數(shù)據(jù)集1上覆蓋距離d取0～3時(shí)的比較．其中，AvePA(d=1)是指算法的覆蓋距離d設(shè)置為1，以此類推．由圖可見，AvePA(d=1)算法的影響效果最好．當(dāng)廣告預(yù)算小于2 700時(shí)，AvePA(d=3)的影響效果稍好于AvePA(d=1)和AvePA(d=2)，AvePA(d=0)的影響效果最差；當(dāng)廣告預(yù)算大于2 700時(shí)，AvePA(d=2)和AvePA(d=3)的影響效果增長緩慢，說明廣告預(yù)算越大，選取到的種子節(jié)點(diǎn)越多，d太大會(huì)覆蓋掉部分影響力大的節(jié)點(diǎn)；當(dāng)廣告預(yù)算大于4 500時(shí)，AvePA(d=0)的影響效果大于其他三者的影響效果．由此判斷，引入覆蓋距離d是有效的．

圖1 無向拓?fù)鋱D下AvePA算法d取0～3時(shí)的比較

圖2是在數(shù)據(jù)集1上，分別選取基于最優(yōu)覆蓋距離的其他算法與在數(shù)據(jù)集1上影響效果較好的AvePA(d=1)算法的對(duì)比．

圖2 數(shù)據(jù)集1上各算法影響效果比較

總體上, AvePA(d=1)在幾種算法中影響效果最好；從圖中也可看出，Degree，DegreeDiscount，IRIE和PageRank這4種算法隨著廣告預(yù)算的增加，影響效果增長緩慢，因?yàn)樗鼈冊谶x擇種子節(jié)點(diǎn)時(shí)未考慮節(jié)點(diǎn)主題屬性在影響力傳播過程中的重要作用．

表3是在數(shù)據(jù)集1上根據(jù)式(8)計(jì)算的AvePA(d=1)與其他算法的影響效果的差異，差異為負(fù)數(shù)表示該算法的影響效果比AvePA(d=1)差．從表中可看出, 與AvePA(d=1)差距最小的是SoPCA(d=1)，因?yàn)镾oPCA算法在選擇種子節(jié)點(diǎn)時(shí)也考慮了節(jié)點(diǎn)主題屬性對(duì)影響概率的影響.AvePA(d=1)算法優(yōu)于其他算法．

表3 數(shù)據(jù)集1上各算法的影響效果對(duì)比 %

圖3是各算法在數(shù)據(jù)集1上的運(yùn)行時(shí)間對(duì)比．AvePA(d=1)算法的運(yùn)行時(shí)間略大于10 s，在可接受范圍之內(nèi)．

圖3 各算法在數(shù)據(jù)集1上運(yùn)行時(shí)間比較

5.2 有向拓?fù)鋱D下各算法效果分析

圖4是AvePA算法在數(shù)據(jù)集4上取不同覆蓋距離時(shí)影響效果的比較，可看出AvePA(d=1)和AvePA(d=2)曲線交替上升．整體上，AvePA(d=1)算法的效果最好．

圖4 有向拓?fù)鋱D下AvePA算法d取0～3時(shí)的比較

圖5是在數(shù)據(jù)集4上，分別選取基于最優(yōu)覆蓋距離的其他算法與在數(shù)據(jù)集4上影響效果較好的AvePA(d=1)算法的對(duì)比．從圖中可看出，AvePA(d=1)的性能優(yōu)于其他算法且較為穩(wěn)定；Page-Rank，SoPCA(d=3)和IRIE這3種算法的影響效果整體上處于振蕩狀態(tài)；SoPCA(d=3)算法振蕩幅度最大，這是因?yàn)镾oPCA算法衡量節(jié)點(diǎn)影響力的指標(biāo)是節(jié)點(diǎn)的概率和，忽略了節(jié)點(diǎn)成本大?。?/p>

圖5 數(shù)據(jù)集4上各算法影響效果比較

表4是在數(shù)據(jù)集4上根據(jù)式(8)計(jì)算的AvePA(d=1)與其他算法的影響效果差異．

表4 數(shù)據(jù)集4上各算法的影響效果對(duì)比 %

圖6給出了各算法在數(shù)據(jù)集4上的運(yùn)行時(shí)間對(duì)比，可看出AvePA(d=1)算法的時(shí)間效率最高．

圖6 各算法在數(shù)據(jù)集4上的運(yùn)行時(shí)間比較

6 結(jié)論

1) 本文綜合考慮節(jié)點(diǎn)的成本及出度大小、節(jié)點(diǎn)對(duì)其粉絲的影響力以及節(jié)點(diǎn)與所投放廣告之間的相似度這3個(gè)因素，提出了平均概率指標(biāo)．Ave-PA算法依據(jù)該指標(biāo)選擇種子節(jié)點(diǎn)，相比于將所有節(jié)點(diǎn)成本視為同一個(gè)值或者不考慮節(jié)點(diǎn)和廣告主題相似度的種子節(jié)點(diǎn)選擇算法考慮更加全面，且有針對(duì)性．

2) AvePA算法通過引入覆蓋距離可有效應(yīng)對(duì)影響范圍重疊問題，提高算法性能.但覆蓋距離太大會(huì)使得部分影響力大的節(jié)點(diǎn)被覆蓋，導(dǎo)致算法性能下降，且最佳覆蓋距離對(duì)于不同數(shù)據(jù)集的取值是不同的．

3) AvePA算法的性能整體上優(yōu)于其他對(duì)比算法且相對(duì)穩(wěn)定，隨著廣告預(yù)算的增加，性能優(yōu)勢更加明顯.AvePA算法的時(shí)間效率也相對(duì)較好.

4) 綜合考慮影響效果和時(shí)間效率，AvePA算法的性能最優(yōu)．