時間傳播網(wǎng)絡(luò)中受影響頂點的預(yù)測

林天巧,趙 雷

(蘇州大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,江蘇 蘇州 215006)

0 概述

受影響頂點預(yù)測是信息傳播研究的一個基本問題,在廣告推薦、流行病預(yù)測和社交網(wǎng)絡(luò)的信息傳播等研究中都有廣泛的應(yīng)用。對于廣告商而言,在廣告發(fā)布后需要獲知被該廣告影響的用戶,從而進行廣告評估,制定營銷策略。在流行性疾病和計算機病毒傳播中,需要快速確認并處理感染者,從而控制病毒傳播。但由于信息傳播具有隨機性和不確定性,有效預(yù)測出受影響者較為困難,因此本文將受影響頂點預(yù)測與頂點狀態(tài)驗證相結(jié)合來預(yù)測發(fā)現(xiàn)受影響頂點,從而確定信息的擴散范圍。但頂點狀態(tài)驗證需要對頂點的屬性進行分析,這會耗費大量計算資源,且在許多應(yīng)用中允許的驗證次數(shù)往往是有限的。

本文研究時間傳播網(wǎng)絡(luò)(Temporal Diffusion Network,TDN)中受影響頂點的預(yù)測問題。首先給出受影響頂點預(yù)測問題的形式化定義,然后設(shè)計基于頂點受影響概率的啟發(fā)式預(yù)測算法IPH,并在此基礎(chǔ)上,結(jié)合廣度優(yōu)先遍歷(Breath First Search,BFS)頂點選擇策略進一步提出相鄰頂點受影響概率啟發(fā)式預(yù)測算法AIPH,最后在模擬數(shù)據(jù)集和真實數(shù)據(jù)集上進行實驗。

1 研究現(xiàn)狀

影響是通過接觸而發(fā)生和傳播的,如社交網(wǎng)絡(luò)中信息的發(fā)布和對信息的評論、回復(fù)、轉(zhuǎn)發(fā)等就屬于一種影響的發(fā)生和傳播。當接觸具有明顯的時間特征如隨時間改變、存在時間間隔等時,接觸可被抽象為時間圖[1]中的信息傳播,即TDN,研究者據(jù)此研究受影響頂點預(yù)測問題。通過用戶行為分析[2]、傳播概率推測[3]和傳播網(wǎng)絡(luò)推測[4-6]等方法,能夠預(yù)測時間傳播網(wǎng)絡(luò)中各邊的傳播概率。

圖1是一個TDN的示例,圖中的邊表示接觸,如邊(A,B,1,2)為A在時間1與B之間延遲為2的一次接觸,P1～P18為預(yù)測得到的邊上的傳播概率。由于信息安全與用戶隱私保護等原因,在TDN中只記錄用戶之間的接觸并不記錄具體傳播內(nèi)容。

圖1 TDN示例

目前關(guān)于受影響頂點預(yù)測問題的研究工作主要分為遍歷抽樣方法和機器學(xué)習(xí)預(yù)測方法。遍歷抽樣方法(如隨機游走[7-8]和BFS[8-9]等)依據(jù)網(wǎng)絡(luò)結(jié)構(gòu)進行頂點選擇,但未利用信息傳播知識,不能有效地預(yù)測發(fā)現(xiàn)受影響頂點;機器學(xué)習(xí)預(yù)測方法[5,10-11]利用邏輯回歸算法等在傳播網(wǎng)絡(luò)中根據(jù)歷史傳播數(shù)據(jù)預(yù)測頂點影響力和信息的最終擴散范圍,但學(xué)習(xí)復(fù)雜度較高不能用于大圖,并且容易出現(xiàn)過擬合現(xiàn)象。上述方法可以用于解決一部分具有代表性的圖中信息傳播的影響預(yù)測問題,如影響力最大化問題[9-15],但TDN中受影響頂點的預(yù)測問題仍然存在以下難點:

1)受影響頂點預(yù)測并非影響力最大化問題。在受影響頂點預(yù)測和部分影響力最大化問題中,雖然都涉及頂點受影響概率計算,但影響力最大化問題是利用頂點受影響概率計算得到頂點影響力后需要解決的頂點組合最優(yōu)問題,而受影響頂點預(yù)測則是利用頂點受影響概率計算受影響頂點到其他頂點的聯(lián)合概率,且在頂點狀態(tài)驗證后需要迭代更新候選集合中頂點的受影響概率。因此,影響力最大化問題研究成果只能部分應(yīng)用于受影響頂點預(yù)測中。

2)TDN中受影響頂點預(yù)測必須滿足圖中信息傳播的時間約束,即頂點在獲得信息后才能向其他頂點傳播信息。因此,預(yù)測頂點間能否產(chǎn)生影響并非通過簡單的連通性計算就能完成。

3)在靜態(tài)傳播網(wǎng)絡(luò)中準確計算頂點受影響概率是#P-hard問題[9],在TDN中該問題仍然是#P-hard問題。由于TDN(如社交網(wǎng)絡(luò))通常具有頂點用戶數(shù)量大、信息更新速度快等特性,因此現(xiàn)有算法難以有效預(yù)測出受影響頂點。

受影響頂點預(yù)測是信息傳播中有廣泛應(yīng)用場景的基本問題,如廣告評估、疾病傳播控制、輿論分析等都涉及受影響頂點的預(yù)測發(fā)現(xiàn)。傳播概率推測[3]、傳播網(wǎng)絡(luò)推測[4-6]、影響力最大化問題[9-15]、傳播模型研究[3,5,10,16-19]等研究成果可用于信息傳播預(yù)測的研究。IC模型和LT模型是信息傳播預(yù)測中最主要的2個預(yù)測模型[14-15]。由于信息傳播隨時間改變,GOMEZ等人基于IC模型提出了NETINF[3]、NETRATE[5]和INFOPATH[17]模型來推測傳播網(wǎng)絡(luò)以及邊上傳播概率。隨著時間圖[1]研究的推進,對于時間圖上路徑問題[20]的研究也不斷出現(xiàn)?；谏鲜龀晒?本文在時間傳播網(wǎng)絡(luò)中研究受影響頂點預(yù)測問題。

影響力最大化問題[9-15]是信息傳播預(yù)測研究中的熱點問題,該問題的求解目標是:對于給定頂點數(shù)k,從傳播網(wǎng)絡(luò)中求得使預(yù)期受影響頂點最多的k個頂點組合。該問題由頂點影響力評估和頂點組合最優(yōu)2個問題組成,這2個問題都是NP-hard問題,其中頂點組合最優(yōu)問題是影響力最大化問題的核心。文獻[9]通過MIA模型進行頂點選擇,在計算頂點影響力時基于MIA模型使用最大傳播路徑MIP近似計算頂點影響力。文獻[11]則不使用傳播模型直接學(xué)習(xí)頂點影響力,并利用梯度下降法進行頂點選擇。雖然在受影響頂點預(yù)測和一些影響力最大化問題研究中都涉及計算頂點受影響概率,但這2個問題存在明顯差異:在影響力最大化問題中,頂點影響力用頂點期望受影響頂點數(shù)表示,而受影響頂點預(yù)測需要計算受影響頂點到待計算頂點的聯(lián)合概率,并且受影響頂點預(yù)測在頂點驗證后需要更新候選集,而影響力最大化問題則需要解決頂點組合最優(yōu)問題。因此,影響力最大化問題的研究成果可以部分應(yīng)用于受影響頂點預(yù)測中,但并不完全適用。

本文對受影響頂點預(yù)測問題研究的目標是在有限的k次驗證中盡量多地發(fā)現(xiàn)受影響頂點,主要工作如下:

1)根據(jù)文獻[21]在靜態(tài)傳播網(wǎng)絡(luò)中提出的Inclusion-Exclusion影響力計算方法,提出基于IC模型[15]的TDN頂點受影響概率計算方法與跳數(shù)受限近似(Hop Limited Approximative,HLA)計算方法。

2)根據(jù)HLA方法提出基于頂點受影響概率的受影響概率啟發(fā)式預(yù)測算法IPH,用以預(yù)測TDN中信息傳播的受影響頂點。同時利用提出的IPC算法構(gòu)造可達頂點構(gòu)成的候選集合,并使用CSU候選集更新算法來更新頂點狀態(tài)驗證后的候選集合。

3)IPH算法雖然能夠在驗證次數(shù)較少時有效預(yù)測發(fā)現(xiàn)受影響頂點,但當驗證次數(shù)k較大時,該方法準確率將較低。為解決該問題,本文結(jié)合BFS算法頂點選擇策略,在IPH算法基礎(chǔ)上提出相鄰頂點受影響概率啟發(fā)式預(yù)測算法AIPH。

由于信息傳播的隨機性,抽樣與圖遍歷算法相對于機器學(xué)習(xí)方法[13]更適用于受影響頂點預(yù)測。文獻[7]比較了若干抽樣算法的性能,并發(fā)現(xiàn)隨機游走(Randow Walk,RW)算法和Forest Fire算法的效果最好。信息傳播存在廣度傳播特征,BFS相對其他遍歷算法更能有效預(yù)測發(fā)現(xiàn)受影響頂點。因此,本文在TDN中預(yù)測受影響頂點時,將BFS算法和隨機游走算法作為實驗對比算法。

2 相關(guān)定義

2.1 時間傳播網(wǎng)絡(luò)

信息通過接觸而發(fā)生傳播,但接觸隨時間改變且存在時間間隔,因此,本文將接觸構(gòu)成的傳播網(wǎng)絡(luò)定義為時間傳播網(wǎng)絡(luò)(TDN),TDN中每一條邊代表一次接觸。

定義1(時間傳播網(wǎng)絡(luò)) 時間傳播網(wǎng)絡(luò)G={V,E},V是頂點集合,E是邊集。邊e=(u,v,t,d)∈E表示頂點u通過時間t時開始延遲為d的邊e向頂點v傳播信息。邊上傳播概率ξ(e)為u通過邊e對v影響的概率,0<ξ(e)<1。到達時間Tv=t+d為v的接收時間,頂點v在Tv之后才能向其他頂點傳遞信息。

由于信息傳播是有向的,因此時間傳播網(wǎng)絡(luò)G為有向圖。在TDN中頂點間可能存在重邊,如圖1中邊(A,C,2,1)和(A,C,2,3),這表示一個頂點多次向另一頂點傳播信息。通過用戶行為分析[2]、傳播概率推測[3]和傳播網(wǎng)絡(luò)推測[4-6]能夠推測出TDN中各邊的信息傳播概率,因此,本文在受影響頂點預(yù)測時將邊上傳播概率ξ(e)作為已知參數(shù)進行計算。

信息在TDN中傳播需要滿足時間約束條件:頂點在獲得信息后才能向其他頂點傳播信息,因此,TDN中信息傳播的路徑為滿足時間約束條件的時間傳播路徑,其定義如下:

定義2(時間傳播路徑) 在給定的時間傳播網(wǎng)絡(luò)G={V,E}中,時間傳播路徑是一邊序列P=<(v1,v2,t1,d1),(v2,v3,t2,d2),…,(vk-1,vk,tk,dk)>,?(vi,vi+1,ti,di)∈P(1≤i

如圖1中<(B,D,3,2),(D,F,5,2),(F,I,8,3)>是B到I的一條時間傳播路徑,但B不能通過<(B,E,4,3),(E,F,9,3),(F,I,8,3)>將信息傳遞給I,因為邊(F,I,8,3)不符合時間約束。

在信息傳播中,信息通過路徑從傳播網(wǎng)絡(luò)的少量初始受影響頂點開始傳播影響其他頂點,從而擴大信息影響范圍。在IC模型中,頂點被信息影響后將保持受影響狀態(tài)而不會改變,頂點狀態(tài)為布爾值:受影響,不受影響。布爾函數(shù)f(v,γ,T)用于表示信息傳播后TDN中頂點v在時間T時對信息γ的受影響狀態(tài)。時間傳播網(wǎng)絡(luò)G中滿足f(v,γ,T)=1的頂點構(gòu)成T時受影響頂點集合S。

2.2 問題定義

2.3 TDN中頂點受影響概率計算

由于受影響概率越大越易成為受影響頂點,因此本文使用頂點受影響概率作為預(yù)測依據(jù)。由于TDN中頂點受影響概率隨時間T和受影響頂點集合I改變,因此TDN中頂點受影響概率定義為:

定義4(頂點受影響概率) 時間傳播網(wǎng)絡(luò)中頂點受影響概率φ((I,v)|T)為時間T時頂點v被受影響頂點集合I中頂點影響的概率。

假設(shè)P=為時間傳播網(wǎng)絡(luò)G中頂點u到頂點uα的一條時間傳播路徑?；贗C模型,時間傳播路徑P的傳播概率為:

(1)

傳播路徑的傳播概率計算是頂點受影響概率計算的基礎(chǔ)。當候選頂點只有一條時間傳播路徑時,頂點的受影響概率等于該路徑的傳播概率。

當從受影響頂點到待計算頂點有多條時間傳播路徑時,可以將其分為重疊傳播路徑和無重疊傳播路徑。無重疊傳播路徑的定義如下:

定義5(無重疊傳播路徑) 在時間傳播網(wǎng)絡(luò)G中,對于到達頂點v的時間傳播路徑{P1,P2,…,Pl},若任意2條路徑除了起點和終點v并沒有其他相同頂點,則到頂點v的路徑為無重疊傳播路徑。

假設(shè)受影響頂點集合I在時間T內(nèi)到頂點v的時間傳播路徑{P1,P2,…,Pl}為無重疊傳播路徑。由于IC模型中無重疊傳播路徑之間相互獨立,因此頂點v的受影響概率為:

(2)

其中,δ(Pk)為通過式(1)計算得到的受影響頂點在時間T內(nèi)到頂點v的時間傳播路徑Pk的傳播概率。

在影響力最大化問題許多研究中,計算頂點受影響概率時假設(shè)傳播路徑之間都是相互獨立的。如DynaDiffuse[10],其在邊和傳播路徑都相互獨立的假設(shè)下,在連續(xù)時間上計算動態(tài)傳播網(wǎng)絡(luò)中頂點影響力并解決影響力最大化問題。文獻[21]介紹了靜態(tài)傳播網(wǎng)絡(luò)中頂點受影響概率的準確計算方法。該文提出的Inclusion-Exclusion方法滿足IC模型的邊獨立而路徑不獨立的假設(shè)。但是該方法是在靜態(tài)傳播網(wǎng)絡(luò)中提出的,而在TDN中,由于存在時間因素,此計算方法并不完全適用。本文基于Inclusion-Exclusion計算思想,在TDN中計算任意頂點的受影響概率,具體過程如下:

在TDN中,每個頂點存在多個受影響時間Ti(接收時間Tv)。假設(shè)已知頂點v在時間Ti時的受影響概率為φ((I,v)|Ti),而頂點v在Ti+1時(時間傳播網(wǎng)絡(luò)G中頂點下一信息接受時間)從入邊相鄰頂點vx(vx∈Nin(v))經(jīng)邊e(vx,v,tx,dx)獲得信息,tx+dx=Ti+1。由于邊之間相互獨立,因此頂點v在時間段Ti到Ti+1的受影響概率增量φ((I,v)|(Ti,Ti+1))和v在Ti+1時的受影響概率可以通過式(3)和式(4)計算得到,頂點v最早受影響時間T1時的受影響概率可通過式(5)計算得到。其中,邊e(vx,v,tx,dx)為T1時到達頂點v的入邊,邊e(vx,v,tx,dx)滿足tx+dx=T1。

φ((I,v)|(Ti,Ti+1))=1-∏(1-φ((I,vx)|Tx)ξ(e(vx,v,tx,dx)))

(3)

φ((I,v)|Ti+1)=φ((I,v)|Ti)+(1-φ((I,v)|Ti))φ((I,v)|(Ti,Ti+1))

(4)

φ((I,v)|(T1))=1-∏(1-φ((I,vx)|Tx)·ξ(e(vx,v,tx,dx)))

(5)

在利用式(3)～式(5)計算頂點受影響概率時,需要遞歸計算前一狀態(tài)的受影響概率直到vx為受影響頂點。在信息傳播過程中,由于頂點不能經(jīng)其他頂點再影響自己,因此在遞歸計算時要避免環(huán)路的出現(xiàn)。在計算頂點受影響概率過程中,若頂點只有一條時間傳播路徑或是無重疊傳播路徑頂點時,可利用式(1)和式(2)計算頂點受影響概率。

2.4 受影響概率近似計算

在TDN中,為計算頂點的受影響概率,從受影響頂點到待計算頂點之間所有時間傳播路徑上經(jīng)過頂點的受影響概率需要預(yù)先求得。由定理1可知,在TDN中計算頂點受影響概率是#P-hard問題。

定理1在時間傳播網(wǎng)絡(luò)中計算頂點受影響概率是#P-hard問題。

證明:在時間傳播網(wǎng)絡(luò)中查找兩頂點間所有時間傳播路徑,相當于在普通有向圖中找出兩頂點間所有路徑并剔除其中不符合時間約束的路徑。由于在有向圖中查找統(tǒng)計兩頂點間所有路徑是#P-complete問題[22],因此在時間傳播網(wǎng)絡(luò)中查找兩頂點之間所有時間傳播路徑是#P-hard問題。而在時間傳播網(wǎng)絡(luò)中計算頂點受影響概率時,待計算頂點和受影響頂點間所有傳播路徑需要被遍歷,因此,在時間傳播網(wǎng)絡(luò)中計算頂點受影響概率是#P-hard問題。

在TDN中,當每條邊具有相同的傳播概率ξ時,若頂點u到頂點v有2條時間傳播路徑P1和P2,則δ(P1)=ξ|P1|,δ(P2)=ξ|P2|,此時若|P1|>|P2|,則δ(P1)<δ(P2)。因此,可以得到如下結(jié)論:

結(jié)論1在TDN中,如果每條邊具有相同的傳播概率,則跳數(shù)較小路徑的傳播概率在終點受影響概率的計算中占較大比例。

結(jié)論2在TDN中,如果每條邊具有相同的傳播概率,則各跳數(shù)路徑中路徑條數(shù)都更多的頂點有更大的受影響概率。

基于以上結(jié)論,本文提出跳數(shù)受限近似(HLA)算法來近似計算頂點受影響概率,定義如下:

定義6(跳數(shù)受限近似算法) 對于給定的跳數(shù)限制參數(shù)h,未受影響頂點的受影響概率通過離受影響頂點跳數(shù)小于h的時間傳播路徑近似計算得到。

在計算過程中,為減少計算所需時間,HLA方法使用式(2)近似計算頂點受影響概率,具體過程為:首先找出時間傳播網(wǎng)絡(luò)G中從受影響頂點到待計算頂點h跳內(nèi)無環(huán)時間傳播路徑,然后利用式(2)計算概率作為頂點受影響概率。

雖然在影響力最大化問題中,也有許多近似方法被提出,但大部分是為解決組合最優(yōu)問題而構(gòu)造的,因此,這些方法在受影響頂點預(yù)測中并不十分有效。如PMIA[9]中基于MIA模型使用最大傳播路徑(Maximum Propagation Path,MIP)評估頂點影響力。MIP在受影響頂點預(yù)測中相當于貪心選擇受影響頂點出邊中傳播概率最大的邊的相鄰頂點作為下一驗證頂點。但由于待計算頂點與受影響頂點之間可能存在多條傳播路徑,MIP選擇的頂點并不一定是受影響概率最大的頂點。而利用HLA近似計算選擇頂點時,當h不小于TDN中最長路徑的跳數(shù)時,其選擇的頂點為受影響概率最大的頂點,當h值為一有限值時選擇的頂點仍為受影響概率較大頂點。參數(shù)h的大小是HLA算法有效性與可行性的折中,h值對受影響頂點預(yù)測的影響將在實驗中進行比較。

3 IPH算法

本節(jié)將介紹基于HLA近似算法的受影響概率啟發(fā)式預(yù)測算法IPH。該算法主要由受影響概率計算(Infection Probability Calculation,IPC)算法和候選集合更新(Candidate Set Update,CSU)算法構(gòu)成。在受影響頂點預(yù)測中,候選集合中受影響概率最大的頂點將進行頂點狀態(tài)驗證。

3.1 IPC算法

受影響頂點的可達頂點查找以及受影響概率計算是受影響頂點預(yù)測發(fā)現(xiàn)的重點,本文提出受影響概率計算算法IPC來查找可達頂點并計算受影響概率。對受影響集合I中頂點調(diào)用IPC算法后得到受影響集合I的可達頂點集合即候選集合。

在利用HLA近似算法近似計算頂點受影響概率時需滿足以下條件:1)時間傳播路徑的跳數(shù)不能超過h;2)在IC模型中每個頂點只能被影響一次,因此,每個頂點在時間傳播路徑中最多只能出現(xiàn)一次,所以,候選集合C由從受影響頂點出發(fā)沒有重復(fù)頂點與其他受影響頂點的路徑跳數(shù)小于h的可達頂點構(gòu)成。由于DFS算法在遍歷圖時能夠?qū)⒔?jīng)過的頂點記錄在堆棧中從而避免環(huán)路的出現(xiàn),因此IPC算法基于DFS算法在TDN中查找符合條件的時間傳播路徑。

在根據(jù)HLA近似算法計算頂點受影響概率時,若已知頂點v的受影響概率為φ((I,v)|T),此時若有另一經(jīng)相鄰頂點u到v的傳播路徑且u的受影響概率為φ((I,u)|Tu),那么頂點v的受影響概率為:

φ((I,v)|T)= 1-(1-φ((I,v)|T))×

(1-φ((I,u)|Tu)×ξ(e))

(6)

其中,ξ(e)是u到v的邊的傳播概率。若頂點u為受影響頂點,則式(6)可簡化為:φ((I,v)|T)=1-(1-φ((I,v)|T))×(1-ξ(e))。

算法1為受影響概率計算算法IPC的偽代碼。若得到的可達頂點v不在候選集合C中,則v將加入候選集合C,其受影響概率由式(6)計算得到;若頂點v已經(jīng)在候選集合C中,則其受影響概率根據(jù)式(6)更新計算得到。在候選集合C中將記錄候選頂點各到達時間的受影響概率用于后續(xù)的計算,C.Update()函數(shù)將更新候選集中頂點v在到達時間t+d后各時刻的頂點受影響概率。

算法1受影響概率計算算法IPC

輸入時間傳播網(wǎng)絡(luò)G,邊上傳播概率ξ(E),起始頂點u,頂點u的受影響概率prob(u),開始時間t,結(jié)束時間T,已驗證頂點集合L,候選集合C,跳數(shù)h

輸出候選集合C

1.Stack S={u;t;prob(u)},List Visited_Edges=?;

2.while (S≠? and S.size()

3. (u′,t′,prob(u′))=S.Pop();

4. 獲得頂點u′在t′之后不指向S中頂點的出邊E′;

5. if (E′-(E′∩Visited_Edges)≠?)

6. e(u′,v,t,d)=Earliest(E′-E′∩Visited_Edges);

7. prob(v)=prob(u′,t)*ξ(e);

8. if (v∈C)

9. C.Update(v,prob(v),t + d);

10. prob(v)=1-(1-C.Prob(v))*(1-prob(v));

11. C.Set(v,prob(v));

12. else

13. C.Add(v,prob(v));

14. S.Push({v,t+d,prob(v)}),Visited_Edges.Add(e);

15. else

16. S.Pop();

17.end while

18.return C;

3.2 候選集合更新

在受影響頂點預(yù)測中,由于信息傳播具有隨機性和不確定性,因此需要結(jié)合頂點狀態(tài)驗證來確認受影響頂點,即選擇候選集合C中受影響概率最大的頂點進行頂點狀態(tài)驗證。而經(jīng)過頂點狀態(tài)驗證,候選頂點的受影響概率將會改變,頂點狀態(tài)驗證對候選集合的改變?nèi)缍ɡ?所述。因此在頂點狀態(tài)驗證后需要更新候選集合。

定理2頂點狀態(tài)驗證后,候選集合始終減小。

證明:在時間傳播網(wǎng)絡(luò)中,候選集合C由受影響頂點的所有可達頂點構(gòu)成。在頂點狀態(tài)驗證后,被驗證頂點v將從候選集合中移除。若頂點v是受影響頂點,頂點v的可達頂點受影響概率將增大,但由于v的可達頂點也是原受影響頂點的可達頂點,因此候選集合并不會增大;而若頂點v不是受影響頂點,v可達頂點的受影響概率將減小,受影響概率變?yōu)?的頂點將從候選集合中移除,候選集合進一步減小。因此,頂點狀態(tài)驗證后,候選集合始終減小。

最簡單直接的候選集合更新方法是將驗證頂點v加入已驗證頂點集合L后調(diào)用IPC算法重新計算候選集合。但是該方法較耗計算資源且候選集合C中只有驗證頂點的可達頂點會改變。為提高算法計算效率,本文提出了CSU候選集合更新算法來更新候選集合。

假設(shè)頂點v′是驗證頂點v的可達頂點,v到v′的傳播路徑為{P1,P2,…,Pi}且已知頂點v在各到達時間v.timej時的受影響概率為v.probj,那么頂點v′經(jīng)頂點v被受影響頂點影響的概率可由式(7)計算得到。

(7)

其中,Pi為v.timej后頂點v到v′的時間傳播路徑。

若頂點v被驗證為非受影響頂點,那么頂點v′的受影響概率更新為:

(8)

若頂點v被驗證為受影響頂點,那么頂點v′的受影響概率更新為:

(9)

其中,Pi為頂點v受影響時間后的時間傳播路徑。

在使用HLA近似算法時,由于只有受影響頂點的h跳內(nèi)可達頂點被包含在候選集合C中,因此在頂點狀態(tài)驗證后若頂點被驗證為受影響頂點,則需要將不在候選集合C中的驗證頂點h跳內(nèi)可達頂點加入候選集合C。

CSU候選集合更新算法的偽代碼如算法2所示。IPC算法可用于計算頂點v各到達時間區(qū)間內(nèi)可達頂點的受影響概率,因此,CSU算法調(diào)用IPC算法查找被驗證頂點v的可達頂點集合C1并計算受影響概率。在獲得集合C1后,利用式(8)和式(9)更新頂點v可達頂點的受影響概率,從而更新候選集合C。在Increase函數(shù)中,不在候選集合C中的可達頂點將加入候選集合C。

算法2候選集合更新算法CSU

輸入時間傳播網(wǎng)絡(luò)G,邊上傳播概率ξ(E),驗證頂點v,結(jié)束時間T,已驗證頂點集合L,候選集合C,跳數(shù)h

輸出候選集合C

2.for ( each (t1,t2,prob(v,t1)) in C.Each(v) )

3. C1=IPC(G,ξ(E),v,t1,prob(v,t1),t2,L,C1,h);

4.end for

5.Decrease(C,C1);

6.if (f (v,γ,T))

7. C2=C1.After(v.InfectedTime );

8. Increase(C,C2);

9. C.Remove(v);

10.return C;

3.3 IPH算法與復(fù)雜度分析

受影響概率啟發(fā)式預(yù)測算法IPH的偽代碼如算法3所示。IPH算法由兩部分構(gòu)成:初始階段和預(yù)測驗證階段。在初始階段,調(diào)用受影響概率計算算法IPC對每個初始受影響頂點查找其可達頂點并計算可達頂點的受影響概率,從而獲得初始候選集合;在預(yù)測驗證階段,受影響概率最大的候選頂點將進行頂點狀態(tài)驗證確定其是否被影響,在驗證之后調(diào)用候選集更新算法CSU來更新候選集合。利用IPH算法將得到k次驗證后的驗證頂點集合L,從而明確哪些頂點確實成為受影響頂點。

算法3受影響概率啟發(fā)式預(yù)測算法IPH

輸出已驗證頂點集合L

3. C=IPC(G,ξ(E),ui,ti,1,T,L,C,h);

4.end for

6. v=C.MaxProb();

7. Node_State(v,γ,T);//頂點狀態(tài)驗證

8. L.Add(v,f(v,γ,T)?v.InfectedTime:-1);

9. C=CSU(G,ξ(E),v,T,L,C,h);//更新候選集合

10.end while

11.return L;

在TDN中,只有在最早開始傳播時間和結(jié)束時間內(nèi)的接觸才能傳播信息,因此,在使用IPH算法預(yù)測受影響頂點前可以對TDN進行時間圖過濾預(yù)處理,即只保留有效時間段內(nèi)的邊,該過程能有效縮短計算時間。

3.4 AIPH算法

在IPH算法中,HLA近似算法被用于計算初始受影響頂點h跳內(nèi)可達頂點的受影響概率,并構(gòu)造候選集合C。在獲得候選集后,受影響概率最大的頂點將進行頂點狀態(tài)驗證。但是隨著頂點逐漸被選擇驗證,候選頂點的受影響概率逐漸趨于相同,同時受影響頂點在候選集合中所占的比例也在逐漸降低,此時使用HLA近似算法計算得到的頂點受影響概率并不能很好地將受影響頂點與非受影響頂點區(qū)分開。因此,IPH算法在驗證次數(shù)k較大時,預(yù)測性能不佳。本文基于BFS算法頂點選擇策略提出相鄰頂點受影響概率啟發(fā)式預(yù)測算法AIPH來解決該問題。AIPH算法與IPH算法的區(qū)別在于:AIPH算法在選擇頂點時只選擇候選集合C中受影響概率最大的受影響頂點的相鄰頂點進行驗證。AIPH算法的候選集合計算與更新與IPH算法相同,因此,其時間復(fù)雜度也相同。

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

本文在真實數(shù)據(jù)集和模擬數(shù)據(jù)集上比較IPH算法、AIPH算法和現(xiàn)有算法在受影響頂點預(yù)測上的性能,對比算法如下:

1)廣度優(yōu)先遍歷算法(BFS)。BFS算法是頂點遍歷中最常用的算法且信息傳播具有廣度傳播特點,因此,選擇BFS算法作為對比算法。

2)隨機游走算法(RW)。隨機游走算法是圖上抽樣算法的代表算法[10],在隨機游走過程中,邊上傳播概率作為隨機游走的概率進行頂點選擇。

3)最大傳播路徑方法(MIP)。PMIA[9]是影響力最大化問題中比較具有代表性的算法,其中的MIP算法可用于受影響頂點預(yù)測。MIP在受影響頂點預(yù)測中等價于貪心選擇傳播概率最大邊的相鄰頂點作為下一驗證頂點。

4)IPH算法。IPH算法利用HLA近似計算頂點受影響概率,因此,用x-IPH表示跳數(shù)h設(shè)為x的IPH算法。

5)AIPH算法。類似于IPH算法,x-AIPH表示跳數(shù)h設(shè)為x的AIPH算法。當h為1時,1-AIPH和1-IPH算法相同,用(A)IPH進行表示。

邊上傳播概率映射:在傳播網(wǎng)絡(luò)中可由用戶行為分析[2],傳播概率推測[3]和傳播網(wǎng)絡(luò)推測[4-6]等研究成果推測邊上傳播概率。本實驗中使用文獻[5,10]中常用的指數(shù)模型進行邊上傳播概率映射,即使用βe-d(T-t)計算TDN邊上傳播概率。

信息傳播模擬:由于信息傳播渠道復(fù)雜等原因,信息傳播在真實環(huán)境中難以跟蹤獲取,因此本實驗在數(shù)據(jù)集上模擬信息傳播。在模擬過程中,隨機選擇若干頂點作為初始受影響頂點,然后以邊上傳播概率映射得到的概率進行傳播,從而獲得信息傳播模擬結(jié)果。傳播模擬結(jié)果將作為受影響頂點預(yù)測實驗的驗證集,而數(shù)據(jù)集和初始受影響頂點集合則作為實驗輸入。

4.1 模擬數(shù)據(jù)集上的實驗分析

本實驗使用文獻[5,11]實驗中使用的3種Kronecker圖生成模擬數(shù)據(jù)集:Random([0∶5;0∶5;0∶5;0∶5]),Hierarchical([0∶9;0∶1;0∶1;0∶9]),Coreperiphery([0∶9;0∶5;0∶5;0∶3])。在構(gòu)造模擬數(shù)據(jù)集時,實驗結(jié)合SNAP中靜態(tài)Kronecker圖生成算法產(chǎn)生1×103個頂點和10×103條邊的模擬時間傳播網(wǎng)絡(luò)。

圖2是已知TDN邊上傳播概率條件下在模擬數(shù)據(jù)集上的實驗結(jié)果。圖中橫坐標R=k/|S|是頂點驗證次數(shù)k與實際受影響頂點數(shù)|S|的比值。圖2(a)～圖2(c)是各算法在不同驗證次數(shù)時召回率的變化曲線,圖2(d)～圖2(f)是各算法在不同驗證次數(shù)時準確率的變化曲線。從召回率圖中可發(fā)現(xiàn)各算法召回率在開始時近似于線性增加,但在召回率超過80%后增長速度明顯下降趨于對數(shù)增長。相較于其他算法,IPH在頂點驗證次數(shù)較大的情況下召回率并不高,但改進后的AIPH算法則有較好的性能,即在k值較大情況下召回率與BFS算法相差無幾。從準確率圖中可發(fā)現(xiàn)IPH算法在準確率上要明顯強于其他算法,當頂點驗證次數(shù)k較小時IPH算法和AIPH算法準確率比其他對比算法高10%～20%。圖2(g)～圖2(i)為準確率與召回率變化圖,從中可以看出,IPH算法和AIPH算法優(yōu)于MIP算法,而MIP算法接近但略優(yōu)于隨機游走算法,BFS算法則性能最差。在k值較小時IPH算法和AIPH算法相差無幾,但AIPH算法在k較大時較穩(wěn)定,因此,AIPH算法能更好地解決受影響頂點預(yù)測問題。對于HLA近似算法參數(shù)值h,從實驗中可發(fā)現(xiàn)較大的h值能夠提高IPH算法和AIPH算法頂點選擇準確性但提高幅度不大,由此可見利用HLA近似算法得到的頂點順序接近于頂點按實際受影響概率排序得到的順序。

在信息傳播預(yù)測中,邊上傳播概率并不一定能夠準確計算得到,圖3為當邊上傳播概率未知(假設(shè)邊上傳播概率均為0.5)時各算法在模擬數(shù)據(jù)集上的結(jié)果。在BFS算法中頂點選擇并不受邊上傳播概率影響,因此,圖2和圖3中BFS算法的結(jié)果是相同的。對于MIP算法,由于邊上傳播概率相同MIP算法隨機從相鄰頂點選擇頂點,因此退化為BFS算法,其實驗結(jié)果確實與BFS算法十分吻合。而對于IPH算法和AIPH算法,雖然準確率有所下降,但相較于其他算法仍有較高的準確率。

圖2 模擬數(shù)據(jù)集邊上傳播概率已知時的召回率和準確率

圖3 模擬數(shù)據(jù)集邊上傳播概率未知時的召回率和準確率

實驗結(jié)果表明,IPH算法和AIPH算法在受影響頂點預(yù)測上有更好的性能,尤其是AIPH算法,其在k較大時準確率和召回率仍略優(yōu)于BFS算法。

4.2 真實數(shù)據(jù)集上的實驗分析

本實驗使用圖數(shù)據(jù)集網(wǎng)站konect (http://konect.uni-koblenz.de/)上的4個數(shù)據(jù)集:Digg,Slashdot,Infectious和Facebook。對于這4個真實數(shù)據(jù)集,需要先進行數(shù)據(jù)補全、傳播模擬等預(yù)處理后再進行受影響頂點預(yù)測。數(shù)據(jù)集的統(tǒng)計信息如表1所示。

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

真實數(shù)據(jù)集上的實驗結(jié)果如圖4所示?？梢钥闯?數(shù)據(jù)集上,IPH算法和AIPH算法相對于其他方法仍有較好的實驗結(jié)果,能準確地預(yù)測受影響頂點。

圖4 真實數(shù)據(jù)集已知邊上傳播概率時的召回率和準確率

5 結(jié)束語

本文將傳播網(wǎng)絡(luò)定義為時間傳播網(wǎng)絡(luò),并研究其中基于IC模型的頂點受影響概率計算方法與受影響頂點預(yù)測方法。針對頂點受影響概率計算這一#P-hard問題,利用HLA算法近似計算頂點受影響概率,提出IPH算法預(yù)測受影響頂點,并結(jié)合BFS策略進一步給出AIPH算法。實驗結(jié)果表明,本文算法能有效預(yù)測受影響頂點。鑒于本文基于IC模型和封閉世界假設(shè)等約束進行研究,下一步將考慮在更少的約束條件下預(yù)測受影響頂點。

[1] HOLME P,SARAMKI J.Temporal Networks[J].Physics Reports,2012,519(3):97-125.

[2] ZHANG Jun,WANG Chaokun,WANG Jianmin,et al.Inferring Continuous Dynamic Social Influence and Personal Preference for Temporal Behavior Prediction[J].Proceedings of VLDB Endowment,2014,8(3):269-280.

[3] GOMEZ R M,LESKOVEC J,KRAUSE A.Inferring Networks of Diffusion and Influence[J].ACM Transac-tions on Knowledge Discovery from Data,2010,5(4):1019-1028.

[4] ABRAHAO B,CHIERICHETTI F,KLEINBERG R,et al.Trace Complexity of Network Inference[C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2013:491-499.

[5] GOMEZ R M,BALDUZZI D,SCH?LKOPF B,et al.Uncovering the Temporal Dynamics of Diffusion Networks[C]//Proceedings of the 28th International Conference on Machine Learning.[S.l.]:International Machine Learning Society,2011:561-568.

[6] RONG Yu,ZHU Qiankun,CHENG Hong.A Model-free Approach to Infer the Diffusion Network from Event Cascade[C]//Proceedings of the 25th ACM Inter-national on Conference on Information and Knowledge Management.New York,USA:ACM Press,2016:1653-1662.

[7] LESKOVEC J,FALOUTSOS C.Sampling from Large Graphs[C]//Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2006:631-636.

[8] MEHDIABADI M E,RABIEE H R,SALEHI M.Sampling from Diffusion Networks[C]//Proceedings of International Conference on Social Informatics.[S.l.]:AAAI,2012:106-112.

[9] CHEN Wei,WANG Chi,WANG Yajun.Scalable Influence Maximization for Prevalent Viral Marketing in Large-scale Social Networks[C]//Proceedings of Inter-national Conference on Social Informatics.New York,USA:ACM Press,2010:1029-1038.

[10] XIE Miao,YANG Qiusong,WANG Qing,et al.DynaDiffuse:A Dynamic Diffusion Model for Continuous Time Constrained Influence Maximization[C]//Pro-ceedings of the 29th AAAI Conference on Artificial Intelligence.[S.l.]:AAAI,2015:346-352.

[11] DU Nan,LIANG Yingyu,Balcan M F,et al.Influence Function Learning in Information Diffusion Networks[C]//Proceedings of International Conference on Machine Learning.Beijing,China:[s.n.],2014:2016-2024.

[12] RODRIGUEZ M G,SCH?LKOPF B.Influence Maximization in Continuous Time Diffusion Networks[J].Cement and Concrete Composites,2012,34(5):684-691.

[13] NAJAR A,DENOYER L,GALLINARI P.Predicting Information Diffusion on Social Networks with Partial Knowledge[C]//Proceedings of the 21st International Conference Companion on World Wide Web.Lyon,France:[s.n.],2012:1197-1204.

[14] GUILLE A.Information Diffusion in Online Social Networks[C]//Proceedings of SIGMOD/PODS’13.New York,USA:[s.n.],2013:31-36.

[15] KEMPE D,KLEINBERG J,TARDOS é.Maximizing the Spread of Influence Through a Social Network[C]//Proceedings of the 9th ACM SIGKDD.New York,USA:ACM Press,2003:137-146.

[16] IWATA T,SHAH A,GHAHRAMANI Z.Discovering Latent Influence in Online Social Activities via Shared Cascade Poisson Processes[C]//Proceedings of SIGKDD’13.New York,USA:ACM Press,2013:266-274.

[17] GOMEZ R M,LESKOVEC J,SCH?LKOPF B.Structure and Dynamics of Information Pathways in Online Media[C]//Proceedings of ACM WSDM Conference.New York,USA:ACM Press,2012:23-32.

[18] 曹玉林,馬建萍.基于微分方程的移動自組網(wǎng)病毒傳播模型研究[J].計算機工程,2017,43(1):172-177.

[19] 曹玖新,吳江林,石 偉,等.新浪微博網(wǎng)信息傳播分析與預(yù)測[J].計算機學(xué)報,2014,37(4):779-790.

[20] WU Huanhuan,CHENG J,HUANG Silu,et al.Path Problems in Temporal Graphs[J].Proceedings of the VLDB Endowment,2013,7(9):721-732.

[21] ZHANG Miao,DAI Chunni,DING C H,et al.Probabilistic Solutions of Influence Propagation on Social Networks[C]//Proceedings of the 22nd ACM International Conference on Information and Knowledge Management.New York,USA:ACM Press,2013:429-438.

[22] VALIANT L G.The Complexity of Enumeration and Reliability Problems[J].SIAM Journal on Computing,1979,8(3):410-421.