考慮用戶意愿的符號(hào)網(wǎng)絡(luò)凈積極影響力最大化問(wèn)題

宗金醒, 帥天平

(北京郵電大學(xué) 理學(xué)院,北京100876)

隨著電子設(shè)備的快速擴(kuò)張和社交媒體的增長(zhǎng),人們通過(guò)社交網(wǎng)絡(luò)聯(lián)系得更加緊密, 社交網(wǎng)絡(luò)的發(fā)展對(duì)人與人之間的信息交流和傳遞有著至關(guān)重要的影響,人與人之間的關(guān)系可以是合作者、朋友、敵人等.近年來(lái),最大化社交網(wǎng)絡(luò)影響力的問(wèn)題引起了研究人員的注意,因?yàn)樵S多主要的社交網(wǎng)絡(luò),如Twitter,微信和谷歌,已經(jīng)變得普遍,這些在線社交網(wǎng)絡(luò)提供的大規(guī)模和多樣化的數(shù)據(jù)促進(jìn)了社會(huì)計(jì)算的研究,其中影響力最大化是一個(gè)根本性和關(guān)鍵性的問(wèn)題[1-9],這個(gè)問(wèn)題的目的是選擇k個(gè)潛在用戶,影響并說(shuō)服他們采用產(chǎn)品,即信息的傳播利用的是口碑效應(yīng).并在網(wǎng)絡(luò)中成功地創(chuàng)造更多的采用.潛在的社會(huì)網(wǎng)絡(luò)通常被表示為有向圖,并且描述傳播過(guò)程的擴(kuò)散模型已經(jīng)被廣泛研究.

由于無(wú)符號(hào)網(wǎng)絡(luò)默認(rèn)的是社交網(wǎng)絡(luò)用戶之間的關(guān)系都是信任友好的關(guān)系,但在實(shí)際情形中,人與人之間的關(guān)系還可能會(huì)有敵對(duì)的關(guān)系,因此,越來(lái)越多的研究人員開始關(guān)注符號(hào)網(wǎng)絡(luò)中影響力最大化的研究.在符號(hào)網(wǎng)絡(luò)中,已經(jīng)有一些研究[10-13]提出了積極影響力最大化(PIM)的問(wèn)題,并提出了幾種解決方案.PIM問(wèn)題的目標(biāo)是在符號(hào)網(wǎng)絡(luò)中選擇具有最大積極影響的種子節(jié)點(diǎn)集.然而僅僅最大化積極影響有時(shí)并不是最好的,因?yàn)樵诂F(xiàn)實(shí)情境中,負(fù)面影響的作用不容小覷,例如我們?cè)谔詫氋?gòu)物時(shí),若看到某個(gè)商品的好評(píng)很多但同時(shí)差評(píng)量也很多時(shí),我們可能不會(huì)購(gòu)買這個(gè)商品,這對(duì)商家來(lái)說(shuō)是不利的.再比如一個(gè)商家想要推廣自己的某個(gè)產(chǎn)品,如果選擇的種子用戶積極影響力很大,但負(fù)面影響力也很大,雖然會(huì)有很多用戶認(rèn)可該產(chǎn)品,但也會(huì)造成很多用戶不喜歡這個(gè)產(chǎn)品的情況,這種結(jié)果肯定不是商家想要的,因此如何選擇種子節(jié)點(diǎn),使得它們具有盡可能多的積極影響和盡可能少的負(fù)面影響是一個(gè)有實(shí)際意義的優(yōu)化問(wèn)題.

為了解決上述問(wèn)題,Li Dong等人[14]針對(duì)符號(hào)網(wǎng)絡(luò)首次提出了凈積極影響的概念,并提出了凈積極影響力最大化問(wèn)題.凈積極影響既考慮了積極影響,也考慮了消極影響,凈積極影響最大化是指在最小化消極影響的同時(shí)最大化積極影響.但是他們?cè)谘芯吭搯?wèn)題時(shí),并沒有將用戶自身的傳播意愿考慮進(jìn)來(lái),由于用戶在傳播信息時(shí),會(huì)考慮到自身的某些原因比如性格等,導(dǎo)致他們并不愿意去影響自己的鄰居.本文在研究最大化種子節(jié)點(diǎn)凈積極影響力的同時(shí),將用戶的傳播意愿考慮在內(nèi),以更貼近實(shí)際情景.

本文創(chuàng)新點(diǎn):1)提出了在符號(hào)網(wǎng)絡(luò)中,考慮用戶傳播意愿的凈積極影響力最大化問(wèn)題,并且證明了在考慮用戶傳播意愿的極性相關(guān)的獨(dú)立級(jí)聯(lián)模型下,目標(biāo)函數(shù)既不是單調(diào)的也不是次模的;2)基于Gong等人[15]提出的概率驅(qū)動(dòng)的結(jié)構(gòu)感知(PDSA)算法,提出了A-PDSA算法來(lái)解決該問(wèn)題;3)給出了在三個(gè)符號(hào)網(wǎng)絡(luò)常用的數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果.

1 相關(guān)工作

Kempe等[1]將IM問(wèn)題建模為離散優(yōu)化問(wèn)題,并引入了兩種傳播模型:IC和LT.在這兩種情況下,IM問(wèn)題都是NP-hard的,并提出了貪婪算法.但是,計(jì)算影響函數(shù)本身就是NP-hard,所以尋找邊際增益最大的節(jié)點(diǎn)也是NP-hard.由于蒙特卡羅模擬用于計(jì)算影響函數(shù),他們的最終算法被稱為蒙特卡羅貪婪,然而基于模擬的方法非常復(fù)雜,為了緩解這一問(wèn)題,Lescovec等[16]注意到,節(jié)點(diǎn)在當(dāng)前迭代中的邊際收益不會(huì)超過(guò)其在前幾次迭代中的邊際收益.通過(guò)這種技術(shù),大大減少了對(duì)傳播估計(jì)過(guò)程的調(diào)用次數(shù),這種方法稱為CELF算法.Tang等[3]提出了具有跳數(shù)限制的貪婪算法,但該算法的效率仍然很低.由于貪心算法的低效性,Chen等提出了兩種啟發(fā)式算法:DegreeDiscount[4]和PMIA[5].在每一步中,DegreeDiscount將度最大的節(jié)點(diǎn)添加到種子集,然后對(duì)所選節(jié)點(diǎn)的鄰接度進(jìn)行相應(yīng)的折扣.PMIA通過(guò)使用局部影響樹來(lái)計(jì)算影響傳播,該樹基于兩個(gè)節(jié)點(diǎn)之間最可能的影響路徑,但該算法仍然無(wú)法擴(kuò)展到大型社交網(wǎng)絡(luò)圖.

無(wú)符號(hào)社交網(wǎng)絡(luò)中影響力最大化問(wèn)題的研究取得了豐富的成果,這些現(xiàn)有的成果也啟發(fā)了學(xué)者們對(duì)符號(hào)網(wǎng)絡(luò)中對(duì)該問(wèn)題的研究.Li等[17]提出了符號(hào)網(wǎng)絡(luò)中與極性相關(guān)的影響力最大化(PRIM)問(wèn)題,包含了積極影響和消極影響,將經(jīng)典的獨(dú)立級(jí)聯(lián)(Independent Cascade)模型推廣到符號(hào)網(wǎng)絡(luò),提出了極性相關(guān)的獨(dú)立級(jí)聯(lián)模型(Polarity-related Independent Cascade),并證明了在該模型下PRIM問(wèn)題的影響函數(shù)是單調(diào)的和次模的,然后使用貪婪算法來(lái)求解該問(wèn)題,該算法得到的近似解可以逼近最優(yōu)解的1-1/e.Ju等[18]在計(jì)算符號(hào)網(wǎng)絡(luò)中節(jié)點(diǎn)間的正激活概率時(shí)采用了獨(dú)立路徑的方法,并且提出了用來(lái)估計(jì)種子節(jié)點(diǎn)集積極影響傳播的影響函數(shù),該方法避免了采用蒙特卡洛模擬來(lái)估計(jì)影響傳播.Li等[14]首次提出了符號(hào)網(wǎng)絡(luò)中凈積極影響的概念,并利用改進(jìn)的R-Greedy算法來(lái)解決該問(wèn)題,該方法雖然準(zhǔn)確度較高但時(shí)間復(fù)雜度也很高.謝等[19]在影響傳播過(guò)程中將用戶傳播意愿考慮進(jìn)來(lái),在IC-P模型的基礎(chǔ)上提出了AIC-P傳播模型,并采用基于用戶傳播意愿的節(jié)點(diǎn)搜索策略的差分進(jìn)化算法(PWDE).

2 模型和問(wèn)題描述

給定一個(gè)符號(hào)網(wǎng)絡(luò)G=(V,E,P,S),其中V為用戶的節(jié)點(diǎn)集,E為用戶之間關(guān)系的有向邊的集合,每條邊e=(u,v)有一個(gè)對(duì)應(yīng)的激活概率pu,v,為節(jié)點(diǎn)u成功激活節(jié)點(diǎn)v的概率.su,v為節(jié)點(diǎn)u和節(jié)點(diǎn)v之間的極性關(guān)系,即su,v=+1表示節(jié)點(diǎn)u與節(jié)點(diǎn)v之間的關(guān)系是正的,su,v=-1表示節(jié)點(diǎn)u與節(jié)點(diǎn)v之間的關(guān)系是負(fù)的.如圖1是一個(gè)代表符號(hào)網(wǎng)絡(luò)的有向圖,每條邊上的權(quán)重即為pu,v·su,v的結(jié)果.

圖1 符號(hào)網(wǎng)絡(luò)

2.1 影響傳播模型

Li等[11]針對(duì)符號(hào)網(wǎng)絡(luò)提出了極性相關(guān)的獨(dú)立級(jí)聯(lián)(IC-P)模型,在IC-P模型中,節(jié)點(diǎn)的活躍狀態(tài)有兩種:積極(正)狀態(tài)和消極(負(fù))狀態(tài).因此,IC-P模型中每個(gè)節(jié)點(diǎn)的狀態(tài)分為3種:積極(正)狀態(tài)、消極(負(fù))狀態(tài)或不活躍狀態(tài).對(duì)于節(jié)點(diǎn)u來(lái)說(shuō),積極狀態(tài)意味著在社交網(wǎng)絡(luò)中,相應(yīng)的用戶采用并進(jìn)而支持或信任傳播信息.u的消極狀態(tài)意味著相應(yīng)的用戶采納了信息,但隨后又反對(duì)或不信任該信息.u的不活躍狀態(tài)意味著相應(yīng)的用戶不采用該信息.

該模型的傳播過(guò)程如下:在IC-P模型中,擴(kuò)散過(guò)程從初始的一組活躍節(jié)點(diǎn)S開始,S中節(jié)點(diǎn)的狀態(tài)有積極狀態(tài)和消極狀態(tài),不在S中的節(jié)點(diǎn)都是不活躍的.該過(guò)程根據(jù)以下隨機(jī)規(guī)則以離散的步驟展開:對(duì)于在(t-1)時(shí)刻被激活的節(jié)點(diǎn)u,它將在t時(shí)刻變成積極或消極狀態(tài).然后這個(gè)節(jié)點(diǎn)u在t時(shí)刻有且只有一次機(jī)會(huì)去嘗試激活每個(gè)當(dāng)前不活躍的鄰居節(jié)點(diǎn).一旦其鄰居節(jié)點(diǎn)v被節(jié)點(diǎn)u成功激活,節(jié)點(diǎn)v的其他活躍的鄰居將不能再去激活它.對(duì)于新激活的節(jié)點(diǎn)v,它的狀態(tài)s(v)與節(jié)點(diǎn)u的狀態(tài)s(u)以及su,v有關(guān),即s(v)=s(u)·su,v.一旦節(jié)點(diǎn)變?yōu)榉e極(正)或消極(負(fù))狀態(tài),它的狀態(tài)將不再發(fā)生改變.該過(guò)程一直進(jìn)行下去,直到?jīng)]有新的節(jié)點(diǎn)被激活.

由于在實(shí)際情境中,用戶的傳播意愿在信息擴(kuò)散過(guò)程中也扮演了很重要的角色,而IC-P模型并沒有考慮用戶在影響傳播過(guò)程中的個(gè)人意愿,對(duì)此謝等[19]提出了考慮用戶傳播意愿的AIC-P模型,將用戶的傳播意愿用w表示,且w∈(0,1).此模型中節(jié)點(diǎn)狀態(tài)的確定與IC-P模型相同,兩個(gè)模型的差異如下:AIC-P模型中每個(gè)節(jié)點(diǎn)的狀態(tài)分為:活躍并表現(xiàn)為積極(正)狀態(tài),活躍并表現(xiàn)為消極(負(fù))狀態(tài),激活但不活躍狀態(tài)或未被激活狀態(tài).擴(kuò)散過(guò)程從初始種子集合S開始,S包含的是活躍并表現(xiàn)為積極狀態(tài)的節(jié)點(diǎn),不在S中的節(jié)點(diǎn)表示未被激活.其次,在激活過(guò)程中,如果節(jié)點(diǎn)u在(t-1)時(shí)刻被激活,它將在t時(shí)刻根據(jù)自身的傳播意愿值w(u),判斷自身是否會(huì)處于活躍狀態(tài),如果激活的節(jié)點(diǎn)u處于活躍狀態(tài),那么會(huì)在(t+1)時(shí)刻變?yōu)榉e極或消極狀態(tài).而后在(t+1)時(shí)刻才有一次機(jī)會(huì)去激活當(dāng)前未被激活的鄰居v.其中激活且處于活躍狀態(tài)的節(jié)點(diǎn)u改變其對(duì)應(yīng)狀態(tài)的過(guò)程與IC-P模型一樣.

2.2 符號(hào)網(wǎng)絡(luò)中考慮用戶傳播意愿的凈積極影響力最大化

令f±(·)表示積極影響函數(shù),給定一個(gè)節(jié)點(diǎn)集S,f+(S)即為在AIC-P模型下,被S激活為積極狀態(tài)的期望節(jié)點(diǎn)數(shù),被認(rèn)為是S的積極影響.同樣,f-(·)表示消極影響函數(shù),給定一個(gè)節(jié)點(diǎn)集S,f-(S)即為被S激活為消極狀態(tài)的期望節(jié)點(diǎn)數(shù),被認(rèn)為是S的消極影響.我們定義f±(·)為凈積極影響函數(shù),對(duì)于節(jié)點(diǎn)集S,凈積極影響函數(shù)的計(jì)算方法如下:

f±(S)=f+(S)-f-(S)

符號(hào)網(wǎng)絡(luò)中考慮用戶意愿的凈積極影響力最大化問(wèn)題的定義如下:給定一個(gè)符號(hào)的網(wǎng)絡(luò)G=(V,E,P,S,w),一個(gè)信息擴(kuò)散模型(AIC-P)以及一個(gè)非負(fù)整數(shù)k,目標(biāo)是尋找一個(gè)包含k個(gè)種子節(jié)點(diǎn)的集合S,使得凈積極影響函數(shù)f±(S)最大化.這個(gè)問(wèn)題可以形式化為:

S=arg maxS?V,|S|=kf±(S)

其中:集合S包含的種子節(jié)點(diǎn)都設(shè)置為活躍狀態(tài)并表現(xiàn)為積極狀態(tài),有些節(jié)點(diǎn)雖然被激活,但未處于活躍狀態(tài),視為影響力不會(huì)繼續(xù)傳播下去.f±(S)表示的是在AIC-P模型下,由種子節(jié)點(diǎn)集S激活并處于活躍狀態(tài)的凈積極節(jié)點(diǎn)數(shù)量的期望值.

2.3 影響函數(shù)的性質(zhì)

定理:在AIC-P模型下,凈積極影響函數(shù)f±(S)既不是單調(diào)的也不是次模的.

證明:由于在IC-P模型下,凈積極影響函數(shù)f±(S)既不是單調(diào)的也不是次模的[14],而IC-P模型是AIC-P模型當(dāng)用戶傳播意愿為1時(shí)的特殊情況,因此,在AIC-P模型下,凈積極影響函數(shù)f±(S)既不是單調(diào)的也不是次模的.

2.4 影響函數(shù)的計(jì)算

由于在AIC-P模型中,激活節(jié)點(diǎn)前要先看節(jié)點(diǎn)的意愿,如果節(jié)點(diǎn)愿意才執(zhí)行激活. 因此在AIC-P模型中,對(duì)于活躍邊圖g,其發(fā)生的概率為Pr[g]=Πpe·wuΠ(1-pe·wu),其中:pe表示邊e上的激活概率,wu表示節(jié)點(diǎn)u的傳播意愿值.

f±(S,g)=f+(S,g)-f-(S,g)=

3 求解算法

Gong等人[15]針對(duì)無(wú)符號(hào)網(wǎng)絡(luò)中的影響力最大化問(wèn)題,提出了概率驅(qū)動(dòng)結(jié)構(gòu)感知(PDSA)算法.該算法的主要思想是,生成一定數(shù)量的活躍邊圖,找出每個(gè)節(jié)點(diǎn)在這些活躍邊圖中可以激活的節(jié)點(diǎn)數(shù)量的總和,再求出平均值即作為每個(gè)節(jié)點(diǎn)的擴(kuò)散得分,最后根據(jù)每個(gè)結(jié)點(diǎn)的擴(kuò)散得分來(lái)對(duì)節(jié)點(diǎn)進(jìn)行排序.由于該算法可以基于網(wǎng)絡(luò)結(jié)構(gòu)的變化自適應(yīng)地尋找有影響力的節(jié)點(diǎn),在效率和準(zhǔn)確性方面取得了良好的性能.因此,本文將該算法的思想推廣到符號(hào)網(wǎng)絡(luò)中,用來(lái)求解符號(hào)網(wǎng)絡(luò)中考慮用戶傳播意愿的凈積極影響力最大化問(wèn)題.

定義3(可達(dá)集):設(shè)g為圖G的一個(gè)活躍邊圖,圖g中的節(jié)點(diǎn)v沿著圖中的路徑可以到達(dá)的所有節(jié)點(diǎn)的集合稱為v的可達(dá)集.在v的可達(dá)集中表現(xiàn)為積極狀態(tài)的節(jié)點(diǎn)的集合稱為v的積極可達(dá)集,表現(xiàn)為消極狀態(tài)的節(jié)點(diǎn)的集合稱為v的消極可達(dá)集.

定義4(凈擴(kuò)散得分):給定一個(gè)圖G=(V,E),則節(jié)點(diǎn)v∈V的凈擴(kuò)散得分定義為:NSS(v)=f±(v).其中f±(v)表示在圖G中被節(jié)點(diǎn)v激活且處于活躍狀態(tài)的凈積極節(jié)點(diǎn)的預(yù)期數(shù)量.

對(duì)節(jié)點(diǎn)v,它的凈擴(kuò)散得分的精確計(jì)算方法如下:

其中:X為圖G的所有活躍邊圖的集合,NNSg(v)為節(jié)點(diǎn)v在圖g中的凈積極擴(kuò)散得分.然而由于活躍邊圖的數(shù)量很多,所以給定一個(gè)節(jié)點(diǎn)v后,利用上述方法很難精確計(jì)算NNS(v),因此可利用蒙特卡洛模擬的方法來(lái)估計(jì)NNS(v).

由于添加了用戶的意愿值,因此,可將提出的算法命名為A-PDSA算法.我們將節(jié)點(diǎn)的積極可達(dá)集記為PR,消極可達(dá)集記為NR,算法具體描述如下:

A-PDSA算法輸入:符號(hào)網(wǎng)絡(luò)G=(V,E,P,S,w),種子集大小k,蒙特卡洛模擬次數(shù)Mc輸出:種子集S1.生成節(jié)點(diǎn)的傳播意愿值,并計(jì)算每條邊添加意愿后的激活概率,得到Ep2.對(duì)圖G中的每個(gè)節(jié)點(diǎn)v,NSS[v]=03.for i=1,...,Mc, do4. g=copy(G)5. while e∈E do6. if c>Ep(e) do7. 將邊e從圖g中刪除8. end if9. end while10. while v∈V do11. 在g中計(jì)算節(jié)點(diǎn)v的凈積極可達(dá)集NPRS[v]=PR[v]-NR[v]12. NSS[v]=NSS[v]+NPRS[v]13. for v∈V do14. NSS[v]=NSS[v]/Mc15. 將節(jié)點(diǎn)按凈擴(kuò)散得分降序排列得到Rank16. 返回Rank[:k]

在該算法中,首先生成節(jié)點(diǎn)的傳播意愿值,Ep為邊的參數(shù)空間,即若邊e=(u,v),則Ep(e)=wu·pu,v.第4～9行是生成圖G的活躍邊圖g的過(guò)程,其中c為在[0,1]之間隨機(jī)生成的一個(gè)均勻分布的隨機(jī)數(shù).第10～14行計(jì)算每個(gè)節(jié)點(diǎn)的凈擴(kuò)散得分,在g中通過(guò)廣度優(yōu)先搜索算法(BFS)來(lái)獲得每個(gè)節(jié)點(diǎn)的積極可達(dá)集PR和消極可達(dá)集NR,從而得到該節(jié)點(diǎn)的凈積極可達(dá)集NPRS.然后將每個(gè)節(jié)點(diǎn)在生成的所有活躍邊圖中得到的NPRS作和并求出平均值作為每個(gè)節(jié)點(diǎn)的凈擴(kuò)散得分(NSS),最后按照該得分進(jìn)行排序得到排名列表Rank,從而得到種子集S.

4 實(shí)驗(yàn)與結(jié)果分析

4.1 用戶傳播意愿的生成

對(duì)于符號(hào)網(wǎng)絡(luò)中用戶的傳播意愿,謝等人[19]通過(guò)對(duì)微博數(shù)據(jù)集進(jìn)行分析,模擬生成了一組用戶的傳播意愿值,并對(duì)于每個(gè)節(jié)點(diǎn)分析了其分享程度和度值的關(guān)系,并采用了生成用戶意愿的方法:將節(jié)點(diǎn)度值升序排列,若數(shù)據(jù)集節(jié)點(diǎn)總數(shù)用M表示,則前r*M個(gè)節(jié)點(diǎn)的傳播意愿要和自身度值成線性關(guān)系,剩下的(1-r)*M個(gè)節(jié)點(diǎn)的傳播意愿要滿足冪律分布和部分節(jié)點(diǎn)度值很大但傳播意愿較小的情況.本文采用同樣的方法來(lái)模擬生成一組用戶的傳播意愿值.為了確定r值,本文采用A-PDSA算法在三個(gè)真實(shí)數(shù)據(jù)集Bitcoinotc、Bitcoinalpha和Slashdot上進(jìn)行了實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖2所示.

圖2 對(duì)不同r值求得的凈積極影響力隨種子節(jié)點(diǎn)的變化情況

通過(guò)對(duì)比發(fā)現(xiàn),r=0.9時(shí),A-PDSA算法的效果最好.所以在模擬生成用戶傳播意愿值時(shí),均采用r=0.9.

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

本文測(cè)試了三個(gè)不同大小的真實(shí)網(wǎng)絡(luò)的數(shù)據(jù)集:Bitcoinotc、Bitcoinalpha和Slashdot,并與其他三個(gè)啟發(fā)式算法在性能和時(shí)間上進(jìn)行了比較.Bitcoinotc是在稱為比特幣OTC的平臺(tái)上使用比特幣進(jìn)行交易的人的誰(shuí)信任誰(shuí)網(wǎng)絡(luò);Bitcoinalpha是在一個(gè)名為比特幣Alpha的平臺(tái)上使用比特幣進(jìn)行交易的人的誰(shuí)信任誰(shuí)網(wǎng)絡(luò).Slashdot是一個(gè)受歡迎的技術(shù)新聞網(wǎng)站.Slashdot中的用戶可以將其他用戶標(biāo)記為朋友(正面)或敵人(負(fù)面).由于該數(shù)據(jù)集太大,因此我們從Slashdot中選擇度最高的10 900個(gè)節(jié)點(diǎn)以及所選節(jié)點(diǎn)之間的邊.表1統(tǒng)計(jì)了三個(gè)數(shù)據(jù)集的信息,實(shí)驗(yàn)所用數(shù)據(jù)集可以從斯坦福大型網(wǎng)絡(luò)數(shù)據(jù)集網(wǎng)站(http://snap.stanford.edu/data)中下載.

表1 數(shù)據(jù)集

4.3 參數(shù)設(shè)置

對(duì)于這三個(gè)網(wǎng)絡(luò),邊上的激活概率p=0.1,在模擬信息傳播階段,蒙特卡洛模擬的次數(shù)設(shè)置為1 000.考慮到貪心算法時(shí)間復(fù)雜度較高,因此本文不考慮貪心算法作為對(duì)比算法,將所提出的算法(A-PDSA)與K-shell算法[20],MaxShare算法[19]和Iv-greedy算法[21]進(jìn)行對(duì)比.

K-shell算法遞歸地剝離網(wǎng)絡(luò)中度小于或等于k的節(jié)點(diǎn),直到網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都被賦予ks值,選擇前k個(gè)ks值最高的節(jié)點(diǎn)做為種子節(jié)點(diǎn).

MaxShare算法是選擇前k個(gè)分享意愿最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn).

Iv-greedy算法為圖中的每個(gè)節(jié)點(diǎn)建立一個(gè)影響向量,節(jié)點(diǎn)的影響向量體現(xiàn)了該節(jié)點(diǎn)對(duì)其鄰居的影響程度,本文中要同時(shí)考慮該節(jié)點(diǎn)的傳播意愿和對(duì)鄰居節(jié)點(diǎn)的影響概率.

4.4 實(shí)驗(yàn)結(jié)果與分析

圖3為數(shù)值實(shí)驗(yàn)的結(jié)果,圖(A)～(C)是分別在三個(gè)不同數(shù)據(jù)集上當(dāng)k分別取10、20、30、40、50時(shí),四個(gè)算法求得的凈積極影響力范圍.其中:橫軸表示種子集的大小,縱軸表示種子節(jié)點(diǎn)的凈積極影響力.

圖3 不同數(shù)據(jù)集上求得的凈積極影響力隨種子

從圖3中可以看出,在這三個(gè)數(shù)據(jù)集上,本算法找到的種子集產(chǎn)生的凈積極影響均明顯大于其他三個(gè)算法的結(jié)果.

表2為在三個(gè)不同數(shù)據(jù)集上,當(dāng)種子集中節(jié)點(diǎn)個(gè)數(shù)取50時(shí)四個(gè)算法的運(yùn)行時(shí)間.結(jié)合表2和圖3,可以看出雖然在數(shù)據(jù)集Bitcoinalpha和Bitcoinotc中三個(gè)對(duì)比算法比本文算法要快一些,但是產(chǎn)生的凈積極影響卻比本文算法小很多,在數(shù)據(jù)集Slashdot(subgraph)中,本文算法不僅比Iv-greedy快,求得的結(jié)果也是最好的.

表2 k=50時(shí)的運(yùn)行時(shí)間(s)

5 結(jié) 語(yǔ)

符號(hào)網(wǎng)絡(luò)中的凈積極影響力最大化問(wèn)題是一個(gè)具有實(shí)際意義的問(wèn)題,但由于用戶在傳播信息時(shí)會(huì)考慮自身的原因,因此,本文引入了用戶的傳播意愿來(lái)使得這個(gè)問(wèn)題更符合實(shí)際場(chǎng)景.其次,證明了在AIC-P模型中,目標(biāo)函數(shù)既不是單調(diào)的也不是次模的,另外提出了改進(jìn)的PDSA算法,即A-PDSA算法來(lái)解決考慮用戶意愿的凈積極影響力最大化問(wèn)題.并且在三個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行大量的實(shí)驗(yàn)表明,利用本文算法得到的種子集,具有更大的凈積極影響力.對(duì)于本文提出的算法,在尋找種子節(jié)點(diǎn)時(shí)仍會(huì)花費(fèi)大量時(shí)間,因此未來(lái)應(yīng)該考慮其他更優(yōu)的算法;在模擬生成節(jié)點(diǎn)的傳播意愿值時(shí),是通過(guò)微博數(shù)據(jù)集進(jìn)行分析的,有一定的缺陷,將來(lái)還要研究更合適的方法來(lái)生成用戶的傳播意愿值.