基于時序關系的社交網絡影響最大化算法研究

陳晶，祁子怡

（1.燕山大學信息科學與工程學院，河北 秦皇島 066004；2.河北省虛擬技術與系統集成重點實驗室，河北 秦皇島 066004；3.河北省軟件工程重點實驗室，河北 秦皇島 066004）

1 引言

隨著互聯網的快速發展，越來越多的人喜歡通過社交媒體傳播他們的想法和信息來影響平臺中的其他用戶。如何使分享的信息快速傳播并且影響范圍最廣，已成為社交網絡分析領域的熱點問題。針對此類問題，Richardson 等[1]首次提出了影響力最大化問題。目前廣泛應用的基于靜態社交網絡的影響最大化問題是通過在社交網絡中尋找k個用戶作為種子節點，使信息在特定的傳播模型下，通過種子節點在網絡中盡可能多地影響其他用戶。

目前，大多數研究通常將社交網絡抽象為靜態圖，簡化了影響最大化問題的研究，忽略了實際網絡中節點間存在的時間關系特性，例如，人們之間相互的電話通信、郵件傳送、交通網絡和大腦神經網絡等，進而造成了影響范圍不準確的問題。在這些網絡中，節點之間的聯系并不會一直存在，而是只在某個時間段或者時間點存在聯系，即節點之間的聯系是動態的、具有時序性的。以時序信息傳送為例，社交網絡中的用戶節點之間更加傾向于在特定的時間段內對某類主題信息進行交流和傳播，因此，當研究信息在傳播過程中具有重要作用的用戶節點時，便可通過研究時序社交網絡影響最大化問題來解決。

目前，針對時序網絡的影響最大化研究很少，并且絕大多數研究集中在使用傳統方法在時序網絡上進行研究，即實驗環境是具有時序特性的數據集，而研究方法是傳統的。在此類問題中，由于時序社交網絡中節點之間的時序性，節點間的聯系狀態是隨著時間動態變化的，因此時序社交網絡影響最大化問題面臨如下挑戰：1) 傳統信息傳播模型由于沒有考慮網絡的時序特性，故無法被應用于時序社交網絡；2) 在種子節點選取過程中，節點影響范圍的計算方式與傳統方式不同。

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

1) 本文以時序社交網絡為對象研究影響最大化問題，基于傳統的加權級聯傳播模型，提出了新的計算節點間傳播概率的方法，并以此為基礎，進一步提出了改進的加權級聯模型（IWCM,improved weighted cascade model），使信息可以在基于時序關系的社交網絡圖中進行傳播。

2) 定義了一種新的節點影響力估算方式，基于該估算方式和IWCM 提出了兩階段時序社交網絡影響最大化算法，有效地減少了程序的運行時間。

3) 驗證了本文提出的TIM 算法可以高效地解決時序社交網絡的影響最大化問題，且能在運行時間極短的情況下保證較高的影響范圍。研究成果適用于中等規模對運行時間要求較高的時序社交網絡。

2 相關工作

近年來，國內外研究者在影響最大化方面做了許多工作。Kempe 等[2]針對影響最大化問題，提出了貪心算法，并證明了其運算結果可以達到63%的近似最優，但仍舊存在時間復雜度較高、不適于大規模社交網絡的問題。Leskovec 等[3]針對影響最大化問題的子模特性和單調特性對傳統貪心算法進行優化，提出了比greedy 算法快約數百倍的CELF（cost-effective lazy-forward）算法。Goyal 等[4]通過優化CELF 算法，提出了CELF++，并通過實驗證明其運算速度比CELF 快35%～55%。

上述算法均為貪心算法或改進的貪心算法，近年來，許多研究者對時間復雜度較低的啟發式算法進行了研究。Chen 等[5]針對傳統度估計算法的影響范圍重疊問題，提出了DegreeDiscount 算法，首先選取度數最大的節點作為種子節點，然后將所選節點鄰居的度數進行折扣，直到選擇k個節點。Zhou等[6]首先使用PageRank 算法對節點影響力進行估算，并選擇影響較大的節點作為備選節點，計算備選節點的組合碰撞概率，最后用遺傳算法選擇組合碰撞概率最大的k個節點作為種子節點。李閱志等[7]結合啟發式算法提出了基于k-核過濾的影響最大化算法，經驗證，該算法相較于現有的啟發式算法具有更廣的影響范圍。

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

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

3 問題定義

3.1 基本定義

定義1基于時序關系的社交網絡。給定網絡GT(V,E,TE)表示基于時序關系的社交網絡圖，V表示節點的集合，E表示邊的集合，其中|V|=n，|E|=m，TE表示網絡中各節點間存在聯系時刻的集合。

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

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

由此可見，若只是單純地將基于靜態圖的影響力最大化算法應用在時序社交網絡圖上，則無法得到正確的結果，因此需要研究基于時序關系的社交網絡影響最大化問題。

圖1 靜態圖與時序社交網絡

3.2 傳播概率的計算

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

在傳統的影響力最大化算法研究中，計算節點間傳播概率通常使用度估計的方法，即用該點入度的倒數來估計該點被上一級節點激活的概率，如式(1)所示。

其中，InDegree(v)表示節點v的入度。

此方法在傳統影響力最大化算法研究中已被很好地證實及應用。但是在基于時序關系的社交網絡圖中，該方法沒有考慮到各節點間聯系次數不同的問題，現針對此問題進行舉例說明，如圖2 所示。在靜態圖G中，由于節點c的入度為2，則節點c被節點a及節點d影響的概率均為。但是在圖GT中，考慮連接次數因素時，可以發現節點c與節點a聯系次數小于節點c與節點d的聯系次數，而一個節點被聯系的次數越多，意味著其被影響的概率越大，所以在圖2(b)中節點c被節點a影響的概率應小于節點c被節點d影響的概率，其計算結果與圖2(a)中不符，即用傳統的度估計方法來計算時序社交網絡圖中節點影響概率是不準確的，因此，需要對傳統計算方法進行改進。

在傳統的度估計算法中，節點v被節點u激活的概率為邊(u,v)占節點v所有入邊的比重，即。而在基于時序社交網絡的度估計算法中，由于時序關系的加入，每條邊的權重不同，與兩節點間聯系次數|T(u,v)|相關，即聯系次數越多的邊，權重越大，且二者成正比關系，于是將邊(u,v)的權重設定為|T(u,v)|，則邊(u,v)占節點v所有入邊的比重為，節點v被節點u激活的概率為

其中，|T(u,v)|表示節點u與節點v的聯系次數，vk表示點v的所有入度節點，In(v)表示節點v的入度節點。

圖2 傳播概率計算示例

3.3 對加權級聯模型的改進

3.3.1 傳統的加權級聯模型

傳統的加權級聯傳播模型（WCM,weighted cascade model）為每條有向邊(u,v)設置一個概率值且Pu,v∈[0,1]，Pu,v表示節點u通過有向邊(u,v)成功影響節點v的概率。該模型傳播過程如下。在初始時刻t，種子節點u以概率Pu,v嘗試激活它的非活躍鄰居節點v。如果鄰居節點v在t時刻有多個活躍父節點，則其父節點在t時刻依次對節點v進行嘗試激活，如果鄰居節點v被激活成功，則其將在t+1 時刻由非活躍狀態轉變為活躍，并以同樣的方式去激活它的非活躍鄰居節點。此過程一直循環，直到網絡中沒有新的節點被激活。

3.3.2 改進的加權級聯模型

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

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

傳統的影響最大化算法不需要考慮節點被激活的起始時間，而在基于時序的社交網絡圖中節點被成功激活的初始時間是需要被考慮的。因此，本文對傳統加權級聯模型進行改進，得到了一種新的基于時序社交網絡圖的傳播模型——IWCM。

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

本節基于WCM 設計了IWCM，使信息可以在基于時序關系的社交網絡圖中進行傳播。信息在時序社交網絡圖中通過IWCM 的傳播過程描述如下。

1) 在最初始的網絡中，設置所有節點的初始活躍時間Actv=?1，表示所有節點均處于非活躍狀態。設置種子節點u的初始活躍時間Actu=0，表示種子節點在0 時刻處于活躍狀態。此時種子節點u以一定的概率激活其鄰居節點v，節點u有且僅有一次機會可以去嘗試激活節點v。

2) 節點u在嘗試激活節點v時，首先判斷是否滿足Actu≤max(T(u,v))，如果Actu>max(T(u,v))，則直接跳過該節點開始嘗試激活下一個鄰居節點；如果Actu≤max(T(u,v))，則節點u以概率激活節點v。

3) 無論節點u能否將節點v激活，節點u在以后的傳播過程中都不會再激活節點v。

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

5) 在整個網絡中，信息由新的活躍節點向非活躍鄰居節點嘗試傳播，直到網絡中沒有新的節點被激活。

3.4 問題定義

基于上述問題的描述，本節對時序社交網絡影響最大化問題進行定義及說明。首先對時序社交網絡中節點影響力及邊際收益的概念進行介紹。

定義4節點影響力。節點影響力是指在網絡中可以被節點v成功激活的所有節點的集合，表示為σ(v)。

定義5邊際收益。節點v的邊際收益是指在種子集S中額外加入一個節點v所能帶來的收益增量σv(S)。

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

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

4 時序社交網絡影響最大化算法

4.1 兩階段時序社交網絡影響最大化算法

網絡中度數較大的節點往往對其周邊節點的影響力較強，但這只是局部最優的表現，并沒有考慮到網絡中所有節點的被影響情況，因此網絡中度數大的節點一般具有較大的影響力，但并不一定具有最大的影響力。例如，在圖3 中，節點a的度數最大，但是節點d擁有最大的影響范圍。

圖3 影響范圍示意

本文針對啟發式算法這一特點，結合貪心算法可以精確計算出節點影響范圍這一優點及時序社交網絡影響最大化問題的時序特性，提出了TIM 算法，該算法的核心思想是將節點的選取過程分為2 個階段。

1) 啟發階段及其時序化（時序啟發階段）。選取備選節點，考慮網絡的時序特性，對所有節點進行影響力估算，選取估算值較大的節點作為備選節點。

在時序社交網絡中，節點影響力不僅受到其出度的影響，還與兩節點間的聯系次數相關。如圖4 所示，圖中邊的權重值表示兩節點間的聯系次數。由圖4 可知，節點d與節點a的出度相同，均為2，根據度啟發式算法可得，節點d與節點a的影響力大小相同。但是由于節點d與節點e、節點f的聯系次數遠遠大于節點a與節點b、節點c的聯系次數，即節點e、節點f被節點d嘗試激活的次數大于節點b、節點c被節點a嘗試激活的次數，因此節點f與節點e被激活概率應當大于節點c與節點b，即節點d的影響力應當大于節點a的影響力，這與度啟發式算法得出的結果不同。

圖4 節點影響力范圍對比

針對此問題，為了使其適用于時序影響最大化問題，考慮節點間聯系次數的因素，為節點影響力定義了新的估算方式，如式(4)所示。

其中，Inf(u)表示節點u的影響范圍，|T(u,v)|表示邊(u,v)的聯系次數，O(u)表示節點u的出度節點集合。

2) 貪心階段及其時序化（時序貪心階段）。從已過濾的備選節點中，選取最具影響力的節點。

解決傳統影響最大化問題最有效的方法是每一步都選擇當前最具影響力的節點加入種子集合中，直至找到k個節點。但此類算法由于要計算網絡中所有節點的邊際收益，從而使算法的運行時間過長，針對此問題，TIM 算法的貪心階段將邊際收益的計算對象由網絡中所有節點縮減到了備選節點，并優化了節點間邊際收益的計算方式，大大縮減了算法的運行時間。

優化后節點邊際收益的計算過程為：首先讀取每個節點可以激活的節點，并將可以被激活的節點放入與其父節點對應的列表中，如節點a可以激活節點b，則將節點b放入與節點a對應的列表σ(a)中，即σ(a)={b}，同時計算出種子集可以激活的節點，并放入列表σ(S)中。如果想計算節點v的邊際收益，則將σ(v)中節點與σ(S)中節點作對比，如果σ(v)中擁有3 個σ(S)中沒有的節點，則節點v的邊際收益為3。

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

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

4.2 偽代碼

用GT(V,E,TE)表示一個基于時序關系的社交網絡，k為所需的種子節點數量，S為種子節點集合。算法1 給出了TIM 算法的執行過程。

算法1兩階段時序社交網絡影響最大化算法

輸入社交網絡GT(V,E,TE)，k

輸出種子節點集合S

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

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

5 實驗和評估

本文選取了4 種不同規模的真實數據集作為輸入數據，實現了在基于時序社交網絡圖中種子節點選取及種子影響力計算。

5.1 實驗數據與參數設置

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

表1 實驗數據集參數

本文將基于時序社交網絡圖的影響力最大化問題分為兩步解決。第一步為選取備選節點，通過改進的啟發式算法實現節點的過濾，選出備選節點S1。第二步為選取種子節點，精確計算所有備選節點的影響范圍，并選出影響力最大的前k個節點作為種子節點集。本文在實現了TIM 算法的同時，對基于時序社交網絡的IMIT（improved method for the influence maximization problem on temporal graph）算法和基于覆蓋閾值的影響力最大化（CTMD,coverage threshold maximum degree）算法以及一些經典算法進行復現，從算法的影響范圍和運行時間2 個方面來對比分析各算法的優劣。

IMIT 算法是以時序社交網絡為研究對象的影響最大化算法，該算法以貪心算法為基礎，優化節點邊際收益的計算方法，從而使其可以被應用于大規模時序社交網絡[17]。

CTMD 算法是基于覆蓋閾值的度最大啟發式算法，利用改進的k-shell 算法計算節點影響力以選取初始種子節點，并計算兩度以內節點的激活概率[23]。

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

核覆蓋算法（CCA,core covering algorithm）是基于網絡層次結構和影響半徑d的啟發式算法，在實驗中一般取d=1[25]。

DegreeDiscount 算法作為啟發式算法的代表，選取度數最大的節點作為種子節點，然后將所選節點鄰居的度數進行折扣，直到選擇k個節點[5]。

greedy 算法為一個簡單的貪心算法，用來做實驗對比，計算出所有節點的影響力大小并進行排序，選取前k個節點作為種子節點[2]。

實驗平臺的操作系統為64 位的Windows 10，CPU 為英特爾 Core i5-8300H @ 2.30 GHz 四核，內存為8 GB，硬盤為128 GB，編程環境為Pycharm。

在種子節點選取階段，IMIT 算法、CTMD 算法、IEIR 算法、CCA、DegreeDiscount 算法、greedy算法和兩階段時序社交網絡影響最大化算法選取種子節點集合大小k分別為5、10、15、20、25、30、35、40、45 和50。

5.2 不同算法中種子節點影響力

本文對相關算法在4 個不同的數據集上進行影響范圍測試。影響范圍influnece 是指在網絡的初始階段通過算法計算種子集，讓種子集在網絡中進行傳播，最終影響到的節點個數。種子集的影響范圍越廣，說明算法的準確度越高。圖5 給出了Email-Eu-core 數據集上的種子節點影響效果。從圖5 中可以看到，greedy 算法影響范圍最廣，IMIT 算法和TIM 算法次之，其余算法中，屬于啟發式算法的DegreeDiscount 算法和CCA 的傳播范圍較好，IEIR算法和CTMD 算法的性能最差。

圖5 Email-Eu-core 數據集上的種子節點影響效果

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

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

圖6 CollegeMsg 數據集上的種子節點影響效果

圖7 Math Overflow 數據集上的種子節點影響效果

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

5.3 不同算法中種子節點選取時間

本節實驗在IWCM 傳播模型下，分別對IMIT 算法、CTMD 算法、CCA、IEIR 算法、DegreeDiscount算法、greedy 算法和TIM 算法的運行時間進行了統計，所統計的時間為在4 種不同規模的數據集中，選擇50 個種子節點的運行時間，如表2 所示。

圖8 Ask Ubuntu 數據集上的種子節點影響效果

從表2 中可以看出，隨著網絡規模的增大，TIM算法、CTMD 算法、DegreeDiscount 算法、IEIR 算法、CCA、IMIT 算法的運行時間增幅較小，DegreeDiscount 算法的運行時間最短，TIM 算法次之，IMIT 算法、CTMD 算法、CCA 和IEIR 算法的運行時間較長，greedy 算法的運行時間最長，且隨著網絡規模的增大，greedy 算法的運行時間成指數級增長。

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

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

表2 算法運行時間

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

6 結束語

為解決以時序社交網絡為研究對象的影響最大化問題，本文提出了TIM 算法。首先，通過改進度估計算法來計算節點間的傳播概率；其次，對傳統加權級聯模型進行改進，使其可以應用于基于時序關系的社交網絡上；最后，基于改進的加權級聯模型提出了TIM 算法。在實際網絡中，TIM 算法的影響范圍遠高于啟發式類算法與傳統影響最大化算法中綜合能力最好的IEIR 算法和CCA，而與greedy 算法和IMIT 算法的影響范圍相近；在運行時間方面，TIM 算法運行時間較快，略高于啟發類算法，低于IMIT 算法、CTMD 算法、CCA 和IEIR算法，遠低于greedy 算法。因此，TIM 算法在擁有較短運行時間的同時，保證了較廣的影響范圍，適用于時序社交網絡的影響最大化問題。

在未來的工作中將會進行如下的深入研究：1)在基本時序社交網絡影響最大化問題研究的基礎上，考慮更多實際因素，如不同信息類型、成本、時間等因素對影響最大化問題的影響；2) 近年來有很多研究者利用社區結構來解決影響最大化問題并取得了很大的成果，未來可以嘗試在時序社交網絡圖的基礎上研究基于時序社交網絡圖的社區影響最大化。