融合節點覆蓋范圍和結構洞的影響力最大化算法

楊 杰，張名揚，芮曉彬，王志曉

（中國礦業大學計算機科學與技術學院，江蘇徐州 221116）

0 引言

隨著在線社交網絡的飛速發展，越來越多的用戶喜歡在社交網絡上轉發時事新聞并分享自己的觀點，使得影響力傳播問題成為社交網絡分析領域中的研究熱點。影響力最大化問題是從網絡中選取部分節點，從而使得當這些節點在網絡中擴散消息時，最終能夠影響到的節點數量最大化。該問題作為病毒式營銷和在線廣告投放的重要依據，引起了學者們的廣泛關注。

影響力最大化問題最早由Domingos 等提出，旨在尋找

k

個初始種子節點，并使得最終的信息傳播范圍最廣。后來，國內外學者從不同角度提出了多種影響力最大化算法，這些算法可大致分為兩類：一類是基于蒙特卡洛模擬的貪心算法及其改進算法；另一類是基于網絡拓撲結構的啟發式算法。貪心算法能保證至少達到最優解63%的傳播范圍，但時間復雜度較高，不適用于大規模網絡。啟發式算法效率較高，但性能不穩定，受網絡結構影響較大。

在貪心算法方面，Kempe 等提出General Greedy 算法，該算法有著很高的精確度，但在每次選取種子節點時需要遍歷整個網絡并執行數千次的蒙特卡洛模擬過程，導致該算法效率較低。優化后的貪心算法CELF（Cost-Effective Lazy Forward selection）利用函數的子模性對運行效率進行了改進，運行效率比之前提高了約700 倍。之后，Chen 等又提出了New Greedy 算法和Mix Greedy 算法來優化貪心算法，然而，優化后的貪心算法運行時間仍然較高，很難應用到大規模網絡中。

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

本文從多屬性融合的角度提出一種基于覆蓋范圍和結構洞的影響力最大化算法（influence maximization algorithm based on Node Coverage and Structural Hole，NCSH），該算法融合節點的覆蓋范圍和結構洞性質對節點影響力進行全面評價，有效解決了傳統基于拓撲結構的啟發式算法性能不穩定的問題。實驗結果表明相較于其他算法，本文所提算法能夠獲得更大的節點影響范圍，并且，隨著網絡規模及結構的變化，本文算法表現出良好的穩定性。

1 節點覆蓋范圍計算

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

N

表示節點

i

的鄰居集合，則節點

i

和節點

j

的共同覆蓋范圍

N

∪為：

因此，種子節點集合

S

的覆蓋范圍

N

如式（2）所示：

節點覆蓋增益具有子模性，即將某節點添加至種子集合時所帶來的覆蓋增益不會大于將其添加至該種子集合的子集。節點

v

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

其中：

N

為節點

v

的鄰居集合；

N

為種子集合

S

的節點覆蓋范圍；

S

ˉ為網絡中不包含種子的節點集合。

由于大部分社交網絡傳播概率較低，所能影響到的節點集中在其一階鄰居，因而選取節點覆蓋的一階鄰居數量作為覆蓋范圍增益，忽略與現有種子集的重疊鄰居，著重考察非重疊鄰居數量，可有效避免“富人俱樂部”現象，進一步提高影響范圍。

2 節點結構洞特性評價

對于社交網絡中不直接相連的兩節點之間，若能通過某個中間節點實現間接連接，則將該中間節點稱之為具有結構洞性質的節點。結構洞性質能夠表示信息在網絡中完全擴散的必經之路，不同于介數中心性，它僅通過鄰域的拓撲關系便可計算得到，時間復雜度較低。結構洞節點能夠有效控制信息流向鄰居節點，從而具有更高的網絡覆蓋范圍收益。如圖1 所示，節點2 是三個社區之間的結構洞，若移除該節點，則信息無法在社區間相互傳輸。Lou 等發現Twitter上1%的結構洞節點決定著25%的信息流向，因此結構洞節點的加入可以擴大信息的擴散范圍。此外，結構洞特性對于社交網絡中的社區發現問題也具有重要意義。

圖1 節點結構洞特性Fig.1 Node structure hole characteristics

蘇曉萍等指出可以用網格約束系數來衡量網絡節點在形成結構洞時受到的約束：

其中：

CT

為節點

i

的約束系數；

τ

(

i

)為節點

i

的鄰居節點；節點

q

為節點

i

和節點

j

的共同鄰居；

p

表示節點

i

連接節點

j

付出精力的比重。

p

的計算公式如下：

其中：

圖2 約束系數計算Fig.2 Constraint coefficient calculating

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

3 本文算法

3.1 問題定義

影響力最大化問題是在給定社交網絡

G

(

V

，

E

)中選擇最具影響力的

k

個節點集合

S

（通常稱為種子節點），使其在一定的傳播模型下能影響到盡可能大的網絡范圍

σ

(

S

)。

3.2 算法描述

為解決IM 問題，本文所提NCSH，其基本思想為：首先，利用節點覆蓋范圍增益的中心性指標選擇覆蓋范圍增益最大的節點；然后，隨著所選種子節點數量的增加，每輪可能會出現多個覆蓋增益相同的候選種子節點；在這種情況下，從候選種子集中選擇約束系數最小的節點，確保具有最大的網絡傳播收益；最終重復此過程，直至選出

k

個種子節點。

算法1 基于覆蓋范圍和結構洞的影響力最大化算法（NCSH）。

輸入 網絡

G

(

V

，

E

)，種子節點數

k

。輸出 種子節點集合

S

。

圖3 為NCSH 的執行過程。首先，算法選擇度值最大的節點15 作為1 號種子，其覆蓋范圍在圖3（a）用橫線標出。接著，算法更新剩余節點的覆蓋范圍增益（圖3（b）），更新結果顯示節點5 的覆蓋范圍增益（豎線標出節點）最大，所以選擇節點5 作為2 號種子。

圖3 NCSH執行過程Fig.3 Execution process of NCSH

然后，算法再次更新剩余節點的覆蓋范圍增益，更新結果顯示節點22 和9 的覆蓋范圍增益同為最大，選擇它們均可擴大3 個節點的范圍（如圖3（c）所示的正方形網格節點）。此時，算法根據網格約束系數判斷22 號節點（約束系數為0.249 3）比9 號節點（約束系數為0.506 2）小，因此選擇22 號為3 號種子?？梢园l現，在本圖例中，與9 號節點相比，22 號節點具有較高的度值和較強的社區中心性，雖然它們的覆蓋增益均為3，但22 號節點還有額外6 次機會去影響15 號節點未激活的節點，從而能夠最大化影響范圍。

3.3 算法復雜度

假設網絡

G

(

V

，

E

)包含

n

個節點。算法每選擇一個種子節點，需要更新其余所有節點的覆蓋范圍增益。更新一個節點覆蓋范圍增益的復雜度可近似為

O

(

d

)，其中

d

為節點平均度值。計算

n

個節點的覆蓋范圍增益的時間復雜度則為

O

(

dn

)。由此可見，選取

k

個種子節點的時間復雜度為

O

(

kdn

)。在選擇種子節點之前需要計算

n

個節點的約束系數，復雜度為

O

(

d

n

)。因此，NCSH 總的時間復雜度為

O

(

dn

(

k

+

d

))。

4 實驗與結果分析

4.1 實驗設置

表1 實驗數據集Tab 1 Datasets for experiments

4.2 實驗結果與分析

在社交網絡分析領域中，影響力最大化算法的評價指標通常為：

1）影響范圍，即篩選并激活相同規模的種子節點集合。在相同的傳播模型下該集合最終激活的節點個數越多表示影響范圍越廣。本文是在獨立級聯傳播模型（Independent Cascade model，IC）下使用Monte-Carlo 模擬5 000 次傳播過程并求取平均值作為影響范圍。

2）運行時間，即在相同條件下選擇同等規模的種子節點集合所花費的時間

t

。

t

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

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

圖4 展示了隨著種子節點數由5 增大到50，六種算法在六個真實數據集中的影響范圍變化情況。

圖4 不同算法在六個真實網絡中的影響范圍Fig.4 Influence spread of different algorithms on six real networks

1）在Butterfly 網絡中，NCSH 與NCA 表現最優，Degree、SHDD 性能較差；

2）在Facebook 網絡中，由于該網絡為自我中心網絡，其中少量節點就能覆蓋到網絡的全部節點，因而在

k

=10 時，NCA 無法有效選取種子，pBmH 算法在該網絡中也表現較差，DegreeDiscount 算法、Degree 算法和SHDD 利用了節點的中心度屬性，因而具有較好表現，而NCSH 在覆蓋范圍屬性失效后，仍能根據結構洞性質有效選取影響力大的種子節點，最終達到較大的影響范圍；3）在Power 網絡中，NCSH 幾乎全程保持最大的影響范圍，在

k

為35 至50 時，其覆蓋范圍相較于NCA 仍有明顯優勢，分別提高了2.7%、1.4%、1.9%、1.5%；4）在CaGrQc 網絡中，NCSH 除了在

k

=5 和

k

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

k

=5、10、20 時，相較于NCA 分別有9.8%、6.8%、4%的提升，DegreeDiscount 算法和SHDD 表現一般，Degree 算法較差；5）在CaHepTh 網絡中，

k

=5 時，pBmH 算法具有最高的影響范圍，但隨著種子數量的增加，NCSH 的優勢體現出來；在

k

=10 時，相較于NCA 有2.6%的提高。

由此可見，在種子數量較少時，NCSH 相較于NCA 提升較大。在NetHept 網絡中，NSCH 表現最優，pBmH 與DegreeDiscount 算法性能一般。

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

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

圖5 不同算法在六個真實網絡中不同p值下的影響范圍Fig.5 Influence spread of different algorithms under different p values in six real-world networks

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

圖6 不同算法在兩個真實網絡中的運行時間Fig.6 Running time of different algorithms on two real networks

5 結語

社交網絡影響力最大化是社交網絡分析領域的重要問題，本文從多屬性融合的角度提出了一種基于覆蓋范圍和結構洞的影響力最大化算法NCSH。該算法以節點的覆蓋范圍和結構洞性質作為中心性指標，兼顧節點的覆蓋鄰居數量和位置優勢，有效解決了傳統基于拓撲結構的影響力最大化算法性能不穩定的問題。實驗結果表明，NCSH 在不同數量的種子集中具有較高的影響范圍，在多個真實網絡中具有良好的穩定性。