基于結構洞和度折扣的影響力最大化算法

李敏佳，許國艷，朱 帥，張網娟

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

0 引言

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

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

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

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

1 相關工作

1.1 傳播模型

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

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

1.2 結構洞

把社交網絡中的節點看作是村莊，則節點與節點之間的聯系看作連接村莊的路。如果兩個村莊沒有直接連通的道路，需要通過第三個村莊才能連通兩個村莊，則不能互相連通的兩個村莊在結構上看存在空洞，稱這個空洞為結構洞，而連接這個空洞的村莊被稱為占據結構洞節點。如圖1所示，若節點A、B、C、D兩兩互相連接則不存在結構洞；若節點A、B和C沒有直接連接而是通過節點D建立的聯系，如果去除節點D則節點A、B和C之間存在結構洞，而處于結構洞位置的節點D稱作結構洞節點。

結構洞節點可以有效控制流向其鄰居節點的信息，在信息傳播方面，Lou等[12]發現在Twitter上，1%的結構洞節點決定著25%的信息流向，結構洞節點的加入可以擴大信息的擴散范圍。例如在圖2中，信息在網絡中傳播時假設無結構洞節點1的連接，信息的交互則僅限于單個團體中，若通過結構洞節點1，在A中接收信息后會以一定的概率p將信息傳遞到B中。

圖1 結構洞概念圖Fig. 1 Concept diagram of structure hole

圖2 結構洞信息傳播圖Fig. 2 Propagation diagram of structure hole information

用網絡約束系數CT(ConsTraint)和效率值EF(EFficient)[13]來作為結構洞節點評價標準，但是前者運行內存較大且隨著網絡節點數量的增加效果變差且不穩定，所以本文此次選用效率值EF來作為結構洞節點評價標準：

(1)

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

其中:

mjq的計算式如下：

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

權值相同的拓撲圖節點j對于其鄰居節點付出的精力相同,則有：

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 評價節點i對節點q的投入精力Fig. 3 Investment evaluation of node i on node q

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

2 基于結構洞和度折扣的最大化算法

2.1 影響力最大化現有算法

現有的影響力最大化算法中，DegreeDiscount算法在反映某些節點對當前領域的影響力方面有著良好的表現，基于選取結構洞節點的SG算法具有較好的擴散效果。

DegreeDiscount算法主要思想為：如果某個節點的鄰居節點是種子節點時，則此節點的度在計算時應當打折扣，最終選取k個打折扣后度數仍最高的節點作為種子集合。如圖5所示假定k=2，則根據DegreeDiscount算法會選取度數為7的5號節點和度數為6的3號節點，該算法只是考慮選取中心節點，其時間復雜度為O(klogn+m)。

SG算法的主要思想為：通過設定結構洞值找出社交網絡中所有的結構洞節點，并通過貪心算法找出影響力值較大的k個結構洞節點作為種子集合。如圖5所示假定k=2，則根據SG算法會選取結構洞值較高的2號和6號節點作為種子節點，該算法只選取了結構洞節點，其時間復雜度為O(kRn3)。

圖5 DegreeDiscount及SG算法節點選擇示意圖Fig. 5 Schematic diagram of node selection for DegreeDiscount and SG algorithms

上述兩種算法僅僅利用結構洞節點或核心節點無法使信息擴散得到最大化，結構洞節點可以看作網絡中的邊緣節點，只激活邊緣節點或核心節點，在網絡覆蓋范圍較大的情況下得不到理想的信息擴散范圍。本文綜合考慮社交網絡中基于中心度的核心節點和結構洞節點的傳播優勢，利用結構洞理論可以彌補中心度理論不能識別橋接節點的問題，提出基于結構洞和度折扣的最大化算法(SHDD)。為了充分體現兩個思想融合的優勢，將二度鄰居的影響添加到結構洞節點評價標準中來找出更好的結構洞節點。

2.2 SHDD

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

算法1 SHDD。

輸入 圖G(V,E)，種子節點個數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);

//計算每個節點的效率值

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;

//度折扣計算

19)

tv=0;

20)

21)

S=S∪{m};

22)

end for

23)

end for

24)

returnS

算法1中：NS表示種子節點的鄰居集合，N(u)代表節點u的鄰居節點，tv指節點v的鄰居是種子節點的個數，VS是去掉種子節點的節點集合。

算法第3)行：計算每個節點的度數并保存；第4)行：根據結構洞二度評價標準計算所有節點的效率值并保存，其具體計算方法將在2.3節中詳細介紹；第6)～10)行：每次把效率值最大的節點添加到節點集合S中，并在下次選擇的時候去掉種子節點和種子節點的鄰居節點，以防止選擇的結構洞節點過于集中，迭代選擇出k1個節點添加到種子集合中；第11)～22)行是度折扣階段：對種子節點的鄰居節點進行度折扣計算，選出k2個ddv最大的節點到種子集合中。

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

2.3 結構洞二度評價標準

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

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

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

從一度鄰居來看，節點E和F的拓撲結構相同，但是從二度鄰居考慮，節點F有比E更好的拓撲關系。這種現象在式(1)的效率值的計算中無法體現，因此通過加入二度鄰居來改進效率值的計算方法，更加精準地衡量結構洞節點。

在無向網絡G(V,E)中，節點i的度記作：

其中:

(2)

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

(3)

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

q≠i,j

節點E的效率值是：

mjq)/nE

q是節點E和j的共同鄰居,則：

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

同理可得節點F的效率值：

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

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

3 實驗結果及分析

3.1 數據集

為驗證本文提出的SHDD在IM問題上的可行性，本文選取Route Views、Net HEPT和Net PHY 3個數據集進行實驗,數據集的相關屬性如表1所示。

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

表1 實驗數據集Tab. 1 Experimental data sets

3.2 實驗設置

本文實驗對這3個真實網絡數據集在IC傳播模型中進行操作。為驗證SHDD的性能，將選DegreeDiscount、SG算法和SH*DD算法與其進行實驗對比。SH*DD算法基本與SHDD一致，唯一的區別是SH*DD算法利用1.2節中的結構洞評價標準來選取結構洞節點而SHDD是用2.3節中結構洞二度評價標準來選擇結構洞節點。實驗中SHDD的結果與α取值相關，SHDD的結果會隨著α的變化而變化，因此需要設定不同的α值進行對比分析并找出最佳的α值。在傳播概率不變且一致的IC模型下，為了方便對比分析，本文的算法在傳播概率p=0.04的情況下進行。

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

3.3 結果分析

在社交網絡環境下，影響力最大化算法的評價指標為：1)影響范圍，即篩選并激活相同規模的種子節點集合，在相同的傳播模型下該集合最終激活的節點個數越多表示影響范圍越廣。本文是在IC傳播模型下使用Monte-Carlo模擬2 000次傳播過程并求取平均值作為影響范圍。2)運行時間，即在相同條件下選擇同等規模的種子節點集合所花費的時間t，t越小表明算法的效率越高。

3.3.1 SHDD結果分析

首先考察α的最佳取值，通過SHDD在3個數據集上對不同的α值時進行實驗。

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

通過圖7的分析可知，在不同的數據集中SHDD的最優α值不同。而在不同的網絡中，不可能對每一個α值進行模擬實驗，然后選擇最優α值。但從圖7中可以看出，在3個不同規模的數據集中α=0.6時的SHDD的影響范圍最為穩定，并且α=0.6是一個趨于中間的數值，不管數據集的規模偏大還是偏小，都不會呈現出影響效果偏差很大的現象。因此，本文把α=0.6作為算法的參數，后面實驗中所提到的SHDD均是α=0.6時的SHDD。

3.3.2 對比算法結果分析

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

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

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

不同算法在3個數據集上選取并激活50個種子節點的的運行時間如圖9所示。從圖9可以看出，各個算法的運行時間在同一數量級，其中，SG算法花費時間最多，DegreeDiscount、SH*DD和SHDD花費時間較為均衡。

圖9 不同算法在不同數據集上的運行時間對比Fig. 9 Runtime comparison of different algorithms on different data sets

通過綜合分析圖8～9可以得出以下結論：1) 與DegreeDiscount算法相比，SHDD在沒有增加過多時間開銷的同時提高了影響范圍；與SG算法相比，SHDD降低了時間開銷且在聚類系數較大的網絡中擴大了影響范圍，但在聚類系數較小的稀疏網絡中SHDD在種子集合k較小的情況下影響范圍稍微處于劣勢，隨著k值的增加SHDD影響范圍超過了SG算法；2)在3個數據集中，SHDD的影響范圍高于SH*DD算法，可反映出利用二度鄰居選取結構洞節點的質量優于利用一度鄰居選取的結構洞節點，不足之處在于增加了時間的消耗。

4 結語

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