大規(guī)模時序圖中種子節(jié)點挖掘算法研究

鄒曉紅，許成偉，陳晶，宋彪，王明月

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

0 引言

近些年，隨著信息技術(shù)的快速發(fā)展，在線社交媒體層出不窮，用戶通過社交媒體相互溝通，分享觀點，并借助社交網(wǎng)絡完成信息的快速傳播，以此來影響更多的用戶，這種影響力的擴散與傳播成為社交網(wǎng)絡研究領域熱點問題之一。Domingos 和Richardsom[1-2]首次提出有關社交網(wǎng)絡影響力最大化（IM,influence maximization）問題，IM 問題是指在網(wǎng)絡圖中選定k個種子節(jié)點作為信息源點，使其在特定信息傳播模型下進行信息傳播，目的是以最小的代價盡可能多地影響其他節(jié)點，其研究成果廣泛應用于市場營銷、水質(zhì)檢測等方面[3]。

目前，大多數(shù)IM 問題是基于靜態(tài)圖網(wǎng)絡模型展開的，但針對具有動態(tài)性特征的社交網(wǎng)絡，不能簡單地將其表示為靜態(tài)圖網(wǎng)絡模型進行處理，如生物信息網(wǎng)絡、通信網(wǎng)絡、道路交通網(wǎng)絡等網(wǎng)絡結(jié)構(gòu)[4-6]，節(jié)點間只在某一時間或某段時間發(fā)生交互作用，存在一定的時間關系特性且具有明顯的交互順序，具有這種特征的網(wǎng)絡被稱為時序網(wǎng)絡[7-8]，一般將其抽象為時序圖進行表示。時序網(wǎng)絡模型涵蓋了節(jié)點間聯(lián)系的時間屬性信息，是對現(xiàn)實社交情況的真實反映，以其為對象進行IM 問題的研究具有現(xiàn)實意義。

現(xiàn)有基于時序網(wǎng)絡的影響力最大化算法較少，文獻[9]中所給出的IMIT（improved method for the influence maximization problem on temporal graph）算法需要采用數(shù)萬次蒙特卡羅模擬方法計算單一節(jié)點影響力，因此耗費了大量的運行時間，雖然最終所得種子節(jié)點集影響力較高，但算法時間效率過低而不能高效地完成大規(guī)模網(wǎng)絡中種子節(jié)點的挖掘。與文獻[9]相比，文獻[10]中所給出的種子節(jié)點挖掘算法在運行時間上至少降低了一個數(shù)量級，但面對大規(guī)模網(wǎng)絡數(shù)據(jù)時，該算法無法保證種子節(jié)點的質(zhì)量，會出現(xiàn)種子節(jié)點集影響范圍損失較大的情況。算法時間效率是處理大規(guī)模數(shù)據(jù)首要考慮的問題，脫離算法精度只談時間效率也不符合實際，如何做到種子節(jié)點集影響范圍與算法時間效率之間的平衡，從而高效地完成大規(guī)模時序網(wǎng)絡中種子節(jié)點挖掘這一問題尚待解決。鑒于此，本文提出了一種將啟發(fā)式算法和貪心策略相融合的種子節(jié)點挖掘算法，該算法集中了啟發(fā)式算法速度快與貪心策略精度高這2 個優(yōu)勢，首先，結(jié)合時序圖中信息傳播的時序特性，對單一節(jié)點影響力進行啟發(fā)式評估，從而篩選出一定數(shù)量有影響力的候選節(jié)點；其次，基于貪心策略，通過計算候選節(jié)點的邊際效應，避免由于節(jié)點間影響范圍重疊導致種子節(jié)點集影響力損失較大的情況發(fā)生；最后，力求在時間效率和影響范圍2 個方面均取得良好效果。

本文主要貢獻如下。

1) 結(jié)合時序圖中節(jié)點間聯(lián)系次數(shù)這一因素，在傳統(tǒng)方法的基礎上，提出了一種新的時序圖節(jié)點間傳播概率計算方法，使之更加符合真實社交情況。

2) 給出了一種基于時序圖的節(jié)點影響力評估方法，并根據(jù)節(jié)點影響力的評估結(jié)果，對節(jié)點進行初步篩選，極大地縮小了節(jié)點邊際效應的計算范圍，降低了算法時間復雜度。

3) 在貪心式選取種子節(jié)點階段，進一步優(yōu)化了候選種子節(jié)點邊際效應的計算方法以及利用邊際效應選取種子節(jié)點的策略。

4) 在3 個真實的時序網(wǎng)絡數(shù)據(jù)集上進行了實驗，實驗結(jié)果表明，所提CHG（combining heuristic algorithm and greedy strategy）算法在保證較高影響力的同時，具有相對較低的時間消耗，具備一定的準確性、高效性和可擴展性。

1 相關工作

影響力最大化問題自提出以來，就受到國內(nèi)外學者的廣泛關注。Kempe 等[11]首先將影響力最大化定義為在特定信息傳播模型下挖掘影響力最大的k個節(jié)點的離散優(yōu)化問題，并證明其是一個NP 難問題，同時給出了經(jīng)典的貪心算法，可以達到近似63%的最優(yōu)解。針對貪心算法運行時間過高的問題，Leskovec 等[12]利用邊際效應子模函數(shù)的特性提出了CELF（cost-effective lazy forward selection）算法，實驗結(jié)果顯示該算法比貪心算法的效率提高了近700 倍。Chen 等[13]針對傳統(tǒng)度估計重疊問題，提出了啟發(fā)式算法DegreeDiscount，實驗結(jié)果表明該算法在時間效率上得到了有效的提高。之后，影響力最大化問題被進一步研究，Bagheri 等[14]考慮社交網(wǎng)絡拓撲結(jié)構(gòu)的特點，利用社區(qū)檢測算法對網(wǎng)絡進行劃分，并根據(jù)社區(qū)的結(jié)構(gòu)確定每個社區(qū)的影響節(jié)點配額。王帥等[15]考慮到外界因素對網(wǎng)絡系統(tǒng)的影響，如網(wǎng)絡結(jié)構(gòu)損壞導致網(wǎng)絡連通性被破壞或信息傳播過程中受到干擾，從而定義了穩(wěn)健影響力最大化問題，其目的是尋找具有穩(wěn)健信息傳播能力的種子節(jié)點。Tong 等[16]考慮到信息傳播的時間代價，在種子選擇的每個步驟均加入時間因素，通過在種子選擇的每個階段施加預算限制，在給定的時間范圍內(nèi)實現(xiàn)影響力最大化的目標。

以上IM 算法均是基于靜態(tài)圖模型提出的，基于動態(tài)圖的IM 問題也受到眾多學者的廣泛討論。Yang 等[17]提出通過時間快照將動態(tài)圖轉(zhuǎn)換成多個按時間片離散分布的靜態(tài)圖進行處理，從而完成時態(tài)子圖（temporal subgraph）的挖掘。Sheng 等[18]針對現(xiàn)有基于網(wǎng)絡拓撲結(jié)構(gòu)數(shù)據(jù)存在高維、低效率的局限性，通過網(wǎng)絡表征學習將網(wǎng)絡中的每個節(jié)點轉(zhuǎn)換為低維向量表示，然后在低維潛在空間中解決動態(tài)影響力最大化問題。針對動態(tài)圖中節(jié)點的添加或刪除操作，Wang 等[19]提出一種滑動窗口模型，窗口隨著時間向下滑動來探測節(jié)點的更新，以此完成實時的種子節(jié)點挑選，該算法主要用于解決動態(tài)更新的網(wǎng)絡中種子節(jié)點的挖掘問題。吳安彪等[9]首次以時序圖為研究對象，從網(wǎng)絡全局角度出發(fā)對基于時序圖的影響力最大化問題展開研究，并給出了基于時序圖的影響力最大化算法IMIT，該算法首先利用蒙特卡羅模擬方法計算單個節(jié)點的影響力，然后選定影響力最大的節(jié)點為第一個種子節(jié)點，最后通過計算網(wǎng)絡中剩余節(jié)點邊際效應，并利用邊際效應計算過程中所具有的子模性，得到最終的種子節(jié)點集，實驗結(jié)果顯示該算法所挖掘出的種子節(jié)點集具有極高的影響范圍，但是也付出了較高的時間代價，不能高效地完成大規(guī)模網(wǎng)絡中種子節(jié)點的挖掘工作。在此基礎上，陳晶等[10]更注重算法的時間效率，給出了時序社交網(wǎng)絡兩階段影響力最大化（TIM,two-stage impact maximization）算法，該算法考慮時序圖中節(jié)點間聯(lián)系次數(shù)對節(jié)點重要性的影響，提出以節(jié)點的活躍程度來衡量節(jié)點影響力，并從節(jié)點間聯(lián)系次數(shù)最多的前100 個節(jié)點中確定最終的種子節(jié)點集，實驗表明該算法在時間效率上具有一定優(yōu)勢，但面對大規(guī)模網(wǎng)絡數(shù)據(jù)時，精度略顯不足。

2 基本概念

2.1 時序圖

定義1時序圖（temporal graph）[20-21]。給定網(wǎng)絡表示節(jié)點間具有時序關系的社交網(wǎng)絡有向時序圖[18]。其中，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 時序圖

時序圖與普通靜態(tài)圖相比，最大的不同是節(jié)點之間的聯(lián)系存在時間上的先后順序，即信息傳播具有時序性。例如，圖1 中節(jié)點A 與節(jié)點C 分別在7,9 時刻聯(lián)系，節(jié)點C 與節(jié)點E 已經(jīng)在更早的3,6時刻進行聯(lián)系，在這種情況下，節(jié)點A 便不能把信息通過節(jié)點C 傳遞到節(jié)點E。

2.2 節(jié)點間傳播概率及信息傳播模型

社交網(wǎng)絡中節(jié)點間傳播概率與信息傳播模型是研究IM 問題最基本的2 個要素。

2.2.1 時序圖節(jié)點間傳播概率

定義2傳播概率。活躍節(jié)點u通過有向邊E(u,v)成功激活其鄰居節(jié)點v的概率稱為節(jié)點間的傳播概率，表示為P(u,v)∈[0,1]。

傳統(tǒng)計算節(jié)點間傳播概率有以下2 種方法。1) 隨機賦值方法，例如，設定概率集合P{0.01,0.03,0.05,0.1}，從集合P中隨機選取概率值作為各節(jié)點間的傳播概率，此方法的弊端是所求取的傳播概率并不符合實際情況。2) 度估計方法，即用節(jié)點入度（In-Degree）的倒數(shù)來估計該節(jié)點被上一級節(jié)點激活的概率，如式(1)所示。

時序圖中記錄了節(jié)點間的聯(lián)系次數(shù)，節(jié)點與其鄰居節(jié)點間聯(lián)系次數(shù)越多，激活概率越大，可見節(jié)點的所有入邊并非等值權(quán)重，故該方法并不適用于時序圖中節(jié)點間傳播概率的計算。除父節(jié)點對子節(jié)點的主動激活次數(shù)外，子節(jié)點對父節(jié)點的反向作用也會影響兩節(jié)點間傳播概率的大小，例如，圖1 中節(jié)點B 與節(jié)點E 產(chǎn)生了交互，意味著兩節(jié)點的親密度進一步增大，表現(xiàn)為子節(jié)點更易受父節(jié)點的影響，所以相比于節(jié)點C、D，節(jié)點B 對節(jié)點E 的激活概率更大，因此結(jié)合時序圖中節(jié)點間聯(lián)系的時序信息，對傳統(tǒng)度估計計算傳播概率的方法進行改進，將節(jié)點間聯(lián)系次數(shù)設定為時序邊(u,v)的權(quán)重，則時序邊(u,v)占節(jié)點v所有入邊的比重為則節(jié)點v被節(jié)點u激活的概率可以通過式(2)進行計算。

其中，In(v)表示節(jié)點v的入度節(jié)點集，v′表示入度節(jié)點，表示節(jié)點u,v間的聯(lián)系次數(shù)。

2.2.2 基于時序圖的信息傳播模型

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

以圖1 為例，若節(jié)點A 為種子節(jié)點（設種子節(jié)點的活躍起始時間為0），且其成功激活節(jié)點C，則ActC=min{7,9}=7。

定義4節(jié)點狀態(tài)（state）。節(jié)點狀態(tài)是指節(jié)點在網(wǎng)絡中對信息傳播所能做出的反應，分為活躍狀態(tài)（active）和非活躍狀態(tài)（inactive）。

在初始網(wǎng)絡中，所有節(jié)點v的活躍起始時間均為Actv=-1，節(jié)點狀態(tài)為非活躍狀態(tài)，當選定種子節(jié)點集后，設置種子節(jié)點Actv=0，并將其狀態(tài)修改為活躍狀態(tài)。下面以種子節(jié)點u為例，具體描述信息傳播過程。

1) 種子節(jié)點u以概率嘗試激活其鄰居節(jié)點vi，有且僅有一次激活機會，若成功激活節(jié)點vi，則記錄vi的最早激活時間Activ，并修改節(jié)點狀態(tài)為活躍狀態(tài)；若沒有激活節(jié)點vi，則繼續(xù)嘗試激活下一鄰居節(jié)點vi+1。

2) 若種子節(jié)點的某一鄰居節(jié)點v被成功激活，則節(jié)點v會將信息繼續(xù)傳播下去。節(jié)點v在嘗試激活其鄰居節(jié)點wi時，首先判斷節(jié)點wi是否處于非活躍狀態(tài)，若是則繼續(xù)判斷Activ是否小于或等于maxT(v,wi)，若滿足則以概率P(v,wi)嘗試激活其鄰居節(jié)點wi；否則跳過該節(jié)點嘗試激活下一鄰居節(jié)點wi1+。

3) 信息在整個網(wǎng)絡中由最新的活躍節(jié)點向處于非活躍狀態(tài)的鄰居節(jié)點進行傳播擴散，直到整個網(wǎng)絡沒有新的節(jié)點被激活為止。

3 算法設計

CHG 算法將種子節(jié)點的挖掘分為節(jié)點影響力啟發(fā)式評估、構(gòu)建候選種子節(jié)點集以及種子節(jié)點貪心式選取這3 個步驟。

3.1 節(jié)點影響力啟發(fā)式評估

3.1.1 節(jié)點影響力評估方法的定義

傳統(tǒng)啟發(fā)式度中心性算法是指用節(jié)點度的大小衡量節(jié)點的影響力，節(jié)點度越大，該節(jié)點潛在的影響力就越大，但由于時序圖中信息傳播存在時序性，單一參考節(jié)點度數(shù)尚不能準確判定該節(jié)點在時序圖中作為種子節(jié)點信息傳播效果的好壞。例如，圖2 中節(jié)點a 在5 時刻分別將信息傳播至其后繼一階節(jié)點(b,c,d)，但此時其后繼一階節(jié)點已在更早的時刻與其后繼節(jié)點完成了聯(lián)系，故此種情況下，節(jié)點a 的信息只能傳播至其后繼一階節(jié)點，而無法影響到更高階節(jié)點，這種節(jié)點在全局網(wǎng)絡中的影響力較小。

圖2 時序圖中信息傳播的時序性

時序圖中潛在影響力較大的節(jié)點除具有一定的社交廣度外，還要保證信息的可擴散性，即信息可傳播至更高階節(jié)點。基于以上2 個因素，給出定義5。

定義5二階度（two-order degree）。時序圖中節(jié)點u在滿足信息傳播的時序關系下，在其后繼二階范圍內(nèi)能夠潛在影響到的最多節(jié)點數(shù)，表示為

其中，O(u) 表示節(jié)點u的后繼一階節(jié)點集，表示在滿足信息傳播時序性的條件下，即后繼一階節(jié)點的活躍起始時間早于其繼續(xù)嘗試激活二階節(jié)點的時間，節(jié)點在其后繼二階范圍內(nèi)能夠潛在成功激活的節(jié)點。

二階度大的節(jié)點可以保證信息能夠由中心節(jié)點以更好的效果向外擴散傳播，基于以上分析，本文為時序圖中節(jié)點影響力定義了一種啟發(fā)式計算方法，即以節(jié)點的二階度對其影響力大小進行評估，表示為

其中，Inf (u)表示節(jié)點u的影響力大小。

3.1.2 二階度評估方法可靠性理論依據(jù)

網(wǎng)絡中節(jié)點影響力的傳播是一個離散擴散過程，其圍繞種子節(jié)點向周邊鄰居節(jié)點擴散，并由鄰居節(jié)點繼續(xù)向下后繼一階節(jié)點傳播影響，子節(jié)點被激活的概率總是受到父節(jié)點激活概率的影響，鄰居節(jié)點的階數(shù)越大，節(jié)點被激活的概率越小。文獻[22]證明了節(jié)點u的第i階鄰居節(jié)點v被其成功激活的概率的計算滿足容斥定理。文獻[23]在此基礎上進一步分析得出，在相對較小的傳播概率下，節(jié)點在網(wǎng)絡中的影響力隨著鄰居節(jié)點階數(shù)的增大而逐漸收斂，節(jié)點對其后繼三階鄰居節(jié)點的激活概率會降到較低水平，即使進行數(shù)萬次的蒙特卡羅模擬，信息擴散過程中三階及三階以外的節(jié)點被成功激活的次數(shù)也同樣較少[23]。同時，這也符合Walkers等[24]提出的三度影響力原則，即信息傳播過程中存在內(nèi)部衰減，個人的影響力局限于三階鄰居節(jié)點之內(nèi)，故本文根據(jù)節(jié)點在其后繼二階范圍內(nèi)所能激活的最多節(jié)點數(shù)，即用節(jié)點的二階度來評估其影響力的方法是可靠的，本文方法的誤差率與時間效率通過4.3.3 節(jié)實驗進行了檢驗。

3.2 構(gòu)建候選種子節(jié)點集

定義6邊際效應φ。節(jié)點u的邊際效應是指將其加入種子節(jié)點集S中，所能帶來的影響力增量φs(u)。

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

由于節(jié)點與節(jié)點之間的影響范圍會產(chǎn)生重疊，種子節(jié)點集最終的影響范圍并非每個節(jié)點影響力的簡單相加，故影響力最大的前k個節(jié)點未必是最好的種子節(jié)點組合。針對節(jié)點間影響范圍重疊問題，最有效的解決方法是采用貪心算法思想，每次將當前能夠產(chǎn)生最好影響效果的節(jié)點加入種子節(jié)點集中，直到找到k個種子節(jié)點為止，但此方法要求計算當前網(wǎng)絡中所有節(jié)點的邊際效應，從而延長了算法的運行時間。

文獻[25]表明，大部分社交網(wǎng)絡都具有無標度的特性，即大量節(jié)點擁有少量連接，少量節(jié)點擁有大量連接。網(wǎng)絡中影響力較小的節(jié)點對種子節(jié)點的選取不構(gòu)成影響，卻增加了算法的遍歷范圍與次數(shù)，提升了算法的時間復雜度。因此，CHG 算法通過設置節(jié)點過濾因子r對時序圖節(jié)點進行初步篩選，利用二階度評估方法對節(jié)點影響力進行啟發(fā)式評估，選取影響力評估值較大的前rN個節(jié)點構(gòu)建候選種子節(jié)點集L，這樣可極大地縮小節(jié)點邊際效應的計算范圍，進一步提升算法效率，其中，|L|=rN，N表示網(wǎng)絡節(jié)點總數(shù)，r的取值通過4.3.2 節(jié)相關實驗獲取。

3.3 種子節(jié)點貪心式選取

此階段采用貪心算法思想，通過計算候選節(jié)點的邊際效應，解決節(jié)點間影響力重疊問題，以保證最終獲取最優(yōu)的種子節(jié)點組合。

3.3.1 節(jié)點邊際效應的計算

計算一個節(jié)點邊際效應的傳統(tǒng)方法是將該節(jié)點加入已有種子節(jié)點集中，然后計算新種子集的影響節(jié)點增量，此增量即該節(jié)點邊際效應大小。由于每計算一個節(jié)點的邊際效應都要進行R次信息擴散模擬實驗才可得出最終結(jié)果，因此該方法具有極高的復雜度。針對此問題，本文采用以空間換時間的策略，給出了一種新的節(jié)點邊際效應計算方法，將所有候選種子節(jié)點在時序圖上進行信息模擬擴散傳播，并讀取每個節(jié)點的影響范圍，例如，當前種子集S的影響節(jié)點集為S1={a,b,c,d,e}，節(jié)點u的影響節(jié)點集為U={a,b,f,h}，則只需要計算差集U-S1={f,h}，并統(tǒng)計差集中元素個數(shù)即可得出節(jié)點u的邊際效應，這樣便有效地將節(jié)點邊際效應計算的時間復雜度降低到O(Rrn)+O(1)，其中R表示共進行R次節(jié)點影響范圍模擬實驗。

3.3.2 利用節(jié)點邊際效應確定最優(yōu)種子集

性質(zhì)1子模性。設集合S?T，任意元素x添加到集合S中獲得的函數(shù)收益大于或等于添加到集合T中所獲得的收益，即滿足收益遞減特性，表示為

文獻[12]論證了各個節(jié)點的邊際效應大小是滿足子模性的，即節(jié)點的邊際效應會隨著種子節(jié)點的增多而遞減。IMIT 算法同樣利用了節(jié)點邊際效應計算過程中所具有的子模性，其主要思想如下：1) 如果上一輪中邊際效應第二大節(jié)點w 重新計算的邊際效應大于上一輪中的邊際效應第三大節(jié)點z，則不需要對其余的非種子節(jié)點重新計算邊際效應，直接將w 選為種子節(jié)點即可；2) 否則需要在剩余節(jié)點中找到第一個邊際效應小于節(jié)點w 邊際效應的節(jié)點y，然后重新計算從節(jié)點z到節(jié)點y 這段區(qū)間中所有節(jié)點的邊際效應。

本文針對IMIT 算法進一步優(yōu)化，在算法中設置變量Max_Inf與Max_node以實時更新保存當前邊際效應的最大值及其節(jié)點，在計算下一個節(jié)點之前，用當前邊際效應最大值Max_Inf 與其上輪該節(jié)點的邊際效應進行比較，這樣便可避免IMIT 算法對所截取的一段節(jié)點進行邊際效應的冗余計算問題，CHG算法貪心選取種子節(jié)點流程如表1 所示。其中，數(shù)值表示節(jié)點邊際效應值，√表示選定為種子節(jié)點。

表1 CHG 算法貪心選取種子節(jié)點流程

首先，選定候選種子節(jié)點中影響力最大的節(jié)點a為第一個種子節(jié)點。其次，從節(jié)點b 開始進行第2 輪節(jié)點邊際效應計算，并將其寫入變量Max_Inf 和Max_node 中，在計算下一個節(jié)點c 之前，先用當前邊際效應的最大值Max_Inf與上一輪中節(jié)點c的邊際效應進行比較（30＜60），判斷是否需要繼續(xù)計算節(jié)點c 的邊際效應，并對變量Max_Inf 與Max_node 進行更新，同樣地，在計算下一個節(jié)點d 之前，將Max_Inf與上一輪中節(jié)點d 的邊際效應進行比較（50〉40），根據(jù)子模性可知，節(jié)點c 即此輪邊際效應的最大節(jié)點，直接將其選出即可。在IMIT 算法中至少要計算b,c,d,e 這4 個節(jié)點的邊際效應，而對其優(yōu)化后只需要計算b,c 這2 個節(jié)點。CHG 算法如下所示。

步驟1)表示將種子節(jié)點集S與候選種子節(jié)點集L初始化為空集；步驟2)～步驟4)表示對時序圖中節(jié)點影響力進行評估；步驟5)～步驟8)表示選取前rN個影響力較大的節(jié)點構(gòu)建候選種子節(jié)點集L；步驟9)～步驟10)表示對候選種子節(jié)點按影響力大小排序，并裝入隊列Q中。步驟11)～步驟22)表示貪心式計算節(jié)點邊際效應，并選取出最終的k個種子節(jié)點，其中步驟16)～步驟18)表示利用子模性減少對非必要節(jié)點的計算，提前結(jié)束算法程序遍歷（偽代碼中s′表示上一輪種子節(jié)點集）。計算時序圖中所有節(jié)點二階度時間復雜度為O(n2)，按節(jié)點影響力大小排序并構(gòu)建候選種子節(jié)點的時間復雜度為O(nlog(n))，在貪心選取種子節(jié)點階段，計算所有候選種子節(jié)點的影響范圍時間復雜度為O(Rrn)，計算節(jié)點邊際效應的時間復雜度為O(1)，利用子模性性質(zhì)選取k個種子節(jié)點的時間復雜度為O(k)，故CHG 算法的時間復雜度為O(n2)+O(nlog(n))+O(Rrn)+O(k),n=N。

4 實驗與分析

4.1 實驗設置

4.1.1 實驗環(huán)境

操作系統(tǒng)為Windows 10，英特爾處理器 Core i5-6300HQ 四核，內(nèi)存為 8 GB，編程語言為Python3.0，編程環(huán)境為Pycharm。

4.1.2 實驗數(shù)據(jù)

本節(jié)實驗選取3 個不同規(guī)模的時序社交網(wǎng)絡數(shù)據(jù)集，具體參數(shù)如表2 所示。

表2 實驗數(shù)據(jù)集參數(shù)

Digg 數(shù)據(jù)集[26]記錄了社交新聞網(wǎng)站Digg 某段時間內(nèi)用戶間相互評論的信息；Mathoverflow 數(shù)據(jù)集[27]是根據(jù)Mathoverflow 網(wǎng)站上的問答信息生成的社交網(wǎng)絡；Superuser 數(shù)據(jù)集[27]是由堆棧交換網(wǎng)站Superuser 所生成的時序網(wǎng)絡圖。

4.2 實驗內(nèi)容

本節(jié)實驗從種子節(jié)點集的影響范圍與運行時間2 個方面對算法進行綜合評價，除本文所提CHG 算法外，分別復現(xiàn)了以下5 種算法，作為實驗對比算法。

IMIT 算法[9]。該算法采用10 000 次蒙特卡羅模擬計算單個節(jié)點的影響力，并基于貪心思想利用節(jié)點邊際效應完成種子節(jié)點的最終選取。

TIM 算法[10]。該算法以節(jié)點間聯(lián)系次數(shù)評價節(jié)點影響力，并從評價值較大的前100 個節(jié)點中篩選出最終的種子節(jié)點集。

Degree 算法。該算法是經(jīng)典度啟發(fā)式算法，將節(jié)點按照出度（Out-Degree）大小進行排序，直接選取前k個節(jié)點作為種子節(jié)點。

DegreeDiscount 算法[13]。該算法是啟發(fā)式算法的代表，選取度數(shù)最大的節(jié)點作為種子節(jié)點，然后將所選節(jié)點鄰居的度數(shù)進行折扣，直到選出k個節(jié)點。

Random 算法。該算法是基準比較算法，從時序圖中隨機選取k個非重復節(jié)點作為種子節(jié)點，該算法隨機性較大，共對其做500 次實驗，實驗結(jié)果取平均值。

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

4.3.1 復雜網(wǎng)絡無標度性的驗證

為了驗證復雜網(wǎng)絡的無標度特性，對3 個數(shù)據(jù)集中的節(jié)點度分布情況進行了統(tǒng)計，結(jié)果如圖3所示。

圖3 數(shù)據(jù)集節(jié)點度分布情況

圖3 中橫坐標代表節(jié)點出度，縱坐標代表該值所對應節(jié)點的個數(shù)與總節(jié)點個數(shù)的比值，即出現(xiàn)頻率（Frequency），這里以對數(shù)形式表示。從圖3 中可以看出，3 個數(shù)據(jù)集中節(jié)點的度均服從冪律分布，說明具有較大影響力的節(jié)點分布較稀疏，大部分節(jié)點都擁有少量連接，影響力較小，這為CHG 算法構(gòu)建候選種子節(jié)點集的方法提供了有力依據(jù)。

4.3.2 節(jié)點過濾因子r值的設定

為了修剪網(wǎng)絡中大部分影響力較小的節(jié)點，算法通過設定節(jié)點過濾因子r，依據(jù)3.1 節(jié)中獲得的節(jié)點影響力評估結(jié)果對其進行過濾篩選，r值的大小將直接影響算法的精度，因此，本文通過實驗檢驗了不同r值對算法精度的影響，并確定了一個最合適的r值，從而使算法獲得更高的準確性和更低的時間復雜度。由于時序信息傳播模型是以經(jīng)典獨立級聯(lián)模型為基礎修改得到的，依舊存在獨立級聯(lián)模型中節(jié)點激活過程不確定性的特點。為了讓實驗更具說服力，在實驗中，對節(jié)點間的傳播概率進行相應的調(diào)整，將由式(2)計算出的傳播概率P分別縮小50%、增大一倍，觀察在3 種不同的傳播概率下，不同r值時CHG 算法所得種子節(jié)點集的影響范圍，實驗結(jié)果如圖4 所示。

從圖4 中可以看到，當r值為0.1～0.2 時，種子節(jié)點集影響范圍隨著r值的增大而增大；當r值為0.2～0.3 時，種子節(jié)點集影響范圍略有上升，幅度較小；當r值大于0.3 時，種子節(jié)點集影響范圍趨于收斂。產(chǎn)生以上結(jié)果是因為隨著r值的增大，越來越多影響力較高的節(jié)點進入候選種子節(jié)點集，可供算法挑選的節(jié)點增多，故在一定范圍內(nèi)，種子節(jié)點集的影響力不斷升高。隨著r值的增大，一些影響力相對較低的節(jié)點進入了候選種子節(jié)點集，但其對最終種子節(jié)點的挑選不構(gòu)成影響，不會改變實驗結(jié)果，所以最終種子節(jié)點集的影響力趨于平穩(wěn)。由此可見，r值過小，可能導致一些有影響力的節(jié)點被過濾掉，從而影響算法的精度；r值過大，則會出現(xiàn)過濾效果不明顯，造成候選種子節(jié)點集中存在冗余節(jié)點。當r取值為0.2 時，既有效控制了候選種子集的規(guī)模，又能保證最終種子節(jié)點集具有較高的影響力。

圖4 不同r 值時算法CHG 所得種子節(jié)點集影響范圍

4.3.3 節(jié)點影響力二階度評估方法性能實驗

為了驗證節(jié)點影響力二階度評估方法的準確性，本文實驗采用10 000 次蒙特卡羅模擬方法計算節(jié)點的精確影響力，分析節(jié)點影響力二階度評估方法誤差率（ER,error rate），實驗結(jié)果如圖5 所示。其中，橫坐標表示采用2 種方法所得影響力排名靠前的x個節(jié)點（N表示節(jié)點總數(shù)），縱坐標表示與蒙特卡羅模擬方法相比，二階度評估方法所得結(jié)果的誤差率，計算式為

其中，集合A、B分別表示采用蒙特卡羅模擬方法與二階度評估方法所計算出的影響力排名靠前的x個節(jié)點的集合。由圖5 可知，隨著節(jié)點影響力計算范圍的增大，二階度評估方法的誤差率也逐漸下降，相比于更精確的蒙特卡羅模擬方法，其獲取影響力排名前0.20N個節(jié)點的計算誤差率降到了0.05 左右，由此可見，利用節(jié)點二階度評估節(jié)點影響力，并根據(jù)評估結(jié)果構(gòu)建候選種子節(jié)點集的方法具有較高準確性。

圖5 節(jié)點影響力二階度評估方法誤差率

本節(jié)采用2 種方法計算網(wǎng)絡所有節(jié)點影響力的運行時間，結(jié)果如圖6 所示。從圖6 可知，蒙特卡羅模擬方法時間復雜度較高，尤其處理較大規(guī)模網(wǎng)絡時，運行時間過長，在大規(guī)模數(shù)據(jù)集Superuser下，其運行時間已超過140 s，相比之下，二階度評估方法具有更高的時間效率。

圖6 運行時間對比

4.3.4 不同算法所得種子節(jié)點集影響力對比

為了驗證算法在影響范圍指標上的效果，在特定時序信息傳播模型下，對本文所提CHG 算法以及復現(xiàn)的5 種對比算法進行了種子節(jié)點集的影響力對比，種子節(jié)點的數(shù)量k分別設為10,20,30,40,50，最終實驗結(jié)果如圖7～圖9 所示。

圖7 不同算法所得種子節(jié)點集影響范圍（Digg）

圖8 不同算法所得種子節(jié)點集影響范圍（Mathoverflow）

圖9 不同算法所得種子節(jié)點集影響范圍（Superuser）

在Digg 數(shù)據(jù)集下，6 種算法所得種子節(jié)點集的影響范圍均隨著種子節(jié)點數(shù)的增多而增大，IMIT 算法的影響范圍最大，與之相比，在5 個不同數(shù)量的種子節(jié)點集下，CHG 算法的影響范圍分別下降了4.8%、5.2%、5.3%、7.2%、9.3%。當k＜30 時，TIM 影響范圍與IMIT、CHG 接近；當k〉30 時，TIM 的影響范圍開始下降，與IMIT、CHG 之間的差距逐漸增大。

在Mathoverflow 數(shù)據(jù)集下，CHG 算法影響范圍相比于IMIT 算法在5 個種子節(jié)點集下分別下降了11.1%、8.9%、6.4%、7.6%、7.9%。當k＜20 時，TIM 影響范圍與CHG 接近；當k〉20 時，2 種算法之間的差距逐漸增大。在更大規(guī)模的數(shù)據(jù)集Superuser 下，TIM 的影響效果與IMIT、CHG 的差距更為明顯，其影響范圍相比于IMIT 分別下降了33.5%、20.9%、19.5%、19.1%、18.2%。而CHG曲線與IMIT 曲線接近，5 個種子節(jié)點集下影響范圍分別下降了4.2%、8.1%、7.5%、5.4%、3.3%。DegreeDiscount 與Degree 在時序圖上表現(xiàn)出的影響效果一般，2 個啟發(fā)式算法影響范圍相比于IMIT分別下降了53.2%與68.8%。

產(chǎn)生上述實驗結(jié)果的原因如下。Degree 算法不足之處在于其只關注了單一節(jié)點影響力大小，卻忽略了節(jié)點間的相互作用，同時，由于時序圖上信息傳播所具有的時序性，該算法對單一節(jié)點影響力的評估也不夠準確，這2 個因素導致Degree算法所得種子節(jié)點質(zhì)量下降，DegreeDiscount 算法針對此問題進行了改進，但是相對于貪心算法來說，其所挖掘出的種子節(jié)點集的影響力仍然有一定差距。TIM 算法以節(jié)點間聯(lián)系次數(shù)來簡單評價節(jié)點的重要程度，然后截取前100 個節(jié)點進行最終種子節(jié)點的挑選，節(jié)點間聯(lián)系次數(shù)更多反映的是傳播概率的大小，用來衡量節(jié)點影響力尚存在一定誤差，故導致一些真實影響力較大的節(jié)點，或者更好的節(jié)點組合并不存在于前100 個節(jié)點之中，則所選出的種子集也并非最優(yōu)的節(jié)點組合，這是造成TIM 算法影響力損失的主要原因。另外，TIM 算法在面對小規(guī)模數(shù)據(jù)集或種子節(jié)點數(shù)較小時，尚可以獲得相對較好的效果；當面對大規(guī)模數(shù)據(jù)集時，TIM 算法誤差性開始顯現(xiàn)，其影響力將會大幅下降，正如文獻[10]所述，TIM 算法更適用于中小規(guī)模網(wǎng)絡上的種子節(jié)點挖掘。IMIT 算法采用蒙特卡羅模擬方法計算單一節(jié)點影響力，再通過計算節(jié)點邊際效應而得出最終種子節(jié)點集，獲得了極高的影響力。CHG 算法首先對單一節(jié)點影響力進行啟發(fā)式評估，并根據(jù)評估結(jié)果選取影響力最大的前rN個節(jié)點構(gòu)建候選種子節(jié)點集，然后貪心選取種子節(jié)點，以保證最優(yōu)的種子節(jié)點組合，故最終達到了與IMIT 影響力非常接近的理想效果。由于CHG 算法將種子節(jié)點的篩選范圍縮小至候選種子節(jié)點集，該集合基本涵蓋了對最終實驗結(jié)果產(chǎn)生影響的所有節(jié)點，但不完全排除被過濾掉的節(jié)點是某輪邊際效應計算中最大值節(jié)點的可能性，這是造成CHG 算法所得種子節(jié)點集影響范圍略低于IMIT 算法的主要原因。

4.3.5 不同算法運行時間對比

1)為了驗證CHG 算法在利用節(jié)點邊際效應貪心式選取種子階段對IMIT 算法的優(yōu)化，對2 種算法在該階段選取50 個種子節(jié)點的運行時間進行了實驗對比，結(jié)果如圖10 所示。從圖10 中可以看到，CHG 算法相比IMIT 算法在3 個數(shù)據(jù)集下挖掘50 個種子節(jié)點運行時間均更小，這是因為隨著數(shù)據(jù)集規(guī)模的增大，IMIT 算法將會面臨較為復雜的節(jié)點邊際效應計算，而CHG 算法通過對節(jié)點邊際效應的計算方法進行改進，同時又優(yōu)化了利用邊際效應選點的策略，極大限度地降低了計算的復雜程度，實驗數(shù)據(jù)顯示，此階段CHG 算法比IMIT 算法節(jié)省了59%～71%的運行時間。

圖10 貪心式選取種子節(jié)點階段運行時間

2) 6 種算法在3 個數(shù)據(jù)集下分別挖掘50 個種子節(jié)點的運行時間如表3 所示。

表3 算法運行時間

從表3 中可以看到，在6 種算法中，IMIT 算法運行時間最長，盡管該算法在種子節(jié)點選取的過程中利用了節(jié)點邊際效應的子模性，但是在對單一節(jié)點影響力計算上耗費了大量時間，導致算法最終運行時間較高。相比之下，CHG 算法對節(jié)點影響力進行啟發(fā)式評估，根據(jù)評估結(jié)果構(gòu)建候選種子節(jié)點集，并對節(jié)點邊際效應的計算方法進行了優(yōu)化，減少了對非必要節(jié)點的遍歷計算，極大限度地降低了算法時間復雜度，最終的運行時間相比于IMIT 算法在3 個數(shù)據(jù)集下分別減少了68.2%、85.1%、94.0%。TIM 在時間效率方面表現(xiàn)良好是因為該算法極大限度上縮減了種子節(jié)點的篩選范圍，將最終的種子節(jié)點局限于影響力最大的前100 個節(jié)點之中，直接導致了算法最終所得種子節(jié)點集影響力的下降，可見該算法在追求時間高效的同時，也犧牲了一定的準確性。

綜上所述，與IMIT 算法相比，CHG 算法在運行時間上平均縮短了82.4%，而影響范圍僅平均降低了6.9%，算法展現(xiàn)出了一定的高效性與可擴展性，更好地做到了影響范圍與時間效率2 個方面之間的平衡，即使在大規(guī)模網(wǎng)絡中，CHG 算法也能避免TIM 算法所出現(xiàn)準確率低的問題，并能夠高效地完成大規(guī)模時序圖中種子節(jié)點的挖掘。

5 結(jié)束語

為了解決時序圖中種子節(jié)點集影響范圍與算法時間效率兩者間如何取得平衡，從而能夠高效地完成大規(guī)模數(shù)據(jù)集下種子節(jié)點挖掘這一問題，本文給出了一種將啟發(fā)式算法和貪心策略相結(jié)合的種子節(jié)點挖掘算法CHG，首先對節(jié)點影響力進行啟發(fā)式評估，并以此構(gòu)建候種子節(jié)點集，最后對候選節(jié)點進行邊際效應的計算，從而得到最終的種子節(jié)點集。實驗結(jié)果表明，CHG 在時間效率與影響范圍2 方面均取得了理想效果，為大規(guī)模時序網(wǎng)絡中種子節(jié)點的挖掘提供了更高效的策略。

在未來的工作中將會考慮進行如下深入研究。1) 針對不同類型的時序社交網(wǎng)絡，進一步結(jié)合節(jié)點激活成本、耗費時間、不同信息類型等更多實際因素，研究如何進行種子節(jié)點的挖掘；2) 本文從全局的角度出發(fā)研究時序社交網(wǎng)絡的影響力最大化問題，下一步可以嘗試對時序圖進行時間切片，以動態(tài)的視角研究實時影響力最大化問題。