復雜網(wǎng)絡影響力極大化快速評估算法

王瀟杰，趙城利，張 雪，易東云,2

(1. 國防科技大學 文理學院， 湖南 長沙 410073；2. 國防科技大學 高性能計算國家重點實驗室， 湖南 長沙 410073)

研究網(wǎng)絡科學的主要目的之一是解決復雜網(wǎng)絡上的動力學問題，對于網(wǎng)絡上動力學特性的研究一直是網(wǎng)絡科學研究領域的重點與難點。特別地，對于網(wǎng)絡傳播動力學的研究更是具有極為重要的現(xiàn)實意義。傳播現(xiàn)象在現(xiàn)實生活中無處不在，例如謠言在社交媒體上的傳播[1]，傳染病在人群中的傳播[2]，以及電力網(wǎng)絡的級聯(lián)故障[3]等。對于傳播動力學的研究可以揭示復雜網(wǎng)絡中的傳播機理以及動力學行為，從而提供對這些行為的切實可行的控制方法，創(chuàng)造巨大的經(jīng)濟價值和社會價值。在現(xiàn)實生活中，人們經(jīng)常面臨的一個實際問題就是高效地尋找少部分具有重要影響力的初始傳播者。例如，對于一個新產(chǎn)品的市場營銷而言，選取少量的種子用戶作為產(chǎn)品推廣人，利用口碑營銷的方式迅速打開市場、提高產(chǎn)品知名度，是十分重要的。在網(wǎng)絡科學的領域中，這種通過選取少量節(jié)點作為初始節(jié)點，以極大化這些節(jié)點在整個網(wǎng)絡中的傳播影響力的問題，稱為影響力極大化問題[4]。

關于影響力極大化問題的研究可以追溯到Domingos等的工作[5]，他們第一次研究了如何將影響力極大化問題表述為一個算法問題，并提出了一種基于概率的算法用于近似求解。此后，Kempe等[6]利用社會網(wǎng)絡分析的方法系統(tǒng)地研究了這個問題，他們發(fā)現(xiàn)，網(wǎng)絡中的影響力極大化問題的實質(zhì)是NP-hard的組合優(yōu)化問題，其精確求解非常困難。進一步地，他們給出了一個基于貪婪思想的算法以近似求解影響力極大化問題，并證明了該算法的精確度下界。然而，由于該算法十分耗時，往往只能應用在不大的網(wǎng)絡上進行求解?；陬愃频呢澙匪枷耄琇eskovec等[7]通過對影響力極大化問題的子模塊性質(zhì)進行研究，提出了高效貪婪選擇(Cost-Effective Lazy Forward selection， CELF)算法，提高了Kempe算法的效率。在CELF算法的基礎上，Goyal等[8]對于算法步驟進一步優(yōu)化，提出CELF++算法，極大提高了CELF算法的效率。

雖然基于貪婪思想的算法大多可以取得較為滿意的結果，較高的算法復雜度往往成了限制它們應用的一個關鍵因素。因此，越來越多的學者開始嘗試提出啟發(fā)式算法來近似求解影響力極大化問題。Narayanam等[9]另辟蹊徑，通過引入博弈論中的Shapely值的概念，提出了基于Shapely值的重要節(jié)點選擇(ShaPley value based Influential Nodes，SPIN)算法。Zhao等[10]受到地圖著色問題的啟發(fā)，提出了一種基于著色的算法。Zhang等[11]提出了基于迭代的投票排名算法，可以有效地識別一組影響力較大的離散節(jié)點。通過分析節(jié)點的相對關系，Chen等[12]提出了折扣度算法，很好地平衡了算法的計算效率和精確度，取得了不弱于貪婪算法的結果，已成為現(xiàn)在影響力極大化問題的標準算法之一。Lü等[13]分析了度中心、H指數(shù)以及核數(shù)的關系，驗證了H指數(shù)在描述節(jié)點重要性的良好表現(xiàn)。近年來，Morone等[14]研究了網(wǎng)絡中的級聯(lián)失效問題，提出了基于最優(yōu)滲流理論的集群影響算法，可以有效識別級聯(lián)失效問題中的重要節(jié)點。

通常而言，大多數(shù)啟發(fā)式算法往往通過某種重要性指標來間接反映節(jié)點的影響力。本文結合網(wǎng)絡上具體的傳播動力學分析，提出快速評估算法，通過期望計算的方式直接估計節(jié)點的傳播影響力，并進一步運用序列采樣的策略進行種子集的快速選擇，在保證算法效率的基礎上極大提高了算法的精度。

1 影響力極大化問題分析

沿用圖論中的相關記號，網(wǎng)絡可以用圖G(V,E)來表示[15]，其中節(jié)點V代表網(wǎng)絡中的個體，邊E代表個體之間的聯(lián)系。例如對一個在線社交網(wǎng)絡而言，用戶就是網(wǎng)絡中的節(jié)點，用戶之間的好友關系自然而然地構成了網(wǎng)絡中的邊。

在一個網(wǎng)絡中，影響力極大化問題可以描述為：如何尋找網(wǎng)絡中的L個節(jié)點S?V作為種子節(jié)點(即信息的初始傳播者)，將信息傳播到網(wǎng)絡中盡可能大的范圍。

對于影響力極大化問題，一個直觀的想法是，如果可以對節(jié)點在網(wǎng)絡中的重要性進行排序，依次選取排名靠前的節(jié)點，它們在整個網(wǎng)絡中的集群影響力自然會大。例如，可以利用網(wǎng)絡中的各種中心性指標[15]對節(jié)點進行排序，依次選取排序中靠前的部分節(jié)點作為種子節(jié)點來極大化它們在整個網(wǎng)絡中的影響力。事實上，這種選取方式存在一個嚴重的問題——由于節(jié)點在網(wǎng)絡中的影響力存在著相互重疊的區(qū)域，節(jié)點間的相對位置必然會對它們的集群影響力造成重要的影響，這也是影響力極大化問題的難點所在。

通常而言，針對網(wǎng)絡上不同的信息傳播方式，最優(yōu)的初始傳播者會有所不同，很難找到一種統(tǒng)一的算法適用于所有傳播動力學下的影響力極大化問題。在下面的分析中，將主要討論一種簡單的信息傳遞模型。假定網(wǎng)絡中所有的節(jié)點都可能具有兩種狀態(tài)，即接收態(tài)與未接收態(tài)。處于未接收態(tài)的節(jié)點，代表網(wǎng)絡中還沒有接收到信息的普通個體；而處于接收態(tài)的節(jié)點，則代表那些接收到信息的個體，它們會以概率p向周圍鄰居廣播消息，進而將消息擴散到整個網(wǎng)絡中。

2 影響力極大化快速評估模型

當r=1時，對于所有的普通節(jié)點v∈V-S，它們會受到周圍種子節(jié)點的影響而轉化為接收態(tài)，其概率為：

(1)

式中：p為信息傳遞概率；Γv為節(jié)點v的鄰居，tv=|Γv∩S|為節(jié)點v的種子節(jié)點鄰居數(shù)量。

當r≥2時，信息傳遞由所有處于接收態(tài)的節(jié)點進行，這包含兩部分節(jié)點：初始時刻的種子節(jié)點，以及在之前時刻轉化為接收態(tài)的普通節(jié)點。因此，對于一個非種子節(jié)點v∈V-S，它在第r輪信息傳遞時處于接收態(tài)的概率為：

(2)

(3)

綜合上述分析，當種子節(jié)點集為S時，在第r輪信息傳遞中，網(wǎng)絡中的某節(jié)點v處于信息接收態(tài)的概率為：

(4)

(5)

(a) 冪指數(shù)為2.1時近似誤差圖(a) Errors of the approximations when γ=2.1

(b) 冪指數(shù)為3.0時的近似誤差(b) Errors of the approximations when γ=3.0圖1 不同冪指數(shù)時的近似誤差圖Fig.1 Errors of the approximations with different γ

圖1顯示了不同冪指數(shù)時的近似估計與真實傳播范圍的誤差。仿真網(wǎng)絡的規(guī)模均為10 000個節(jié)點，平均度分別為3，6，9，初始傳播者為隨機選取的100個節(jié)點，傳播概率為p=1.1pc，其中pc為疾病閾值。圖1中的線代表真實傳播范圍，符號代表近似估計結果。從圖1中可以看出，在傳播的早期，近似估計結果與真實傳播范圍符合得很好，隨著傳播過程的進行，二者的差距逐漸增大，這種趨勢在平均度較小的稀疏網(wǎng)絡中表現(xiàn)得更為明顯。由于影響力極大化問題通常關注的是網(wǎng)絡上的早期傳播行為，本估計基本可以滿足精度方面的需求。

通過式(5)，可以快速計算種子節(jié)點集S在整個網(wǎng)絡中的集群影響力，特別地，可以用來評估將一個新的節(jié)點v加入種子節(jié)點集所帶來的集群影響力增量。

(6)

而對于與節(jié)點v不相鄰的節(jié)點u?Γv-S，它們轉化為接收態(tài)的概率不會發(fā)生變化。

=1+(dv-2tv)p

(7)

當r=2時，由式(3)可知，節(jié)點u?S轉化為接收態(tài)的概率為：

通過近似和簡化，可以得到

由上述可知，該近似過程僅需用到節(jié)點u自身的種子節(jié)點鄰居數(shù)量以及鄰居節(jié)點的種子節(jié)點鄰居數(shù)量。

=2(dv-tv)p

(8)

由此提出一種啟發(fā)式算法，用以近似求解網(wǎng)絡中的影響力極大化問題。算法采用序列采樣的方式，按照種子集擴展的方式，每次從所有候選節(jié)點中選取一個對種子節(jié)點集影響力增量最大的節(jié)點加入種子集，直到足夠數(shù)量的種子節(jié)點被選出，構成影響力極大化問題中的初始傳播者。假定信息傳遞概率為p，傳遞輪數(shù)為r，種子節(jié)點數(shù)目為L，如算法1所示。

算法1 影響力極大化快速評估算法

在傳統(tǒng)的基于貪婪思想的影響力極大化算法中，需要通過大量的隨機仿真來計算種子節(jié)點的集群影響力，這導致算法復雜度激增，即便只是在一個中等規(guī)模的網(wǎng)絡中尋找極少數(shù)量的種子節(jié)點也需要花費非常長的時間，難以用來求解現(xiàn)代大規(guī)模商業(yè)和社交網(wǎng)絡上的影響力極大化問題。與傳統(tǒng)算法不同，本算法運用近似估計的方式，可以直接計算候選節(jié)點的集群影響力增量，加快了影響力極大化問題的求解速度。通常而言，傳播輪數(shù)越多，快速評估算法的計算復雜度就越高，為了兼顧算法的效率和精度，在后面的實驗中，固定參數(shù)r=2。

3 算例分析

3.1 傳播模型

當選出種子節(jié)點之后，需要通過傳播模型來度量這些節(jié)點在網(wǎng)絡上的傳播能力，這里考慮一個更為符合現(xiàn)實中消息傳播模式的易感-感染-恢復(Susceptible-Infected-Recovered, SIR)模型[16]。該模型最早被用來研究傳染病在人群中的傳播行為，在該模型中，每個節(jié)點可以處于三個狀態(tài)：易感態(tài)S、感染態(tài)I以及恢復態(tài)R。易感節(jié)點指的是那些尚未被感染的個體，可能以概率p被周圍處于感染態(tài)的個體感染。對于感染節(jié)點，它們代表那些感染了疾病的個體，在下一個時間片上，以概率q康復，即轉為恢復節(jié)點。

在經(jīng)典的SIR模型中，每個感染節(jié)點可以同時嘗試感染所有的易感鄰居。然而，在現(xiàn)實生活中，一個更加常見的現(xiàn)象是一個處于感染狀態(tài)的節(jié)點僅僅可以嘗試感染一個處于易感狀態(tài)的鄰居(例如握手行為)。因此，這里使用有限感染的SIR模型[17]進行仿真。在初始時刻，種子節(jié)點被標記為感染狀態(tài)，其他節(jié)點均為易感狀態(tài)，此后，在每一個時刻，每個感染者以概率p隨機選取一個鄰居節(jié)點進行感染，然后以概率q恢復。定義有效傳播率為感染概率與恢復概率的比值。當網(wǎng)絡中沒有感染者時，整個傳播過程結束，最終感染的節(jié)點越多，說明種子節(jié)點的影響力越大。

3.2 數(shù)據(jù)描述

為了驗證快速評估算法在影響力極大化問題中的表現(xiàn)，選取6個不同類型的真實網(wǎng)絡進行驗證，分別為：郵件網(wǎng)絡[18]——反映了Enron公司內(nèi)部近50萬封郵件的收發(fā)關系；合作網(wǎng)絡[19]——隸屬于計算機科學的科學家合作網(wǎng)絡；購物網(wǎng)絡[19]——一個共同購買網(wǎng)絡，來自購物網(wǎng)站Amazon上的共同購買信息；分享網(wǎng)絡[20]——文件分享網(wǎng)站Gnutella上的p2p網(wǎng)絡；信任網(wǎng)絡[21]——一個在線評價網(wǎng)站Epinions上的用戶信任網(wǎng)絡；社交網(wǎng)絡[22]——在線社交網(wǎng)站Twitter上的用戶間好友關系網(wǎng)絡。上述網(wǎng)絡的簡要介紹見表1。

表1 六個真實網(wǎng)絡數(shù)據(jù)基本性質(zhì)表

3.3 度量準則

選取以下3個度量準則衡量算法的優(yōu)劣性：種子節(jié)點傳播范圍，種子節(jié)點間的平均距離，以及冗余覆蓋率。

傳播范圍是度量種子節(jié)點傳播能力最直觀的度量，定義種子節(jié)點S的傳播范圍FS為這些節(jié)點所能感染的節(jié)點數(shù)目。由于傳播具有一定的隨機性，需要通過多次數(shù)值仿真計算感染節(jié)點數(shù)目的均值。

集合內(nèi)部節(jié)點間的平均距離可以從側面反映這個集合的結構特性，定義種子節(jié)點間的平均距離為：

式中：|S|代表種子節(jié)點數(shù)目；dist(u,v)代表節(jié)點u到節(jié)點v的距離，即從u到v的最短路徑跳數(shù)。

為了衡量種子節(jié)點傳播范圍的重疊程度，定義種子節(jié)點的冗余覆蓋率為：

式中，F(xiàn)S為以S作為初始傳播者時所能達到的傳播范圍，F(xiàn){v}為僅以節(jié)點v作為初始傳播者的傳播范圍。

3.4 實驗結果

在實驗中，設定恢復率q=1/k，感染率p=1.5q，其中k為網(wǎng)絡的平均度。不同種子節(jié)點比例時的影響力傳播范圍如圖2所示。從圖2可以看出，快速評估算法的表現(xiàn)一致優(yōu)于其他三種基準算法，并且隨著種子節(jié)點數(shù)目的增加，快速評估算法的優(yōu)勢越來越明顯。在6個不同類型的網(wǎng)絡中，由快速評估算法選出的種子節(jié)點都具有更強的傳播能力，體現(xiàn)了該算法的廣泛適用性。

種子節(jié)點間的平均距離隨著種子節(jié)點數(shù)量的變化如圖3所示。由圖3可知，種子節(jié)點間的相對距離越近，它們的傳播范圍相互重疊得越明顯，會造成嚴重冗余，這對于信息傳播是不利的。因此，一個好的算法找出的種子節(jié)點應當相互分散，即種子節(jié)點間的平均距離較高。在該指標下，快速評估算法依舊可以取得較為滿意的結果，尤其是在郵件網(wǎng)絡、信任網(wǎng)絡、社交網(wǎng)絡中，快速評估算法明顯優(yōu)于其他基準算法。在分享網(wǎng)絡中，度中心找到的種子節(jié)點間的平均距離隨著種子節(jié)點數(shù)目的增加呈現(xiàn)先減后增的趨勢。事實上，這個結果并不反常，種子節(jié)點平均距離與種子節(jié)點數(shù)目之間并沒有確定性的關系，而是與網(wǎng)絡結構以及具體算法有關。分享網(wǎng)絡是一個高度中心化的網(wǎng)絡，由少數(shù)緊密相連的中心節(jié)點與大量邊緣節(jié)點構成，呈現(xiàn)出一種明顯的中心-邊緣趨勢。度中心算法會將網(wǎng)絡的中心節(jié)點作為種子節(jié)點，由于中心節(jié)點是緊密相連的，因此隨著節(jié)點數(shù)目的增加，種子節(jié)點間的平均距離會減少；當中心節(jié)點全部找出之后，度中心算法才會加入邊緣節(jié)點，導致種子節(jié)點平均距離的逐漸增加。

(a) 郵件網(wǎng)絡(a) E-mail network (b) 合作網(wǎng)絡(b) Collaboration network

(c) 購物網(wǎng)絡(c) Shopping network (d) 分享網(wǎng)絡(d) Sharing network

(e) 信任網(wǎng)絡(e) Trust network (f) 社交網(wǎng)絡(f) Social network圖2 不同種子節(jié)點比例時的影響力傳播范圍Fig.2 Spreading scope with different fractions of seed nodes

(a) 郵件網(wǎng)絡(a) E-mail network (b) 合作網(wǎng)絡(b) Collaboration network

(c) 購物網(wǎng)絡(c) Shopping network (d) 分享網(wǎng)絡(d) Sharing network

(e) 信任網(wǎng)絡(e) Trust network (f) 社交網(wǎng)絡(f) Social network圖3 不同種子節(jié)點比例時的種子節(jié)點平均距離Fig.3 Average distance among seed nodes with different fractions of them

種子節(jié)點冗余覆蓋率是衡量種子節(jié)點傳播重疊程度的直觀指標，冗余覆蓋率越大，說明種子節(jié)點相互間的傳播范圍重疊程度越大，它們構成集群時的影響力損耗也越多。各算法在不同網(wǎng)絡上的種子節(jié)點冗余覆蓋率結果見表2，除了在分享網(wǎng)絡上快速評估算法的表現(xiàn)略差于投票排名以外，在其他網(wǎng)絡中該算法均能得到最優(yōu)的結果。

表2 種子節(jié)點冗余覆蓋率

4 結論

本文實現(xiàn)基于種子集擴展的影響力極大化快速評估算法。在6個真實網(wǎng)絡數(shù)據(jù)集上進行實證分析，驗證了快速評估算法的有效性。而且快速評估算法具有很好的可拓展性。例如，對于節(jié)點傳播能力異質(zhì)的情況，可以將式(3)中的傳播概率p替換為節(jié)點傳播概率pu；當所考慮的網(wǎng)絡為時序網(wǎng)絡時[23-24]，也可以將式(3)中的鄰居集Γv替換為不同時間片r時的鄰居集Γv(r)。仿照本算法中的推導過程，可以得到前述情況下的快速評估算法。在下一步的工作中，將對算法進行進一步優(yōu)化，從圖1中可以看出，算法對于傳播范圍的估計精度偏低，還有較大的改進空間。