基于合并影響概率的社交網(wǎng)絡(luò)影響最大化算法

周 飛,高茂庭

(上海海事大學(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ù)交易類應(yīng)用融合,借助其他應(yīng)用的用戶基礎(chǔ),形成更強大的關(guān)系鏈,從而實現(xiàn)對信息的廣泛、快速傳播。鑒于社交網(wǎng)絡(luò)影響力的傳播特性,信息在社交網(wǎng)絡(luò)傳播中具有“口碑效應(yīng)”,即當(dāng)某用戶接受一新鮮事物時,他通常會將該事物推薦給他的朋友,當(dāng)他的朋友接受的時候就實現(xiàn)了信息的有效擴散。于是,在日常生產(chǎn)生活中決策者們便利用“口碑效應(yīng)”在社交網(wǎng)絡(luò)中進行產(chǎn)品信息宣傳,實現(xiàn)影響最大化在網(wǎng)絡(luò)營銷、輿情監(jiān)控等方面的實際應(yīng)用。社交網(wǎng)絡(luò)的流行也為“病毒式營銷”提供了天然的營銷網(wǎng)絡(luò),因此,如何從眾多網(wǎng)絡(luò)節(jié)點中尋找若干較少節(jié)點,使得影響力能夠最廣泛地擴散成為一個研究熱點。

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

1 相關(guān)研究

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

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

2 傳播模型

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

2.1 線性閾值模型

2.2 獨立級聯(lián)模型

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

3 影響最大化算法CIPIM

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

3.1 種子選取范圍的減少

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

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

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

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

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

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

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

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

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

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

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

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

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

輸出各種子節(jié)點統(tǒng)計信息

執(zhí)行步驟:

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

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

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

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

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

6)返回SR。

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

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

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

輸入seedlist,p,SR

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

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時間復(fù)雜度為O(n),設(shè)p為傳播模型各邊傳播概率,k表示一個族群中種子個數(shù),popsize表示種群集合中種群數(shù),elite表示種群集合中精英所占比例,maxiter表示最大迭代次數(shù),vatiprob用來判定族群選擇交叉還是變異,CIPIM算法GA過程描述如下:

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

輸出k個種子組成的集合

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

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

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

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

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

4 實驗結(jié)果與分析

4.1 實驗數(shù)據(jù)集

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

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

4.2 實驗設(shè)置

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

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

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

4.3 結(jié)果分析

影響最大化算法的評價通常從影響范圍和時間效率2個方面衡量。

4.3.1 Wiki-Vote數(shù)據(jù)集實驗

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

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

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

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

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

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

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

4.3.2 Twitter數(shù)據(jù)集實驗

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

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

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

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

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

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

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

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

5 結(jié)束語

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