周 飛,高茂庭

(上海海事大學(xué) 信息工程學(xué)院,上海 201306)

0 概述

隨著互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展,社交網(wǎng)絡(luò)服務(wù)(Social Network Service,SNS)作為互聯(lián)網(wǎng)應(yīng)用發(fā)展的必備要素,不再局限于信息傳遞,而是與溝通交流、商務(wù)交易類(lèi)應(yīng)用融合,借助其他應(yīng)用的用戶基礎(chǔ),形成更強(qiáng)大的關(guān)系鏈,從而實(shí)現(xiàn)對(duì)信息的廣泛、快速傳播。鑒于社交網(wǎng)絡(luò)影響力的傳播特性,信息在社交網(wǎng)絡(luò)傳播中具有“口碑效應(yīng)”,即當(dāng)某用戶接受一新鮮事物時(shí),他通常會(huì)將該事物推薦給他的朋友,當(dāng)他的朋友接受的時(shí)候就實(shí)現(xiàn)了信息的有效擴(kuò)散。于是,在日常生產(chǎn)生活中決策者們便利用“口碑效應(yīng)”在社交網(wǎng)絡(luò)中進(jìn)行產(chǎn)品信息宣傳,實(shí)現(xiàn)影響最大化在網(wǎng)絡(luò)營(yíng)銷(xiāo)、輿情監(jiān)控等方面的實(shí)際應(yīng)用。社交網(wǎng)絡(luò)的流行也為“病毒式營(yíng)銷(xiāo)”提供了天然的營(yíng)銷(xiāo)網(wǎng)絡(luò),因此,如何從眾多網(wǎng)絡(luò)節(jié)點(diǎn)中尋找若干較少節(jié)點(diǎn),使得影響力能夠最廣泛地?cái)U(kuò)散成為一個(gè)研究熱點(diǎn)。

已知社交網(wǎng)絡(luò)由M個(gè)節(jié)點(diǎn)和N條邊所組成的有向圖G(V,E)表示。社交網(wǎng)絡(luò)影響最大化問(wèn)題(Influence Maximization Problem,IMP)由文獻(xiàn)[1]提出,IMP問(wèn)題就是如何從M個(gè)節(jié)點(diǎn)中選取K個(gè)種子節(jié)點(diǎn),讓這個(gè)K種子節(jié)點(diǎn)在初始時(shí)刻處于激活狀態(tài),通過(guò)網(wǎng)絡(luò)傳播模型嘗試激活其他當(dāng)前狀態(tài)是未激活的節(jié)點(diǎn),最終使得被激活成功的節(jié)點(diǎn)數(shù)最多的問(wèn)題。針對(duì)該問(wèn)題,本文提出一種基于合并影響概率的社交網(wǎng)絡(luò)影響最大化算法。

1 相關(guān)研究

為了解決影響最大化問(wèn)題,文獻(xiàn)[2]將影響最大化問(wèn)題歸納為離散最優(yōu)問(wèn)題,并提出了近似可達(dá)最優(yōu)解63%的爬山貪心算法,運(yùn)用多次蒙特卡洛模擬獲得影響范圍,取最優(yōu)解,但對(duì)于大規(guī)模社交網(wǎng)絡(luò),這種貪心算法的時(shí)間復(fù)雜度太高。針對(duì)此問(wèn)題,文獻(xiàn)[3]提出了改進(jìn)的貪心算法CELF,利用網(wǎng)絡(luò)傳播的子模性,延遲計(jì)算邊際收益,將時(shí)間效率提高了數(shù)百倍。在此基礎(chǔ)上,文獻(xiàn)[4]利用堆特性對(duì)CELF 算法做出改進(jìn)并提出了CELF++算法。文獻(xiàn)[5]提出NewGreedy算法,在獨(dú)立級(jí)聯(lián)傳播模型下,以1-p的概率去除原圖中的邊,再迭代考慮子圖的最大影響力。MixGreedy算法[5]結(jié)合NewGreedy算法和CELF算法,仿真實(shí)驗(yàn)表明,其性能略好于NewGreedy。文獻(xiàn)[5]亦在Degree算法[6]的基礎(chǔ)上提出DegreeDiscount算法,性能也有所提升。網(wǎng)頁(yè)排名的PageRank算法[7]也被運(yùn)用于尋找網(wǎng)絡(luò)影響力節(jié)點(diǎn)中。PMIA算法[8]提供了穩(wěn)定的傳播范圍,且運(yùn)行速度比貪心算法提升了大約3個(gè)數(shù)量級(jí),但由于在本地計(jì)算節(jié)點(diǎn)樹(shù)結(jié)構(gòu),運(yùn)行時(shí)需要耗費(fèi)較大內(nèi)存。文獻(xiàn)[9]提出CGA算法,采用分治思想,拆分?jǐn)?shù)據(jù)集,對(duì)各個(gè)子集并行計(jì)算。文獻(xiàn)[10]在CELE的基礎(chǔ)上使用上界逼近法減小了算法響應(yīng)時(shí)間。UGGreedy算法[11]在去除不重要節(jié)點(diǎn)簡(jiǎn)化網(wǎng)絡(luò)結(jié)構(gòu)后再使用貪心算法求解,但算法時(shí)間復(fù)雜度依然相對(duì)較高。文獻(xiàn)[12]提出k-核概念,并考慮節(jié)點(diǎn)間影響區(qū)域重疊現(xiàn)象提出核覆蓋CCA算法,認(rèn)為影響重疊會(huì)使得影響力難以擴(kuò)散,帶來(lái)的邊際受益很小。CCA算法優(yōu)先選擇距離參數(shù)d內(nèi)影響重疊較少的節(jié)點(diǎn)。然而,在獨(dú)立級(jí)聯(lián)的模型下,重疊部分的節(jié)點(diǎn)被影響次數(shù)要多于非重疊部分節(jié)點(diǎn),因此,重疊部分節(jié)點(diǎn)相對(duì)被影響的概率更大,繼而可以影響到其他后續(xù)節(jié)點(diǎn)。文獻(xiàn)[13]結(jié)合網(wǎng)絡(luò)在線傳播和現(xiàn)實(shí)社會(huì)中口口相傳的特性建立模型,但也正因如此算法擴(kuò)展性較差。BCIM算法,先使用PageRank選取備用節(jié)點(diǎn),再使用動(dòng)態(tài)規(guī)劃的方法獲取最優(yōu)解,其不足之處是只考慮到近距離鄰居的影響,雖然在算法時(shí)間上有較大提高,但是會(huì)出現(xiàn)部分影響力在傳播過(guò)程中丟失的現(xiàn)象。

為了更好地解決影響最大化問(wèn)題,且考慮到現(xiàn)有算法中存在貪心算法時(shí)間復(fù)雜度過(guò)高,節(jié)點(diǎn)間影響區(qū)域重疊,算法可擴(kuò)展性以及在傳播過(guò)程中只考慮近距離傳播而犧牲影響力間接傳播來(lái)提高算法時(shí)間性能等問(wèn)題。本文在第4節(jié)提出基于合并影響概率的社交網(wǎng)絡(luò)影響最大化算法(Influence Maximization with Combined Impact Probability,CIPIM),在沿用BCIM算法中先使用PageRank選取備用種子節(jié)點(diǎn),再在計(jì)算備選種子節(jié)點(diǎn)合并影響概率的基礎(chǔ)上,使用遺傳算法(Genetic Algorithm,GA)解決全局優(yōu)化問(wèn)題。

2 傳播模型

尋找社交網(wǎng)絡(luò)影響最大化節(jié)點(diǎn)往往需要借助于網(wǎng)絡(luò)傳播模型,通常情況下將社交網(wǎng)絡(luò)表示為由M個(gè)節(jié)點(diǎn)和N條邊所組成的有向圖G(V,E),其中,節(jié)點(diǎn)表示社交網(wǎng)絡(luò)中的個(gè)體,有向邊表示個(gè)體之間的關(guān)系,如Twitter中用戶之間的關(guān)注關(guān)系。線性閾值模型(Linear Threshold Model)和獨(dú)立級(jí)聯(lián)模型(Independent Cascade Model,ICM)是2種常用的網(wǎng)絡(luò)傳播模型。

2.1 線性閾值模型

2.2 獨(dú)立級(jí)聯(lián)模型

在獨(dú)立級(jí)聯(lián)模型[15]中,任意一條邊∈E都有一個(gè)puv∈[0,1],表示節(jié)點(diǎn)u通過(guò)邊影響節(jié)點(diǎn)v的概率。該模型中,只有在當(dāng)前節(jié)點(diǎn)被激活后才有一次機(jī)會(huì)去激活其鄰居節(jié)點(diǎn)。假設(shè)u在時(shí)間t被激活,那么在單步時(shí)間內(nèi),u可以嘗試去激活它的鄰居v。如果v被激活,那么v將在時(shí)間t+1變成激活狀態(tài)。時(shí)間t+1之后,u將不再嘗試激活其鄰居節(jié)點(diǎn)。當(dāng)若干單步時(shí)間后,如果不存在激活可能性的時(shí)候,傳播過(guò)程結(jié)束。在簡(jiǎn)單的獨(dú)立級(jí)聯(lián)模型中,通常將puv設(shè)置為常量,或是從{0.1,0.01,0.001}中隨機(jī)選取。獨(dú)立級(jí)聯(lián)模型更側(cè)重于影響力的傳播過(guò)程,在現(xiàn)實(shí)工作中應(yīng)用更為廣泛,因此本文選用獨(dú)立級(jí)聯(lián)模型作為傳播模型。

3 影響最大化算法CIPIM

影響最大化問(wèn)題就是要從M個(gè)節(jié)點(diǎn)中選取影響傳播影響范圍最大的K個(gè)種子節(jié)點(diǎn)。但在實(shí)際社交網(wǎng)絡(luò)中存在大量低影響力用戶,在信息傳播中幾乎沒(méi)有任何貢獻(xiàn),因此,他們不能作為種子節(jié)點(diǎn)。從減少種子選取范圍上考慮,先使用PageRank算法計(jì)算M個(gè)節(jié)點(diǎn)的PageRank值,從中選取排名靠前的節(jié)點(diǎn)作為備選種子集合,再對(duì)各備選種子節(jié)點(diǎn)進(jìn)行合并影響概率預(yù)計(jì)算,最后使用遺傳算法進(jìn)行全局優(yōu)化挑選出K個(gè)種子節(jié)點(diǎn)。

3.1 種子選取范圍的減少

意見(jiàn)領(lǐng)袖通常是網(wǎng)絡(luò)社區(qū)中的活躍分子,是信息的積極傳播者,能夠引起大量關(guān)注并影響社區(qū)中的輿論導(dǎo)向。在線社交網(wǎng)絡(luò)通常采用PageRank值來(lái)表示用戶的影響力大小,值越大則影響力越大。社交網(wǎng)絡(luò)中還存在著大量的信息接收者,但單純的接受者對(duì)信息傳播的貢獻(xiàn)卻非常小。為了分析選取高影響力用戶作為備用種子節(jié)點(diǎn)的占比規(guī)律,對(duì)Wiki-Vote數(shù)據(jù)集[16]7 115個(gè)節(jié)點(diǎn)按照PageRank值進(jìn)行排序,歸一化處理各節(jié)點(diǎn)PageRank值并計(jì)算可影響范圍占比情況,考慮圖像顯示效果和方便觀察,截取前1 000個(gè)節(jié)點(diǎn),如圖1所示。1 000位之后的圖像延續(xù)圖1后半段走勢(shì),平緩遞增與遞減。

圖1 前1 000名PageRank值及影響范圍占比情況

圖1顯示,選取1/10的節(jié)點(diǎn)就可達(dá)到超過(guò)80%的影響范圍,僅需1%的節(jié)點(diǎn)即可達(dá)到60%以上的影響范圍。因此,本文從減小種子節(jié)點(diǎn)選取范圍出發(fā),選取具有較高PageRank值的節(jié)點(diǎn)作為備選種子節(jié)點(diǎn)?？紤]到當(dāng)K值較小時(shí)(比如K=10),并不需要從前500個(gè)甚至很多的節(jié)點(diǎn)中挑選出10個(gè)種子節(jié)點(diǎn),僅從前100個(gè)節(jié)點(diǎn)來(lái)看完全可以達(dá)到預(yù)想效果。同時(shí),為了防止使用固定數(shù)量的備選種子可能會(huì)造成的局部最優(yōu)情況,本文使用線性規(guī)則來(lái)選取備用種子節(jié)點(diǎn),即選取PageRank值排名靠前的hK個(gè)節(jié)點(diǎn)作為備選種子節(jié)點(diǎn),為了方便計(jì)算在實(shí)驗(yàn)中將h值設(shè)為10。這樣,不僅從數(shù)量上減少運(yùn)算時(shí)間,而且在一定程度上消除可能存在的局部最優(yōu)情況。

3.2 備選種子合并影響預(yù)計(jì)算

文獻(xiàn)[17]在數(shù)據(jù)集DBLP上證實(shí)了六度分割理論猜想:每個(gè)人最多通過(guò)6個(gè)人就可以認(rèn)識(shí)一個(gè)陌生人。同樣,在社交網(wǎng)絡(luò)信息傳播的過(guò)程中,也僅需幾次即可將信息傳播開(kāi)。圖2是社交網(wǎng)絡(luò)中種子節(jié)點(diǎn)A、B影響傳播的局部路徑簡(jiǎn)單傳播模型,其中,t表示當(dāng)前傳播次數(shù)。

圖2 社交網(wǎng)絡(luò)信息傳播路徑

在圖2中,設(shè)每條有向邊傳播概率相同,為常量p,那么種子節(jié)點(diǎn)A通過(guò)邊激活節(jié)點(diǎn)C的概率即為p,節(jié)點(diǎn)C被激活后,就有p的概率通過(guò)邊影響到F節(jié)點(diǎn),故節(jié)點(diǎn)A通過(guò)邊和激活節(jié)點(diǎn)F的概率為p2。節(jié)點(diǎn)D的影響來(lái)源于種子節(jié)點(diǎn)A、B以及節(jié)點(diǎn)C的傳遞影響,那么它可被以p概率激活2次,以p2概率激活一次,于是,節(jié)點(diǎn)D被激活的概率為1-(1-p)2+p2。

備選種子合并影響預(yù)計(jì)算,是對(duì)備選種子集中每個(gè)備選種子進(jìn)行一次節(jié)點(diǎn)自身傳播范圍內(nèi)可被激活節(jié)點(diǎn)次數(shù)及輪次統(tǒng)計(jì)。對(duì)于種子節(jié)點(diǎn)A,其可激活節(jié)點(diǎn)集為{C,D,F,G,M},且t=1的有{C,D},t=2的有{D,F,G},t=3的有{G,M},其中,當(dāng)t=3時(shí)有節(jié)點(diǎn)G的原因是存在一條A-C-D-G通路。對(duì)于種子集合{A,B}來(lái)說(shuō),由于它們之間有共同影響部分,故它們的影響概率并不是節(jié)點(diǎn)A和B的概率簡(jiǎn)單相加。因此,在最終計(jì)算種子集合的影響概率時(shí),先要分別統(tǒng)計(jì)各種子節(jié)點(diǎn)的預(yù)處理結(jié)果,再合并計(jì)算它們的影響概率。

在不同傳播概率p下,若以不同傳播次數(shù)t分別嘗試500次激活,通過(guò)公式P=1-(1-pt)500可計(jì)算出節(jié)點(diǎn)被激活概率。例如,當(dāng)t=3時(shí),節(jié)點(diǎn)被激活的概率為p3,假設(shè)該節(jié)點(diǎn)被激活500次,則該節(jié)點(diǎn)在t=3下被激活概率為1-(1-p3)500,如表1所示。

表1 500次激活下節(jié)點(diǎn)被激活概率

如表1所示,當(dāng)t=3,p=0.01時(shí),仍有萬(wàn)分之五的概率能夠激活節(jié)點(diǎn),而當(dāng)t=3,p=0.06時(shí)被激活概率達(dá)到約0.1。當(dāng)t=4,p=0.01時(shí),節(jié)點(diǎn)幾乎不可能被激活,而p=0.06時(shí)也僅僅只有0.006的概率。因此,本文針對(duì)文獻(xiàn)[13]中只考慮近距離(t=2)傳播的問(wèn)題,將種子節(jié)點(diǎn)可影響步數(shù)調(diào)整為t=3步,雖然在一定程度上加大了算法的時(shí)間復(fù)雜度,但是其傳播概率計(jì)算更為準(zhǔn)確合理。

設(shè)G(V,E)為有向圖,seed表示某種子節(jié)點(diǎn),t表示當(dāng)前傳播輪次,該備選種子預(yù)處理算法(Alternative Seed Preprocess Algorithm,ASPA)采用圖深度優(yōu)先遍歷策略,算法描述如下:

輸入t,seed,G(V,E)

輸出各種子節(jié)點(diǎn)統(tǒng)計(jì)信息

執(zhí)行步驟:

1)如果t>3,返回,否則轉(zhuǎn)到2)。

2)Fseed←節(jié)點(diǎn)seed所有未嘗試激活的鄰居節(jié)點(diǎn),轉(zhuǎn)到3)。

3)SR(seed,times)←Fseed,轉(zhuǎn)到4)。

4)標(biāo)記節(jié)點(diǎn)seed已嘗試激活,轉(zhuǎn)到5)。

5)對(duì)于?u∈Fseed,遞歸計(jì)算ASPA(t+1,u,G)。

6)返回SR。

其中,步驟1)、步驟3)、步驟4)的時(shí)間復(fù)雜度都是O(1),步驟2)的時(shí)間復(fù)雜度為O(n),G圖以類(lèi)似鄰接表的形式存儲(chǔ),在一定程度上降低了算法時(shí)間復(fù)雜度,以單節(jié)點(diǎn)出發(fā)的時(shí)間復(fù)雜度為O(n+e),因此,總體時(shí)間復(fù)雜度為O(Kn+e)。

3.3 遺傳算法全局優(yōu)化過(guò)程

設(shè)p表示傳播模型傳播概率,seedlist表示包含k個(gè)種子節(jié)點(diǎn)的列表集合,SR表示3.2節(jié)計(jì)算所得信息集,遺傳算法優(yōu)化過(guò)程的適應(yīng)性函數(shù)CountSeed描述如下:

輸入seedlist,p,SR

輸出這k個(gè)種子節(jié)點(diǎn)的綜合影響概率

1.total_probability←0

2.for t=1 to 3:

4.count=Count(infect_list)

5.for user in count.keys():

6.number←count[user]

7.probability←1-(1-pt)numbers

8.total_probability+=probability

9.return total_probability

該適應(yīng)性函數(shù)CountSeed時(shí)間復(fù)雜度為O(n),設(shè)p為傳播模型各邊傳播概率,k表示一個(gè)族群中種子個(gè)數(shù),popsize表示種群集合中種群數(shù),elite表示種群集合中精英所占比例,maxiter表示最大迭代次數(shù),vatiprob用來(lái)判定族群選擇交叉還是變異,CIPIM算法GA過(guò)程描述如下:

輸入costfunc,k,popsize,elite,maxiter,vatiprob,p

輸出k個(gè)種子組成的集合

1)生成初始種群POP={P1,P2…,Ppopsize},其中每個(gè)族群P都包含k個(gè)節(jié)點(diǎn),轉(zhuǎn)到2)。

2)計(jì)算種群集每個(gè)族群綜合影響概率,將種群中CountSeed返回值較大者作為精英保留;如果迭代次數(shù)達(dá)到maxiter,轉(zhuǎn)到5),否則轉(zhuǎn)到3)。

3)根據(jù)vatiprob判斷對(duì)保留下來(lái)的精英族群進(jìn)行交叉操作還是變異操作,并添加到新的種群集POP'中,轉(zhuǎn)到4)。

4)如果len(POP′)小于popsize,轉(zhuǎn)到3),否則轉(zhuǎn)到2)。

5)返回綜合影響概率最高的種子集合。

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

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

為了全面分析CIPIM算法在不同規(guī)模網(wǎng)絡(luò)環(huán)境下影響傳播效果、可擴(kuò)展性及性能,本文選取規(guī)模不同的2個(gè)真實(shí)社交網(wǎng)絡(luò)數(shù)據(jù)集Wiki-Vote[16]和Twitter[18],它們的統(tǒng)計(jì)特性如表2所示。

表2 屬性特征權(quán)重

4.2 實(shí)驗(yàn)設(shè)置

為驗(yàn)證本文算法的性能,選取當(dāng)前較有代表性的算法進(jìn)行比較。因?yàn)樨澬乃惴ㄔ跁r(shí)間復(fù)雜度上較高,即便是后續(xù)優(yōu)化后的算法仍然需要較長(zhǎng)、甚至數(shù)天的時(shí)間才能得到結(jié)果,所以本文不與貪心算法進(jìn)行比較,而與DegreeDiscount、PageRank、CCA等算法進(jìn)行比較。DegreeDiscount算法是一種種子節(jié)點(diǎn)對(duì)鄰居節(jié)點(diǎn)進(jìn)行度折扣的啟發(fā)式算法;PageRank算法,是Google用于標(biāo)識(shí)網(wǎng)頁(yè)重要性的算法,本文中將阻尼因子設(shè)置為0.85;CCA(d)算法是基于核數(shù)層次特征、消除重復(fù)影響的一種啟發(fā)式算法,原文中距離參數(shù)d為2時(shí)效果更好,因此,本文使用CCA(2)進(jìn)行比較。本文算法CIPIM中備選種子比例h取為10;種群數(shù)一般設(shè)置為20～100,本文將種群數(shù)popsize設(shè)為50;最大迭代數(shù)一般取100～500,在本算法中因?yàn)閷?duì)下一層精英選擇過(guò)程做了特殊處理,算法將加速收斂,因此將最大迭代次數(shù)maxiter設(shè)為100;同理,精英策略elite設(shè)為0.2。

為了討論傳播概率對(duì)傳播結(jié)果的影響,排除實(shí)驗(yàn)結(jié)果的偶然性,分別將影響傳播概率設(shè)置為0.01、0.03、0.06進(jìn)行蒙特卡洛模擬傳播,并對(duì)每次模擬傳播進(jìn)行1 000次實(shí)驗(yàn),取平均值作為傳播結(jié)果。

實(shí)驗(yàn)硬件環(huán)境為macOS,內(nèi)存8 GB,處理器1.6 GHz Intel Core i5,所有代碼均使用Python2.7.10書(shū)寫(xiě)。

4.3 結(jié)果分析

影響最大化算法的評(píng)價(jià)通常從影響范圍和時(shí)間效率2個(gè)方面衡量。

4.3.1 Wiki-Vote數(shù)據(jù)集實(shí)驗(yàn)

Wiki-Vote數(shù)據(jù)集是維基百科的一個(gè)投票數(shù)據(jù),屬于中型數(shù)據(jù)集。圖3～圖5為各傳播概率下的模擬實(shí)驗(yàn)平均被影響節(jié)點(diǎn)個(gè)數(shù)趨勢(shì)。

圖3 Wiki-Vote上p=0.01時(shí)被影響節(jié)點(diǎn)數(shù)

圖4 Wiki-Vote上p=0.03時(shí)被影響節(jié)點(diǎn)數(shù)

圖5 Wiki-Vote上p=0.06時(shí)被影響節(jié)點(diǎn)數(shù)

從圖3～圖5可以看出,在k<10時(shí),各種算法在影響范圍上結(jié)果較為接近,相差不大。但當(dāng)k>10時(shí),可以明顯看出,CCA算法比其他算法在影響范圍上要稍稍遜色,且隨著k值增大,差異也越來(lái)越大。CCA算法為了減少算法運(yùn)行時(shí)間,犧牲掉間接傳播這一網(wǎng)絡(luò)特性,導(dǎo)致其影響范圍跟其他算法相比有些差距。CIPIM算法在PageRank的算法基礎(chǔ)上進(jìn)行全局優(yōu)化,其結(jié)果要好于單純的PageRank算法。隨著種子數(shù)k和傳播概率p的變大,算法之間效果的差異也越來(lái)越大。表3為不同傳播概率下各算法的平均運(yùn)行時(shí)間。

表3 WikiVote數(shù)據(jù)集下各算法平均運(yùn)行時(shí)間 s

由表3可以看出,CIPIM算法在運(yùn)行時(shí)間上比其他算法稍多一點(diǎn),但時(shí)間差距并不算大,居于相同數(shù)量級(jí)下。由于種子節(jié)點(diǎn)數(shù)k對(duì)CIPIM算法有一定的影響,因此,隨著k值的增大,算法所用時(shí)間也會(huì)隨之稍稍增大。但對(duì)于貪心算法而言,CIPIM算法用時(shí)已經(jīng)相當(dāng)?shù)土?。綜上,CIPIM算法在數(shù)據(jù)集Wiki-Vote上有良好表現(xiàn),算法有效。

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

Twitter數(shù)據(jù)集屬于大型社交網(wǎng)絡(luò)數(shù)據(jù)集,雖然節(jié)點(diǎn)數(shù)不到10萬(wàn)個(gè),但是卻有著百萬(wàn)級(jí)別由關(guān)注關(guān)系形成的有向邊。圖6～圖8為各傳播概率下的模擬實(shí)驗(yàn)被影響節(jié)點(diǎn)數(shù)趨勢(shì)。

圖6 Twitter上p=0.01時(shí)被影響節(jié)點(diǎn)數(shù)

圖7 Twitter上p=0.03時(shí)被影響節(jié)點(diǎn)數(shù)

圖8 Twitter上p=0.06時(shí)被影響節(jié)點(diǎn)數(shù)

從圖6～圖8可以看出,在較大型社交網(wǎng)絡(luò)中,CIPIM算法表現(xiàn)優(yōu)異。當(dāng)k值較小時(shí),除了PageRank算法表現(xiàn)一般,各算法相差不大。和Wiki-Vote數(shù)據(jù)集的運(yùn)行結(jié)果相似,但是在k>10之后,算法之間的差異開(kāi)始凸顯,CCA算法在Twitter數(shù)據(jù)集上比DegreeDiscount算法要好上一點(diǎn),說(shuō)明在真正的社交網(wǎng)絡(luò)上確實(shí)會(huì)有影響重疊的現(xiàn)象存在。CIPIM算法是從經(jīng)PageRank算法排序后的節(jié)點(diǎn)中選擇有較高影響力的節(jié)點(diǎn)作為備選節(jié)點(diǎn),然后再通過(guò)潛在被激活節(jié)點(diǎn)的綜合激活概率優(yōu)化得到,所以在運(yùn)行結(jié)果上,CIPIM算法始終高于PageRank算法。表4為不同傳播概率下各算法的平均運(yùn)行時(shí)間。

表4 Twitter數(shù)據(jù)集下各算法平均運(yùn)行時(shí)間 s

從表4可以看出,CIPIM算法在大型數(shù)據(jù)集上平均運(yùn)行時(shí)間方面仍然表現(xiàn)良好,雖然比一些算法稍稍偏多,但是在影響范圍覆蓋度上彌補(bǔ)了這些不足。其中需要說(shuō)明的是,在CIPIM算法中包含PageRank算法,但是只需計(jì)算一次,所以,在運(yùn)行時(shí)間內(nèi)沒(méi)有包含在里面。

從以上實(shí)驗(yàn)結(jié)果表明,不管是在Wiki-Vote數(shù)據(jù)集還是Twitter數(shù)據(jù)集上,不管傳播概率的取值如何,CIPIM算法均表現(xiàn)出較大優(yōu)勢(shì)。因?yàn)楸疚乃惴〞?huì)在全局上進(jìn)行優(yōu)化,所以與直接從節(jié)點(diǎn)度或核出發(fā)的算法相比在平均時(shí)間上要略高,但在節(jié)點(diǎn)選取效果上要好于這些算法,且在時(shí)間效率上要遠(yuǎn)遠(yuǎn)好于貪心算法,能在影響覆蓋度和運(yùn)行時(shí)間上取得了較好的平衡。

5 結(jié)束語(yǔ)

本文提出一種基于合并影響概率的遺傳算法,并利用該算法來(lái)解決影響最大化問(wèn)題,通過(guò)縮減種子搜尋范圍來(lái)減少工作量,使用遺傳算法進(jìn)行全局優(yōu)化。實(shí)驗(yàn)結(jié)果表明,CIPIM算法改善了CCA算法在共同影響概率缺失方面的問(wèn)題,同時(shí)與CCA算法、DegreeDiscount算法以及PageRank算法相比影響范圍更廣,時(shí)間復(fù)雜度遠(yuǎn)小于貪心算法。然而,本文算法仍存在不足之處,即各節(jié)點(diǎn)間的傳播概率都是固定值,但在實(shí)際社交網(wǎng)絡(luò)中并非如此。因此,在下一步工作中,將通過(guò)數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等方法綜合考慮多個(gè)社交網(wǎng)絡(luò),使其能夠確定用戶間不同的傳播概率。

[1] DOMINGOS P,RICHARDSON M.Mining the network value of customers[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2001:57-66.

[2] KEMPE D,KLEINBERG J,TARDOSE.Maximizing the spread of influence through a social network[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2003:137-146.

[3] LESKOVEC J,KRAUSE A,GUESTRIN C,et al.Cost-effective outbreak detection in networks[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2007:420-429.

[4] GOYAL A,LU W,LAKSHMANAN L V S.CELF++:optimizing the greedy algorithm for influence maximization in social networks[C]//Proceedings of International Conference on World Wide Web.New York,USA:ACM Press,2011:47-48.

[5] CHEN Wei,WANG Yajun,YANG Siyu.Efficient influence maximization in social networks[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2009:199-208.

[6] WASSERMAN S,FAUST K.Social network analysis[J].Encyclopedia of Social Network Analysis & Mining,2011,22(Suppl 1):109-127.

[7] BRIN S,PAGE L.The anatomy of a large-scale hypertextual web search engine[J].Computer Networks & Isdn Systems,1998,30(1-7):107-117.

[8] CHEN W,WANG C,WANG Y.Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2010:1029-1038.

[9] SONG Guojie,ZHOU Xiabing,WANG Yu,et al.Influence maximization on large-scale mobile social network:a divide-and-conquer method[J].IEEE Transactions on Parallel & Distributed Systems,2015,26(5):1379-1392.

[10] ZHOU Chuan,ZHANG Peng,ZANG Wenyu,et al.On the upper bounds of spread for greedy algorithms in social network influence maximization[J].IEEE Transactions on Knowledge & Data Engineering,2015,27(10):1.

[11] LI Ji,CAI Zhipeng,YAN Mingyuan,et al.Using crowdsourced data in location-based social networks to explore influence maximization[C]//Proceedings of IEEE Conference on Computer Communications.Washington D.C.,USA:IEEE Press,2016:1-9.

[12] 曹玖新,董 丹,徐 順,等.一種基于k-核的社會(huì)網(wǎng)絡(luò)影響最大化算法[J].計(jì)算機(jī)學(xué)報(bào),2015,38(2):238-248.

[13] MIAO Yu,WU Yang,WANG Wei,et al.UGGreedy:Influence maximization for user group in microb-logging[J].Chinese Journal of Electronics,2016,25(2):241-248.

[14] GRANOVETTER M.Threshold models of collective behavior[J].American Journal of Sociology,1978,83(6):1420-1443.

[15] WATTS D J.A simple model of global cascades on random networks[J].Proceedings of the National Academy of Sciences of the United States of America,2002,99(9):5766-5771.

[16] LESKOVEC J.Wikipedia vote network[EB/OL].[2017-03-10].http://snap.stanford.edu/data/wiki-Vote.html.

[17] ELMACIOGLU E,LEE D.On six degrees of separation in DBLP-DB and more[J].Acm Sigmod Record,2005,34(2):33-40.

[18] LESKOVEC J.Social corcles:twitter[EB/OL].[2017-03-10].http://snap.stanford.edu/data/egonets-Twitter.html.