融合節(jié)點(diǎn)覆蓋范圍和結(jié)構(gòu)洞的影響力最大化算法

楊 杰，張名揚(yáng)，芮曉彬，王志曉

（中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇徐州 221116）

0 引言

隨著在線社交網(wǎng)絡(luò)的飛速發(fā)展，越來(lái)越多的用戶喜歡在社交網(wǎng)絡(luò)上轉(zhuǎn)發(fā)時(shí)事新聞并分享自己的觀點(diǎn)，使得影響力傳播問(wèn)題成為社交網(wǎng)絡(luò)分析領(lǐng)域中的研究熱點(diǎn)。影響力最大化問(wèn)題是從網(wǎng)絡(luò)中選取部分節(jié)點(diǎn)，從而使得當(dāng)這些節(jié)點(diǎn)在網(wǎng)絡(luò)中擴(kuò)散消息時(shí)，最終能夠影響到的節(jié)點(diǎn)數(shù)量最大化。該問(wèn)題作為病毒式營(yíng)銷和在線廣告投放的重要依據(jù)，引起了學(xué)者們的廣泛關(guān)注。

影響力最大化問(wèn)題最早由Domingos 等提出，旨在尋找

k

個(gè)初始種子節(jié)點(diǎn)，并使得最終的信息傳播范圍最廣。后來(lái)，國(guó)內(nèi)外學(xué)者從不同角度提出了多種影響力最大化算法，這些算法可大致分為兩類：一類是基于蒙特卡洛模擬的貪心算法及其改進(jìn)算法；另一類是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的啟發(fā)式算法。貪心算法能保證至少達(dá)到最優(yōu)解63%的傳播范圍，但時(shí)間復(fù)雜度較高，不適用于大規(guī)模網(wǎng)絡(luò)。啟發(fā)式算法效率較高，但性能不穩(wěn)定，受網(wǎng)絡(luò)結(jié)構(gòu)影響較大。

在貪心算法方面，Kempe 等提出General Greedy 算法，該算法有著很高的精確度，但在每次選取種子節(jié)點(diǎn)時(shí)需要遍歷整個(gè)網(wǎng)絡(luò)并執(zhí)行數(shù)千次的蒙特卡洛模擬過(guò)程，導(dǎo)致該算法效率較低。優(yōu)化后的貪心算法CELF（Cost-Effective Lazy Forward selection）利用函數(shù)的子模性對(duì)運(yùn)行效率進(jìn)行了改進(jìn)，運(yùn)行效率比之前提高了約700 倍。之后，Chen 等又提出了New Greedy 算法和Mix Greedy 算法來(lái)優(yōu)化貪心算法，然而，優(yōu)化后的貪心算法運(yùn)行時(shí)間仍然較高，很難應(yīng)用到大規(guī)模網(wǎng)絡(luò)中。

近年來(lái)，研究者傾向于設(shè)計(jì)啟發(fā)式算法來(lái)解決貪心算法運(yùn)行效率低的問(wèn)題。Chen 等提出的DegreeDiscount 算法是經(jīng)典的啟發(fā)式算法，該算法通過(guò)削弱鄰居節(jié)點(diǎn)度值來(lái)避免所選種子過(guò)于集中，提高了最終性能。Nguyen 等提出pBmH（probability-Based multi-Hop diffusion）算法，該算法將節(jié)點(diǎn)在多跳鄰域內(nèi)能影響的節(jié)點(diǎn)數(shù)作為中心性指標(biāo)，確保篩選出的種子節(jié)點(diǎn)不相鄰。高菊遠(yuǎn)等和Wang 等將節(jié)點(diǎn)的覆蓋范圍增益作為衡量節(jié)點(diǎn)影響力的中心性指標(biāo)，進(jìn)一步避免了“富人俱樂(lè)部”現(xiàn)象，提出的基于節(jié)點(diǎn)覆蓋范圍的算法（Node Coverage Algorithm，NCA）性能表現(xiàn)突出。但是，該算法僅依靠單一的中心性指標(biāo)來(lái)衡量節(jié)點(diǎn)影響力，只能反映節(jié)點(diǎn)的單一屬性，無(wú)法很好地適應(yīng)網(wǎng)絡(luò)結(jié)構(gòu)的變化，因此在不同結(jié)構(gòu)特征的網(wǎng)絡(luò)中表現(xiàn)不穩(wěn)定。

本文從多屬性融合的角度提出一種基于覆蓋范圍和結(jié)構(gòu)洞的影響力最大化算法（influence maximization algorithm based on Node Coverage and Structural Hole，NCSH），該算法融合節(jié)點(diǎn)的覆蓋范圍和結(jié)構(gòu)洞性質(zhì)對(duì)節(jié)點(diǎn)影響力進(jìn)行全面評(píng)價(jià)，有效解決了傳統(tǒng)基于拓?fù)浣Y(jié)構(gòu)的啟發(fā)式算法性能不穩(wěn)定的問(wèn)題。實(shí)驗(yàn)結(jié)果表明相較于其他算法，本文所提算法能夠獲得更大的節(jié)點(diǎn)影響范圍，并且，隨著網(wǎng)絡(luò)規(guī)模及結(jié)構(gòu)的變化，本文算法表現(xiàn)出良好的穩(wěn)定性。

1 節(jié)點(diǎn)覆蓋范圍計(jì)算

節(jié)點(diǎn)的覆蓋范圍是指節(jié)點(diǎn)本身及其能直接影響到的一階鄰居節(jié)點(diǎn)數(shù)量，若這些節(jié)點(diǎn)中存在其他種子的鄰居節(jié)點(diǎn)，則去除這些重復(fù)節(jié)點(diǎn)后的數(shù)量即為節(jié)點(diǎn)的覆蓋范圍增益。一組節(jié)點(diǎn)的覆蓋范圍為它們各自覆蓋范圍的并集。例如，用

N

表示節(jié)點(diǎn)

i

的鄰居集合，則節(jié)點(diǎn)

i

和節(jié)點(diǎn)

j

的共同覆蓋范圍

N

∪為：

因此，種子節(jié)點(diǎn)集合

S

的覆蓋范圍

N

如式（2）所示：

節(jié)點(diǎn)覆蓋增益具有子模性，即將某節(jié)點(diǎn)添加至種子集合時(shí)所帶來(lái)的覆蓋增益不會(huì)大于將其添加至該種子集合的子集。節(jié)點(diǎn)

v

的覆蓋增益計(jì)算方法如式（3）所示：

其中：

N

為節(jié)點(diǎn)

v

的鄰居集合；

N

為種子集合

S

的節(jié)點(diǎn)覆蓋范圍；

S

ˉ為網(wǎng)絡(luò)中不包含種子的節(jié)點(diǎn)集合。

由于大部分社交網(wǎng)絡(luò)傳播概率較低，所能影響到的節(jié)點(diǎn)集中在其一階鄰居，因而選取節(jié)點(diǎn)覆蓋的一階鄰居數(shù)量作為覆蓋范圍增益，忽略與現(xiàn)有種子集的重疊鄰居，著重考察非重疊鄰居數(shù)量，可有效避免“富人俱樂(lè)部”現(xiàn)象，進(jìn)一步提高影響范圍。

2 節(jié)點(diǎn)結(jié)構(gòu)洞特性評(píng)價(jià)

對(duì)于社交網(wǎng)絡(luò)中不直接相連的兩節(jié)點(diǎn)之間，若能通過(guò)某個(gè)中間節(jié)點(diǎn)實(shí)現(xiàn)間接連接，則將該中間節(jié)點(diǎn)稱之為具有結(jié)構(gòu)洞性質(zhì)的節(jié)點(diǎn)。結(jié)構(gòu)洞性質(zhì)能夠表示信息在網(wǎng)絡(luò)中完全擴(kuò)散的必經(jīng)之路，不同于介數(shù)中心性，它僅通過(guò)鄰域的拓?fù)潢P(guān)系便可計(jì)算得到，時(shí)間復(fù)雜度較低。結(jié)構(gòu)洞節(jié)點(diǎn)能夠有效控制信息流向鄰居節(jié)點(diǎn)，從而具有更高的網(wǎng)絡(luò)覆蓋范圍收益。如圖1 所示，節(jié)點(diǎn)2 是三個(gè)社區(qū)之間的結(jié)構(gòu)洞，若移除該節(jié)點(diǎn)，則信息無(wú)法在社區(qū)間相互傳輸。Lou 等發(fā)現(xiàn)Twitter上1%的結(jié)構(gòu)洞節(jié)點(diǎn)決定著25%的信息流向，因此結(jié)構(gòu)洞節(jié)點(diǎn)的加入可以擴(kuò)大信息的擴(kuò)散范圍。此外，結(jié)構(gòu)洞特性對(duì)于社交網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)問(wèn)題也具有重要意義。

圖1 節(jié)點(diǎn)結(jié)構(gòu)洞特性Fig.1 Node structure hole characteristics

蘇曉萍等指出可以用網(wǎng)格約束系數(shù)來(lái)衡量網(wǎng)絡(luò)節(jié)點(diǎn)在形成結(jié)構(gòu)洞時(shí)受到的約束：

其中：

CT

為節(jié)點(diǎn)

i

的約束系數(shù)；

τ

(

i

)為節(jié)點(diǎn)

i

的鄰居節(jié)點(diǎn)；節(jié)點(diǎn)

q

為節(jié)點(diǎn)

i

和節(jié)點(diǎn)

j

的共同鄰居；

p

表示節(jié)點(diǎn)

i

連接節(jié)點(diǎn)

j

付出精力的比重。

p

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

其中：

圖2 約束系數(shù)計(jì)算Fig.2 Constraint coefficient calculating

網(wǎng)格約束系數(shù)能考量節(jié)點(diǎn)的度值和鄰域連接緊密度，若節(jié)點(diǎn)的約束系數(shù)越小，則意味著其具有較高的度值和較低的鄰域鏈接緊密度，使得該節(jié)點(diǎn)具有程度更高的結(jié)構(gòu)洞性質(zhì)。在具有相同覆蓋增益的情況下，該節(jié)點(diǎn)作為信息傳播的中樞節(jié)點(diǎn)，有利于將信息擴(kuò)散至其他社區(qū)，進(jìn)一步擴(kuò)大影響范圍。

3 本文算法

3.1 問(wèn)題定義

影響力最大化問(wèn)題是在給定社交網(wǎng)絡(luò)

G

(

V

，

E

)中選擇最具影響力的

k

個(gè)節(jié)點(diǎn)集合

S

（通常稱為種子節(jié)點(diǎn)），使其在一定的傳播模型下能影響到盡可能大的網(wǎng)絡(luò)范圍

σ

(

S

)。

3.2 算法描述

為解決IM 問(wèn)題，本文所提NCSH，其基本思想為：首先，利用節(jié)點(diǎn)覆蓋范圍增益的中心性指標(biāo)選擇覆蓋范圍增益最大的節(jié)點(diǎn)；然后，隨著所選種子節(jié)點(diǎn)數(shù)量的增加，每輪可能會(huì)出現(xiàn)多個(gè)覆蓋增益相同的候選種子節(jié)點(diǎn)；在這種情況下，從候選種子集中選擇約束系數(shù)最小的節(jié)點(diǎn)，確保具有最大的網(wǎng)絡(luò)傳播收益；最終重復(fù)此過(guò)程，直至選出

k

個(gè)種子節(jié)點(diǎn)。

算法1 基于覆蓋范圍和結(jié)構(gòu)洞的影響力最大化算法（NCSH）。

輸入 網(wǎng)絡(luò)

G

(

V

，

E

)，種子節(jié)點(diǎn)數(shù)

k

。輸出 種子節(jié)點(diǎn)集合

S

。

圖3 為NCSH 的執(zhí)行過(guò)程。首先，算法選擇度值最大的節(jié)點(diǎn)15 作為1 號(hào)種子，其覆蓋范圍在圖3（a）用橫線標(biāo)出。接著，算法更新剩余節(jié)點(diǎn)的覆蓋范圍增益（圖3（b）），更新結(jié)果顯示節(jié)點(diǎn)5 的覆蓋范圍增益（豎線標(biāo)出節(jié)點(diǎn)）最大，所以選擇節(jié)點(diǎn)5 作為2 號(hào)種子。

圖3 NCSH執(zhí)行過(guò)程Fig.3 Execution process of NCSH

然后，算法再次更新剩余節(jié)點(diǎn)的覆蓋范圍增益，更新結(jié)果顯示節(jié)點(diǎn)22 和9 的覆蓋范圍增益同為最大，選擇它們均可擴(kuò)大3 個(gè)節(jié)點(diǎn)的范圍（如圖3（c）所示的正方形網(wǎng)格節(jié)點(diǎn)）。此時(shí)，算法根據(jù)網(wǎng)格約束系數(shù)判斷22 號(hào)節(jié)點(diǎn)（約束系數(shù)為0.249 3）比9 號(hào)節(jié)點(diǎn)（約束系數(shù)為0.506 2）小，因此選擇22 號(hào)為3 號(hào)種子?？梢园l(fā)現(xiàn)，在本圖例中，與9 號(hào)節(jié)點(diǎn)相比，22 號(hào)節(jié)點(diǎn)具有較高的度值和較強(qiáng)的社區(qū)中心性，雖然它們的覆蓋增益均為3，但22 號(hào)節(jié)點(diǎn)還有額外6 次機(jī)會(huì)去影響15 號(hào)節(jié)點(diǎn)未激活的節(jié)點(diǎn)，從而能夠最大化影響范圍。

3.3 算法復(fù)雜度

假設(shè)網(wǎng)絡(luò)

G

(

V

，

E

)包含

n

個(gè)節(jié)點(diǎn)。算法每選擇一個(gè)種子節(jié)點(diǎn)，需要更新其余所有節(jié)點(diǎn)的覆蓋范圍增益。更新一個(gè)節(jié)點(diǎn)覆蓋范圍增益的復(fù)雜度可近似為

O

(

d

)，其中

d

為節(jié)點(diǎn)平均度值。計(jì)算

n

個(gè)節(jié)點(diǎn)的覆蓋范圍增益的時(shí)間復(fù)雜度則為

O

(

dn

)。由此可見，選取

k

個(gè)種子節(jié)點(diǎn)的時(shí)間復(fù)雜度為

O

(

kdn

)。在選擇種子節(jié)點(diǎn)之前需要計(jì)算

n

個(gè)節(jié)點(diǎn)的約束系數(shù)，復(fù)雜度為

O

(

d

n

)。因此，NCSH 總的時(shí)間復(fù)雜度為

O

(

dn

(

k

+

d

))。

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab 1 Datasets for experiments

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

在社交網(wǎng)絡(luò)分析領(lǐng)域中，影響力最大化算法的評(píng)價(jià)指標(biāo)通常為：

1）影響范圍，即篩選并激活相同規(guī)模的種子節(jié)點(diǎn)集合。在相同的傳播模型下該集合最終激活的節(jié)點(diǎn)個(gè)數(shù)越多表示影響范圍越廣。本文是在獨(dú)立級(jí)聯(lián)傳播模型（Independent Cascade model，IC）下使用Monte-Carlo 模擬5 000 次傳播過(guò)程并求取平均值作為影響范圍。

2）運(yùn)行時(shí)間，即在相同條件下選擇同等規(guī)模的種子節(jié)點(diǎn)集合所花費(fèi)的時(shí)間

t

。

t

越小表明算法的效率越高。

本文選取以下幾個(gè)典型算法進(jìn)行對(duì)比分析：Degree，DegreeDiscount、pBmH、NCA、基于結(jié)構(gòu)洞和度折扣的最大化算法（maximization algorithm based on Structure Hole and DegreeDiscount，SHDD）。

圖4 展示了隨著種子節(jié)點(diǎn)數(shù)由5 增大到50，六種算法在六個(gè)真實(shí)數(shù)據(jù)集中的影響范圍變化情況。

圖4 不同算法在六個(gè)真實(shí)網(wǎng)絡(luò)中的影響范圍Fig.4 Influence spread of different algorithms on six real networks

1）在Butterfly 網(wǎng)絡(luò)中，NCSH 與NCA 表現(xiàn)最優(yōu)，Degree、SHDD 性能較差；

2）在Facebook 網(wǎng)絡(luò)中，由于該網(wǎng)絡(luò)為自我中心網(wǎng)絡(luò)，其中少量節(jié)點(diǎn)就能覆蓋到網(wǎng)絡(luò)的全部節(jié)點(diǎn)，因而在

k

=10 時(shí)，NCA 無(wú)法有效選取種子，pBmH 算法在該網(wǎng)絡(luò)中也表現(xiàn)較差，DegreeDiscount 算法、Degree 算法和SHDD 利用了節(jié)點(diǎn)的中心度屬性，因而具有較好表現(xiàn)，而NCSH 在覆蓋范圍屬性失效后，仍能根據(jù)結(jié)構(gòu)洞性質(zhì)有效選取影響力大的種子節(jié)點(diǎn)，最終達(dá)到較大的影響范圍；3）在Power 網(wǎng)絡(luò)中，NCSH 幾乎全程保持最大的影響范圍，在

k

為35 至50 時(shí)，其覆蓋范圍相較于NCA 仍有明顯優(yōu)勢(shì)，分別提高了2.7%、1.4%、1.9%、1.5%；4）在CaGrQc 網(wǎng)絡(luò)中，NCSH 除了在

k

=5 和

k

=15 時(shí)的影響范圍略低于pBmH 算法，在其他情況下的影響范圍均為最高，尤其在

k

=5、10、20 時(shí)，相較于NCA 分別有9.8%、6.8%、4%的提升，DegreeDiscount 算法和SHDD 表現(xiàn)一般，Degree 算法較差；5）在CaHepTh 網(wǎng)絡(luò)中，

k

=5 時(shí)，pBmH 算法具有最高的影響范圍，但隨著種子數(shù)量的增加，NCSH 的優(yōu)勢(shì)體現(xiàn)出來(lái)；在

k

=10 時(shí)，相較于NCA 有2.6%的提高。

由此可見，在種子數(shù)量較少時(shí)，NCSH 相較于NCA 提升較大。在NetHept 網(wǎng)絡(luò)中，NSCH 表現(xiàn)最優(yōu)，pBmH 與DegreeDiscount 算法性能一般。

圖5 展示了IC 模型下六種算法在六種不同網(wǎng)絡(luò)下影響范圍隨傳播概率增加的變化情況，針對(duì)不同網(wǎng)絡(luò)選擇適合它們的傳播概率范圍：1）Butterfly 與NetHept 網(wǎng)絡(luò)的傳播概率從0.03 增大到0.11，步長(zhǎng)為0.01；2）Facebook 網(wǎng)絡(luò)的傳播概率從0.006 增大到0.014，步長(zhǎng)為0.001；3）Power 網(wǎng)絡(luò)的傳播概率從0.21 增大到0.29，步長(zhǎng)為0.01；4）CaGrQc 與CaHepTh網(wǎng)絡(luò)的傳播概率從0.01 增大到0.09，步長(zhǎng)為0.01。從圖5中可以看出，NCSH 在多個(gè)網(wǎng)絡(luò)中能達(dá)到最大的影響范圍。

在Butterfly 網(wǎng)絡(luò)（圖5（a））中，NCSH 與NCA 表現(xiàn)最佳。由圖5（b）可以看出，在Facebook 網(wǎng)絡(luò)中，當(dāng)傳播概率較小時(shí)，各種算法的影響范圍相差不大，隨著傳播概率的增大，除了NCA 和pBmH 算法之外，其余算法均表現(xiàn)出較高的增長(zhǎng)趨勢(shì)，由于傳播概率較小，DegreeDiscount 算法的影響范圍在不同的傳播概率下具有良好的性能。在Power 網(wǎng)絡(luò)（圖5（c））中，NCSH 與NCA 相比，在各個(gè)不同的傳播概率情況下均有明顯提升，說(shuō)明NCSH 所選種子節(jié)點(diǎn)更為精確。該網(wǎng)絡(luò)中所有算法的影響范圍呈線性增長(zhǎng)，DegreeDiscount 算法、pBmH算法和SHDD 表現(xiàn)一般，Degree 算法仍較差。從圖5（d）可以看出在CaGrQc 網(wǎng)絡(luò)中，DegreeDiscount 算法在傳播概率較小時(shí)影響范圍較大，但隨著傳播概率的增加，其影響范圍的增長(zhǎng)幅度變小，說(shuō)明該算法適用于傳播概率較小的網(wǎng)絡(luò)，但當(dāng)傳播概率增大到接近0.1 時(shí)，應(yīng)考慮種子節(jié)點(diǎn)對(duì)二階鄰居的影響。類似的，SHDD 在后一階段也使用度折扣算法選擇種子節(jié)點(diǎn)，因而也受到影響。在CaHepTh 網(wǎng)絡(luò)（圖5（e））中，隨著傳播概率的增加，NCSH 的影響范圍具有最高的增長(zhǎng)率，隨著種子集的覆蓋范圍擴(kuò)大、傳播概率的提高，種子節(jié)點(diǎn)對(duì)鄰居的影響范圍也越大。從圖5（f）可以看出在NetHept 網(wǎng)絡(luò)中，NCSH 表現(xiàn)最佳，SHDD 表現(xiàn)較差。

圖5 不同算法在六個(gè)真實(shí)網(wǎng)絡(luò)中不同p值下的影響范圍Fig.5 Influence spread of different algorithms under different p values in six real-world networks

最后，圖6 展示了不同算法在CaHepTh 與NetHept 兩個(gè)較大網(wǎng)絡(luò)中的運(yùn)行時(shí)間，其余網(wǎng)絡(luò)上各算法運(yùn)行時(shí)間的大小關(guān)系與這兩個(gè)網(wǎng)絡(luò)類似。由圖6 可知，DegreeDiscount 算法和Degree 算法具有近乎毫秒級(jí)的運(yùn)行時(shí)間，NCA 在各個(gè)網(wǎng)絡(luò)中也具有較低的時(shí)間開銷。pBmH 需要計(jì)算所有節(jié)點(diǎn)兩跳范圍內(nèi)的加權(quán)概率和，因此需要的時(shí)間高于NCA。NCSH 和SHDD 由于都需要計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)的結(jié)構(gòu)洞指標(biāo)，因此時(shí)間開銷比前述幾個(gè)算法大。而由于NCSH 在不同結(jié)構(gòu)特征的真實(shí)網(wǎng)絡(luò)中均具有最高的影響范圍，且隨著種子節(jié)點(diǎn)規(guī)模和傳播概率的變化，本算法具有良好的穩(wěn)定性，因此增加的運(yùn)行時(shí)間在合理范圍之內(nèi)。此外，相較于同樣基于結(jié)構(gòu)洞的SHDD，NCSH 在時(shí)間上也具有一定優(yōu)勢(shì)。

圖6 不同算法在兩個(gè)真實(shí)網(wǎng)絡(luò)中的運(yùn)行時(shí)間Fig.6 Running time of different algorithms on two real networks

5 結(jié)語(yǔ)

社交網(wǎng)絡(luò)影響力最大化是社交網(wǎng)絡(luò)分析領(lǐng)域的重要問(wèn)題，本文從多屬性融合的角度提出了一種基于覆蓋范圍和結(jié)構(gòu)洞的影響力最大化算法NCSH。該算法以節(jié)點(diǎn)的覆蓋范圍和結(jié)構(gòu)洞性質(zhì)作為中心性指標(biāo)，兼顧節(jié)點(diǎn)的覆蓋鄰居數(shù)量和位置優(yōu)勢(shì)，有效解決了傳統(tǒng)基于拓?fù)浣Y(jié)構(gòu)的影響力最大化算法性能不穩(wěn)定的問(wèn)題。實(shí)驗(yàn)結(jié)果表明，NCSH 在不同數(shù)量的種子集中具有較高的影響范圍，在多個(gè)真實(shí)網(wǎng)絡(luò)中具有良好的穩(wěn)定性。