基于時序圖的替補種子節(jié)點挖掘算法研究

許成偉,鄒曉紅,2,*

(1.燕山大學 信息科學與工程學院,河北 秦皇島 066004;2.燕山大學 河北省計算機虛擬技術與系統(tǒng)集成重點實驗室,河北 秦皇島 066004)

0 引言

Domingos和Richardsom等[1-2]在2001年首次提出有關社交網(wǎng)絡影響力最大化問題(Influence maximization),簡稱IM問題。IM問題是指在網(wǎng)絡圖中選定k個種子節(jié)點作為信息源點,使其在特定信息傳播模型下進行信息傳播,目的是在一定時間內(nèi)盡可能多地影響并激活其他的節(jié)點。到目前,IM問題大多數(shù)是基于靜態(tài)圖進行分析研究的,但針對具有動態(tài)性特征的社交網(wǎng)絡,不能簡單地將其表示為靜態(tài)圖模型進行處理,比如生物信息網(wǎng)絡、通信網(wǎng)絡、道路交通網(wǎng)絡等網(wǎng)絡結(jié)構,節(jié)點間只在某段時間或某一時間發(fā)生交互作用,存在一定的時間關系特性,并且具有明顯的交互順序,具有這樣特征的網(wǎng)絡被稱為時序網(wǎng)絡[3-4]。鑒于時序社交關系更能真實地反映現(xiàn)實中信息傳播的實際情況,一些學者[5-7]便開始在時序網(wǎng)絡中展開IM問題的研究,并提出一系列基于時序網(wǎng)絡的影響力最大化算法。

k個種子節(jié)點的選取是研究IM問題最主要的目標之一,但卻沒有考慮種子節(jié)點在實際應用的過程中,可能會因自身某些原因或各種外界因素影響而無法投入使用。例如,有著高影響力的明星并不愿意代言某一產(chǎn)品,或是在代言過程中觸犯解約條例被解約而無法繼續(xù)代言等諸多現(xiàn)實問題,本文將這種現(xiàn)象稱之為種子節(jié)點失效問題,稱這樣的節(jié)點為失效種子節(jié)點。種子節(jié)點失效問題所帶來的影響與損失是不可忽視的,這種變化對組合效果最優(yōu)的種子節(jié)點集所能發(fā)揮出影響效果造成了嚴重破壞,信息的擴散與傳播將會受到極大影響。因此,當網(wǎng)絡中出現(xiàn)這樣的問題時,為了繼續(xù)維持網(wǎng)絡影響力最大化的最初目標,及時在網(wǎng)絡中挖掘?qū)ふ曳N子節(jié)點的替補節(jié)點是十分必要的。因此,本文對時序圖中替補種子節(jié)點挖掘問題展開了研究,并提出了一種高效的可適用于大規(guī)模時序圖的替補種子節(jié)點挖掘算法(Two-stage substitute seed mining algorithm,TSSM),算法TSSM將替補種子節(jié)點的挖掘分為啟發(fā)式預選與貪心式終選兩個階段,預選階段從失效種子節(jié)點入手,選取一部分具有最優(yōu)局部替代效果的節(jié)點構建備選替補節(jié)點列表。終選階段,通過計算備選替補節(jié)點的邊際效應,進一步篩選出能夠使網(wǎng)絡全局影響力達到最優(yōu)的替補種子節(jié)點。

1 相關工作

針對種子節(jié)點失效問題,Lappas等[8]首先提出了效應者的概念,效應者是指在網(wǎng)絡中近似有相同傳播效果的節(jié)點,所提算法實現(xiàn)了在特定群體內(nèi),效應者的影響力覆蓋范圍接近種子節(jié)點的傳播效果。之后Li等[9]正式提出在社會網(wǎng)絡中尋找種子節(jié)點繼任者這一概念,充分考慮了替補節(jié)點現(xiàn)實意義,選擇在種子節(jié)點的鄰居節(jié)點中尋找繼任者,馬茜等[10]認為這種方法拋棄了影響力最大化的初衷,難以保證網(wǎng)絡影響力全局最優(yōu),對此提出應該從網(wǎng)絡整體出發(fā)去尋找替補種子節(jié)點,以達到網(wǎng)絡全局影響力最大化的目的,以此為出發(fā)點,首次將該問題定義為在影響力最大化問題中挖掘替補種子節(jié)點(Substitutes discovery in influence maximization,SDIM),并給出了全局靜態(tài)貪心算法(Global static greedy,GSG)。Xu等[11]針對算法GSG時間復雜度過高的問題,又提出了預選式貪心算(Pre-selected-based substitutes mining algorithm,P-S),該算法主要思想是在選取k個種子節(jié)點的同時便預先選定n個替補種子節(jié)點。以上2種算法篩選出的替補節(jié)點和失效種子節(jié)點的位置無關性較大,算法沒有較好的實際應用意義,對此Sun等[12]提出將失效種子節(jié)點的鄰居節(jié)點與網(wǎng)絡中一定數(shù)量最大度的節(jié)點一起構成后繼節(jié)點集,然后利用模擬退火的方法去處理后繼結(jié)點與原種子節(jié)點的最優(yōu)組合問題,以獲取最終的新種子節(jié)點集,由于模擬退火算法收斂速度慢,該算法的時間效率較低。

2 基本概念

2.1 時序圖

定義1時序圖(Temporal graph,也被稱為Temporal network[13]),給定網(wǎng)絡GT(V,E,TE)表示節(jié)點間具有時序關系的社交網(wǎng)絡有向時序圖。其中V表示節(jié)點的集合,E表示邊的集合,TE表示圖中所有節(jié)點之間存在聯(lián)系時刻的集合,T(u,v)表示節(jié)點u和v之間存在聯(lián)系的時刻的集合,T(u,v)∈TE,u,v∈V。

時序圖是指在邊上帶有時間戳的動態(tài)有向圖,且節(jié)點間的邊會隨著邊上時間戳的到來而被激活,它表示兩節(jié)點在此刻時間存在聯(lián)系。圖1為一個簡單的時序圖,邊上的數(shù)字代表著時間戳,以節(jié)點A、B為例,T(A,B)={1,3,5}表示節(jié)點A分別在1,3,5時刻與節(jié)點B存在聯(lián)系并以傳播概率P(A,B)嘗試將其激活。

圖1 時序圖Fig.1 Temporal graph

2.2 問題定義

定義2SDIM問題:給定一個網(wǎng)絡G,使用一定的IM算法找到含有k個節(jié)點的種子集合S,在種子節(jié)點工作過程中,出現(xiàn)t個無法繼續(xù)工作的失效種子節(jié)點構成集合S1,目的是在剩余非種子節(jié)點中找出t個替補種子節(jié)點,構成替補種子節(jié)點集S2。新種子節(jié)點集S″=S2∪(S-S1),|S″|=k,使得最終在網(wǎng)絡中的傳播結(jié)果與原種子節(jié)點集S的傳播結(jié)果的差值最小,即

其中,Inf(S)表示種子集S影響力大小。

由于S是提前給定的且認為是最優(yōu)的,所以目標函數(shù)也可記作

定理1SDIM問題是NP難問題。

時序圖替補種子節(jié)點挖掘是在影響力最大化算法基礎上延伸出的新問題,是在已知種子節(jié)點集的基礎上作進一步探究。SDIM問題可看作在VS中繼續(xù)挖掘t個種子節(jié)點的問題,因此同種子節(jié)點挖掘算法一樣,SDIM問題也是NP難的問題。

3 算法設計

在不脫離網(wǎng)絡影響力最大化的前提下,考慮時序圖中信息傳播的時序性,提出了時序圖兩階段替補種子節(jié)點挖掘算法TSSM,算法將時序圖中替補種子節(jié)點的挖掘分為預選與終選兩個階段。

3.1 構建失效種子節(jié)點替補列表

在普通靜態(tài)圖中,可以根據(jù)節(jié)點與失效種子節(jié)點含有公共一階后繼節(jié)點的個數(shù)去評估節(jié)點的替補效果,例如在圖2(a)中,節(jié)點A為失效種子節(jié)點,若網(wǎng)絡中存在節(jié)點α,其與節(jié)點A含有全部公共一階后繼節(jié)點,則此種情況下節(jié)點α便可在種子節(jié)點A失效后較好地代替其繼續(xù)工作。

圖2 替補種子節(jié)點對信息傳播路徑的重構Fig.2 Reconstruction of information dissemination path by substitute seed nodes

由于時序圖中信息傳播存在時序性,信息在時序圖中的傳播過程與靜態(tài)圖不同,例如在圖2(b)中,當種子節(jié)點A被移除后,其后繼一階信息傳播路徑,即時序邊E(A,B)、E(A,C)直接遭到破壞,同時由于時序圖中鄰近兩條邊之間具有一定的時序關系,因此后繼第二階信息傳播路徑也間接受到影響,當替補節(jié)點α取代失效節(jié)點A后,其將會重新構建節(jié)點A后繼兩階范圍內(nèi)的信息傳播路徑。在圖2中可以看到只有邊E(α,B)、E(B,D)、E(B,E)三條路徑滿足信息傳播的時序關系,是信息可達的有效路徑,而節(jié)點α在7時刻與節(jié)點C聯(lián)系,此時節(jié)點C分別已經(jīng)在更早的時刻4、6與其后繼節(jié)點完成了聯(lián)系,故節(jié)點α只能將信息傳播至節(jié)點C而無法到達節(jié)點F、G,所以此時邊E(C,F)、E(C,G)為信息不可達的無效路徑。由此可見時序圖中備選替補節(jié)點的尋找不能只關注公共一階后繼節(jié)點的個數(shù),應從對失效種子節(jié)點后繼二階范圍內(nèi)構建有效可達信息傳播路徑的條數(shù)去衡量替補節(jié)點替補效果的優(yōu)劣,基于此給出節(jié)點可替代度的概念如下。

定義3可替代度R:指網(wǎng)絡中非種子節(jié)點α在失效種子節(jié)點A的后繼兩階范圍內(nèi)重新構建的可達有效信息傳播路徑的條數(shù),表示為RA(α) ,

式(3)給出了時序圖中節(jié)點α對于失效種子節(jié)點A可替代度的計算方法,其中{O(A)∩O(α)}表示節(jié)點α與失效種子節(jié)點A的公共一階后繼節(jié)點集,|E(v,w)|min(T(α,v))≤max(T(v,w))|表示替補節(jié)點α在失效種子節(jié)點A后繼第二階構建的滿足信息傳播時序關系的可達有效信息傳播路徑的條數(shù)。為保證替補節(jié)點與原失效節(jié)點有著較強的位置關聯(lián)性,且一個理想的替補節(jié)點的影響范圍應與失效種子節(jié)點的影響范圍有著較高的重合程度,即替補節(jié)點應對失效種子節(jié)點影響范圍內(nèi)的節(jié)點有著較高的激活率,這樣才能達到最佳的替補效果。因此,算法在預選階段從失效種子節(jié)點局部入手,將節(jié)點可替代度的大小作為備選替補節(jié)點的篩選依據(jù)為失效種子節(jié)點構建替補列表,具體步驟如下:

1) 確定節(jié)點可替代度的計算范圍

算法只需要對與失效節(jié)點含有關聯(lián)的其他節(jié)點進行遍歷計算即可,這個關聯(lián)是指與失效種子節(jié)點含有公共一階后繼節(jié)點的所有非種子節(jié)點,將滿足這種關聯(lián)關系的所有節(jié)點組成集合Q,該集合即為網(wǎng)絡節(jié)點可替代度的計算范圍,這樣便有效地縮小了節(jié)點的篩選范圍,避免了對網(wǎng)絡所有節(jié)點均進行遍歷的冗余計算問題。

2) 進行節(jié)點可替代度計算

采用式(3)所給出的節(jié)點可替代度計算方法,對步驟1)中所得節(jié)點集Q中所有節(jié)點進行遍歷計算,并記錄備選節(jié)點的可替代度值大小。

3) 為失效種子節(jié)點構建替補列表

替補列表容量過大可能會存在局部替代效果較差的節(jié)點進入替補列表,影響最終替補節(jié)點質(zhì)量,且會導致算法在終選階段存在冗余計算;容量過小則可能會導致替代效果較好的節(jié)點被過濾掉。綜上所述,算法在預選階段啟發(fā)式地選取步驟2)中計算所得可替代度值最大的前50個節(jié)點為失效節(jié)點構建替補列表List。

3.2 篩選最終替補種子節(jié)點

定義4邊際效應?:節(jié)點u的邊際效應是指將其加入種子節(jié)點集S中,所能帶來的影響力增量?S(u),

在算法預選階段中,已經(jīng)獲取了具有特定區(qū)域節(jié)點高覆蓋率的備選替補節(jié)點,為保證替補種子節(jié)點加入原種子節(jié)點集之后仍具有較高的網(wǎng)絡全局影響力,以繼續(xù)實現(xiàn)影響力最大化的最初目標,在終選階段,基于貪心算法思想,通過計算備選替補節(jié)點的邊際效應,進一步篩選出能夠使網(wǎng)絡全局影響力到達最大化的最優(yōu)種子節(jié)點組合。

傳統(tǒng)方法計算某一節(jié)點邊際效應通常是將該節(jié)點加入已有種子節(jié)點集中,然后通過模擬實驗,計算新種子節(jié)點集的影響范圍增量,此增量即為該節(jié)點邊際效應值。該方法由于每計算一個節(jié)點的邊際效應都要進行R次信息擴散模擬實驗才可得出最終結(jié)果,具有極高的復雜程度。對此本文采用一種新的節(jié)點邊際效應計算方法,以空間換時間的策略,首先將備選替補節(jié)點在時序圖上進行信息模擬擴散傳播,并讀取每個節(jié)點的影響范圍,例如當前種子集S的影響節(jié)點集合為W={A,B,C,D},備選替補節(jié)點u的影響節(jié)點集為U={B,E,F},則只需要計算差集U-W={E,F},并統(tǒng)計差集中元素個數(shù)即可得出節(jié)點u的邊際效應,這樣便有效地將節(jié)點邊際效應計算的時間復雜度降低到了O(Rn)+O(1),其中R表示共進行R次節(jié)點影響范圍實驗模擬,n表示節(jié)點數(shù)。

算法TSSM偽代碼及時間復雜度分析如下:

代碼第1行表示將替補種子節(jié)點集初始化為空集;第2至7行表示獲取節(jié)點計算范圍;第8至10行表示對備選節(jié)點進行可替代度的遍歷計算;第11至14行表示選取50個可替代度值最大的點構建替補列表;第15至17行表示對替補列表中備選節(jié)點進行邊際效應的計算,第18行表示選定邊際效應值最大的節(jié)點為最終的替補節(jié)點,第19、20行分別表示將篩選出替補種子節(jié)點加入種子節(jié)點集與替補節(jié)點集合中。其中構建待遍歷節(jié)點集合Q的時間復雜度為O(n2)。遍歷計算集合Q中所有節(jié)點的可替代度時間復雜度為O(n3);篩選可替代度值最大的50個節(jié)點構建替補列表的時間復雜度為O(nlog(n));模擬所有候選種子節(jié)點的影響范圍時間復雜度為O(Rn),R表示節(jié)點影響范圍實驗模擬次數(shù),利用本文所提出的影響力并集方法計算替補列表中備選替補節(jié)點的邊際效應的時間復雜度為O(1);篩選出最終替補種子節(jié)點時間復雜度為O(n),故算法TSSM的時間復雜度為O(n(n+n2+log(n)+R)。

4 實驗與分析

4.1 實驗設置

1) 實驗環(huán)境。操作系統(tǒng)Windows 10,處理器Intel Core i5-6300HQ ,內(nèi)存8 G,編程語言Python 3.0,編程環(huán)境Pycharm。

2) 實驗數(shù)據(jù)。本實驗選取了2個不同規(guī)模的時序網(wǎng)絡數(shù)據(jù)集,具體數(shù)據(jù)信息見表1所示。

表1 實驗數(shù)據(jù)信息Tab.1 Experimental data information

Digg數(shù)據(jù)集記錄了社交新聞網(wǎng)站Digg某段時間內(nèi)用戶間相互評論回復的信息;

Mathoverflow數(shù)據(jù)集是根據(jù)Mathoverflow網(wǎng)站上的問答信息生成的社交網(wǎng)絡。

4.2 實驗內(nèi)容

定義5區(qū)域節(jié)點覆蓋率C:替補種子節(jié)點能夠成功激活原失效種子節(jié)點影響范圍內(nèi)的節(jié)點的比率,

其中,Scover表示原種子節(jié)點影響節(jié)點集,S'cover表示替補節(jié)點影響節(jié)點集。

本實驗從替補種子節(jié)點的區(qū)域節(jié)點覆蓋率和替補種子節(jié)點加入原種子節(jié)點集所組成的新種子節(jié)點集的網(wǎng)絡全局影響力兩方面,去衡量不同算法所得替補種子節(jié)點質(zhì)量的優(yōu)劣。除本文所提算法TSSM外,分別復現(xiàn)以下幾種算法作為實驗對比算法。

GSG算法[10]:從網(wǎng)絡所有剩余非種子節(jié)點中,基于貪心算法選出能夠使網(wǎng)絡全局影響力達到最大的替補種子節(jié)點。

P-S算法[11]:在選擇種子節(jié)點的同時便從剩余網(wǎng)絡節(jié)點中選出t個替補節(jié)點。

SABS算法[12]:將失效種子節(jié)點的鄰居節(jié)點與網(wǎng)絡中一定數(shù)量最大度的節(jié)點一起構成后繼節(jié)點集,然后利用模擬退火的方法處理后繼結(jié)點與原種子節(jié)點的最優(yōu)組合問題,以獲取最終的新種子節(jié)點集。

實驗中采用文獻[7]所給出的時序圖信息傳播模型及大規(guī)模時序圖種子節(jié)點挖掘算法CHG,在2個數(shù)據(jù)集上均預先選定出50個原始種子節(jié)點,其中失效種子節(jié)點的選取為每次從種子節(jié)點集中隨機抽取t(t=2,4,6,8,10)個不放回,直至將種子節(jié)點集全部抽取為空或剩余種子節(jié)點數(shù)不夠一次抽取則完畢,其中每次抽取都要挖掘其替補節(jié)點并計算區(qū)域節(jié)點覆蓋率與新種子節(jié)點集的網(wǎng)絡全局影響力,最終取數(shù)次實驗結(jié)果的平均值作為最終結(jié)果。

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

1) 替補種子節(jié)點區(qū)域節(jié)點覆蓋率

區(qū)域節(jié)點覆蓋率是指讓替補種子節(jié)點在基于時序圖的信息傳播模型下進行信息傳播,其最終能夠影響到的節(jié)點范圍與原失效種子節(jié)點影響節(jié)點范圍的重合程度,用以去測評替補種子節(jié)點對特定節(jié)點的激活率。4種算法在不同數(shù)據(jù)集下所得替補種子節(jié)點的特定區(qū)域節(jié)點覆蓋率實驗結(jié)果如圖3所示。

圖3 替補種子節(jié)點區(qū)域節(jié)點覆蓋率Fig.3 Substitute seed node area node coverage

在數(shù)據(jù)集Digg下,算法TSSM所得替補種子節(jié)點區(qū)域節(jié)點覆蓋率平均達到0.8左右,算法SABS處于0.4～0.5之間,算法GSG與P-S所得替補種子節(jié)點的區(qū)域節(jié)點覆蓋率最低,大致在0.2～0.3。4種算法在該數(shù)據(jù)集下都表現(xiàn)出了相對較好的效果,這是因為數(shù)據(jù)集Digg所抽象表示出的時序圖是較稠密的,邊點比值較高,節(jié)點間聯(lián)系較多,這樣節(jié)點被激活的潛在可能性就更大。相反,數(shù)據(jù)集Mathoverflow所對應的時序圖屬于稀疏圖,邊點比值較低,其中算法TSSM所得替補種子節(jié)點區(qū)域節(jié)點覆蓋率處于0.6～0.7水平,算法SABS區(qū)域節(jié)點覆蓋率在0.2～0.3左右,而算法GSG與P-S區(qū)域節(jié)點覆蓋率較低,分別處于0.2與0.1之下水平。

盡管在不同稀疏性的數(shù)據(jù)集下,算法TSSM挖掘得到的替補種子節(jié)點區(qū)域節(jié)點覆蓋率有所波動,但仍處于較高水平,這是因為算法TSSM在預選階段從失效種子節(jié)點入手,采用局部選點的策略,利用節(jié)點的可替代度篩選出備選替補節(jié)點,故其對原失效種子節(jié)點影響范圍內(nèi)的節(jié)點具有較高的激活率。算法SABS所得替補種子節(jié)點具有一定水平的區(qū)域節(jié)點激活率,但仍遠低于算法TSSM,這是因為該算法直接選取失效種子節(jié)點的鄰居節(jié)點為備選替補節(jié)點,其并未考慮時序圖中信息傳播的時序性,導致算法最終所得替補節(jié)點對原失效種子節(jié)點影響范圍內(nèi)的節(jié)點的激活率不高。算法GSG與P-S選取替補種子節(jié)點的原則是保證網(wǎng)絡全局具有較高的影響力,并沒有考慮替補節(jié)點對特定區(qū)域節(jié)點的激活性,替補節(jié)點與失效種子節(jié)點在網(wǎng)絡拓撲結(jié)構上具有很大的不相關性,故其整體區(qū)域節(jié)點覆蓋率較低。

2) 替補種子節(jié)點網(wǎng)絡全局影響力

4種算法在2個數(shù)據(jù)集下所得替補種子節(jié)點加入原種子節(jié)點集后,所構成的新種子節(jié)點集的網(wǎng)絡全局影響力實驗結(jié)果如圖4所示。

圖4 替補種子節(jié)點網(wǎng)絡全局影響力Fig.4 Substitute seed node network global influence range

圖中R(S)表示原始種子節(jié)點集影響到的最多節(jié)點數(shù),可以看到在2幅實驗結(jié)果圖中,4種算法所得替補種子節(jié)點的網(wǎng)絡全局影響力均隨著失效種子節(jié)點數(shù)的增多而下降,這是因為原始種子節(jié)點集是網(wǎng)絡中可以產(chǎn)生最優(yōu)傳播效果的節(jié)點組合,盡管替補節(jié)點可以彌補因部分種子節(jié)點失效所導致的傳播效果方面的損失,但仍不能與原始種子節(jié)點的組合效果相媲美,故各算法與原始種子節(jié)點集傳播效果之間的差距均隨著失效種子節(jié)點數(shù)的增多而增大。其中2個數(shù)據(jù)集下全局貪心算法GSG均表現(xiàn)出最好效果,這一點是與理論預期相符的。相比于算法GSG,算法TSSM在數(shù)據(jù)集Digg下對于5個不同數(shù)量替補種子節(jié)點,新種子節(jié)點集的影響范圍分別下降了1.4%、1.6%、1.8%、1.7%、2.1%;在數(shù)據(jù)集Mathoverflow下,算法TSSM相比于GSG所得替補種子節(jié)點全局影響范圍分別下降了1.5%、1.9%、2.2%、2.9%、3.4%。

可見算法TSSM所得替補種子節(jié)點的網(wǎng)絡全局影響力已經(jīng)能夠達到與貪心算法GSG十分相近的水平。算法SABS由于構建候選替補節(jié)點集的方式不夠準確,故導致了最終所得替補種子節(jié)點的網(wǎng)絡全局影響力下降較大。預選式算法P-S的設計思想是無論任何一個種子節(jié)點缺失都會選擇預先影響力排名最好的節(jié)點,但由于種子節(jié)點集是影響力最優(yōu)組合,其中某一節(jié)點缺失都會影響節(jié)點的組合效果,此時按預先影響力排名替補選取種子節(jié)點已經(jīng)不是效果最優(yōu)的節(jié)點組合,這是算法P-S所得替補種子節(jié)點網(wǎng)絡全局影響力下降的原因所在。

3) 算法運行時間對比

4種算法在2個數(shù)據(jù)集上挖掘獲取10個替補種子節(jié)點的運行時間如表2所示。

表2 算法運行時間Tab.2 Running time of each algorithms

算法TSSM在設計的過程中,首先將節(jié)點可替代度計算的范圍由網(wǎng)絡全局節(jié)點縮小到與失效節(jié)點含有公共一階后繼節(jié)點的節(jié)點集Q,并通過計算啟發(fā)式地選取可替代度較大的前50個節(jié)點構建替補列表,極大地縮小了算法在第二階段節(jié)點邊際效應的計算范圍,這是算法提高時間效率的主要原因。算法GSG基于貪心算法思想且在算法中并未利用到邊際效應的子模特性[5],故其時間復雜度較大。算法SABS為追求新種子節(jié)點集在網(wǎng)絡全局影響力上具有最優(yōu)效果,后期采用模擬退火的方法篩選最終替補節(jié)點,因此付出了較高的時間代價。相反,預選式算法P-S在運行時間上具有極高的效率,但卻導致新種子節(jié)點集犧牲了較大影響力。

綜上所述,算法GSG所挖掘出的替補種子節(jié)點具有較高的網(wǎng)絡全局影響力,但其在特定區(qū)域節(jié)點的激活上表現(xiàn)出的效果較差,同時算法時間復雜度較高,該算法無法高效地適用于大規(guī)模網(wǎng)絡數(shù)據(jù)。算法SABS與P-S在區(qū)域節(jié)點覆蓋率與網(wǎng)絡全局影響力兩方面表現(xiàn)出的效果均一般,而算法TSSM在以上兩方面均表現(xiàn)出良好效果,挖掘所得替補種子節(jié)點在保證具有較高特定節(jié)點激活率的同時,依舊能夠在網(wǎng)絡全局影響力方面達到較高水平,且算法時間效率可觀,可用于解決大規(guī)模時序圖中替補種子節(jié)點挖掘問題。

5 結(jié)論

為解決時序圖中種子節(jié)點失效問題,本文提出了時序圖兩階段替補種子節(jié)點挖掘算法TSSM。算法在啟發(fā)式預選階段從失效種子節(jié)點局部入手,定義了節(jié)點可替代度概念,并將其作為選點依據(jù)為失效種子節(jié)點集構建替補列表。在貪心式終選階段,從網(wǎng)絡全局影響力最優(yōu)化角度出發(fā),通過計算備選替補節(jié)點邊際效應以確定最終的替補種子節(jié)點。通過實驗分析驗證,算法TSSM挖掘所得替補種子節(jié)點可替代性較高,其影響力在保證對特定區(qū)域節(jié)點高覆蓋率的同時,依舊能夠維持較高的網(wǎng)絡全局影響力,算法表現(xiàn)出更好的準確性與可擴展性。在未來的工作中將會考慮進一步結(jié)合節(jié)點激活成本、耗費時間、不同信息類型等更多的實際因素,研究如何進行替補種子節(jié)點的挖掘。