基于超圖的社交網(wǎng)絡(luò)中的預(yù)算影響力最大化

陳 彬，帥天平,宋新月

(北京郵電大學(xué) 理學(xué)院， 北京 100876)

隨著網(wǎng)絡(luò)社交的迅速發(fā)展和演進(jìn)，在線社交網(wǎng)絡(luò)吸引了大量研究人員的興趣.研究人員能夠在大規(guī)模的社交網(wǎng)絡(luò)和海量交互信息中提取、研究并分析社交用戶之間的關(guān)系.影響力最大化問題是社交網(wǎng)絡(luò)研究中最熱點(diǎn)問題之一，其廣泛的應(yīng)用于推薦系統(tǒng)、病毒式營銷和突發(fā)事件檢測(cè)等領(lǐng)域.

然而由于社交網(wǎng)絡(luò)用戶群體的不斷擴(kuò)大，形成了結(jié)構(gòu)復(fù)雜的社交網(wǎng)絡(luò).如何準(zhǔn)確刻畫結(jié)構(gòu)復(fù)雜的社交網(wǎng)絡(luò)，如何模擬計(jì)算信息在社交網(wǎng)絡(luò)中的傳播，如何設(shè)計(jì)高效的算法尋找高影響力的用戶等是社交網(wǎng)絡(luò)中亟待解決的核心問題.

1 國內(nèi)外研究現(xiàn)狀

Kempe[1]等人通過有向圖去刻畫社交網(wǎng)絡(luò)，首次將影響力最大化問題建模成一個(gè)組合優(yōu)化問題.證明了在獨(dú)立級(jí)聯(lián)模型下影響力最大化問題是NP-hard的，并給出一個(gè)近似比為1-1/e的貪婪算法.目前，對(duì)社交網(wǎng)絡(luò)中影響力最大化問題的研究大都是在Kempe等研究的基礎(chǔ)上進(jìn)行探索，主要包括如下幾個(gè)方面：

1)針對(duì)Kempe等提出的模型，進(jìn)行算法優(yōu)化.Leskovec[2]等將偷懶估值的方法運(yùn)用到貪婪算法中，提出CELF算法.CELF算法既能達(dá)到1-1/e近似比，又能在實(shí)際計(jì)算中比貪婪算法效率更高.Borgs[3]等優(yōu)化采樣過程，提出基于反向影響力采樣的近線性算法.Tang[4-5]在反向影響力采樣的算法基礎(chǔ)上,分別提出了TIM/TIM+[4]和IMM[5]算法.兩種算法都能達(dá)到1-1/e-ε近似比，但是IMM算法減少了反向可達(dá)集的數(shù)目，算法運(yùn)行時(shí)間更短.在IMM算法的基礎(chǔ)上，Nguyen[6]等加入停止和注視策略，提出SSA/D-SSA算法，雖然總體上效率優(yōu)于IMM算法，但是該算法理論的表述和論證尚沒有IMM算法嚴(yán)格清晰.

2)模型優(yōu)化：將影響力最大化問題推廣到不同的應(yīng)用場(chǎng)景中，演變成不同背景下的優(yōu)化問題.比如預(yù)算影響力最大化問題[7]、魯棒影響力最大化問題[8]和多話題的影響力最大化問題[9]等.

3)在上述兩個(gè)方向的探索中，研究者都是通過有向圖去刻畫社交網(wǎng)絡(luò).Zhu[10]等提出用有向超圖去刻畫社交網(wǎng)絡(luò)，有向超邊可以表示社交網(wǎng)絡(luò)中的群體影響，但是這種模型下目標(biāo)函數(shù)不具備次模性.Zhu等利用三明治算法的思想，即通過尋找目標(biāo)函數(shù)的次模上下界函數(shù)，再通過SSA/D-SSA算法求解次模上下界函數(shù)，從而得到原問題的解.Zheng[11]等利用在線社交網(wǎng)絡(luò)的結(jié)構(gòu)特性，研究在線社交網(wǎng)絡(luò)中基于超圖的影響力最大化問題，并提出近似比為1-1/e-1/(Δ+1)的改進(jìn)貪婪算法.

通過以上研究現(xiàn)狀分析，可以看出：影響力最大化問題的算法研究進(jìn)入瓶頸階段.目前理論更完善和效率更好的是IMM算法；利用有向超圖表示社交網(wǎng)絡(luò)中的群體影響的研究工作較少，很少涉及不同傳播模型和不同應(yīng)用場(chǎng)景下優(yōu)化問題的研究.

本文考慮把基于超圖的在線社交網(wǎng)絡(luò)影響力最大化問題[11]擴(kuò)展到選取種子節(jié)點(diǎn)需要成本的場(chǎng)景，研究如何在總預(yù)算約束下尋找使得最終影響用戶最多的種子集合.

2 預(yù)備知識(shí)

2.1 超圖

定義1(超圖) 超圖[12]是二元對(duì)HG=(V,E)，V表示超圖中的節(jié)點(diǎn)集，E表示節(jié)點(diǎn)之間的超邊關(guān)系，記E={e1,e2,…,em}，其中?ej?V,j=1,2,…,m滿足ej≠?.

定義2(有向超圖) 有向超圖[12]是二元對(duì)DG=(V,E)，V表示節(jié)點(diǎn)集，E={e1,e2,…,em}表示有向超邊集.任一有向超邊ej是有序?qū)?Xj,Yj)，其中Xj和Yj是V的不相交子集，稱Xj為有向超邊ej的頭部節(jié)點(diǎn)集，Yj為有向超邊ej的尾部節(jié)點(diǎn)集，分別記為H(ej)和T(ej).

有向超圖是在超圖的超邊上添加方向，表示超邊的頂點(diǎn)之間的順序.由定義1，2可知，當(dāng)E上的所有超邊e都只關(guān)聯(lián)兩個(gè)節(jié)點(diǎn)時(shí)，超圖就退化成普通圖，即普通圖是超圖的特例.

2.2 有向超圖與社交網(wǎng)絡(luò)

在真實(shí)的社交網(wǎng)絡(luò)中，用戶之間如果存在社交聯(lián)系，可以將用戶之間通過有向邊進(jìn)行連接.但是這種有向邊只能表示兩個(gè)用戶之間的獨(dú)立關(guān)系.在心理學(xué)上[13],一個(gè)人接受信息更多的受群體影響，群體影響就是群體對(duì)某一個(gè)人的影響.超邊e=(He,v)可以在形式上刻畫這種群體影響，He表示群體包含的用戶集，v表示受該群體影響的用戶，因此本文提到的超圖都是只包含這類超邊的特殊超圖.

圖1表示用有向超圖刻畫的一個(gè)三個(gè)用戶的社交網(wǎng)絡(luò)，V={v1,v2,v3}表示用戶集，E={e1,e2}，其中H(e1)={v1,v2}，T(e1)={v3}；H(e2)={v1}，T(e2)={v3}.當(dāng)v1，v2都給v3傳遞信息的時(shí)候，v3才能接受信息，即v1，v2通過超邊e1影響v3.當(dāng)只有v2傳遞信息時(shí)，v3將不受其影響.因此，超邊e1刻畫了v1，v2的群體影響.

圖1 社交網(wǎng)絡(luò)Figure 1 Social Networks

2.3 次模函數(shù)

定義3(次模函數(shù))給定一個(gè)有限集合V和定義在V的冪集合2V上的集合函數(shù)σ，對(duì)于任意的V的子集S′?S?V和v∈VS，σ(S′∪{v})-σ(S′)≥σ(S∪{v})-σ(S)，則稱集合函數(shù)σ為次模函數(shù)[14].

3 預(yù)算影響力最大化

3.1 信息傳播模型

社交網(wǎng)絡(luò)中的信息傳播模型是用來模擬社交用戶之間的交互過程.常見的信息傳播模型包括：獨(dú)立級(jí)聯(lián)模型和線性閾值模型.本文研究的預(yù)算影響力最大化問題是在獨(dú)立級(jí)聯(lián)模型下進(jìn)行的，因此以下部分主要介紹獨(dú)立級(jí)聯(lián)模型.

超圖中的獨(dú)立級(jí)聯(lián)模型的場(chǎng)景:給定一個(gè)有向超圖DG=(V,E,P)表示一個(gè)社交網(wǎng)絡(luò)，V={v}是節(jié)點(diǎn)集，即社交網(wǎng)絡(luò)中的用戶；E={e}是有向超邊集，有向超邊表示信息在社交網(wǎng)絡(luò)中的傳播方向；P={pe}是有向超邊的權(quán)重集，表示影響傳播概率.模型初始條件：在有向超圖DG中給定一組節(jié)點(diǎn)集S，S中的所有節(jié)點(diǎn)最初都是活躍的，也稱為種子用戶，而所有不在S中的其他節(jié)點(diǎn)最初都是不活躍的.

獨(dú)立級(jí)聯(lián)模型按照以下隨機(jī)過程以離散步驟展開：

1)在t=0時(shí)刻，集合S0=S，集合S0=S中的節(jié)點(diǎn)被激活；

2)在任意的t≥1，St表示到t時(shí)刻為止所有活躍節(jié)點(diǎn)的集合.對(duì)于任意一個(gè)超邊e=(He,v)，當(dāng)且僅當(dāng)滿足HeSt-1≠?和He?St時(shí)，e才在t時(shí)刻第一次被激活；

3) 當(dāng)He中的所有節(jié)點(diǎn)都處于活躍狀態(tài)，每個(gè)激活的超邊e=(He,v)有且只有一次機(jī)會(huì)以pe的概率激活節(jié)點(diǎn)v.

3.2 預(yù)算影響力最大化問題模型

傳統(tǒng)的影響力最大化問題的目標(biāo)是尋找k個(gè)影響力高的節(jié)點(diǎn)，然而在實(shí)際的病毒式營銷場(chǎng)景中，尋找高影響力的用戶是需要成本的.因此，我們考慮在有向超圖中，在一定的預(yù)算約束下尋找高影響力的用戶，使得最終受影響的節(jié)點(diǎn)最多，稱其為預(yù)算影響力最大化問題.

給定一個(gè)有向超圖DG=(V,E,P,c)，c表示節(jié)點(diǎn)的成本集合，c(v)表示選擇作v為初始激活節(jié)點(diǎn)的成本.預(yù)算影響力最大化問題的是在總成本不超過預(yù)算的約束下，找到一個(gè)具有最高期望影響的種子集S:

maxσ(S)

(1)

(2)

其中:σ(S)是在獨(dú)立級(jí)聯(lián)模型下，最終被激活的節(jié)點(diǎn)的期望數(shù)目.

3.3 影響力擴(kuò)展度的計(jì)算

當(dāng)在有向圖上計(jì)算影響力擴(kuò)展度[15]時(shí)，則：

其中:p(u,v)表示u激活v的概率，u是v的入鄰居.

當(dāng)在有向超圖上計(jì)算擴(kuò)展度時(shí)，則：

Chen[15]等證明了在獨(dú)立級(jí)聯(lián)模型下，有向圖中影響力擴(kuò)展度σ(S)的遞歸計(jì)算是#P-難的.由于有向圖是有向超圖的一種特例，因此容易得到如下定理.

定理3.1(影響力擴(kuò)展度計(jì)數(shù)復(fù)雜性)在有向超圖的社交網(wǎng)絡(luò)中，在獨(dú)立級(jí)聯(lián)模型下計(jì)算一個(gè)集合的影響力擴(kuò)展度是#P-難的.

定理3.1指出了超圖中的影響力擴(kuò)展度的計(jì)數(shù)難解性，因此用精確計(jì)算的方法在實(shí)際中是沒有效率的.Kempe[1]等提出了在有向圖中的影響力擴(kuò)展度可以用蒙特卡洛近似計(jì)算.在這里我們將蒙特卡洛近似估計(jì)推廣到有向超圖中，并作為預(yù)算影響力問題的擴(kuò)展度計(jì)算方法.

算法1中A表示每一步完成后總的激活節(jié)點(diǎn)集，B表示每一步新激活的節(jié)點(diǎn)集.算法1的第6行表示節(jié)點(diǎn)激活的條件，θv表示每個(gè)節(jié)點(diǎn)被激活的閾值.算法1的時(shí)間復(fù)雜度是O(R|E|).

-------------------------------------------

算法1 影響力擴(kuò)展度的蒙特卡洛估計(jì)

-------------------------------------------

輸入：有向超圖DG，種子集合S，模擬次數(shù)R

初始化：total←0

1)fori=1toRdo

2)A=S,B=S

3)whileB≠? do

4)New?

5)for 第一次滿足H(e)?A的edo

6)p(A,v) =p(A,H(e))pe

7)if 閾值θv尚未生成 then 獨(dú)立均勻隨機(jī)采樣

[0,1]中的一值賦值給θeend if

8)ifp(A,H(e))≥θethenNew=New∪{{v}A}

end if end for

9)A=A∪New,B=Newend while

10)total=total+|A| end for

-------------------------------------------

3.4 預(yù)算影響力最大化問題的性質(zhì)

定理3.2(預(yù)算影響力最大化的難解性) 在有向超圖的社交網(wǎng)絡(luò)中，在獨(dú)立級(jí)聯(lián)模型下預(yù)算影響力最大化問題是NP-hard的.

證明：令所有節(jié)點(diǎn)的成本c(v)=1，目標(biāo)函數(shù)保持不變，約束條件就轉(zhuǎn)化為|S|≤B;此時(shí)預(yù)算影響力最大化問題等同于基于超圖的影響力最大化問題[11]，即影響力最大化問題是預(yù)算影響力最大化問題的特例.由于影響力最大化問題是NP-hard，所以預(yù)算影響力最大化問題在獨(dú)立級(jí)聯(lián)模型下是NP-hard.

定理3.3(目標(biāo)函數(shù)的次模性)在有向超圖的社交網(wǎng)絡(luò)中，在獨(dú)立級(jí)聯(lián)模型下σ(S)是單調(diào)非負(fù)的非次模函數(shù).

證明：?jiǎn)握{(diào)非負(fù)性是顯而易見的.非次模性通過一個(gè)反例來證.給定一個(gè)如圖2所示的社交網(wǎng)絡(luò)，設(shè)成本c(vi)=rand(1,10)，i=1,…,6，影響傳播概率p(ej)，j=1,…,4.

圖2 反例Figure 2 Counter Example

假設(shè)T=?，S={v1,v2}，v=v4，由于每條邊的影響傳播概率都是1，因此在獨(dú)立級(jí)聯(lián)模型下：σ(T∪{v})=1，σ(T)=0；σ(S∪{v})=6，σ(S)=4；

則σ(T∪{v})-σ(T)<σ(S∪{v})-σ(S)，不滿足次模函數(shù)的定義，因此在獨(dú)立級(jí)聯(lián)模型下σ(S)是單調(diào)非負(fù)的非次模函數(shù).

預(yù)算影響力最大化問題在獨(dú)立級(jí)聯(lián)模型下是NP-hard的，因此求解該問題需要另辟蹊徑.近似算法是解決NP-hard優(yōu)化問題的一類有效的方式，因此下面重點(diǎn)介紹解決預(yù)算影響力最大化問題的近似算法.

4 算法設(shè)計(jì)與分析

4.1 預(yù)算貪婪算法

在傳統(tǒng)的影響力最大化問題中，近似算法的設(shè)計(jì)依賴于影響力擴(kuò)展度的次模性質(zhì).單調(diào)次模函數(shù)的一個(gè)重要的性質(zhì)是可以用貪婪算法找到一個(gè)近似比為1-1/e的近似最優(yōu)解.貪婪算法的思想是每一步選取影響力增量最大的節(jié)點(diǎn)到種子集中，直到種子集滿足要求為止.將貪婪算法思想運(yùn)用到預(yù)算影響力最大化問題中，形成預(yù)算貪婪算法.預(yù)算貪婪算法的思想就是在每一步選取單位成本下影響力增量最大的節(jié)點(diǎn)到種子集中，即滿足arg maxv∈VS{Δvσ(S)/c(v)}，其中Δvσ(S)=σ(S∪{v})-σ(S)表示影響力增量；直到c(S∪{u})>B停止選取.算法的具體步驟如算法2所示.

-------------------------------------------

算法2 預(yù)算貪婪算法(BG)

-------------------------------------------

輸入：有向超圖DG=(V,E,P,c)，總預(yù)算B

輸出: 種子集合S

初始化：,S=?,V1=V

1)whileV1=? do

2)u=arg maxv∈V1{Δvσ(S)/c(v)}

3)ifc(S∪{u})≤BthenS=S∪{u}

4)end if

5)V1←V1{u}

6)end while

7)s← arg maxv∈V,c(v)≤Bσ({v})

8)S=arg max(σ({s}),σ(S))

-------------------------------------------

但是，在預(yù)算影響力最大化問題中，目標(biāo)函數(shù)不滿足次模性.這種非次模性破壞了貪婪算法的1-1/e近似比.Zheng等在定理4[11]中給出貪婪算法求解非次模最大化問題的近似比，將其應(yīng)用到我們問題中，可以得到如下定理：

4.2 改進(jìn)貪婪算法

定義4(模性集)給定單調(diào)目標(biāo)函數(shù)σ(·)，節(jié)點(diǎn)v的模性集定義為：Mv={v′|σ(S∪{v,v′})>σ(S∪{v′})>σ(S∪{v})-σ(S),v′∈V,S?V}.

定義5(超模性[16])Δ=maxv|Mv|，稱Δ為超模性.

模性集Mv度量了節(jié)點(diǎn)v局部次模性.當(dāng)Mv=?，稱v節(jié)點(diǎn)是局部次模的.當(dāng)所有節(jié)點(diǎn)都是局部次模時(shí)，即Δ=maxv|Mv|=0，則σ(S)是次模函數(shù).

受模性集的啟發(fā)，我們對(duì)預(yù)算貪婪算法進(jìn)行改進(jìn).改進(jìn)貪婪算法的思想是將Zheng等提出的近似算法思想和預(yù)算貪婪算法相結(jié)合.預(yù)算貪婪算法是每一步選擇滿足arg max{Δvσ(S)/c(v)}的節(jié)點(diǎn)v.假設(shè)v已經(jīng)被選取，預(yù)算貪婪算法會(huì)繼續(xù)選取滿足上述條件的節(jié)點(diǎn).但是Mv中的節(jié)點(diǎn)會(huì)使得v產(chǎn)生更大的影響力增量.因此，改進(jìn)貪婪算法是在選取v節(jié)點(diǎn)的同時(shí)優(yōu)先選取Mv中的節(jié)點(diǎn)，選取的節(jié)點(diǎn)集滿足單位成本下的影響力增量最大，即算法3的步驟2).算法的具體步驟如算法3所示.

-------------------------------------------

算法3 改進(jìn)預(yù)算貪婪算法(IBG)

-------------------------------------------

輸入：有向超圖DG=(V,E,P,c)，總預(yù)算B

-------------------------------------------

-------------------------------------------

輸出: 種子集合S

初始化：S=?,V1=V

1)whileV1=? do

6)s←arg maxv∈V,c(v)≤Bσ({v})

7)S=arg max(σ({s}),σ(S))

-------------------------------------------

由于給定一個(gè)集合S，通過算法1求解影響力擴(kuò)展度的時(shí)間復(fù)雜度為O(R|E|).算法3一次循環(huán)最多產(chǎn)生子集數(shù)量為2Δ，所以算法3的時(shí)間復(fù)雜度為O(2Δ|V|R|E|).下面對(duì)算法3 進(jìn)行理論分析.

定理4.2(改進(jìn)貪婪算法的近似比)改進(jìn)貪婪算法的近似比不超過(1+Δ+α)β+1，即:σ(S*)≤((1+Δ+α)β+1)σ(S).

證：設(shè)S*為最優(yōu)解的種子節(jié)點(diǎn)集合，定義一個(gè)集合Hi滿足如下條件：1)H0=S*；2)Hi是Hi=1∪Si子集中滿足SiHi，c(Hi)≤B的最大子集；Si表示算法3第i步迭代選取的節(jié)點(diǎn)集；3)Si中的節(jié)點(diǎn)都被增加到Hi中，S*中的部分節(jié)點(diǎn)從Hi-1中被移除.由定義可知：

|Hi+1|=|Hi|-|HiHi+1|+|Si+1Si|

(1)

因此：

|Hi|-|Hi+1|≤1+Δ+α

(2)

其中α=max{|Hi|-|Hi+1|}.

(3)

將上述式子累加可得：

σ(Hi)-σ(Hi+1)

(4)

又注意到

(5)

上面的第一個(gè)不等號(hào)成立是因?yàn)槭?2)成立，第二個(gè)不等號(hào)成立是因?yàn)闈M足算法3的第二步，第四個(gè)不等號(hào)成立是因?yàn)槭?4)成立.

對(duì)式(5)化簡(jiǎn)，可得：

上式對(duì)i進(jìn)行累加，得：

(σ(Si)-σ(S0))≤

(σ(Si)-σ(S0))

(6)

4.3 啟發(fā)式算法

上面提到的兩個(gè)貪婪算法都能找到一個(gè)近似最優(yōu)解.為了使得得到的解更接近于最優(yōu)解，在此基礎(chǔ)上進(jìn)一步進(jìn)行處理，得到節(jié)點(diǎn)交換的啟發(fā)式算法.該算法的思想是，首先通過算法2或3得到一個(gè)種子集合S，然后在S中去掉一個(gè)節(jié)點(diǎn)v，得到種子集合S1，去掉節(jié)點(diǎn)v需滿足σ(S)-σ(S1)最小.最后在VS1中挑選節(jié)點(diǎn)增加到S1中，使得S1的影響力增量最大.增加后的節(jié)點(diǎn)集S1仍然需要滿足c(S1)≤B,且σ(S)≤σ(S1).

-------------------------------------------

算法4 交換啟發(fā)式算法

-------------------------------------------

輸入：有向超圖DG=(V,E,P,c)，總預(yù)算B

輸出: 種子集合S

初始化：S1=BG或者S1=IBG

1)u=arg minv∈S1(σ(S1)-σ(S1v))

2)u′=arg maxv′∈VS1,c((S1u)∪v′)≤B{σ((S1u)∪

{v′})-σ(S1u)}

3)ifσ(S1)≤σ((S1u)∪{u′})

4)thenS1=(S1u)∪{u′} end if

5)S=S1

-------------------------------------------

算法4時(shí)間復(fù)雜度取決于兩個(gè)部分：1)初始化算法的時(shí)間復(fù)雜度;2)進(jìn)行節(jié)點(diǎn)交換的時(shí)間復(fù)雜度，節(jié)點(diǎn)交換的迭代次數(shù)是O(|V|).每次要對(duì)影響力擴(kuò)展度σ(S)及其增量進(jìn)行計(jì)算，而這個(gè)時(shí)間復(fù)雜度不超過算法2和3中計(jì)算相應(yīng)的影響力擴(kuò)展度的時(shí)間復(fù)雜度.因此當(dāng)選擇算法2或3作為初始化算法時(shí)，算法4的時(shí)間復(fù)雜度與算法2或3的時(shí)間復(fù)雜度同階.

5 仿真實(shí)驗(yàn)

本文通過真實(shí)的社交網(wǎng)絡(luò)上的數(shù)據(jù)測(cè)試提出的算法的有效性和性能，并采用加權(quán)超度算法[11](WH)作為基準(zhǔn)來對(duì)算法2～4進(jìn)行比較分析.

5.1 數(shù)據(jù)集和實(shí)驗(yàn)設(shè)置

本文的實(shí)驗(yàn)是在三個(gè)在線社交網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行的，它們分別來自兩個(gè)在線網(wǎng)絡(luò)存儲(chǔ)庫Tore Opsahl[17]和net-workrepository[18].數(shù)據(jù)集1(Board)來自Tore Opsahl，Board記錄屬于某些公司董事會(huì)的董事.數(shù)據(jù)集2(ca-netscience)來自net-workrepository，是一個(gè)合著者網(wǎng)絡(luò).數(shù)據(jù)集3(Forum)來自Tore Opsahl[17]，記錄的是論壇中用戶之間的活動(dòng)關(guān)系，其中數(shù)據(jù)集3是Forum 中的一個(gè)子集.

給定的三個(gè)數(shù)據(jù)集初始描述都是有向圖，而本文考慮的是有向超圖，因此需要在其基礎(chǔ)上建立超圖模型.這里有向超圖是通過Huang[17]提出的基于統(tǒng)計(jì)推理的框架生成.將數(shù)據(jù)集1～3輸入到基于統(tǒng)計(jì)推理的框架，生成有向超圖的結(jié)果如表1所示.

表1 數(shù)據(jù)集統(tǒng)計(jì)Table 1 Dataset Statistics

數(shù)值實(shí)驗(yàn)設(shè)置包含兩個(gè)部分:1)節(jié)點(diǎn)成本的設(shè)置;2)總預(yù)算的設(shè)置.在實(shí)驗(yàn)中每個(gè)節(jié)點(diǎn)成本設(shè)置成1～10中間的隨機(jī)數(shù)，總預(yù)算分別取5，10，15，20，25.

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

本文仿真實(shí)驗(yàn)代碼在Matlab2019中實(shí)現(xiàn)，在搭載2.10 GHz Intel Silver4116處理器的聯(lián)想臺(tái)式電腦上執(zhí)行.我們對(duì)提出的預(yù)算貪婪算法及其改進(jìn)算法和交換算法進(jìn)行實(shí)驗(yàn)分析，其中交換算法有3種情形，分別取算法2 、算法3和加權(quán)超度算法得到的解為初始解.為方便起見，對(duì)要比較的這幾種算法進(jìn)行簡(jiǎn)單說明：加權(quán)超度算法[11](WH): 通過節(jié)點(diǎn)的度去排序節(jié)點(diǎn)，然后利用貪婪策略優(yōu)先選取當(dāng)前階段度大的節(jié)點(diǎn)，直到選擇的節(jié)點(diǎn)的總成本大于預(yù)算為止.預(yù)算貪婪算法(BG)：本文中的算法改進(jìn)貪婪算法(IBG):本文中的算法交換啟發(fā)式算法1(SBG):算法4的一類，在其初始化步驟選取算法2.交換啟發(fā)式算法2(SIBG):算法4的一類，在其初始化步驟選取算法3.交換啟發(fā)式算法3(SWH):算法4的一類，在其初始化步驟選取加權(quán)超度算法.

對(duì)于這六種算法，我們比較5～25不同預(yù)算下總的影響力.為了確保結(jié)果的可靠性，蒙特卡洛模擬的次數(shù)設(shè)為R=100，同時(shí)在不同算法實(shí)驗(yàn)中，相同節(jié)點(diǎn)的成本是相同的.圖3展示三個(gè)數(shù)據(jù)集中，不同預(yù)算下所有算法的影響力結(jié)果.

根據(jù)圖3，顯然可見，總的影響力隨著預(yù)算的增加而增加，但是增加的幅度越來越小.在三個(gè)數(shù)據(jù)集中，BG和IBG的在同一預(yù)算下影響力明顯高于SWH，尤其在更大的數(shù)據(jù)集中，這種優(yōu)勢(shì)更加明顯.對(duì)于IBG，在小型社交網(wǎng)絡(luò)中，雖然優(yōu)于BG,但是優(yōu)勢(shì)較?。辉跀?shù)據(jù)集3中，優(yōu)勢(shì)明顯.這是因?yàn)閿?shù)據(jù)3的社交網(wǎng)絡(luò)較復(fù)雜，IBG的設(shè)計(jì)中考慮網(wǎng)絡(luò)的結(jié)構(gòu)，優(yōu)先選取了模性集中的節(jié)點(diǎn).

圖3 不同預(yù)算下的算法性能Figure 3 Algorithm performance under different budgets

三種交換算法都是在初始化算法的基礎(chǔ)上進(jìn)行交換優(yōu)化，顯然也是優(yōu)于其初始化算法.IBG算法在非交換啟發(fā)式算法(WH,BG,IBG)中是最好的， SIBG在交換啟發(fā)式算法中是最好. 顯然， 若初始化選取的算法較好，則交換啟發(fā)式算法也更好.

圖4顯然可見，三種交換啟發(fā)式算法結(jié)果優(yōu)于三種非交換啟發(fā)式算法.圖4中紫色部分表示不同預(yù)算下三種非交換啟發(fā)算法的影響力擴(kuò)展度，橙色部分表示交換啟發(fā)式算法與對(duì)應(yīng)的非交換啟發(fā)式算法之間的影響力擴(kuò)展度之差.SIBG與IBG的影響力擴(kuò)展度之差相對(duì)較小，說明IBG算法已經(jīng)能達(dá)到一個(gè)相對(duì)較優(yōu)的解.SWH與WH的影響力擴(kuò)展度之差相對(duì)較大，說明WH算法解較差.

圖4 數(shù)據(jù)集3上的算法性能Figure 4 Algorithm performance on dataset 3

運(yùn)行時(shí)間：表2給出了預(yù)算B=25時(shí)不同算法的運(yùn)行時(shí)間.WH算法雖然結(jié)果較差，但是其運(yùn)行時(shí)間很短，適合應(yīng)用到超大數(shù)據(jù)集中.IBG和SIBG的解比其他四種算法更優(yōu)，但是運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)大于其他四種算法.

表2 預(yù)算B=25時(shí)算法的運(yùn)行時(shí)間Table 2 Running time of algorithm when budget B=25

6 結(jié) 語

本文主要把基于超圖的影響力最大化問題推廣到基于超圖的預(yù)算影響力最大化問題.在預(yù)算影響力最大化問題的模型下，研究問題的難解性和目標(biāo)函數(shù)的次模性，并提出目標(biāo)函數(shù)的蒙特卡洛估計(jì)算法.基于該問題的模型的性質(zhì)，提出了預(yù)算貪婪、改進(jìn)的預(yù)算貪婪和節(jié)點(diǎn)交換的啟發(fā)式算法來解決該問題.此外，我們?cè)谌齻€(gè)真實(shí)的社交網(wǎng)絡(luò)數(shù)據(jù)集中進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明本文算法是正確有效的.

在接下來的研究中，力圖設(shè)計(jì)具有更好近似比和時(shí)間復(fù)雜度的近似算法.另外，考慮其他擴(kuò)散模型下(如:線性閾值模型)相應(yīng)問題的算法設(shè)計(jì)也是很有意義的工作.