基于結(jié)構(gòu)洞和度折扣的影響力最大化算法

李敏佳，許國(guó)艷，朱 帥，張網(wǎng)娟

(河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，南京 211100)(*通信作者電子郵箱1256868536@qq.com)

0 引言

隨著信息化和互聯(lián)網(wǎng)的快速普及，社交網(wǎng)絡(luò)在信息傳播、思想交流等方面有著舉足輕重的地位。由于社交網(wǎng)絡(luò)的日益深入，以影響力最大化(Influence Maximization, IM) 問(wèn)題為主要應(yīng)用的需求也逐步增長(zhǎng)[1]。如何選取部分節(jié)點(diǎn)，通過(guò)這些節(jié)點(diǎn)在網(wǎng)絡(luò)中擴(kuò)散使得最終影響的節(jié)點(diǎn)數(shù)目最多，成為當(dāng)前需要解決的問(wèn)題[2]。

Kempe等[3]詳盡地描述了經(jīng)典的信息傳播模型并驗(yàn)證了影響力最大化問(wèn)題是NP(Non-deterministic Polynomial)-hard問(wèn)題，在此基礎(chǔ)上，提出來(lái)性能至少是最優(yōu)解63%的貪心算法來(lái)解決這一難題;但是貪心算法時(shí)間開(kāi)銷較大，難以很好地應(yīng)用在規(guī)模較大的網(wǎng)絡(luò)平臺(tái)上。之后，Chen等[4]提出了New Greedy算法和Mix Greedy算法來(lái)優(yōu)化貪心算法；然而，優(yōu)化后的貪心算法時(shí)間消耗仍很高，很難應(yīng)用到大型社交網(wǎng)絡(luò)中。

近年來(lái)出現(xiàn)了大批的啟發(fā)式算法來(lái)改善貪心算法效率低下的情況。Chen等[4]提出DegreeDiscount算法來(lái)克服基于Degree算法的局限性，該算法是當(dāng)某個(gè)節(jié)點(diǎn)被存儲(chǔ)在種子節(jié)點(diǎn)集合中時(shí)，在計(jì)算其鄰居節(jié)點(diǎn)的度時(shí)要打一定的折扣。文獻(xiàn)[5]針對(duì)篩選度數(shù)最大的節(jié)點(diǎn)而造成影響重疊問(wèn)題提出了一種覆蓋貪心算法(Set Covering Greedy algorithm, SCG)來(lái)最大限度地散開(kāi)種子節(jié)點(diǎn)。曹玖新等[6]提出了基于核數(shù)的啟發(fā)式算法，該算法通過(guò)核數(shù)定義網(wǎng)絡(luò)層次，層層剝?nèi)ネ鈱庸?jié)點(diǎn)以獲得內(nèi)層的核心節(jié)點(diǎn)集合來(lái)解決影響力最大化問(wèn)題。隨后蘇曉萍等[7]考慮網(wǎng)絡(luò)中節(jié)點(diǎn)的結(jié)構(gòu)特征利用結(jié)構(gòu)洞思想[8]來(lái)評(píng)定網(wǎng)絡(luò)中節(jié)點(diǎn)影響力，但文獻(xiàn)[7]中提出的方法較適用于小型網(wǎng)絡(luò)且并未將該思想進(jìn)一步應(yīng)用在影響力最大化問(wèn)題中。Zhu等[9]提出基于結(jié)構(gòu)的貪心(Structure-based Greedy, SG)算法通過(guò)選取能橋接多個(gè)群體的結(jié)構(gòu)洞節(jié)點(diǎn)來(lái)擴(kuò)大影響范圍。

針對(duì)當(dāng)前僅選取核心或邊緣節(jié)點(diǎn)的算法造成影響范圍小的現(xiàn)狀，本文提出一種基于結(jié)構(gòu)洞和度折扣的最大化算法(maximization algorithm based on Structure Hole and Degree Discount, SHDD)。該算法將結(jié)構(gòu)洞思想和中心度思想互相融合應(yīng)用到影響力最大化問(wèn)題中,兼顧核心節(jié)點(diǎn)和結(jié)構(gòu)洞節(jié)點(diǎn)在信息傳播中的作用，提高最終的影響范圍。

1 相關(guān)工作

1.1 傳播模型

通常將社交網(wǎng)絡(luò)表示成一個(gè)有向(無(wú)向)圖G(V,E),V表示節(jié)點(diǎn)的集合，節(jié)點(diǎn)v∈V代表個(gè)人或組織；E表示邊的集合，每條邊(u,v)∈E表示節(jié)點(diǎn)u和節(jié)點(diǎn)v之間的影響關(guān)系。通常假設(shè)社會(huì)網(wǎng)絡(luò)G(V,E)有n個(gè)節(jié)點(diǎn)、m條邊，網(wǎng)絡(luò)中的節(jié)點(diǎn)有兩種可能狀態(tài)：激活和未激活。未激活形式下的節(jié)點(diǎn)會(huì)受到已激活節(jié)點(diǎn)的影響，節(jié)點(diǎn)從未激活模式轉(zhuǎn)化為激活模式的過(guò)程被稱作激活。

目前影響力最大化問(wèn)題中應(yīng)用最廣的傳播模型是獨(dú)立級(jí)聯(lián)模型(Independent Cascade model, IC)和線性閾值模型(Linear Threshold model, LT)[10-11]。其中本文使用的獨(dú)立級(jí)聯(lián)模型是一個(gè)概率模型，節(jié)點(diǎn)u通過(guò)邊(u,v)∈E激活節(jié)點(diǎn)v的概率為p(u,v)∈[0,1]。該模型下的傳播方式如下：在t=0時(shí)刻，激活篩選出的種子節(jié)點(diǎn)集合S0，其他節(jié)點(diǎn)保持在未激活模式。St表示t時(shí)刻處于激活模式的所有節(jié)點(diǎn)的集合，則在t+1時(shí)刻利用St中的節(jié)點(diǎn)去激活其鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)被激活的概率是p(u,v)，并把所有被激活的節(jié)點(diǎn)添加到St中形成St+1。迭代操作這一過(guò)程直到不再出現(xiàn)新的節(jié)點(diǎn)被激活。尤為重要的是在此模型下，節(jié)點(diǎn)從未激活模式轉(zhuǎn)換成激活模式的過(guò)程不可逆，并且節(jié)點(diǎn)v被節(jié)點(diǎn)u激活的概率p(u,v)是系統(tǒng)常量，而和其他試圖激活節(jié)點(diǎn)v未遂的節(jié)點(diǎn)沒(méi)有關(guān)系。

1.2 結(jié)構(gòu)洞

把社交網(wǎng)絡(luò)中的節(jié)點(diǎn)看作是村莊，則節(jié)點(diǎn)與節(jié)點(diǎn)之間的聯(lián)系看作連接村莊的路。如果兩個(gè)村莊沒(méi)有直接連通的道路，需要通過(guò)第三個(gè)村莊才能連通兩個(gè)村莊，則不能互相連通的兩個(gè)村莊在結(jié)構(gòu)上看存在空洞，稱這個(gè)空洞為結(jié)構(gòu)洞，而連接這個(gè)空洞的村莊被稱為占據(jù)結(jié)構(gòu)洞節(jié)點(diǎn)。如圖1所示，若節(jié)點(diǎn)A、B、C、D兩兩互相連接則不存在結(jié)構(gòu)洞；若節(jié)點(diǎn)A、B和C沒(méi)有直接連接而是通過(guò)節(jié)點(diǎn)D建立的聯(lián)系，如果去除節(jié)點(diǎn)D則節(jié)點(diǎn)A、B和C之間存在結(jié)構(gòu)洞，而處于結(jié)構(gòu)洞位置的節(jié)點(diǎn)D稱作結(jié)構(gòu)洞節(jié)點(diǎn)。

結(jié)構(gòu)洞節(jié)點(diǎn)可以有效控制流向其鄰居節(jié)點(diǎn)的信息，在信息傳播方面，Lou等[12]發(fā)現(xiàn)在Twitter上，1%的結(jié)構(gòu)洞節(jié)點(diǎn)決定著25%的信息流向，結(jié)構(gòu)洞節(jié)點(diǎn)的加入可以擴(kuò)大信息的擴(kuò)散范圍。例如在圖2中，信息在網(wǎng)絡(luò)中傳播時(shí)假設(shè)無(wú)結(jié)構(gòu)洞節(jié)點(diǎn)1的連接，信息的交互則僅限于單個(gè)團(tuán)體中，若通過(guò)結(jié)構(gòu)洞節(jié)點(diǎn)1，在A中接收信息后會(huì)以一定的概率p將信息傳遞到B中。

圖1 結(jié)構(gòu)洞概念圖Fig. 1 Concept diagram of structure hole

圖2 結(jié)構(gòu)洞信息傳播圖Fig. 2 Propagation diagram of structure hole information

用網(wǎng)絡(luò)約束系數(shù)CT(ConsTraint)和效率值EF(EFficient)[13]來(lái)作為結(jié)構(gòu)洞節(jié)點(diǎn)評(píng)價(jià)標(biāo)準(zhǔn)，但是前者運(yùn)行內(nèi)存較大且隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的增加效果變差且不穩(wěn)定，所以本文此次選用效率值EF來(lái)作為結(jié)構(gòu)洞節(jié)點(diǎn)評(píng)價(jià)標(biāo)準(zhǔn)：

(1)

式中：EF(i)表示節(jié)點(diǎn)i的效率值；τ(i)代表直接與節(jié)點(diǎn)i相連的鄰居節(jié)點(diǎn)的集合；j表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)；q代表節(jié)點(diǎn)i和j的共同鄰居；ni表示節(jié)點(diǎn)i所處網(wǎng)絡(luò)的大小；piq則如圖3所示代表節(jié)點(diǎn)i連接q付出精力占總精力的比重;mjq代表節(jié)點(diǎn)j連接節(jié)點(diǎn)q付出的精力和節(jié)點(diǎn)j連接其他節(jié)點(diǎn)付出的最大精力的比值。piq的計(jì)算式如下：

其中:

mjq的計(jì)算式如下：

mjq=pjq/max(pjm);m∈τ(j)

權(quán)值相同的拓?fù)鋱D節(jié)點(diǎn)j對(duì)于其鄰居節(jié)點(diǎn)付出的精力相同,則有：

EiA=(1-1/2)/6=1/12,同理可得EiB、EiC、EiD、EiE、EiF分別為1/9、1/6、5/36、5/36、5/36，則EF(i)=7/9。

圖3 評(píng)價(jià)節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)q的投入精力Fig. 3 Investment evaluation of node i on node q

圖4 效率值計(jì)算示意圖Fig. 4 Schematic diagram of efficiency value calculation

2 基于結(jié)構(gòu)洞和度折扣的最大化算法

2.1 影響力最大化現(xiàn)有算法

現(xiàn)有的影響力最大化算法中，DegreeDiscount算法在反映某些節(jié)點(diǎn)對(duì)當(dāng)前領(lǐng)域的影響力方面有著良好的表現(xiàn)，基于選取結(jié)構(gòu)洞節(jié)點(diǎn)的SG算法具有較好的擴(kuò)散效果。

DegreeDiscount算法主要思想為：如果某個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)是種子節(jié)點(diǎn)時(shí)，則此節(jié)點(diǎn)的度在計(jì)算時(shí)應(yīng)當(dāng)打折扣，最終選取k個(gè)打折扣后度數(shù)仍最高的節(jié)點(diǎn)作為種子集合。如圖5所示假定k=2，則根據(jù)DegreeDiscount算法會(huì)選取度數(shù)為7的5號(hào)節(jié)點(diǎn)和度數(shù)為6的3號(hào)節(jié)點(diǎn)，該算法只是考慮選取中心節(jié)點(diǎn)，其時(shí)間復(fù)雜度為O(klogn+m)。

SG算法的主要思想為：通過(guò)設(shè)定結(jié)構(gòu)洞值找出社交網(wǎng)絡(luò)中所有的結(jié)構(gòu)洞節(jié)點(diǎn)，并通過(guò)貪心算法找出影響力值較大的k個(gè)結(jié)構(gòu)洞節(jié)點(diǎn)作為種子集合。如圖5所示假定k=2，則根據(jù)SG算法會(huì)選取結(jié)構(gòu)洞值較高的2號(hào)和6號(hào)節(jié)點(diǎn)作為種子節(jié)點(diǎn)，該算法只選取了結(jié)構(gòu)洞節(jié)點(diǎn)，其時(shí)間復(fù)雜度為O(kRn3)。

圖5 DegreeDiscount及SG算法節(jié)點(diǎn)選擇示意圖Fig. 5 Schematic diagram of node selection for DegreeDiscount and SG algorithms

上述兩種算法僅僅利用結(jié)構(gòu)洞節(jié)點(diǎn)或核心節(jié)點(diǎn)無(wú)法使信息擴(kuò)散得到最大化，結(jié)構(gòu)洞節(jié)點(diǎn)可以看作網(wǎng)絡(luò)中的邊緣節(jié)點(diǎn)，只激活邊緣節(jié)點(diǎn)或核心節(jié)點(diǎn)，在網(wǎng)絡(luò)覆蓋范圍較大的情況下得不到理想的信息擴(kuò)散范圍。本文綜合考慮社交網(wǎng)絡(luò)中基于中心度的核心節(jié)點(diǎn)和結(jié)構(gòu)洞節(jié)點(diǎn)的傳播優(yōu)勢(shì)，利用結(jié)構(gòu)洞理論可以彌補(bǔ)中心度理論不能識(shí)別橋接節(jié)點(diǎn)的問(wèn)題，提出基于結(jié)構(gòu)洞和度折扣的最大化算法(SHDD)。為了充分體現(xiàn)兩個(gè)思想融合的優(yōu)勢(shì)，將二度鄰居的影響添加到結(jié)構(gòu)洞節(jié)點(diǎn)評(píng)價(jià)標(biāo)準(zhǔn)中來(lái)找出更好的結(jié)構(gòu)洞節(jié)點(diǎn)。

2.2 SHDD

基于結(jié)構(gòu)洞和度折扣的最大化算法(SHDD)的基本思想為：分兩個(gè)步驟來(lái)挑選k個(gè)種子節(jié)點(diǎn)，首先添加k1個(gè)效率值最大的結(jié)構(gòu)洞節(jié)點(diǎn)到種子節(jié)點(diǎn)集合中，其次添加k2個(gè)“度數(shù)最大”的節(jié)點(diǎn)到種子節(jié)點(diǎn)集合中。其中k1=|αk|，k2=k-k1。0<α<1 是一個(gè)關(guān)鍵值，這個(gè)值在后面的實(shí)驗(yàn)中給出。SHDD的偽代碼如算法1所示。

算法1 SHDD。

輸入 圖G(V,E)，種子節(jié)點(diǎn)個(gè)數(shù)k,因子α；

輸出 種子集合S。

1)

初始化S=?,NS=?,k1=「αk?，k2=k-k1，tv=0;

2)

for all nodev∈Vdo

3)

dv=d(v);

4)

SHv=EF(v);

//計(jì)算每個(gè)節(jié)點(diǎn)的效率值

5)

end for

6)

fori=1 tok1do

7)

8)

S=S∪{u};

9)

NS=NS∪N(u);

10)

end for

11)

fori=1 tok2do

12)

for all nodev∈VSdo

13)

for each nodem1,m1∈N(v)

14)

ifm1∈S

15)

tv=tv+1;

16)

end if

17)

end for

18)

ddv=dv-2tv-(dv-tv)×tv×p;

//度折扣計(jì)算

19)

tv=0;

20)

21)

S=S∪{m};

22)

end for

23)

end for

24)

returnS

算法1中：NS表示種子節(jié)點(diǎn)的鄰居集合，N(u)代表節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)，tv指節(jié)點(diǎn)v的鄰居是種子節(jié)點(diǎn)的個(gè)數(shù)，VS是去掉種子節(jié)點(diǎn)的節(jié)點(diǎn)集合。

算法第3)行：計(jì)算每個(gè)節(jié)點(diǎn)的度數(shù)并保存；第4)行：根據(jù)結(jié)構(gòu)洞二度評(píng)價(jià)標(biāo)準(zhǔn)計(jì)算所有節(jié)點(diǎn)的效率值并保存，其具體計(jì)算方法將在2.3節(jié)中詳細(xì)介紹；第6)～10)行：每次把效率值最大的節(jié)點(diǎn)添加到節(jié)點(diǎn)集合S中，并在下次選擇的時(shí)候去掉種子節(jié)點(diǎn)和種子節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，以防止選擇的結(jié)構(gòu)洞節(jié)點(diǎn)過(guò)于集中，迭代選擇出k1個(gè)節(jié)點(diǎn)添加到種子集合中；第11)～22)行是度折扣階段：對(duì)種子節(jié)點(diǎn)的鄰居節(jié)點(diǎn)進(jìn)行度折扣計(jì)算，選出k2個(gè)ddv最大的節(jié)點(diǎn)到種子集合中。

假設(shè)社會(huì)網(wǎng)絡(luò)G(V,E)有n個(gè)節(jié)點(diǎn)、m條邊，SHDD的時(shí)間復(fù)雜度分析如下：第3)行的時(shí)間花費(fèi)為O(m)；第4)行根據(jù)2.3節(jié)計(jì)算節(jié)點(diǎn)的效率值的時(shí)間花費(fèi)為O(n)+O(m)；第6)～10)行選擇結(jié)構(gòu)洞節(jié)點(diǎn)的時(shí)間花費(fèi)為O(k1n)；則第11)～22)行的度折扣階段時(shí)間花費(fèi)為O(k2logn+m)；因此算法的總時(shí)間復(fù)雜度為O(k2logn+m)。原基礎(chǔ)算法DegreeDiscount時(shí)間復(fù)雜度為O(klogn+m)，因此SHDD沒(méi)有增加額外的時(shí)間復(fù)雜度。

2.3 結(jié)構(gòu)洞二度評(píng)價(jià)標(biāo)準(zhǔn)

式(1)的效率值僅僅考慮到節(jié)點(diǎn)及其一度鄰居節(jié)點(diǎn)之間的結(jié)構(gòu)特征，忽略了二度鄰居的影響，會(huì)識(shí)別不出一些可能是結(jié)構(gòu)洞的節(jié)點(diǎn)。如圖6所示，根據(jù)式(1)可得節(jié)點(diǎn)E和F的效率值是：

EF(E)=EF(F)=(1-1/2×1)/2+

(1-1/2×1)/2=1/2

從一度鄰居來(lái)看，節(jié)點(diǎn)E和F的拓?fù)浣Y(jié)構(gòu)相同，但是從二度鄰居考慮，節(jié)點(diǎn)F有比E更好的拓?fù)潢P(guān)系。這種現(xiàn)象在式(1)的效率值的計(jì)算中無(wú)法體現(xiàn)，因此通過(guò)加入二度鄰居來(lái)改進(jìn)效率值的計(jì)算方法，更加精準(zhǔn)地衡量結(jié)構(gòu)洞節(jié)點(diǎn)。

在無(wú)向網(wǎng)絡(luò)G(V,E)中，節(jié)點(diǎn)i的度記作：

其中:

(2)

式(2)考慮了節(jié)點(diǎn)對(duì)鄰居投入的精力和對(duì)其二度鄰居投入精力所占的比例，真實(shí)地反映節(jié)點(diǎn)的重要性。節(jié)點(diǎn)i的效率值為：

(3)

將式(2)代入式(3)得：

q≠i,j

節(jié)點(diǎn)E的效率值是：

mjq)/nE

q是節(jié)點(diǎn)E和j的共同鄰居,則：

EF(E)=(1+18/34+19/34)/3=71/102

同理可得節(jié)點(diǎn)F的效率值：

EF(F)=(1+21/37+22/37)/3=80/111

圖6 二度效率值計(jì)算示意圖Fig. 6 Schematic diagram of second-degree efficiency value calculation

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

3.1 數(shù)據(jù)集

為驗(yàn)證本文提出的SHDD在IM問(wèn)題上的可行性，本文選取Route Views、Net HEPT和Net PHY 3個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),數(shù)據(jù)集的相關(guān)屬性如表1所示。

數(shù)據(jù)集1(Route Views)是互聯(lián)網(wǎng)絡(luò)的自治系統(tǒng)，點(diǎn)表示自治系統(tǒng)，邊表示系統(tǒng)之間的通信,無(wú)向無(wú)權(quán)圖，來(lái)自The Koblenz Network Collection(http://Konect.uni-koblenz.de)。數(shù)據(jù)集2(Net HEPT)是1991年至1993年的高能物理模塊科學(xué)論文作者合作圖，點(diǎn)表示作者，邊表示兩作者之間共同的出版物，無(wú)向無(wú)權(quán)圖。數(shù)據(jù)集3(Net PHY)是物理學(xué)板塊的論文作者合作圖，點(diǎn)表示作者，邊表示兩作者之間共同的出版物，無(wú)向無(wú)權(quán)圖。數(shù)據(jù)集2和3均來(lái)自論文共享網(wǎng)站arxiv(www.arxiv.org)。

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab. 1 Experimental data sets

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

本文實(shí)驗(yàn)對(duì)這3個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集在IC傳播模型中進(jìn)行操作。為驗(yàn)證SHDD的性能，將選DegreeDiscount、SG算法和SH*DD算法與其進(jìn)行實(shí)驗(yàn)對(duì)比。SH*DD算法基本與SHDD一致，唯一的區(qū)別是SH*DD算法利用1.2節(jié)中的結(jié)構(gòu)洞評(píng)價(jià)標(biāo)準(zhǔn)來(lái)選取結(jié)構(gòu)洞節(jié)點(diǎn)而SHDD是用2.3節(jié)中結(jié)構(gòu)洞二度評(píng)價(jià)標(biāo)準(zhǔn)來(lái)選擇結(jié)構(gòu)洞節(jié)點(diǎn)。實(shí)驗(yàn)中SHDD的結(jié)果與α取值相關(guān)，SHDD的結(jié)果會(huì)隨著α的變化而變化，因此需要設(shè)定不同的α值進(jìn)行對(duì)比分析并找出最佳的α值。在傳播概率不變且一致的IC模型下，為了方便對(duì)比分析，本文的算法在傳播概率p=0.04的情況下進(jìn)行。

在本文的對(duì)比實(shí)驗(yàn)中，4個(gè)算法的種子集合大小k∈{5,10,15,20,25,30,35,40,45,50}時(shí)進(jìn)行對(duì)比分析。本次實(shí)驗(yàn)環(huán)境為：主頻為2.50 GHz的Intel Core i5-2450,運(yùn)行內(nèi)存為6 GB。實(shí)驗(yàn)中涉及的編程語(yǔ)言采用python。

3.3 結(jié)果分析

在社交網(wǎng)絡(luò)環(huán)境下，影響力最大化算法的評(píng)價(jià)指標(biāo)為：1)影響范圍，即篩選并激活相同規(guī)模的種子節(jié)點(diǎn)集合，在相同的傳播模型下該集合最終激活的節(jié)點(diǎn)個(gè)數(shù)越多表示影響范圍越廣。本文是在IC傳播模型下使用Monte-Carlo模擬2 000次傳播過(guò)程并求取平均值作為影響范圍。2)運(yùn)行時(shí)間，即在相同條件下選擇同等規(guī)模的種子節(jié)點(diǎn)集合所花費(fèi)的時(shí)間t，t越小表明算法的效率越高。

3.3.1 SHDD結(jié)果分析

首先考察α的最佳取值，通過(guò)SHDD在3個(gè)數(shù)據(jù)集上對(duì)不同的α值時(shí)進(jìn)行實(shí)驗(yàn)。

設(shè)置了在3個(gè)真實(shí)數(shù)據(jù)集中不同的α值(α∈{0.1,0.4,0.5,0.6,0.9})，隨著不同的k值運(yùn)行SHDD的影響范圍如圖7所示，圖中影響范圍代表影響節(jié)點(diǎn)數(shù)。從圖7可以看出：在3個(gè)數(shù)據(jù)集中，當(dāng)k值相同時(shí)，SHDD的影響范圍隨著α值的變化而變化。其中，在數(shù)據(jù)集1中，隨著k值的變化，不同的α值的影響節(jié)點(diǎn)個(gè)數(shù)基本上都大于α=0.1時(shí)，當(dāng)α取0.6時(shí)，SHDD的影響范圍整體較大。在數(shù)據(jù)集2中，SHDD在α值取0.1和0.9時(shí)的影響范圍整體最小，α的值越接近中心值影響范圍越大。在數(shù)據(jù)集3中，隨著k值的變化，SHDD在不同α值下的圖像趨勢(shì)和數(shù)據(jù)集2相差無(wú)幾，α值取0.1和0.9時(shí)SHDD的影響范圍整體最小，α的值越接近中心值影響范圍越大。

通過(guò)圖7的分析可知，在不同的數(shù)據(jù)集中SHDD的最優(yōu)α值不同。而在不同的網(wǎng)絡(luò)中，不可能對(duì)每一個(gè)α值進(jìn)行模擬實(shí)驗(yàn)，然后選擇最優(yōu)α值。但從圖7中可以看出，在3個(gè)不同規(guī)模的數(shù)據(jù)集中α=0.6時(shí)的SHDD的影響范圍最為穩(wěn)定，并且α=0.6是一個(gè)趨于中間的數(shù)值，不管數(shù)據(jù)集的規(guī)模偏大還是偏小，都不會(huì)呈現(xiàn)出影響效果偏差很大的現(xiàn)象。因此，本文把α=0.6作為算法的參數(shù)，后面實(shí)驗(yàn)中所提到的SHDD均是α=0.6時(shí)的SHDD。

3.3.2 對(duì)比算法結(jié)果分析

在3個(gè)真實(shí)數(shù)據(jù)集中，SHDD(α=0.6)、SH*DD算法(α=0.6)、DegreeDiscount和SG算法在傳播概率為0.04的IC模型下的影響范圍如圖8所示。由圖8(a)可知，在Route views數(shù)據(jù)集中，由于該數(shù)據(jù)集聚類系數(shù)較小屬于稀疏網(wǎng)絡(luò)，所以起橋梁作用的結(jié)構(gòu)洞節(jié)點(diǎn)在信息傳播中發(fā)揮著巨大作用，當(dāng)k≤15 時(shí)，全部選取結(jié)構(gòu)洞節(jié)點(diǎn)的SG算法其影響效果略優(yōu)于SHDD，但只依靠結(jié)構(gòu)洞節(jié)點(diǎn)并不能使信息在網(wǎng)絡(luò)的中心位置進(jìn)行更大范圍的流通，所以隨著k值的增大,SHDD綜合結(jié)構(gòu)洞節(jié)點(diǎn)和中心節(jié)點(diǎn)的傳播優(yōu)勢(shì),其影響范圍超過(guò)了SG算法，而且SHDD的影響范圍明顯優(yōu)于SH*DD和DegreeDiscount算法。在聚類系數(shù)較大的數(shù)據(jù)集2和3中，SHDD相比于其他算法有著較好的影響效果且隨著k值的增大，SHDD的優(yōu)勢(shì)越明顯。

圖7 不同α值的SHDD在不同數(shù)據(jù)集上的影響范圍Fig. 7 Influence range of SHDD algorithm with different α values on different data sets

圖8 不同算法在不同數(shù)據(jù)集上的影響范圍對(duì)比Fig. 8 Influence range comparison of different algorithms on different data sets

不同算法在3個(gè)數(shù)據(jù)集上選取并激活50個(gè)種子節(jié)點(diǎn)的的運(yùn)行時(shí)間如圖9所示。從圖9可以看出，各個(gè)算法的運(yùn)行時(shí)間在同一數(shù)量級(jí)，其中，SG算法花費(fèi)時(shí)間最多，DegreeDiscount、SH*DD和SHDD花費(fèi)時(shí)間較為均衡。

圖9 不同算法在不同數(shù)據(jù)集上的運(yùn)行時(shí)間對(duì)比Fig. 9 Runtime comparison of different algorithms on different data sets

通過(guò)綜合分析圖8～9可以得出以下結(jié)論：1) 與DegreeDiscount算法相比，SHDD在沒(méi)有增加過(guò)多時(shí)間開(kāi)銷的同時(shí)提高了影響范圍；與SG算法相比，SHDD降低了時(shí)間開(kāi)銷且在聚類系數(shù)較大的網(wǎng)絡(luò)中擴(kuò)大了影響范圍，但在聚類系數(shù)較小的稀疏網(wǎng)絡(luò)中SHDD在種子集合k較小的情況下影響范圍稍微處于劣勢(shì)，隨著k值的增加SHDD影響范圍超過(guò)了SG算法；2)在3個(gè)數(shù)據(jù)集中，SHDD的影響范圍高于SH*DD算法，可反映出利用二度鄰居選取結(jié)構(gòu)洞節(jié)點(diǎn)的質(zhì)量?jī)?yōu)于利用一度鄰居選取的結(jié)構(gòu)洞節(jié)點(diǎn)，不足之處在于增加了時(shí)間的消耗。

4 結(jié)語(yǔ)

本文分別研究中心度理論和結(jié)構(gòu)洞理論的兩種影響力最大化算法，在這兩個(gè)算法特有的基礎(chǔ)上提出基于結(jié)構(gòu)洞和度折扣的最大化算法(SHDD)。本文方法相較于上述兩種算法，主要有兩處改進(jìn)：1)將結(jié)構(gòu)洞理論與中心度思想有效地結(jié)合；2)在大型社會(huì)網(wǎng)絡(luò)中，考慮節(jié)點(diǎn)的結(jié)構(gòu)特征將二度鄰居的影響加入到結(jié)構(gòu)洞檢測(cè)思想中。實(shí)驗(yàn)表明，本文提出的SHDD在穩(wěn)定運(yùn)行時(shí)間的情況下提高了影響范圍。未來(lái)我們將尋找更好的挖掘結(jié)構(gòu)洞節(jié)點(diǎn)方法來(lái)提高算法的精度和效率，還可以考慮帶有成本限制的影響力最大化問(wèn)題[14]。