基于拓?fù)鋭?shì)的影響力最大化算法

王秀芳，牛煒南，孫承愛(ài)，仇麗青

(山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，山東 青島 266510)

0 引 言

近年來(lái)，很多大型社交網(wǎng)絡(luò)不斷涌現(xiàn)，人們可以通過(guò)微信，qq和微博等社交網(wǎng)絡(luò)獲取有價(jià)值的信息。于是，商家趨向于在社交網(wǎng)絡(luò)上發(fā)布廣告信息，讓信息通過(guò)社交網(wǎng)絡(luò)傳播的更廣。例如，商家在想要推銷(xiāo)一款產(chǎn)品時(shí)，首先選擇一些有影響力的人來(lái)接受它們，讓他們推薦給自己的朋友，朋友的朋友，依次影響更多的人購(gòu)買(mǎi)這款產(chǎn)品，這就是“口碑效應(yīng)”。最近比較流行一種職業(yè)-美妝博主，他們通過(guò)在線試妝，根據(jù)用戶的要求試該產(chǎn)品，然后分析其產(chǎn)品的優(yōu)點(diǎn)，推薦該產(chǎn)品，使得很多人對(duì)此產(chǎn)品滿意，主動(dòng)去搶購(gòu)該產(chǎn)品，最終使得產(chǎn)品庫(kù)存不足，那么，這些商家如何選擇合適的美妝博主為他們?cè)噴y，使得產(chǎn)品推廣的更好，這就是“影響力最大化問(wèn)題”。當(dāng)然，社交網(wǎng)絡(luò)中的影響力最大化問(wèn)題還有很多其余的應(yīng)用。比如，職業(yè)路徑的預(yù)測(cè)。用戶根據(jù)自己的基本信息，提取到人生的各個(gè)階段中最具影響力的因素和特征，從而預(yù)測(cè)未來(lái)可能從事的職業(yè)。這樣對(duì)自己的人生規(guī)劃有著重要的意義。

IMP(influence maximization problem)作為數(shù)學(xué)優(yōu)化問(wèn)題解決的第一個(gè)模型是由Kempe等建立的，驗(yàn)證了影響力最大化問(wèn)題是一個(gè)NP問(wèn)題，提出運(yùn)用貪心算法和Monte Carlo模擬解決該問(wèn)題，然而貪心算法的時(shí)間復(fù)雜度高，不適合大型社交網(wǎng)絡(luò)。為了提高算法的運(yùn)行時(shí)間，一系列啟發(fā)式算法被研究者們相繼提出。然而，啟發(fā)式算法在準(zhǔn)確率方面還有待提高。研究發(fā)現(xiàn)，貪心階段和啟發(fā)階段相結(jié)合的綜合型算法可以適當(dāng)均衡影響力和運(yùn)行時(shí)間，這是最近的研究熱點(diǎn)。拓?fù)鋭?shì)理論[1]首次在物理學(xué)中提出，近年來(lái)被應(yīng)用到社交網(wǎng)絡(luò)中用來(lái)衡量節(jié)點(diǎn)重要性，并取得了一定的效果。

因此，為了均衡運(yùn)行時(shí)間和影響力，從而更有效解決影響力最大化問(wèn)題，本文提出了一種基于拓?fù)鋭?shì)的影響力最大化算法，TSH(topology-stage-heuristic)算法。首先，啟發(fā)式階段：基于拓?fù)鋭?shì)理論，識(shí)別“山峰”，“山谷”和“斜坡”節(jié)點(diǎn)，選擇“山峰”和“斜坡”節(jié)點(diǎn)作為候選種子集。然后，貪心階段：使用CELF算法[2]從候選種子集中選擇最優(yōu)種子集。

1 相關(guān)研究

影響力最大化問(wèn)題被Kempe等提出后，因?yàn)槠鋸V泛的應(yīng)用，得到了研究者們極大的關(guān)注。目前，研究者對(duì)此問(wèn)題的解決方法可以歸納為兩類：貪心算法和啟發(fā)式算法。

自從Richardson和Domingos等[1]將影響力最大化問(wèn)題歸納為算法問(wèn)題后，Kempe等[2]提出了貪心算法來(lái)解決此問(wèn)題。貪心算法需要重復(fù)計(jì)算節(jié)點(diǎn)的影響增益，然后選擇影響力增益最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，導(dǎo)致了其在大規(guī)模社交網(wǎng)絡(luò)上運(yùn)行時(shí)間慢，不適合大規(guī)模社交網(wǎng)絡(luò)。為了解決貪心算法時(shí)間效率低的問(wèn)題，一些優(yōu)化算法被提出，比如經(jīng)典的CELF算法[3]，它利用子模性來(lái)減少計(jì)算的時(shí)間，從而提高運(yùn)行時(shí)間。然而，這些優(yōu)化算法雖然提高了運(yùn)行時(shí)間，但是在面對(duì)大規(guī)模社交網(wǎng)絡(luò)時(shí)仍存在時(shí)間效率問(wèn)題。因此，一系列啟發(fā)式算法被研究者們提出[4-20]。Nguyen等[5]提出了一種基于概率的多跳擴(kuò)散方法來(lái)解決影響力最大化問(wèn)題，該算法考慮了多跳鄰居節(jié)點(diǎn)的影響，從而提高算法的準(zhǔn)確性。Han Meng等[6]將時(shí)間延遲，接受率和傳播寬度這3個(gè)因素相結(jié)合，研究了一個(gè)新的模型，其運(yùn)行結(jié)果優(yōu)于傳統(tǒng)的算法。另外，Kyomin Jung等[7]提出了包括信息排序和信息評(píng)估兩個(gè)方面的IRIE(influence ranking influence estimation)算法，此算法在運(yùn)行時(shí)間和影響范圍上有了明顯的提高。與上述研究方向不同，Cao等[8]結(jié)合度和核提出了CCA(core covering algorithm)算法，首先從核心開(kāi)始選擇度比較大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)，一旦某個(gè)節(jié)點(diǎn)被選為種子節(jié)點(diǎn)，其鄰居節(jié)點(diǎn)將會(huì)被覆蓋。該算法可能覆蓋部分影響力較高的節(jié)點(diǎn)，使得影響范圍不太準(zhǔn)確。為了解決重疊社區(qū)的影響力問(wèn)題，Qiu等[20]提出了IM-BOC(influence maximization algorithm based on overlapping community)算法。該算法分為3個(gè)階段：劃分社區(qū)，啟發(fā)階段和貪心階段。

近年來(lái)，很多研究者將拓?fù)鋭?shì)理論應(yīng)用于社交網(wǎng)絡(luò)[21-24]，并取得了很好效果。復(fù)雜網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)并不是孤立存在的，而是通過(guò)邊相互聯(lián)系，從而可以使用拓?fù)鋭?shì)場(chǎng)來(lái)進(jìn)行模擬。假設(shè)一個(gè)節(jié)點(diǎn)為一個(gè)場(chǎng)源，則它會(huì)作用于場(chǎng)中的其它節(jié)點(diǎn)，從而構(gòu)成了拓?fù)鋭?shì)場(chǎng)。文獻(xiàn)[21]基于拓?fù)鋭?shì)，提出了一種基于位置的重疊社區(qū)發(fā)現(xiàn)方法。文獻(xiàn)[22]利用拓?fù)鋭?shì)來(lái)評(píng)估節(jié)點(diǎn)重要性。與上述不同的是，何婧等[23]利用拓?fù)鋭?shì)來(lái)進(jìn)行動(dòng)態(tài)社區(qū)挖掘。

綜上所述，為了解決影響力最大化問(wèn)題中效率和效益問(wèn)題，本文首先使用拓?fù)鋭?shì)理論挖掘社交網(wǎng)絡(luò)中的“山峰”，“山谷”和“斜坡”節(jié)點(diǎn)，選取“山峰”和“山谷”節(jié)點(diǎn)作為候選種子集。然后，采用CELF算法確定最優(yōu)種子集。這樣，在保證影響范圍的情況下，有效提高了算法的運(yùn)行時(shí)間，從而彌補(bǔ)傳統(tǒng)算法的缺陷。

2 影響力最大化與傳播模型

2.1 問(wèn)題描述

用網(wǎng)絡(luò)圖G(V,E) 表示是社交網(wǎng)絡(luò)，V表示節(jié)點(diǎn)，E表示邊。按照某種指標(biāo)(度指標(biāo)，介數(shù)指標(biāo)，最短路徑等)，從所有節(jié)點(diǎn)中選取k個(gè)影響力最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)(激活狀態(tài))，按照規(guī)定的傳播模型將其消息傳播給其鄰居節(jié)點(diǎn)，使得最終影響到的節(jié)點(diǎn)最多。其具體表示如下所示

σ(S*)=max{σ(S)|S?V,|S|=k}

(1)

2.2 傳播模型

社交網(wǎng)絡(luò)信息傳播的模型中，有兩種比較常用的傳播模型：獨(dú)立級(jí)聯(lián)(independent cascade，IC)模型和線性閾值(linear threshold，LT)模型。在這兩種模型中，節(jié)點(diǎn)只有一種狀態(tài)，要么激活態(tài)，要么非激活態(tài)。一個(gè)節(jié)點(diǎn)只可從非激活態(tài)轉(zhuǎn)換為激活態(tài)，反之，不成立。一旦節(jié)點(diǎn)被其它節(jié)點(diǎn)激活或者未被其它節(jié)點(diǎn)激活，這個(gè)節(jié)點(diǎn)將保持激活態(tài)或者未激活態(tài)，不會(huì)再改變。IC模型假設(shè)種子集處于激活態(tài)，其它節(jié)點(diǎn)為未激活態(tài)，種子節(jié)點(diǎn)有且僅有一次機(jī)會(huì)去激活其鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)要么被激活，要么未被激活。而LT模型是對(duì)節(jié)點(diǎn)的激活概率進(jìn)行累計(jì)，當(dāng)達(dá)到一定閾值時(shí)，節(jié)點(diǎn)則會(huì)被激活。否則，節(jié)點(diǎn)將不會(huì)再被激活，保持非激活態(tài)。因?yàn)镮C模型容易理解，而且比較符合信息傳播特征，大多數(shù)研究采用IC模型，因此，本文也選用IC模型。該模型的傳播流程如下所示：

(1)設(shè)種子集S為激活狀態(tài)，其余節(jié)點(diǎn)為未激活態(tài)；

(2)激活態(tài)節(jié)點(diǎn)S以概率p去嘗試激活其每一個(gè)鄰居節(jié)點(diǎn)v；

(3)若節(jié)點(diǎn)v被激活，則v為激活狀態(tài)，v將會(huì)重復(fù)(2)。否則，v是為未激活狀態(tài)，它將保持此狀態(tài)，不會(huì)再改變狀態(tài)；

(4)不斷重復(fù)上述過(guò)程，直至所有的節(jié)點(diǎn)都保持一種狀態(tài)。

3 算法實(shí)現(xiàn)

為了均衡影響力范圍和運(yùn)行時(shí)間，本文提出了一種基于拓?fù)鋭?shì)的影響力最大化算法。該算法主要由以下兩個(gè)階段組成：?jiǎn)l(fā)式階段和貪心階段。啟發(fā)式階段，運(yùn)用拓?fù)鋭?shì)理論，鑒別“山峰”，“山谷”和“斜坡”節(jié)點(diǎn)?！吧椒濉惫?jié)點(diǎn)為影響力較大的節(jié)點(diǎn)，而“斜坡”節(jié)點(diǎn)為連接節(jié)點(diǎn)，我們將“山峰”和“山谷”節(jié)點(diǎn)加入候選種子集中。貪心階段，采用CELF算法從候選種子集中確定最優(yōu)種子集。其結(jié)構(gòu)框架如圖1所示。

圖1 算法框架

3.1 啟發(fā)式階段：選取候選種子集

拓?fù)鋭?shì)理論自從被提出后，很多研究者將其用于社交網(wǎng)絡(luò)。本文中，我們將節(jié)點(diǎn)的拓?fù)鋭?shì)作為衡量節(jié)點(diǎn)影響力指標(biāo)。拓?fù)鋭?shì)理論需要研究的重點(diǎn)是如何評(píng)估節(jié)點(diǎn)的質(zhì)量，節(jié)點(diǎn)的影響力因子以及節(jié)點(diǎn)間的最短路徑。因?yàn)楣?jié)點(diǎn)之間距離越遠(yuǎn)，受到的影響可能越小。

3.1.1 拓?fù)鋭?shì)

定義1 拓?fù)鋭?shì)：節(jié)點(diǎn)v的拓?fù)鋭?shì)計(jì)算方法如下

(2)

其中，nn為節(jié)點(diǎn)v的二度鄰居節(jié)點(diǎn)，u為節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)，m(u) 為節(jié)點(diǎn)u的質(zhì)量(如式(4)所示)，σ為影響力因子(如式(3)所示)，dvu為節(jié)點(diǎn)v和節(jié)點(diǎn)u之間的距離，取值為1或2(若鄰居節(jié)點(diǎn)，則取值為1；若二度鄰居節(jié)點(diǎn)，則取值為2)。

3.1.2 影響力因子

影響力因子σ用來(lái)控制節(jié)點(diǎn)的影響范圍。通?？筛鶕?jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的勢(shì)熵來(lái)篩選。勢(shì)熵的大小與網(wǎng)絡(luò)的不確定性有關(guān)。勢(shì)熵越小，網(wǎng)絡(luò)的不確定性越小，網(wǎng)絡(luò)的分布越不均勻。

定義2 勢(shì)熵：設(shè)節(jié)點(diǎn)v的拓?fù)鋭?shì)為φ(v)， 則勢(shì)熵為

(3)

由式(2)可知，當(dāng)σ=0時(shí)，φ(u→v)→0時(shí)，則說(shuō)明u和v之間無(wú)作用力，即φ(v)=mv=M， 此時(shí)，勢(shì)熵趨近于最大值logN。 當(dāng)φ(u→v)→∞時(shí)，φ(u→v)→mu， 則說(shuō)明u和v的影響力相同，此時(shí)，勢(shì)熵趨近于最大值logN。 因此，σ∈[0,∞)，H∈[0,logN]。 它們的關(guān)系如圖2所示。因?yàn)閯?shì)熵越小，網(wǎng)絡(luò)的分布越均勻，所以，取H=logN， 此時(shí)σ≈2。 因此，我們?nèi)」?jié)點(diǎn)的拓?fù)鋭?shì)的影響范圍主要是由二度鄰居決定。

圖2 勢(shì)熵與影響因子關(guān)系

3.1.3 節(jié)點(diǎn)質(zhì)量

節(jié)點(diǎn)的度是指與該節(jié)點(diǎn)直接相連的邊的數(shù)量，其在一定程度上能夠反應(yīng)節(jié)點(diǎn)影響力，節(jié)點(diǎn)的度越大，說(shuō)明其影響力越高。然而，若一個(gè)度很大的節(jié)點(diǎn)，其卻很少進(jìn)行傳播信息，即其傳播概率很小，這樣，其影響力整體上來(lái)說(shuō)，應(yīng)該相對(duì)較小。因此，本文中，我們將傳播概率和度結(jié)合，提出了加權(quán)度，作為衡量節(jié)點(diǎn)質(zhì)量的指標(biāo)。

定義3 節(jié)點(diǎn)質(zhì)量：節(jié)點(diǎn)u的質(zhì)量m(u) 的計(jì)算方法如下所示

(4)

其中，du和dw為節(jié)點(diǎn)u和w的度，N(u) 為u的鄰居節(jié)點(diǎn)，puw為節(jié)點(diǎn)u激活v的概率。

3.1.4 節(jié)點(diǎn)位置

我們根據(jù)相鄰節(jié)點(diǎn)的拓?fù)鋭?shì)，將節(jié)點(diǎn)的位置分為以下3類：山峰，山谷和斜坡。山峰節(jié)點(diǎn)代表著影響力相對(duì)較大，為相鄰節(jié)點(diǎn)間的代表。斜坡節(jié)點(diǎn)相當(dāng)于邊緣節(jié)點(diǎn)，與外界聯(lián)系密切，其充當(dāng)“中介”的作用。山谷節(jié)點(diǎn)是內(nèi)部節(jié)點(diǎn)且其影響力較小。我們根據(jù)影響因子將影響范圍考慮為二度鄰居節(jié)點(diǎn)。

(1)山峰。對(duì)于社交網(wǎng)絡(luò)中節(jié)點(diǎn)v滿足?φ(v)≥φ(u)， 其中u為v的二度鄰居節(jié)點(diǎn)，則v為山峰節(jié)點(diǎn)。

(2)山谷。對(duì)于社交網(wǎng)絡(luò)中節(jié)點(diǎn)v滿足?φ(v)≤φ(u), 其中u為v的二度鄰居節(jié)點(diǎn)，則v為山谷節(jié)點(diǎn)。

(3)斜坡。對(duì)于社交網(wǎng)絡(luò)中節(jié)點(diǎn)v滿足?φ(v)<φ(u) 或者?φ(v)>φ(u)， 其中u為v的二度鄰居節(jié)點(diǎn)，則v為斜坡節(jié)點(diǎn)。

為了更加清楚的解釋山峰，山谷和斜坡節(jié)點(diǎn)，我們以一個(gè)包含10個(gè)節(jié)點(diǎn)的社交網(wǎng)絡(luò)為例，其簡(jiǎn)易圖如圖3所示。根據(jù)拓?fù)鋭?shì)公式(式(2)和式(4))，社交網(wǎng)絡(luò)中的10個(gè)節(jié)點(diǎn)的拓?fù)鋭?shì)及節(jié)點(diǎn)的位置，見(jiàn)表1。

3.1.5 候選種子集

根據(jù)以上小節(jié)，我們已確定節(jié)點(diǎn)的相對(duì)位置：山峰，山谷，斜坡。在影響力傳播的過(guò)程中，我們不僅需要影響力大的節(jié)點(diǎn)，而且需要邊緣節(jié)點(diǎn)與外界進(jìn)行聯(lián)系。因此，為了提高算法的準(zhǔn)確性，我們按照節(jié)點(diǎn)質(zhì)量大小選取k個(gè)山峰節(jié)點(diǎn)和k個(gè)山谷節(jié)點(diǎn)作為候選種子集。

圖3 社交網(wǎng)絡(luò)

表1 社交網(wǎng)絡(luò)中節(jié)點(diǎn)拓?fù)鋭?shì)及位置

節(jié)點(diǎn)12345678910拓?fù)鋭?shì)16162423232120171710位置山谷山谷山峰斜坡斜坡斜坡斜坡斜坡斜坡山谷

3.2 貪心階段：確定最終種子集

通過(guò)上一小節(jié)我們得到了由k個(gè)山峰節(jié)點(diǎn)和k個(gè)山谷節(jié)點(diǎn)組成的候選種子集，本小節(jié)的主要任務(wù)就是利用CELF算法從候選種子集中選出最優(yōu)種子集，使得最終影響力最大。CELF算法主要是在貪心算法的基礎(chǔ)上利用節(jié)點(diǎn)的影響力具有子模性進(jìn)行優(yōu)化，使得時(shí)間效率比原始的貪心算法快了近700倍。

定義4 CELF算法：對(duì)于節(jié)點(diǎn)A，B和C，在節(jié)點(diǎn)A加入種子節(jié)點(diǎn)后，在下一輪選擇種子節(jié)點(diǎn)時(shí)，若B在此輪的影響力增益大于C在上一輪的影響力增益，利用子模性，C在此輪的影響力必定小于其在上一輪的影響力增益，因此，B在此輪的影響力增益大于C。所以，我們可以直接將節(jié)點(diǎn)B加入種子節(jié)點(diǎn)，不需要再額外計(jì)算C的影響力增益，從而提高時(shí)間效率。

CELF算法利用子模型改進(jìn)了貪心算法，在準(zhǔn)確率上有了一定的保證，但是，其運(yùn)行時(shí)間雖然比貪心算法快了700倍，仍然不適用于大型網(wǎng)絡(luò)。所以，我們先根據(jù)拓?fù)鋭?shì)理論劃分節(jié)點(diǎn)的位置，將山峰節(jié)點(diǎn)和斜坡節(jié)點(diǎn)作為候選集，再利用CELF算法從候選集中選擇最優(yōu)種子集，從而提高時(shí)間效率。該算法的偽代碼如下。

算法1：TSH算法

輸入：社交網(wǎng)絡(luò)G=(V,E)， 種子數(shù)量k

輸出:種子集S

(1)初始化: 種子集S←φ

(2)forv∈V：

(3) 計(jì)算節(jié)點(diǎn)v的拓?fù)鋭?shì)φ(v)

(4)判斷節(jié)點(diǎn)的位置

(5)從山峰山谷節(jié)點(diǎn)中：

(6) 按照加權(quán)度選取k個(gè)山峰節(jié)點(diǎn)和k個(gè)斜坡節(jié)點(diǎn)組成候選種子集

(7)對(duì)候選種子集進(jìn)行CELF算法，尋找最優(yōu)k個(gè)種子

(8)返回種子集S

時(shí)間復(fù)雜度：假設(shè)社交網(wǎng)絡(luò)G=(V,E) 有n個(gè)節(jié)點(diǎn)，m條邊，TSH算法的時(shí)間復(fù)雜度分析如下：第(2)～(3)行，計(jì)算節(jié)點(diǎn)拓?fù)鋭?shì)的時(shí)間復(fù)雜度為O(nemax2)， 其中emax為最大連邊數(shù)。第(4)行判斷節(jié)點(diǎn)的位置的時(shí)間復(fù)雜度為O(n)。 第(5)～(6)行選取候選種子集的時(shí)間復(fù)雜度為O(2k)。 因此，該算法的總的時(shí)間復(fù)雜度為O(nemax2+n+2k)≈O(nemax2)。

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

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

為了驗(yàn)證算法的合理性，本文從斯坦福網(wǎng)站(http://snap.Stanford.edu/data/)上選取了4種不同類型的數(shù)據(jù)集：Ca-AstroPh，As-Caida，Email-Enron和Amazon數(shù)據(jù)集。其中，Ca-AstroPh源自e-print Arxiv，是由提交文章的科學(xué)家之間的協(xié)作關(guān)系所構(gòu)成的。As-Caida是從地理和拓?fù)渖喜煌恢玫膸追N不同類型的數(shù)據(jù)中收集的。Email-Enron數(shù)據(jù)集是由CALO項(xiàng)目得出，它是由大約150個(gè)員工進(jìn)行交流溝通所構(gòu)成的網(wǎng)絡(luò)。最后，Amazon數(shù)據(jù)集是通過(guò)爬取Amazon網(wǎng)站的評(píng)論和鏈接等而收集的。這4種數(shù)據(jù)集的基本信息見(jiàn)表2。

表2 數(shù)據(jù)集基本信息

4.2 對(duì)比算法及參數(shù)設(shè)置

為了驗(yàn)證算法的有效性，我們將TSH算法在IC模型的基礎(chǔ)上，與CELF，PMIA，IRIE，Degree Discount和CCA算法進(jìn)行比較。這6種算法的簡(jiǎn)要介紹如下所示。

TSH：該算法分為啟發(fā)式算法和貪心算法。啟發(fā)式階段根據(jù)拓?fù)鋭?shì)找出候選種子集；貪心階段使用CELF算法求出最優(yōu)種子集。

CELF：貪心算法的代表算法，使用子模性原理優(yōu)化了貪心算法。

PMIA：基于最短傳播路徑的較為經(jīng)典的啟發(fā)式算法。

IRIE：由IR和IE兩個(gè)階段組成，在時(shí)間效率和影響力范圍上表現(xiàn)較好。

Degree Discount：在度中心性的基礎(chǔ)上，對(duì)種子節(jié)點(diǎn)的鄰居節(jié)點(diǎn)進(jìn)行打折，從而提高了算法的準(zhǔn)確性。

CCA：基于核覆蓋理論，為了減少影響力重疊，將種子的節(jié)點(diǎn)的鄰居進(jìn)行覆蓋。本文設(shè)radius=2。

為了評(píng)估上述6種算法的優(yōu)劣，我們?cè)贗C模型的基礎(chǔ)上，用蒙特卡羅模擬了10 000次實(shí)驗(yàn)，并在4.3.1中給出了影響力擴(kuò)散的平均值。

4.3 結(jié)果分析

影響范圍和運(yùn)行時(shí)間是衡量社交網(wǎng)絡(luò)影響力最大化的兩個(gè)標(biāo)準(zhǔn)。目前現(xiàn)存的大部分算法存在影響力計(jì)算的準(zhǔn)確性或者運(yùn)行時(shí)間的問(wèn)題。本節(jié)中，我們從影響力和運(yùn)行時(shí)間兩方面對(duì)我們的TSH算法和5個(gè)對(duì)比算法在4種不同的數(shù)據(jù)集上進(jìn)行評(píng)估。

4.3.1 影響范圍

圖4(a)～圖4(d)分別描述TSH，CELF，PMIA，IRIE，Degree Discount，和CCA算法在Ca-AstroPh，As-Caida，Email_Enron和Amazon數(shù)據(jù)集上的傳播范圍。通過(guò)比較這4種數(shù)據(jù)集上表現(xiàn)，我們可以輕易地發(fā)現(xiàn)CCA算法的影響范圍整體上來(lái)說(shuō)相對(duì)較低，其影響力分別低于TSH算法54%，78%，74%和44%。這可能是由于CCA算法雖然考慮了節(jié)點(diǎn)的度和核，但是其為了減少影響力重疊，覆蓋了種子的鄰居節(jié)點(diǎn)，這可能覆蓋了過(guò)多的影響力高的節(jié)點(diǎn)，導(dǎo)致其影響范圍不準(zhǔn)確。PMIA算法整體上影響力明顯低于TSH，CELF，IRIE和Degree Discount。比如，在Amazon數(shù)據(jù)集上，當(dāng)種子集為100時(shí)，PMIA低于TSH算法36%。這可能是因?yàn)镻MIA僅考慮了最短路徑這一個(gè)因素，導(dǎo)致其影響力存在一定的誤差。另外，Degree Discount算法的表現(xiàn)相對(duì)較好，明顯高于PMIA和CCA算法，而且跟IRIE的影響范圍相差無(wú)幾。值得注意的是，TSH算法在4個(gè)數(shù)據(jù)集上仍分別以4%，5%，4%和11% 高于Degree Discount算法。這可能是因?yàn)镈egreeDiscount算法將度大的節(jié)點(diǎn)看作影響力大的節(jié)點(diǎn)，沒(méi)有考慮網(wǎng)絡(luò)的整體結(jié)構(gòu)，可能導(dǎo)致其影響力存在一定的誤差。除此之外，當(dāng)種子集為100時(shí)，TSH在4種數(shù)據(jù)集上的影響范圍分別以2%，6%，6%和1%高于IRIE算法，充分說(shuō)明了TSH算法的優(yōu)越性。在這4個(gè)數(shù)據(jù)集上，TSH算法影響力跟CELF算法差不多，但是，由圖4可知，CELF算法在Ca-AstroPh，As-Caida，Email-Enron和Amazon這4個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間分別是1090 s，1733 s，13 401 s和12 850 s，不適合大型網(wǎng)絡(luò)。而TSH算法在262 111個(gè)節(jié)點(diǎn)，1 234 877 條邊的Amazon算法上的運(yùn)行時(shí)間僅需344 s。綜合考慮，TSH算法有效均衡了影響力和運(yùn)行時(shí)間，不僅其準(zhǔn)確率較高，而且其運(yùn)行時(shí)間較快，適合大規(guī)模的社交網(wǎng)絡(luò)。

圖4 影響范圍

4.3.2 運(yùn)行時(shí)間

TSH，CELF，PMIA，IRIE，Degree Discount和CCA算法的時(shí)間復(fù)雜度分別是O(nemax2)，O(knm)，O(ntiθ+knoθniθlogn)，O(∑v∈Vdout(v))，O(klongn+m) 和O(km)。 由于各種數(shù)據(jù)集的內(nèi)部屬性不同可能導(dǎo)致其運(yùn)行時(shí)間存在差距，因此，我們從斯坦福網(wǎng)站上選擇了4種不同類型的數(shù)據(jù)集進(jìn)行比較，以增強(qiáng)說(shuō)服性。圖5描述了TSH，CELF，PMIA，IRIE，Degree Discount和CCA算法在Ca-AstroPh，As-Caida，Email-Enron和Amazon數(shù)據(jù)集上的運(yùn)行時(shí)間。從圖5中可以看出，CCA算法的運(yùn)行時(shí)間最快，而TSH算法的運(yùn)行時(shí)間僅次于CCA算法。但是由圖4可知，當(dāng)種子集為100時(shí)，CCA算法在4個(gè)數(shù)據(jù)集上的影響范圍約占TSH算法的45%，20%，25%和56%，影響力較低。圖4顯示CELF算法影響力較大，但是從圖5中可知，其運(yùn)行時(shí)間最長(zhǎng)，尤其在Email-Enron數(shù)據(jù)集上的運(yùn)行時(shí)間高達(dá)12 850 s，約是TSH運(yùn)行時(shí)間的兩倍。Degree Discount算法的運(yùn)行時(shí)間整體上來(lái)看運(yùn)行效率較高，但是，Degree Discount未重復(fù)考慮網(wǎng)絡(luò)的整體結(jié)構(gòu)，僅從局部角度評(píng)估節(jié)點(diǎn)的影響力，所以，其運(yùn)行結(jié)果可能不太準(zhǔn)確。TSH算法的運(yùn)行時(shí)間在4個(gè)數(shù)據(jù)集上比PMIA分別快了77%，66%，41%和96%。另外，TSH算法的運(yùn)行時(shí)間在4個(gè)數(shù)據(jù)集上比IRIE分別快了57%，73%，42%和24%。雖然TSH算法在計(jì)算拓?fù)鋭?shì)時(shí)，需要考慮節(jié)點(diǎn)間的傳播度，導(dǎo)致了其運(yùn)行時(shí)間稍長(zhǎng)。但是，TSH在中大型社交網(wǎng)絡(luò)Amazon上僅用344 s，比CELF，PMIA，IRIE，Degree Discount快了97%，59%，90%和24%，說(shuō)明了TSH算法在大規(guī)模社交網(wǎng)絡(luò)的可行性。

圖5 運(yùn)行時(shí)間

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

本文基于拓?fù)鋭?shì)理論，提出了一種啟發(fā)式和貪心算法相結(jié)合的啟發(fā)式算法-TSH算法。該算法首先使用拓?fù)鋭?shì)理論判斷節(jié)點(diǎn)的位置，鑒別節(jié)點(diǎn)為“山峰”“山谷”和“斜坡”節(jié)點(diǎn)。然后，將“山峰”和“斜坡”節(jié)點(diǎn)加入到候選種子集。最后，使用CELF算法從候選種子集中確定最優(yōu)種子集。

實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的算法相比，該算法的影響力與貪心算法近似，而運(yùn)行時(shí)間卻是貪心算法的兩倍，從而，有效均衡了運(yùn)行時(shí)間和傳播范圍。然而，我們分別選取k個(gè)山峰節(jié)點(diǎn)和k個(gè)山谷節(jié)點(diǎn)來(lái)構(gòu)成候選種子集可能存在誤差，如何對(duì)“山谷節(jié)點(diǎn)”和“山峰節(jié)點(diǎn)”的數(shù)量進(jìn)行合理分配是我們下一步研究的重點(diǎn)。