基于時(shí)序關(guān)系的社交網(wǎng)絡(luò)影響最大化算法研究

陳晶，祁子怡

（1.燕山大學(xué)信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2.河北省虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004；3.河北省軟件工程重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004）

1 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展，越來(lái)越多的人喜歡通過(guò)社交媒體傳播他們的想法和信息來(lái)影響平臺(tái)中的其他用戶(hù)。如何使分享的信息快速傳播并且影響范圍最廣，已成為社交網(wǎng)絡(luò)分析領(lǐng)域的熱點(diǎn)問(wèn)題。針對(duì)此類(lèi)問(wèn)題，Richardson 等[1]首次提出了影響力最大化問(wèn)題。目前廣泛應(yīng)用的基于靜態(tài)社交網(wǎng)絡(luò)的影響最大化問(wèn)題是通過(guò)在社交網(wǎng)絡(luò)中尋找k個(gè)用戶(hù)作為種子節(jié)點(diǎn)，使信息在特定的傳播模型下，通過(guò)種子節(jié)點(diǎn)在網(wǎng)絡(luò)中盡可能多地影響其他用戶(hù)。

目前，大多數(shù)研究通常將社交網(wǎng)絡(luò)抽象為靜態(tài)圖，簡(jiǎn)化了影響最大化問(wèn)題的研究，忽略了實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)間存在的時(shí)間關(guān)系特性，例如，人們之間相互的電話通信、郵件傳送、交通網(wǎng)絡(luò)和大腦神經(jīng)網(wǎng)絡(luò)等，進(jìn)而造成了影響范圍不準(zhǔn)確的問(wèn)題。在這些網(wǎng)絡(luò)中，節(jié)點(diǎn)之間的聯(lián)系并不會(huì)一直存在，而是只在某個(gè)時(shí)間段或者時(shí)間點(diǎn)存在聯(lián)系，即節(jié)點(diǎn)之間的聯(lián)系是動(dòng)態(tài)的、具有時(shí)序性的。以時(shí)序信息傳送為例，社交網(wǎng)絡(luò)中的用戶(hù)節(jié)點(diǎn)之間更加傾向于在特定的時(shí)間段內(nèi)對(duì)某類(lèi)主題信息進(jìn)行交流和傳播，因此，當(dāng)研究信息在傳播過(guò)程中具有重要作用的用戶(hù)節(jié)點(diǎn)時(shí)，便可通過(guò)研究時(shí)序社交網(wǎng)絡(luò)影響最大化問(wèn)題來(lái)解決。

目前，針對(duì)時(shí)序網(wǎng)絡(luò)的影響最大化研究很少，并且絕大多數(shù)研究集中在使用傳統(tǒng)方法在時(shí)序網(wǎng)絡(luò)上進(jìn)行研究，即實(shí)驗(yàn)環(huán)境是具有時(shí)序特性的數(shù)據(jù)集，而研究方法是傳統(tǒng)的。在此類(lèi)問(wèn)題中，由于時(shí)序社交網(wǎng)絡(luò)中節(jié)點(diǎn)之間的時(shí)序性，節(jié)點(diǎn)間的聯(lián)系狀態(tài)是隨著時(shí)間動(dòng)態(tài)變化的，因此時(shí)序社交網(wǎng)絡(luò)影響最大化問(wèn)題面臨如下挑戰(zhàn)：1) 傳統(tǒng)信息傳播模型由于沒(méi)有考慮網(wǎng)絡(luò)的時(shí)序特性，故無(wú)法被應(yīng)用于時(shí)序社交網(wǎng)絡(luò)；2) 在種子節(jié)點(diǎn)選取過(guò)程中，節(jié)點(diǎn)影響范圍的計(jì)算方式與傳統(tǒng)方式不同。

為解決上述問(wèn)題，本文針對(duì)網(wǎng)絡(luò)的時(shí)序特性，以時(shí)序社交網(wǎng)絡(luò)作為研究對(duì)象，將傳統(tǒng)的信息傳播模型時(shí)序化，并以此為基礎(chǔ)設(shè)計(jì)了時(shí)序社交網(wǎng)絡(luò)兩階段影響最大化（TIM,two-stage impact maximization）算法，該算法將網(wǎng)絡(luò)的時(shí)序特性完全融入了種子節(jié)點(diǎn)的選取過(guò)程中，并分別通過(guò)時(shí)序啟發(fā)階段和時(shí)序貪心階段進(jìn)行研究。在時(shí)序啟發(fā)階段，結(jié)合網(wǎng)絡(luò)的時(shí)序特性，定義了新的節(jié)點(diǎn)影響力估算方式，并選出估計(jì)值較大的節(jié)點(diǎn)作為備選節(jié)點(diǎn)；在時(shí)序貪心階段，優(yōu)化了節(jié)點(diǎn)間邊際效益的計(jì)算方法，并從備選節(jié)點(diǎn)中精準(zhǔn)地選取種子節(jié)點(diǎn)。該算法充分考慮了節(jié)點(diǎn)間的時(shí)序特性，時(shí)間復(fù)雜度低，影響范圍與貪心（greedy）算法相近，可以高效地解決具有時(shí)序特性的網(wǎng)絡(luò)影響最大化問(wèn)題，并為相關(guān)問(wèn)題的模型建立、種子節(jié)點(diǎn)選取以及如何降低時(shí)間復(fù)雜度提供了基礎(chǔ)。本文的主要貢獻(xiàn)如下。

1) 本文以時(shí)序社交網(wǎng)絡(luò)為對(duì)象研究影響最大化問(wèn)題，基于傳統(tǒng)的加權(quán)級(jí)聯(lián)傳播模型，提出了新的計(jì)算節(jié)點(diǎn)間傳播概率的方法，并以此為基礎(chǔ)，進(jìn)一步提出了改進(jìn)的加權(quán)級(jí)聯(lián)模型（IWCM,improved weighted cascade model），使信息可以在基于時(shí)序關(guān)系的社交網(wǎng)絡(luò)圖中進(jìn)行傳播。

2) 定義了一種新的節(jié)點(diǎn)影響力估算方式，基于該估算方式和IWCM 提出了兩階段時(shí)序社交網(wǎng)絡(luò)影響最大化算法，有效地減少了程序的運(yùn)行時(shí)間。

3) 驗(yàn)證了本文提出的TIM 算法可以高效地解決時(shí)序社交網(wǎng)絡(luò)的影響最大化問(wèn)題，且能在運(yùn)行時(shí)間極短的情況下保證較高的影響范圍。研究成果適用于中等規(guī)模對(duì)運(yùn)行時(shí)間要求較高的時(shí)序社交網(wǎng)絡(luò)。

2 相關(guān)工作

近年來(lái)，國(guó)內(nèi)外研究者在影響最大化方面做了許多工作。Kempe 等[2]針對(duì)影響最大化問(wèn)題，提出了貪心算法，并證明了其運(yùn)算結(jié)果可以達(dá)到63%的近似最優(yōu)，但仍舊存在時(shí)間復(fù)雜度較高、不適于大規(guī)模社交網(wǎng)絡(luò)的問(wèn)題。Leskovec 等[3]針對(duì)影響最大化問(wèn)題的子模特性和單調(diào)特性對(duì)傳統(tǒng)貪心算法進(jìn)行優(yōu)化，提出了比greedy 算法快約數(shù)百倍的CELF（cost-effective lazy-forward）算法。Goyal 等[4]通過(guò)優(yōu)化CELF 算法，提出了CELF++，并通過(guò)實(shí)驗(yàn)證明其運(yùn)算速度比CELF 快35%～55%。

上述算法均為貪心算法或改進(jìn)的貪心算法，近年來(lái)，許多研究者對(duì)時(shí)間復(fù)雜度較低的啟發(fā)式算法進(jìn)行了研究。Chen 等[5]針對(duì)傳統(tǒng)度估計(jì)算法的影響范圍重疊問(wèn)題，提出了DegreeDiscount 算法，首先選取度數(shù)最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，然后將所選節(jié)點(diǎn)鄰居的度數(shù)進(jìn)行折扣，直到選擇k個(gè)節(jié)點(diǎn)。Zhou等[6]首先使用PageRank 算法對(duì)節(jié)點(diǎn)影響力進(jìn)行估算，并選擇影響較大的節(jié)點(diǎn)作為備選節(jié)點(diǎn)，計(jì)算備選節(jié)點(diǎn)的組合碰撞概率，最后用遺傳算法選擇組合碰撞概率最大的k個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)。李閱志等[7]結(jié)合啟發(fā)式算法提出了基于k-核過(guò)濾的影響最大化算法，經(jīng)驗(yàn)證，該算法相較于現(xiàn)有的啟發(fā)式算法具有更廣的影響范圍。

目前，越來(lái)越多的研究者開(kāi)始研究影響最大化的延伸變形問(wèn)題。仇麗青等[8]提出重疊社區(qū)的影響力最大化算法，該算法在運(yùn)行時(shí)間方面最高能夠提升約90%，可被應(yīng)用于大型社交網(wǎng)絡(luò)。Siyu 等[9]提出了多主題意識(shí)下的影響最大化問(wèn)題，通過(guò)改進(jìn)線性閾值模型，設(shè)計(jì)了一個(gè)跨社會(huì)網(wǎng)絡(luò)的主題感知影響最大化模型，然后借助啟發(fā)式算法選擇種子節(jié)點(diǎn)。Li 等[10]考慮價(jià)格等因素，研究了產(chǎn)品在多條件限制的情況下，如何定價(jià)以實(shí)現(xiàn)收入最大化。趙玉芳等[11]考慮了社交網(wǎng)絡(luò)中用戶(hù)之間存在多種關(guān)系，且多種關(guān)系共同影響信息傳播的情況，提出MR-RRset 算法，以解決多關(guān)系社交網(wǎng)絡(luò)影響力最大化問(wèn)題。

Kim 等[12]將影響最大化的研究對(duì)象轉(zhuǎn)移到了動(dòng)態(tài)圖上，并設(shè)計(jì)了算法來(lái)處理動(dòng)態(tài)圖上的更新操作。Wang 等[13]在社交網(wǎng)絡(luò)中定義了新穎的IM（influence maximization）查詢(xún)，使用窗口滑動(dòng)模型解決動(dòng)態(tài)圖上的實(shí)時(shí)影響最大化問(wèn)題。Zhang 等[14]研究了網(wǎng)絡(luò)中存在相互促進(jìn)傳播和相互抑制傳播的不同關(guān)系時(shí)的影響力最大化問(wèn)題。郭景峰等[15]對(duì)傳統(tǒng)算法進(jìn)行改進(jìn)，使其適用于動(dòng)態(tài)圖的影響最大化問(wèn)題，通過(guò)計(jì)算節(jié)點(diǎn)的刪除或添加對(duì)當(dāng)前采樣集合的影響來(lái)重新計(jì)算種子節(jié)點(diǎn)集合。曹玖新等[16]設(shè)置了一個(gè)時(shí)間窗口，將節(jié)點(diǎn)間的聯(lián)系看作一個(gè)動(dòng)作。窗口隨著時(shí)間向下滑動(dòng)，此時(shí)新的動(dòng)作進(jìn)入窗口而舊的動(dòng)作則退出，根據(jù)節(jié)點(diǎn)的進(jìn)入和退出，判斷是否需要對(duì)在上一個(gè)時(shí)間段所求出的窗口中的種子節(jié)點(diǎn)進(jìn)行重新計(jì)算，以解決動(dòng)態(tài)圖中影響最大化問(wèn)題。吳安彪等[17]以時(shí)序圖為對(duì)象研究影響力最大化問(wèn)題，對(duì)傳統(tǒng)獨(dú)立級(jí)聯(lián)模型進(jìn)行改進(jìn)，并以此為基礎(chǔ)提出了AIMT（advanced method for the influence maximization problem on temporal graph）和IMIT（improved method for the influence maximization problem on temporal graph）以解決時(shí)序圖影響力最大化問(wèn)題。魏磊[18]提出了一種基于節(jié)點(diǎn)度與網(wǎng)絡(luò)最大系派相結(jié)合的度值衰減算法。Li 等[19]認(rèn)為網(wǎng)絡(luò)中不同節(jié)點(diǎn)間的傳播概率是不同的，隨著內(nèi)容的變化有著不同的影響程度，并以此為基礎(chǔ)研究了動(dòng)態(tài)社交網(wǎng)絡(luò)中影響最大化問(wèn)題。

3 問(wèn)題定義

3.1 基本定義

定義1基于時(shí)序關(guān)系的社交網(wǎng)絡(luò)。給定網(wǎng)絡(luò)GT(V,E,TE)表示基于時(shí)序關(guān)系的社交網(wǎng)絡(luò)圖，V表示節(jié)點(diǎn)的集合，E表示邊的集合，其中|V|=n，|E|=m，TE表示網(wǎng)絡(luò)中各節(jié)點(diǎn)間存在聯(lián)系時(shí)刻的集合。

由于在社交網(wǎng)絡(luò)的影響最大化問(wèn)題中，經(jīng)常使用圖論的方法來(lái)表示社交網(wǎng)絡(luò)，從而進(jìn)一步分析影響最大化問(wèn)題。本文給出了如圖1 所示的靜態(tài)圖與基于時(shí)序關(guān)系的社交網(wǎng)絡(luò)，并以此為例來(lái)說(shuō)明靜態(tài)圖影響最大化問(wèn)題和時(shí)序網(wǎng)絡(luò)影響最大化問(wèn)題在節(jié)點(diǎn)影響力計(jì)算方面的不同。相比于靜態(tài)社交網(wǎng)絡(luò)圖G（邊的權(quán)重表示節(jié)點(diǎn)的傳播概率），時(shí)序社交網(wǎng)絡(luò)圖GT被賦予時(shí)間軸的概念，各節(jié)點(diǎn)只在特定的時(shí)間點(diǎn)存在聯(lián)系，邊上的權(quán)重表示兩節(jié)點(diǎn)間存在聯(lián)系的時(shí)刻，如圖1(b)所示。相較于靜態(tài)社交網(wǎng)絡(luò)圖1(a)，圖1(b)加入了時(shí)間權(quán)重的概念。如T(a,b)={3,6}表示節(jié)點(diǎn)a和節(jié)點(diǎn)b在3 和6 這2 個(gè)時(shí)刻存在聯(lián)系。以真實(shí)的電子郵件網(wǎng)絡(luò)為例，T(a,b)={3,6}表示用戶(hù)a在3 和6 這2個(gè)時(shí)刻與用戶(hù)b通過(guò)電子郵件進(jìn)行了信息交流，其余時(shí)刻則不存在聯(lián)系。因此，通過(guò)節(jié)點(diǎn)之間邊的時(shí)間權(quán)重來(lái)體現(xiàn)時(shí)序社交網(wǎng)絡(luò)的時(shí)序特性?，F(xiàn)分別計(jì)算節(jié)點(diǎn)a在圖1(a)和圖1(b)中的影響范圍，其計(jì)算過(guò)程如下。

為了便于計(jì)算，設(shè)圖1(a)和圖1(b)中各節(jié)點(diǎn)間傳播概率相同，均為圖1(a)中各邊的權(quán)重值。在圖1(a)中，節(jié)點(diǎn)a分別以0.1 和0.3 的概率去激活節(jié)點(diǎn)b和節(jié)點(diǎn)c。若此時(shí)節(jié)點(diǎn)c被激活，則節(jié)點(diǎn)c以0.1的概率去激活節(jié)點(diǎn)e，假設(shè)節(jié)點(diǎn)e此時(shí)被激活，則節(jié)點(diǎn)a成功將節(jié)點(diǎn)c和節(jié)點(diǎn)e激活，其影響范圍為2。而在圖1(b)中節(jié)點(diǎn)a分別以0.1 和0.3 的概率在3 和2 這2 個(gè)時(shí)刻去激活節(jié)點(diǎn)b和節(jié)點(diǎn)c。若節(jié)點(diǎn)c被激活，則節(jié)點(diǎn)c在時(shí)刻2 之后處于激活狀態(tài)，由于節(jié)點(diǎn)c和節(jié)點(diǎn)e只在時(shí)刻1 存在聯(lián)系，而在時(shí)刻1 節(jié)點(diǎn)c處于未激活狀態(tài)，因此節(jié)點(diǎn)c不能將節(jié)點(diǎn)e激活，節(jié)點(diǎn)a只成功將節(jié)點(diǎn)c激活，其影響范圍為1。

由此可見(jiàn)，若只是單純地將基于靜態(tài)圖的影響力最大化算法應(yīng)用在時(shí)序社交網(wǎng)絡(luò)圖上，則無(wú)法得到正確的結(jié)果，因此需要研究基于時(shí)序關(guān)系的社交網(wǎng)絡(luò)影響最大化問(wèn)題。

圖1 靜態(tài)圖與時(shí)序社交網(wǎng)絡(luò)

3.2 傳播概率的計(jì)算

定義2傳播概率。非活躍鄰居節(jié)點(diǎn)v通過(guò)有向邊(u,v)被其活躍父節(jié)點(diǎn)u激活成功的概率為傳播概率，表示為Pu,v∈[0,1]。

在傳統(tǒng)的影響力最大化算法研究中，計(jì)算節(jié)點(diǎn)間傳播概率通常使用度估計(jì)的方法，即用該點(diǎn)入度的倒數(shù)來(lái)估計(jì)該點(diǎn)被上一級(jí)節(jié)點(diǎn)激活的概率，如式(1)所示。

其中，InDegree(v)表示節(jié)點(diǎn)v的入度。

此方法在傳統(tǒng)影響力最大化算法研究中已被很好地證實(shí)及應(yīng)用。但是在基于時(shí)序關(guān)系的社交網(wǎng)絡(luò)圖中，該方法沒(méi)有考慮到各節(jié)點(diǎn)間聯(lián)系次數(shù)不同的問(wèn)題，現(xiàn)針對(duì)此問(wèn)題進(jìn)行舉例說(shuō)明，如圖2 所示。在靜態(tài)圖G中，由于節(jié)點(diǎn)c的入度為2，則節(jié)點(diǎn)c被節(jié)點(diǎn)a及節(jié)點(diǎn)d影響的概率均為。但是在圖GT中，考慮連接次數(shù)因素時(shí)，可以發(fā)現(xiàn)節(jié)點(diǎn)c與節(jié)點(diǎn)a聯(lián)系次數(shù)小于節(jié)點(diǎn)c與節(jié)點(diǎn)d的聯(lián)系次數(shù)，而一個(gè)節(jié)點(diǎn)被聯(lián)系的次數(shù)越多，意味著其被影響的概率越大，所以在圖2(b)中節(jié)點(diǎn)c被節(jié)點(diǎn)a影響的概率應(yīng)小于節(jié)點(diǎn)c被節(jié)點(diǎn)d影響的概率，其計(jì)算結(jié)果與圖2(a)中不符，即用傳統(tǒng)的度估計(jì)方法來(lái)計(jì)算時(shí)序社交網(wǎng)絡(luò)圖中節(jié)點(diǎn)影響概率是不準(zhǔn)確的，因此，需要對(duì)傳統(tǒng)計(jì)算方法進(jìn)行改進(jìn)。

在傳統(tǒng)的度估計(jì)算法中，節(jié)點(diǎn)v被節(jié)點(diǎn)u激活的概率為邊(u,v)占節(jié)點(diǎn)v所有入邊的比重，即。而在基于時(shí)序社交網(wǎng)絡(luò)的度估計(jì)算法中，由于時(shí)序關(guān)系的加入，每條邊的權(quán)重不同，與兩節(jié)點(diǎn)間聯(lián)系次數(shù)|T(u,v)|相關(guān)，即聯(lián)系次數(shù)越多的邊，權(quán)重越大，且二者成正比關(guān)系，于是將邊(u,v)的權(quán)重設(shè)定為|T(u,v)|，則邊(u,v)占節(jié)點(diǎn)v所有入邊的比重為，節(jié)點(diǎn)v被節(jié)點(diǎn)u激活的概率為

其中，|T(u,v)|表示節(jié)點(diǎn)u與節(jié)點(diǎn)v的聯(lián)系次數(shù)，vk表示點(diǎn)v的所有入度節(jié)點(diǎn)，In(v)表示節(jié)點(diǎn)v的入度節(jié)點(diǎn)。

圖2 傳播概率計(jì)算示例

3.3 對(duì)加權(quán)級(jí)聯(lián)模型的改進(jìn)

3.3.1 傳統(tǒng)的加權(quán)級(jí)聯(lián)模型

傳統(tǒng)的加權(quán)級(jí)聯(lián)傳播模型（WCM,weighted cascade model）為每條有向邊(u,v)設(shè)置一個(gè)概率值且Pu,v∈[0,1]，Pu,v表示節(jié)點(diǎn)u通過(guò)有向邊(u,v)成功影響節(jié)點(diǎn)v的概率。該模型傳播過(guò)程如下。在初始時(shí)刻t，種子節(jié)點(diǎn)u以概率Pu,v嘗試激活它的非活躍鄰居節(jié)點(diǎn)v。如果鄰居節(jié)點(diǎn)v在t時(shí)刻有多個(gè)活躍父節(jié)點(diǎn)，則其父節(jié)點(diǎn)在t時(shí)刻依次對(duì)節(jié)點(diǎn)v進(jìn)行嘗試激活，如果鄰居節(jié)點(diǎn)v被激活成功，則其將在t+1 時(shí)刻由非活躍狀態(tài)轉(zhuǎn)變?yōu)榛钴S，并以同樣的方式去激活它的非活躍鄰居節(jié)點(diǎn)。此過(guò)程一直循環(huán)，直到網(wǎng)絡(luò)中沒(méi)有新的節(jié)點(diǎn)被激活。

3.3.2 改進(jìn)的加權(quán)級(jí)聯(lián)模型

定義3節(jié)點(diǎn)活躍初始時(shí)間。節(jié)點(diǎn)v被其活躍父節(jié)點(diǎn)u成功激活的時(shí)刻為其活躍初始時(shí)間，表示為Actv，且Actv=min{t|(t∈T(u,v) &t≥Actu)}。

以圖2(b)為例，設(shè)點(diǎn)d為種子節(jié)點(diǎn)（種子節(jié)點(diǎn)的初始活躍時(shí)間為0），若其成功激活節(jié)點(diǎn)c，則Actc=min{4,5}=4。

傳統(tǒng)的影響最大化算法不需要考慮節(jié)點(diǎn)被激活的起始時(shí)間，而在基于時(shí)序的社交網(wǎng)絡(luò)圖中節(jié)點(diǎn)被成功激活的初始時(shí)間是需要被考慮的。因此，本文對(duì)傳統(tǒng)加權(quán)級(jí)聯(lián)模型進(jìn)行改進(jìn)，得到了一種新的基于時(shí)序社交網(wǎng)絡(luò)圖的傳播模型——IWCM。

以圖1(b)為例，設(shè)節(jié)點(diǎn)d為種子節(jié)點(diǎn)且成功將其鄰居節(jié)點(diǎn)c激活，則節(jié)點(diǎn)c的初始活躍時(shí)間Actc=2，即節(jié)點(diǎn)c在時(shí)刻2 之后處于活躍狀態(tài)，又由于節(jié)點(diǎn)c與節(jié)點(diǎn)e只在時(shí)刻1 時(shí)存在聯(lián)系，此時(shí)節(jié)點(diǎn)c還處于未激活狀態(tài)，因此節(jié)點(diǎn)c一定無(wú)法將節(jié)點(diǎn)e激活。

本節(jié)基于WCM 設(shè)計(jì)了IWCM，使信息可以在基于時(shí)序關(guān)系的社交網(wǎng)絡(luò)圖中進(jìn)行傳播。信息在時(shí)序社交網(wǎng)絡(luò)圖中通過(guò)IWCM 的傳播過(guò)程描述如下。

1) 在最初始的網(wǎng)絡(luò)中，設(shè)置所有節(jié)點(diǎn)的初始活躍時(shí)間Actv=?1，表示所有節(jié)點(diǎn)均處于非活躍狀態(tài)。設(shè)置種子節(jié)點(diǎn)u的初始活躍時(shí)間Actu=0，表示種子節(jié)點(diǎn)在0 時(shí)刻處于活躍狀態(tài)。此時(shí)種子節(jié)點(diǎn)u以一定的概率激活其鄰居節(jié)點(diǎn)v，節(jié)點(diǎn)u有且僅有一次機(jī)會(huì)可以去嘗試激活節(jié)點(diǎn)v。

2) 節(jié)點(diǎn)u在嘗試激活節(jié)點(diǎn)v時(shí)，首先判斷是否滿(mǎn)足Actu≤max(T(u,v))，如果Actu>max(T(u,v))，則直接跳過(guò)該節(jié)點(diǎn)開(kāi)始嘗試激活下一個(gè)鄰居節(jié)點(diǎn)；如果Actu≤max(T(u,v))，則節(jié)點(diǎn)u以概率激活節(jié)點(diǎn)v。

3) 無(wú)論節(jié)點(diǎn)u能否將節(jié)點(diǎn)v激活，節(jié)點(diǎn)u在以后的傳播過(guò)程中都不會(huì)再激活節(jié)點(diǎn)v。

4) 如果節(jié)點(diǎn)v被成功激活，則記錄其初始活躍時(shí)間Actv，其中Actv∈T(u,v)，Actu≤Actv≤max(T(u,v))。

5) 在整個(gè)網(wǎng)絡(luò)中，信息由新的活躍節(jié)點(diǎn)向非活躍鄰居節(jié)點(diǎn)嘗試傳播，直到網(wǎng)絡(luò)中沒(méi)有新的節(jié)點(diǎn)被激活。

3.4 問(wèn)題定義

基于上述問(wèn)題的描述，本節(jié)對(duì)時(shí)序社交網(wǎng)絡(luò)影響最大化問(wèn)題進(jìn)行定義及說(shuō)明。首先對(duì)時(shí)序社交網(wǎng)絡(luò)中節(jié)點(diǎn)影響力及邊際收益的概念進(jìn)行介紹。

定義4節(jié)點(diǎn)影響力。節(jié)點(diǎn)影響力是指在網(wǎng)絡(luò)中可以被節(jié)點(diǎn)v成功激活的所有節(jié)點(diǎn)的集合，表示為σ(v)。

定義5邊際收益。節(jié)點(diǎn)v的邊際收益是指在種子集S中額外加入一個(gè)節(jié)點(diǎn)v所能帶來(lái)的收益增量σv(S)。

其中，σ(S)表示種子集合S的影響范圍。

問(wèn)題定義基于時(shí)序關(guān)系的社交網(wǎng)絡(luò)影響最大化問(wèn)題。給定時(shí)序社交網(wǎng)絡(luò)圖GT=(V,E,TE)以及特定的傳播模型，在時(shí)序社交網(wǎng)絡(luò)中找到一個(gè)節(jié)點(diǎn)集合S，其中集合S中含有節(jié)點(diǎn)個(gè)數(shù)|S|=k，使集合S的影響范圍最廣，集合S即為GT的種子節(jié)點(diǎn)集。

4 時(shí)序社交網(wǎng)絡(luò)影響最大化算法

4.1 兩階段時(shí)序社交網(wǎng)絡(luò)影響最大化算法

網(wǎng)絡(luò)中度數(shù)較大的節(jié)點(diǎn)往往對(duì)其周邊節(jié)點(diǎn)的影響力較強(qiáng)，但這只是局部最優(yōu)的表現(xiàn)，并沒(méi)有考慮到網(wǎng)絡(luò)中所有節(jié)點(diǎn)的被影響情況，因此網(wǎng)絡(luò)中度數(shù)大的節(jié)點(diǎn)一般具有較大的影響力，但并不一定具有最大的影響力。例如，在圖3 中，節(jié)點(diǎn)a的度數(shù)最大，但是節(jié)點(diǎn)d擁有最大的影響范圍。

圖3 影響范圍示意

本文針對(duì)啟發(fā)式算法這一特點(diǎn)，結(jié)合貪心算法可以精確計(jì)算出節(jié)點(diǎn)影響范圍這一優(yōu)點(diǎn)及時(shí)序社交網(wǎng)絡(luò)影響最大化問(wèn)題的時(shí)序特性，提出了TIM 算法，該算法的核心思想是將節(jié)點(diǎn)的選取過(guò)程分為2 個(gè)階段。

1) 啟發(fā)階段及其時(shí)序化（時(shí)序啟發(fā)階段）。選取備選節(jié)點(diǎn)，考慮網(wǎng)絡(luò)的時(shí)序特性，對(duì)所有節(jié)點(diǎn)進(jìn)行影響力估算，選取估算值較大的節(jié)點(diǎn)作為備選節(jié)點(diǎn)。

在時(shí)序社交網(wǎng)絡(luò)中，節(jié)點(diǎn)影響力不僅受到其出度的影響，還與兩節(jié)點(diǎn)間的聯(lián)系次數(shù)相關(guān)。如圖4 所示，圖中邊的權(quán)重值表示兩節(jié)點(diǎn)間的聯(lián)系次數(shù)。由圖4 可知，節(jié)點(diǎn)d與節(jié)點(diǎn)a的出度相同，均為2，根據(jù)度啟發(fā)式算法可得，節(jié)點(diǎn)d與節(jié)點(diǎn)a的影響力大小相同。但是由于節(jié)點(diǎn)d與節(jié)點(diǎn)e、節(jié)點(diǎn)f的聯(lián)系次數(shù)遠(yuǎn)遠(yuǎn)大于節(jié)點(diǎn)a與節(jié)點(diǎn)b、節(jié)點(diǎn)c的聯(lián)系次數(shù)，即節(jié)點(diǎn)e、節(jié)點(diǎn)f被節(jié)點(diǎn)d嘗試激活的次數(shù)大于節(jié)點(diǎn)b、節(jié)點(diǎn)c被節(jié)點(diǎn)a嘗試激活的次數(shù)，因此節(jié)點(diǎn)f與節(jié)點(diǎn)e被激活概率應(yīng)當(dāng)大于節(jié)點(diǎn)c與節(jié)點(diǎn)b，即節(jié)點(diǎn)d的影響力應(yīng)當(dāng)大于節(jié)點(diǎn)a的影響力，這與度啟發(fā)式算法得出的結(jié)果不同。

圖4 節(jié)點(diǎn)影響力范圍對(duì)比

針對(duì)此問(wèn)題，為了使其適用于時(shí)序影響最大化問(wèn)題，考慮節(jié)點(diǎn)間聯(lián)系次數(shù)的因素，為節(jié)點(diǎn)影響力定義了新的估算方式，如式(4)所示。

其中，Inf(u)表示節(jié)點(diǎn)u的影響范圍，|T(u,v)|表示邊(u,v)的聯(lián)系次數(shù)，O(u)表示節(jié)點(diǎn)u的出度節(jié)點(diǎn)集合。

2) 貪心階段及其時(shí)序化（時(shí)序貪心階段）。從已過(guò)濾的備選節(jié)點(diǎn)中，選取最具影響力的節(jié)點(diǎn)。

解決傳統(tǒng)影響最大化問(wèn)題最有效的方法是每一步都選擇當(dāng)前最具影響力的節(jié)點(diǎn)加入種子集合中，直至找到k個(gè)節(jié)點(diǎn)。但此類(lèi)算法由于要計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)的邊際收益，從而使算法的運(yùn)行時(shí)間過(guò)長(zhǎng)，針對(duì)此問(wèn)題，TIM 算法的貪心階段將邊際收益的計(jì)算對(duì)象由網(wǎng)絡(luò)中所有節(jié)點(diǎn)縮減到了備選節(jié)點(diǎn)，并優(yōu)化了節(jié)點(diǎn)間邊際收益的計(jì)算方式，大大縮減了算法的運(yùn)行時(shí)間。

優(yōu)化后節(jié)點(diǎn)邊際收益的計(jì)算過(guò)程為：首先讀取每個(gè)節(jié)點(diǎn)可以激活的節(jié)點(diǎn)，并將可以被激活的節(jié)點(diǎn)放入與其父節(jié)點(diǎn)對(duì)應(yīng)的列表中，如節(jié)點(diǎn)a可以激活節(jié)點(diǎn)b，則將節(jié)點(diǎn)b放入與節(jié)點(diǎn)a對(duì)應(yīng)的列表σ(a)中，即σ(a)=，同時(shí)計(jì)算出種子集可以激活的節(jié)點(diǎn)，并放入列表σ(S)中。如果想計(jì)算節(jié)點(diǎn)v的邊際收益，則將σ(v)中節(jié)點(diǎn)與σ(S)中節(jié)點(diǎn)作對(duì)比，如果σ(v)中擁有3 個(gè)σ(S)中沒(méi)有的節(jié)點(diǎn)，則節(jié)點(diǎn)v的邊際收益為3。

針對(duì)時(shí)序社交網(wǎng)絡(luò)的影響最大化算法，在計(jì)算節(jié)點(diǎn)影響力時(shí)，由于時(shí)序關(guān)系的加入，節(jié)點(diǎn)v能否被種子節(jié)點(diǎn)u激活不僅與激活概率Pu,v有關(guān)，還與初始活躍時(shí)間相關(guān)。當(dāng)節(jié)點(diǎn)初始活躍時(shí)間Actu≤max(T(u,v))時(shí)，節(jié)點(diǎn)v才有可能被節(jié)點(diǎn)u激活。所以，在時(shí)序貪心階段中，判斷節(jié)點(diǎn)v能否被節(jié)點(diǎn)u激活，需滿(mǎn)足2 個(gè)條件，即Actu≤max(T(u,v))和Pθ≤Pu,v，其中，Pθ為概率閾值。

時(shí)序貪心階段的思想如下：該節(jié)點(diǎn)數(shù)法共執(zhí)行k輪，每輪均從時(shí)序啟發(fā)階段選取的備選節(jié)點(diǎn)中選擇邊際收益最大的節(jié)點(diǎn)加入種子集合S中，直到|S|=k（其中，k為種子節(jié)點(diǎn)數(shù)）。

4.2 偽代碼

用GT(V,E,TE)表示一個(gè)基于時(shí)序關(guān)系的社交網(wǎng)絡(luò)，k為所需的種子節(jié)點(diǎn)數(shù)量，S為種子節(jié)點(diǎn)集合。算法1 給出了TIM 算法的執(zhí)行過(guò)程。

算法1兩階段時(shí)序社交網(wǎng)絡(luò)影響最大化算法

輸入社交網(wǎng)絡(luò)GT(V,E,TE)，k

輸出種子節(jié)點(diǎn)集合S

在算法1 中，步驟1)將備選種子集S1與種子集S初始化為空集；步驟2)～步驟4)估算所有節(jié)點(diǎn)的影響范圍大小；步驟5)～步驟8)尋找影響范圍估計(jì)值較大的前K（K為備選種子集的大小且k

TIM 算法的時(shí)間復(fù)雜度分析過(guò)程如下。設(shè)網(wǎng)絡(luò)GT(V,E,TE)的節(jié)點(diǎn)數(shù)為n，邊數(shù)為m，種子集規(guī)模為k，網(wǎng)絡(luò)中各節(jié)點(diǎn)間存在聯(lián)系時(shí)刻的數(shù)量為t。算法1中，步驟2)～步驟4)計(jì)算所有節(jié)點(diǎn)Inf(u)值時(shí)產(chǎn)生的時(shí)間復(fù)雜度為O(n)；步驟9)將計(jì)算節(jié)點(diǎn)影響力部分迭代k輪，故時(shí)間復(fù)雜度為O(k)；步驟10)對(duì)所有備選非種子節(jié)點(diǎn)進(jìn)行邊際效應(yīng)計(jì)算，計(jì)算完成后對(duì)所有備選非種子節(jié)點(diǎn)進(jìn)行排序的運(yùn)行時(shí)間為O(KlbK)；步驟11)～步驟15)算法將節(jié)點(diǎn)影響范圍的計(jì)算模擬了R次，故時(shí)間復(fù)雜度為O(R)，綜上所述，TIM 算法的時(shí)間復(fù)雜度為O(n+kRKlbK)。如果不采用TIM 算法將邊際收益的計(jì)算對(duì)象由網(wǎng)絡(luò)中所有節(jié)點(diǎn)縮減到備選節(jié)點(diǎn)，而直接選取貪心式算法計(jì)算所有節(jié)點(diǎn)的邊際收益，則其時(shí)間復(fù)雜度為O(kRnlbn)。由于K?n，即kRKlbK?kRnlbn，因此TIM 算法的時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)低于貪心算法。

5 實(shí)驗(yàn)和評(píng)估

本文選取了4 種不同規(guī)模的真實(shí)數(shù)據(jù)集作為輸入數(shù)據(jù)，實(shí)現(xiàn)了在基于時(shí)序社交網(wǎng)絡(luò)圖中種子節(jié)點(diǎn)選取及種子影響力計(jì)算。

5.1 實(shí)驗(yàn)數(shù)據(jù)與參數(shù)設(shè)置

本文實(shí)驗(yàn)使用的數(shù)據(jù)集1（CollegeMsg）源于由私人消息組成的加州大學(xué)分校在線社交網(wǎng)絡(luò)，邊(u,v,t)表示用戶(hù)u在時(shí)間t向用戶(hù)v發(fā)送了一條私人消息[20]。數(shù)據(jù)集2（Email-Eu-core）為歐洲某大型研究機(jī)構(gòu)的電子郵件數(shù)據(jù)，有向邊(u,v,t)表示用戶(hù)u在時(shí)刻t與用戶(hù)v通過(guò)電子郵件進(jìn)行了信息交流[21]。數(shù)據(jù)集3 源于Math Overflow 上的一個(gè)時(shí)間交互網(wǎng)絡(luò)，邊(u,v,t)表示用戶(hù)u在時(shí)間t與用戶(hù)v進(jìn)行了信息交流[22]。數(shù)據(jù)集4 源于Ask Ubuntu 上的一個(gè)時(shí)間交互網(wǎng)絡(luò)，邊(u,v,t)表示用戶(hù)u在時(shí)間t對(duì)用戶(hù)v的答案發(fā)表了評(píng)論[21]。實(shí)驗(yàn)數(shù)據(jù)集參數(shù)如表1 所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集參數(shù)

本文將基于時(shí)序社交網(wǎng)絡(luò)圖的影響力最大化問(wèn)題分為兩步解決。第一步為選取備選節(jié)點(diǎn)，通過(guò)改進(jìn)的啟發(fā)式算法實(shí)現(xiàn)節(jié)點(diǎn)的過(guò)濾，選出備選節(jié)點(diǎn)S1。第二步為選取種子節(jié)點(diǎn)，精確計(jì)算所有備選節(jié)點(diǎn)的影響范圍，并選出影響力最大的前k個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)集。本文在實(shí)現(xiàn)了TIM 算法的同時(shí)，對(duì)基于時(shí)序社交網(wǎng)絡(luò)的IMIT（improved method for the influence maximization problem on temporal graph）算法和基于覆蓋閾值的影響力最大化（CTMD,coverage threshold maximum degree）算法以及一些經(jīng)典算法進(jìn)行復(fù)現(xiàn)，從算法的影響范圍和運(yùn)行時(shí)間2 個(gè)方面來(lái)對(duì)比分析各算法的優(yōu)劣。

IMIT 算法是以時(shí)序社交網(wǎng)絡(luò)為研究對(duì)象的影響最大化算法，該算法以貪心算法為基礎(chǔ)，優(yōu)化節(jié)點(diǎn)邊際收益的計(jì)算方法，從而使其可以被應(yīng)用于大規(guī)模時(shí)序社交網(wǎng)絡(luò)[17]。

CTMD 算法是基于覆蓋閾值的度最大啟發(fā)式算法，利用改進(jìn)的k-shell 算法計(jì)算節(jié)點(diǎn)影響力以選取初始種子節(jié)點(diǎn)，并計(jì)算兩度以?xún)?nèi)節(jié)點(diǎn)的激活概率[23]。

IEIR（influence estimation influence ranking）算法是基于影響力估計(jì)和影響力排名的算法，是目前傳統(tǒng)影響最大化算法中綜合能力最好的算法[24]。

核覆蓋算法（CCA,core covering algorithm）是基于網(wǎng)絡(luò)層次結(jié)構(gòu)和影響半徑d的啟發(fā)式算法，在實(shí)驗(yàn)中一般取d=1[25]。

DegreeDiscount 算法作為啟發(fā)式算法的代表，選取度數(shù)最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，然后將所選節(jié)點(diǎn)鄰居的度數(shù)進(jìn)行折扣，直到選擇k個(gè)節(jié)點(diǎn)[5]。

greedy 算法為一個(gè)簡(jiǎn)單的貪心算法，用來(lái)做實(shí)驗(yàn)對(duì)比，計(jì)算出所有節(jié)點(diǎn)的影響力大小并進(jìn)行排序，選取前k個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)[2]。

實(shí)驗(yàn)平臺(tái)的操作系統(tǒng)為64 位的Windows 10，CPU 為英特爾 Core i5-8300H @ 2.30 GHz 四核，內(nèi)存為8 GB，硬盤(pán)為128 GB，編程環(huán)境為Pycharm。

在種子節(jié)點(diǎn)選取階段，IMIT 算法、CTMD 算法、IEIR 算法、CCA、DegreeDiscount 算法、greedy算法和兩階段時(shí)序社交網(wǎng)絡(luò)影響最大化算法選取種子節(jié)點(diǎn)集合大小k分別為5、10、15、20、25、30、35、40、45 和50。

5.2 不同算法中種子節(jié)點(diǎn)影響力

本文對(duì)相關(guān)算法在4 個(gè)不同的數(shù)據(jù)集上進(jìn)行影響范圍測(cè)試。影響范圍influnece 是指在網(wǎng)絡(luò)的初始階段通過(guò)算法計(jì)算種子集，讓種子集在網(wǎng)絡(luò)中進(jìn)行傳播，最終影響到的節(jié)點(diǎn)個(gè)數(shù)。種子集的影響范圍越廣，說(shuō)明算法的準(zhǔn)確度越高。圖5 給出了Email-Eu-core 數(shù)據(jù)集上的種子節(jié)點(diǎn)影響效果。從圖5 中可以看到，greedy 算法影響范圍最廣，IMIT 算法和TIM 算法次之，其余算法中，屬于啟發(fā)式算法的DegreeDiscount 算法和CCA 的傳播范圍較好，IEIR算法和CTMD 算法的性能最差。

圖5 Email-Eu-core 數(shù)據(jù)集上的種子節(jié)點(diǎn)影響效果

圖6是CollegeMsg數(shù)據(jù)集上的種子節(jié)點(diǎn)影響效果。從圖6 中可以看到，當(dāng)k=50 時(shí)，greedy 算法和IMIT 算法信息傳播范圍最廣，影響范圍曲線幾乎重合，且比TIM 算法、DegreeDiscount 算法、IEIR算法、CCA、CTMD 算法分別提高了16.8%、61.8%、81.1%、84.1%、90.4%。當(dāng)k<20 時(shí)，greedy 算法與TIM 算法的影響效果折線幾乎重合，其性能差異不大；當(dāng)k>20 時(shí)，greedy 算法優(yōu)于TIM 算法。CCA和CTMD 算法的性能最差。

圖7 是Math Overflow 數(shù)據(jù)集上的種子節(jié)點(diǎn)影響效果。從圖7 中可以看到，當(dāng)k<40 時(shí)，greedy算法、TIM 算法與IMIT 算法的折線高度重合，影響范圍幾乎相同；當(dāng)k>40 時(shí)，TIM 算法稍次于IMIT算法和greedy 算法。在其余算法中，IEIR 算法和DegreeDiscount 算法的影響范圍較高，而CCA 和CTMD 算法的影響范圍較低。

圖6 CollegeMsg 數(shù)據(jù)集上的種子節(jié)點(diǎn)影響效果

圖7 Math Overflow 數(shù)據(jù)集上的種子節(jié)點(diǎn)影響效果

圖8是Ask Ubuntu數(shù)據(jù)集上的種子節(jié)點(diǎn)影響效果。從圖8 中可以看到，TIM 算法和IMIT 算法的影響范圍接近于擁有近似最優(yōu)解的greedy 算法，且遠(yuǎn)遠(yuǎn)高于其余算法。當(dāng)k<25 時(shí)，TIM 算法和IMIT算法的影響范圍曲線與greedy 算法的曲線幾乎重合，影響范圍高度接近；當(dāng)k>25 時(shí)，TIM 算法和IMIT 算法的影響范圍略遜于greedy 算法。在其余4種算法中，DegreeDiscount 算法的影響范圍最高，而CCA、CTMD 算法和IEIR 算法的影響范圍較低。

5.3 不同算法中種子節(jié)點(diǎn)選取時(shí)間

本節(jié)實(shí)驗(yàn)在IWCM 傳播模型下，分別對(duì)IMIT 算法、CTMD 算法、CCA、IEIR 算法、DegreeDiscount算法、greedy 算法和TIM 算法的運(yùn)行時(shí)間進(jìn)行了統(tǒng)計(jì)，所統(tǒng)計(jì)的時(shí)間為在4 種不同規(guī)模的數(shù)據(jù)集中，選擇50 個(gè)種子節(jié)點(diǎn)的運(yùn)行時(shí)間，如表2 所示。

圖8 Ask Ubuntu 數(shù)據(jù)集上的種子節(jié)點(diǎn)影響效果

從表2 中可以看出，隨著網(wǎng)絡(luò)規(guī)模的增大，TIM算法、CTMD 算法、DegreeDiscount 算法、IEIR 算法、CCA、IMIT 算法的運(yùn)行時(shí)間增幅較小，DegreeDiscount 算法的運(yùn)行時(shí)間最短，TIM 算法次之，IMIT 算法、CTMD 算法、CCA 和IEIR 算法的運(yùn)行時(shí)間較長(zhǎng)，greedy 算法的運(yùn)行時(shí)間最長(zhǎng)，且隨著網(wǎng)絡(luò)規(guī)模的增大，greedy 算法的運(yùn)行時(shí)間成指數(shù)級(jí)增長(zhǎng)。

通過(guò)對(duì)實(shí)驗(yàn)結(jié)果的分析表明，IEIR 算法和CCA雖然是傳統(tǒng)影響最大化算法中綜合能力較好的算法，但由于時(shí)序影響最大化問(wèn)題中時(shí)序關(guān)系的加入，導(dǎo)致算法的影響范圍縮小，故不適用于時(shí)序社交網(wǎng)絡(luò)的影響最大化問(wèn)題的研究；CTMD 算法雖然是近兩年較新的影響最大化算法，但同樣沒(méi)有考慮時(shí)序的因素，導(dǎo)致影響范圍縮水；greedy 算法雖然影響范圍最廣，但運(yùn)行時(shí)間也最長(zhǎng)，由于現(xiàn)實(shí)生活中社交網(wǎng)絡(luò)的規(guī)模一般較大，故該算法并不實(shí)用；DegreeDiscount 算法為啟發(fā)式算法，運(yùn)行時(shí)間最短，但影響范圍也較小，達(dá)不到對(duì)算法影響范圍的要求；IMIT 算法是以時(shí)序社交網(wǎng)絡(luò)為研究對(duì)象的影響最大化算法，故能很好地貼合實(shí)際問(wèn)題，同時(shí)該算法以貪心算法為基礎(chǔ)，對(duì)節(jié)點(diǎn)邊際收益的計(jì)算方法進(jìn)行優(yōu)化，相較于傳統(tǒng)的貪心算法，其效率提高了300 倍。由于IMIT 算法是基于貪心算法的改進(jìn)算法，因此其影響范圍與貪心算法相近。與本文提出的TIM 算法相比，由于將節(jié)點(diǎn)影響力的計(jì)算范圍由網(wǎng)絡(luò)中所有節(jié)點(diǎn)縮減到了備選節(jié)點(diǎn)，導(dǎo)致節(jié)點(diǎn)影響范圍的計(jì)算不夠準(zhǔn)確。由此可知，TIM 算法在影響范圍略有降低的情況下，較大幅度地縮短了運(yùn)行時(shí)間。以Ask Ubuntu 網(wǎng)絡(luò)為例，當(dāng)k=50 時(shí)，IMIT 算法的影響范圍為423，而TIM 算法的影響范圍為402，IMIT 算法的影響范圍比TIM 算法提高了4.9%，但TIM 算法的運(yùn)行時(shí)間比IMIT 算法縮短了一半，所以TIM 算法相比于IMIT 算法能以較小的影響范圍為代價(jià)，換取更快的運(yùn)行時(shí)間。

TIM 算法相較于IMIT 算法運(yùn)行時(shí)間較短的原因如下。TIM 算法在時(shí)序啟發(fā)階段，節(jié)點(diǎn)影響力估算的時(shí)間復(fù)雜度為O(|V|)（V為網(wǎng)絡(luò)中所有節(jié)點(diǎn)），而通過(guò)參考文獻(xiàn)[17]可知，IMIT 算法的時(shí)間復(fù)雜度為O(ψ(v)|V|+|V|lb|V|)，即TIM 算法時(shí)序啟發(fā)階段的運(yùn)行時(shí)間要小于IMIT 算法。以Ask Ubuntu 網(wǎng)絡(luò)為例，TIM 算法時(shí)序啟發(fā)階段的運(yùn)行時(shí)間為0.093 s，而IMIT 算法為2.43 s，雖然TIM 算法還需要在時(shí)序貪心階段對(duì)備選節(jié)點(diǎn)的影響范圍進(jìn)行精確計(jì)算，但備選節(jié)點(diǎn)數(shù)一般為100，相較于Ask Ubuntu 網(wǎng)絡(luò)中75 555 的節(jié)點(diǎn)數(shù)，大規(guī)模地縮減了節(jié)點(diǎn)影響力的計(jì)算范圍，該階段的運(yùn)行時(shí)間為0.52 s，所以TIM算法總體運(yùn)行時(shí)間為0.093 s+0.52 s，即約為0.62 s，比IMIT 算法減少了近20%。IMIT 算法比TIM 算法影響范圍廣的原因如下。IMIT 算法對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的影響范圍進(jìn)行了精確計(jì)算，而TIM 算法只是對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)進(jìn)行了影響范圍的估算，并選取估算值較大的前100 個(gè)節(jié)點(diǎn)進(jìn)行影響范圍的精確計(jì)算，而在影響力估算階段由于計(jì)算的不準(zhǔn)確性，可能出現(xiàn)影響范圍較大節(jié)點(diǎn)的估計(jì)值較小，沒(méi)有被選入備選節(jié)點(diǎn)中，從而損失了一部分的影響力。

表2 算法運(yùn)行時(shí)間

綜上所述，IMIT 算法更適用于大規(guī)模對(duì)影響范圍要求較高的網(wǎng)絡(luò)，而TIM 算法在小規(guī)模網(wǎng)絡(luò)，例如Email-Eu-core 中，當(dāng)k=50 時(shí)，備選節(jié)點(diǎn)的數(shù)量一般為100，而網(wǎng)絡(luò)中總節(jié)點(diǎn)數(shù)為986，即在時(shí)序貪心階段，節(jié)點(diǎn)影響力的計(jì)算范圍僅縮減了89%，該比例較低，運(yùn)行時(shí)間的優(yōu)勢(shì)體現(xiàn)不明顯；在大規(guī)模網(wǎng)絡(luò)，例如Ask Ubuntu 中，相較于網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)75 555，影響力的計(jì)算范圍縮減了99.8%，雖然能節(jié)省大量的運(yùn)行時(shí)間，但由于時(shí)序啟發(fā)階段節(jié)點(diǎn)影響力的估計(jì)范圍較廣，所以出現(xiàn)誤差的概率較大，即計(jì)算影響力的準(zhǔn)確度較差；而對(duì)于中等規(guī)模網(wǎng)絡(luò)，例如Math Overflow 中，網(wǎng)絡(luò)中總節(jié)點(diǎn)數(shù)為21 688，節(jié)點(diǎn)影響力的計(jì)算范圍縮減了99.5%，該數(shù)量級(jí)適中，既可節(jié)約大量的時(shí)間成本，又能讓影響力的誤差值控制在較小的范圍內(nèi)，由表2 和圖7可知，TIM 算法相較于IMIT 算法，在中等規(guī)模網(wǎng)絡(luò)Ask Ubuntu 中，運(yùn)行時(shí)間縮短了78.2%，而影響范圍僅減少了2.25%，故TIM 算法更適于中等規(guī)模對(duì)運(yùn)行時(shí)間要求較高的網(wǎng)絡(luò)。

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

為解決以時(shí)序社交網(wǎng)絡(luò)為研究對(duì)象的影響最大化問(wèn)題，本文提出了TIM 算法。首先，通過(guò)改進(jìn)度估計(jì)算法來(lái)計(jì)算節(jié)點(diǎn)間的傳播概率；其次，對(duì)傳統(tǒng)加權(quán)級(jí)聯(lián)模型進(jìn)行改進(jìn)，使其可以應(yīng)用于基于時(shí)序關(guān)系的社交網(wǎng)絡(luò)上；最后，基于改進(jìn)的加權(quán)級(jí)聯(lián)模型提出了TIM 算法。在實(shí)際網(wǎng)絡(luò)中，TIM 算法的影響范圍遠(yuǎn)高于啟發(fā)式類(lèi)算法與傳統(tǒng)影響最大化算法中綜合能力最好的IEIR 算法和CCA，而與greedy 算法和IMIT 算法的影響范圍相近；在運(yùn)行時(shí)間方面，TIM 算法運(yùn)行時(shí)間較快，略高于啟發(fā)類(lèi)算法，低于IMIT 算法、CTMD 算法、CCA 和IEIR算法，遠(yuǎn)低于greedy 算法。因此，TIM 算法在擁有較短運(yùn)行時(shí)間的同時(shí)，保證了較廣的影響范圍，適用于時(shí)序社交網(wǎng)絡(luò)的影響最大化問(wèn)題。

在未來(lái)的工作中將會(huì)進(jìn)行如下的深入研究：1)在基本時(shí)序社交網(wǎng)絡(luò)影響最大化問(wèn)題研究的基礎(chǔ)上，考慮更多實(shí)際因素，如不同信息類(lèi)型、成本、時(shí)間等因素對(duì)影響最大化問(wèn)題的影響；2) 近年來(lái)有很多研究者利用社區(qū)結(jié)構(gòu)來(lái)解決影響最大化問(wèn)題并取得了很大的成果，未來(lái)可以嘗試在時(shí)序社交網(wǎng)絡(luò)圖的基礎(chǔ)上研究基于時(shí)序社交網(wǎng)絡(luò)圖的社區(qū)影響最大化。