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

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

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

0 引言

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

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

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

本文主要貢獻(xiàn)如下。

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

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

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

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

1 相關(guān)工作

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

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

2 基本概念

2.1 時(shí)序圖

定義1時(shí)序圖（temporal graph）[20-21]。給定網(wǎng)絡(luò)表示節(jié)點(diǎn)間具有時(shí)序關(guān)系的社交網(wǎng)絡(luò)有向時(shí)序圖[18]。其中，V表示節(jié)點(diǎn)的集合，E表示邊的集合，TE表示圖中所有節(jié)點(diǎn)之間存在聯(lián)系時(shí)刻的集合，T(u,v)表示節(jié)點(diǎn)u和v之間存在聯(lián)系時(shí)刻的集合，T(u,v)∈TE，u,v∈V。

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

圖1 時(shí)序圖

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

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

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

2.2.1 時(shí)序圖節(jié)點(diǎn)間傳播概率

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

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

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

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

2.2.2 基于時(shí)序圖的信息傳播模型

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

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

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

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

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

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

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

3 算法設(shè)計(jì)

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

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

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

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

圖2 時(shí)序圖中信息傳播的時(shí)序性

時(shí)序圖中潛在影響力較大的節(jié)點(diǎn)除具有一定的社交廣度外，還要保證信息的可擴(kuò)散性，即信息可傳播至更高階節(jié)點(diǎn)?；谝陨? 個(gè)因素，給出定義5。

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3.1 節(jié)點(diǎn)邊際效應(yīng)的計(jì)算

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 實(shí)驗(yàn)環(huán)境

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

4.1.2 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

4.2 實(shí)驗(yàn)內(nèi)容

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

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

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

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

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

Random 算法。該算法是基準(zhǔn)比較算法，從時(shí)序圖中隨機(jī)選取k個(gè)非重復(fù)節(jié)點(diǎn)作為種子節(jié)點(diǎn)，該算法隨機(jī)性較大，共對其做500 次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果取平均值。

4.3 實(shí)驗(yàn)結(jié)果及分析

4.3.1 復(fù)雜網(wǎng)絡(luò)無標(biāo)度性的驗(yàn)證

為了驗(yàn)證復(fù)雜網(wǎng)絡(luò)的無標(biāo)度特性，對3 個(gè)數(shù)據(jù)集中的節(jié)點(diǎn)度分布情況進(jìn)行了統(tǒng)計(jì)，結(jié)果如圖3所示。

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

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

4.3.2 節(jié)點(diǎn)過濾因子r值的設(shè)定

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

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

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

4.3.3 節(jié)點(diǎn)影響力二階度評估方法性能實(shí)驗(yàn)

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

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

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

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

圖6 運(yùn)行時(shí)間對比

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

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

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

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

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

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

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

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

4.3.5 不同算法運(yùn)行時(shí)間對比

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

圖10 貪心式選取種子節(jié)點(diǎn)階段運(yùn)行時(shí)間

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

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

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

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

5 結(jié)束語

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

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