王瀟杰,趙城利,張 雪,易東云,2
(1. 國防科技大學(xué) 文理學(xué)院, 湖南 長沙 410073;2. 國防科技大學(xué) 高性能計(jì)算國家重點(diǎn)實(shí)驗(yàn)室, 湖南 長沙 410073)
研究網(wǎng)絡(luò)科學(xué)的主要目的之一是解決復(fù)雜網(wǎng)絡(luò)上的動(dòng)力學(xué)問題,對(duì)于網(wǎng)絡(luò)上動(dòng)力學(xué)特性的研究一直是網(wǎng)絡(luò)科學(xué)研究領(lǐng)域的重點(diǎn)與難點(diǎn)。特別地,對(duì)于網(wǎng)絡(luò)傳播動(dòng)力學(xué)的研究更是具有極為重要的現(xiàn)實(shí)意義。傳播現(xiàn)象在現(xiàn)實(shí)生活中無處不在,例如謠言在社交媒體上的傳播[1],傳染病在人群中的傳播[2],以及電力網(wǎng)絡(luò)的級(jí)聯(lián)故障[3]等。對(duì)于傳播動(dòng)力學(xué)的研究可以揭示復(fù)雜網(wǎng)絡(luò)中的傳播機(jī)理以及動(dòng)力學(xué)行為,從而提供對(duì)這些行為的切實(shí)可行的控制方法,創(chuàng)造巨大的經(jīng)濟(jì)價(jià)值和社會(huì)價(jià)值。在現(xiàn)實(shí)生活中,人們經(jīng)常面臨的一個(gè)實(shí)際問題就是高效地尋找少部分具有重要影響力的初始傳播者。例如,對(duì)于一個(gè)新產(chǎn)品的市場營銷而言,選取少量的種子用戶作為產(chǎn)品推廣人,利用口碑營銷的方式迅速打開市場、提高產(chǎn)品知名度,是十分重要的。在網(wǎng)絡(luò)科學(xué)的領(lǐng)域中,這種通過選取少量節(jié)點(diǎn)作為初始節(jié)點(diǎn),以極大化這些節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的傳播影響力的問題,稱為影響力極大化問題[4]。
關(guān)于影響力極大化問題的研究可以追溯到Domingos等的工作[5],他們第一次研究了如何將影響力極大化問題表述為一個(gè)算法問題,并提出了一種基于概率的算法用于近似求解。此后,Kempe等[6]利用社會(huì)網(wǎng)絡(luò)分析的方法系統(tǒng)地研究了這個(gè)問題,他們發(fā)現(xiàn),網(wǎng)絡(luò)中的影響力極大化問題的實(shí)質(zhì)是NP-hard的組合優(yōu)化問題,其精確求解非常困難。進(jìn)一步地,他們給出了一個(gè)基于貪婪思想的算法以近似求解影響力極大化問題,并證明了該算法的精確度下界。然而,由于該算法十分耗時(shí),往往只能應(yīng)用在不大的網(wǎng)絡(luò)上進(jìn)行求解?;陬愃频呢澙匪枷耄琇eskovec等[7]通過對(duì)影響力極大化問題的子模塊性質(zhì)進(jìn)行研究,提出了高效貪婪選擇(Cost-Effective Lazy Forward selection, CELF)算法,提高了Kempe算法的效率。在CELF算法的基礎(chǔ)上,Goyal等[8]對(duì)于算法步驟進(jìn)一步優(yōu)化,提出CELF++算法,極大提高了CELF算法的效率。
雖然基于貪婪思想的算法大多可以取得較為滿意的結(jié)果,較高的算法復(fù)雜度往往成了限制它們應(yīng)用的一個(gè)關(guān)鍵因素。因此,越來越多的學(xué)者開始嘗試提出啟發(fā)式算法來近似求解影響力極大化問題。Narayanam等[9]另辟蹊徑,通過引入博弈論中的Shapely值的概念,提出了基于Shapely值的重要節(jié)點(diǎn)選擇(ShaPley value based Influential Nodes,SPIN)算法。Zhao等[10]受到地圖著色問題的啟發(fā),提出了一種基于著色的算法。Zhang等[11]提出了基于迭代的投票排名算法,可以有效地識(shí)別一組影響力較大的離散節(jié)點(diǎn)。通過分析節(jié)點(diǎn)的相對(duì)關(guān)系,Chen等[12]提出了折扣度算法,很好地平衡了算法的計(jì)算效率和精確度,取得了不弱于貪婪算法的結(jié)果,已成為現(xiàn)在影響力極大化問題的標(biāo)準(zhǔn)算法之一。Lü等[13]分析了度中心、H指數(shù)以及核數(shù)的關(guān)系,驗(yàn)證了H指數(shù)在描述節(jié)點(diǎn)重要性的良好表現(xiàn)。近年來,Morone等[14]研究了網(wǎng)絡(luò)中的級(jí)聯(lián)失效問題,提出了基于最優(yōu)滲流理論的集群影響算法,可以有效識(shí)別級(jí)聯(lián)失效問題中的重要節(jié)點(diǎn)。
通常而言,大多數(shù)啟發(fā)式算法往往通過某種重要性指標(biāo)來間接反映節(jié)點(diǎn)的影響力。本文結(jié)合網(wǎng)絡(luò)上具體的傳播動(dòng)力學(xué)分析,提出快速評(píng)估算法,通過期望計(jì)算的方式直接估計(jì)節(jié)點(diǎn)的傳播影響力,并進(jìn)一步運(yùn)用序列采樣的策略進(jìn)行種子集的快速選擇,在保證算法效率的基礎(chǔ)上極大提高了算法的精度。
沿用圖論中的相關(guān)記號(hào),網(wǎng)絡(luò)可以用圖G(V,E)來表示[15],其中節(jié)點(diǎn)V代表網(wǎng)絡(luò)中的個(gè)體,邊E代表個(gè)體之間的聯(lián)系。例如對(duì)一個(gè)在線社交網(wǎng)絡(luò)而言,用戶就是網(wǎng)絡(luò)中的節(jié)點(diǎn),用戶之間的好友關(guān)系自然而然地構(gòu)成了網(wǎng)絡(luò)中的邊。
在一個(gè)網(wǎng)絡(luò)中,影響力極大化問題可以描述為:如何尋找網(wǎng)絡(luò)中的L個(gè)節(jié)點(diǎn)S?V作為種子節(jié)點(diǎn)(即信息的初始傳播者),將信息傳播到網(wǎng)絡(luò)中盡可能大的范圍。
對(duì)于影響力極大化問題,一個(gè)直觀的想法是,如果可以對(duì)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性進(jìn)行排序,依次選取排名靠前的節(jié)點(diǎn),它們?cè)谡麄€(gè)網(wǎng)絡(luò)中的集群影響力自然會(huì)大。例如,可以利用網(wǎng)絡(luò)中的各種中心性指標(biāo)[15]對(duì)節(jié)點(diǎn)進(jìn)行排序,依次選取排序中靠前的部分節(jié)點(diǎn)作為種子節(jié)點(diǎn)來極大化它們?cè)谡麄€(gè)網(wǎng)絡(luò)中的影響力。事實(shí)上,這種選取方式存在一個(gè)嚴(yán)重的問題——由于節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力存在著相互重疊的區(qū)域,節(jié)點(diǎn)間的相對(duì)位置必然會(huì)對(duì)它們的集群影響力造成重要的影響,這也是影響力極大化問題的難點(diǎn)所在。
通常而言,針對(duì)網(wǎng)絡(luò)上不同的信息傳播方式,最優(yōu)的初始傳播者會(huì)有所不同,很難找到一種統(tǒng)一的算法適用于所有傳播動(dòng)力學(xué)下的影響力極大化問題。在下面的分析中,將主要討論一種簡單的信息傳遞模型。假定網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都可能具有兩種狀態(tài),即接收態(tài)與未接收態(tài)。處于未接收態(tài)的節(jié)點(diǎn),代表網(wǎng)絡(luò)中還沒有接收到信息的普通個(gè)體;而處于接收態(tài)的節(jié)點(diǎn),則代表那些接收到信息的個(gè)體,它們會(huì)以概率p向周圍鄰居廣播消息,進(jìn)而將消息擴(kuò)散到整個(gè)網(wǎng)絡(luò)中。
當(dāng)r=1時(shí),對(duì)于所有的普通節(jié)點(diǎn)v∈V-S,它們會(huì)受到周圍種子節(jié)點(diǎn)的影響而轉(zhuǎn)化為接收態(tài),其概率為:
(1)
式中:p為信息傳遞概率;Γv為節(jié)點(diǎn)v的鄰居,tv=|Γv∩S|為節(jié)點(diǎn)v的種子節(jié)點(diǎn)鄰居數(shù)量。
當(dāng)r≥2時(shí),信息傳遞由所有處于接收態(tài)的節(jié)點(diǎn)進(jìn)行,這包含兩部分節(jié)點(diǎn):初始時(shí)刻的種子節(jié)點(diǎn),以及在之前時(shí)刻轉(zhuǎn)化為接收態(tài)的普通節(jié)點(diǎn)。因此,對(duì)于一個(gè)非種子節(jié)點(diǎn)v∈V-S,它在第r輪信息傳遞時(shí)處于接收態(tài)的概率為:
(2)
(3)
綜合上述分析,當(dāng)種子節(jié)點(diǎn)集為S時(shí),在第r輪信息傳遞中,網(wǎng)絡(luò)中的某節(jié)點(diǎn)v處于信息接收態(tài)的概率為:
(4)
(5)
(a) 冪指數(shù)為2.1時(shí)近似誤差圖(a) Errors of the approximations when γ=2.1
(b) 冪指數(shù)為3.0時(shí)的近似誤差(b) Errors of the approximations when γ=3.0圖1 不同冪指數(shù)時(shí)的近似誤差圖Fig.1 Errors of the approximations with different γ
圖1顯示了不同冪指數(shù)時(shí)的近似估計(jì)與真實(shí)傳播范圍的誤差。仿真網(wǎng)絡(luò)的規(guī)模均為10 000個(gè)節(jié)點(diǎn),平均度分別為3,6,9,初始傳播者為隨機(jī)選取的100個(gè)節(jié)點(diǎn),傳播概率為p=1.1pc,其中pc為疾病閾值。圖1中的線代表真實(shí)傳播范圍,符號(hào)代表近似估計(jì)結(jié)果。從圖1中可以看出,在傳播的早期,近似估計(jì)結(jié)果與真實(shí)傳播范圍符合得很好,隨著傳播過程的進(jìn)行,二者的差距逐漸增大,這種趨勢(shì)在平均度較小的稀疏網(wǎng)絡(luò)中表現(xiàn)得更為明顯。由于影響力極大化問題通常關(guān)注的是網(wǎng)絡(luò)上的早期傳播行為,本估計(jì)基本可以滿足精度方面的需求。
通過式(5),可以快速計(jì)算種子節(jié)點(diǎn)集S在整個(gè)網(wǎng)絡(luò)中的集群影響力,特別地,可以用來評(píng)估將一個(gè)新的節(jié)點(diǎn)v加入種子節(jié)點(diǎn)集所帶來的集群影響力增量。
(6)
而對(duì)于與節(jié)點(diǎn)v不相鄰的節(jié)點(diǎn)u?Γv-S,它們轉(zhuǎn)化為接收態(tài)的概率不會(huì)發(fā)生變化。
=1+(dv-2tv)p
(7)
當(dāng)r=2時(shí),由式(3)可知,節(jié)點(diǎn)u?S轉(zhuǎn)化為接收態(tài)的概率為:
通過近似和簡化,可以得到
由上述可知,該近似過程僅需用到節(jié)點(diǎn)u自身的種子節(jié)點(diǎn)鄰居數(shù)量以及鄰居節(jié)點(diǎn)的種子節(jié)點(diǎn)鄰居數(shù)量。
=2(dv-tv)p
(8)
由此提出一種啟發(fā)式算法,用以近似求解網(wǎng)絡(luò)中的影響力極大化問題。算法采用序列采樣的方式,按照種子集擴(kuò)展的方式,每次從所有候選節(jié)點(diǎn)中選取一個(gè)對(duì)種子節(jié)點(diǎn)集影響力增量最大的節(jié)點(diǎn)加入種子集,直到足夠數(shù)量的種子節(jié)點(diǎn)被選出,構(gòu)成影響力極大化問題中的初始傳播者。假定信息傳遞概率為p,傳遞輪數(shù)為r,種子節(jié)點(diǎn)數(shù)目為L,如算法1所示。
算法1 影響力極大化快速評(píng)估算法
在傳統(tǒng)的基于貪婪思想的影響力極大化算法中,需要通過大量的隨機(jī)仿真來計(jì)算種子節(jié)點(diǎn)的集群影響力,這導(dǎo)致算法復(fù)雜度激增,即便只是在一個(gè)中等規(guī)模的網(wǎng)絡(luò)中尋找極少數(shù)量的種子節(jié)點(diǎn)也需要花費(fèi)非常長的時(shí)間,難以用來求解現(xiàn)代大規(guī)模商業(yè)和社交網(wǎng)絡(luò)上的影響力極大化問題。與傳統(tǒng)算法不同,本算法運(yùn)用近似估計(jì)的方式,可以直接計(jì)算候選節(jié)點(diǎn)的集群影響力增量,加快了影響力極大化問題的求解速度。通常而言,傳播輪數(shù)越多,快速評(píng)估算法的計(jì)算復(fù)雜度就越高,為了兼顧算法的效率和精度,在后面的實(shí)驗(yàn)中,固定參數(shù)r=2。
當(dāng)選出種子節(jié)點(diǎn)之后,需要通過傳播模型來度量這些節(jié)點(diǎn)在網(wǎng)絡(luò)上的傳播能力,這里考慮一個(gè)更為符合現(xiàn)實(shí)中消息傳播模式的易感-感染-恢復(fù)(Susceptible-Infected-Recovered, SIR)模型[16]。該模型最早被用來研究傳染病在人群中的傳播行為,在該模型中,每個(gè)節(jié)點(diǎn)可以處于三個(gè)狀態(tài):易感態(tài)S、感染態(tài)I以及恢復(fù)態(tài)R。易感節(jié)點(diǎn)指的是那些尚未被感染的個(gè)體,可能以概率p被周圍處于感染態(tài)的個(gè)體感染。對(duì)于感染節(jié)點(diǎn),它們代表那些感染了疾病的個(gè)體,在下一個(gè)時(shí)間片上,以概率q康復(fù),即轉(zhuǎn)為恢復(fù)節(jié)點(diǎn)。
在經(jīng)典的SIR模型中,每個(gè)感染節(jié)點(diǎn)可以同時(shí)嘗試感染所有的易感鄰居。然而,在現(xiàn)實(shí)生活中,一個(gè)更加常見的現(xiàn)象是一個(gè)處于感染狀態(tài)的節(jié)點(diǎn)僅僅可以嘗試感染一個(gè)處于易感狀態(tài)的鄰居(例如握手行為)。因此,這里使用有限感染的SIR模型[17]進(jìn)行仿真。在初始時(shí)刻,種子節(jié)點(diǎn)被標(biāo)記為感染狀態(tài),其他節(jié)點(diǎn)均為易感狀態(tài),此后,在每一個(gè)時(shí)刻,每個(gè)感染者以概率p隨機(jī)選取一個(gè)鄰居節(jié)點(diǎn)進(jìn)行感染,然后以概率q恢復(fù)。定義有效傳播率為感染概率與恢復(fù)概率的比值。當(dāng)網(wǎng)絡(luò)中沒有感染者時(shí),整個(gè)傳播過程結(jié)束,最終感染的節(jié)點(diǎn)越多,說明種子節(jié)點(diǎn)的影響力越大。
為了驗(yàn)證快速評(píng)估算法在影響力極大化問題中的表現(xiàn),選取6個(gè)不同類型的真實(shí)網(wǎng)絡(luò)進(jìn)行驗(yàn)證,分別為:郵件網(wǎng)絡(luò)[18]——反映了Enron公司內(nèi)部近50萬封郵件的收發(fā)關(guān)系;合作網(wǎng)絡(luò)[19]——隸屬于計(jì)算機(jī)科學(xué)的科學(xué)家合作網(wǎng)絡(luò);購物網(wǎng)絡(luò)[19]——一個(gè)共同購買網(wǎng)絡(luò),來自購物網(wǎng)站Amazon上的共同購買信息;分享網(wǎng)絡(luò)[20]——文件分享網(wǎng)站Gnutella上的p2p網(wǎng)絡(luò);信任網(wǎng)絡(luò)[21]——一個(gè)在線評(píng)價(jià)網(wǎng)站Epinions上的用戶信任網(wǎng)絡(luò);社交網(wǎng)絡(luò)[22]——在線社交網(wǎng)站Twitter上的用戶間好友關(guān)系網(wǎng)絡(luò)。上述網(wǎng)絡(luò)的簡要介紹見表1。
表1 六個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)基本性質(zhì)表
選取以下3個(gè)度量準(zhǔn)則衡量算法的優(yōu)劣性:種子節(jié)點(diǎn)傳播范圍,種子節(jié)點(diǎn)間的平均距離,以及冗余覆蓋率。
傳播范圍是度量種子節(jié)點(diǎn)傳播能力最直觀的度量,定義種子節(jié)點(diǎn)S的傳播范圍FS為這些節(jié)點(diǎn)所能感染的節(jié)點(diǎn)數(shù)目。由于傳播具有一定的隨機(jī)性,需要通過多次數(shù)值仿真計(jì)算感染節(jié)點(diǎn)數(shù)目的均值。
集合內(nèi)部節(jié)點(diǎn)間的平均距離可以從側(cè)面反映這個(gè)集合的結(jié)構(gòu)特性,定義種子節(jié)點(diǎn)間的平均距離為:
式中:|S|代表種子節(jié)點(diǎn)數(shù)目;dist(u,v)代表節(jié)點(diǎn)u到節(jié)點(diǎn)v的距離,即從u到v的最短路徑跳數(shù)。
為了衡量種子節(jié)點(diǎn)傳播范圍的重疊程度,定義種子節(jié)點(diǎn)的冗余覆蓋率為:
式中,F(xiàn)S為以S作為初始傳播者時(shí)所能達(dá)到的傳播范圍,F(xiàn){v}為僅以節(jié)點(diǎn)v作為初始傳播者的傳播范圍。
在實(shí)驗(yàn)中,設(shè)定恢復(fù)率q=1/k,感染率p=1.5q,其中k為網(wǎng)絡(luò)的平均度。不同種子節(jié)點(diǎn)比例時(shí)的影響力傳播范圍如圖2所示。從圖2可以看出,快速評(píng)估算法的表現(xiàn)一致優(yōu)于其他三種基準(zhǔn)算法,并且隨著種子節(jié)點(diǎn)數(shù)目的增加,快速評(píng)估算法的優(yōu)勢(shì)越來越明顯。在6個(gè)不同類型的網(wǎng)絡(luò)中,由快速評(píng)估算法選出的種子節(jié)點(diǎn)都具有更強(qiáng)的傳播能力,體現(xiàn)了該算法的廣泛適用性。
種子節(jié)點(diǎn)間的平均距離隨著種子節(jié)點(diǎn)數(shù)量的變化如圖3所示。由圖3可知,種子節(jié)點(diǎn)間的相對(duì)距離越近,它們的傳播范圍相互重疊得越明顯,會(huì)造成嚴(yán)重冗余,這對(duì)于信息傳播是不利的。因此,一個(gè)好的算法找出的種子節(jié)點(diǎn)應(yīng)當(dāng)相互分散,即種子節(jié)點(diǎn)間的平均距離較高。在該指標(biāo)下,快速評(píng)估算法依舊可以取得較為滿意的結(jié)果,尤其是在郵件網(wǎng)絡(luò)、信任網(wǎng)絡(luò)、社交網(wǎng)絡(luò)中,快速評(píng)估算法明顯優(yōu)于其他基準(zhǔn)算法。在分享網(wǎng)絡(luò)中,度中心找到的種子節(jié)點(diǎn)間的平均距離隨著種子節(jié)點(diǎn)數(shù)目的增加呈現(xiàn)先減后增的趨勢(shì)。事實(shí)上,這個(gè)結(jié)果并不反常,種子節(jié)點(diǎn)平均距離與種子節(jié)點(diǎn)數(shù)目之間并沒有確定性的關(guān)系,而是與網(wǎng)絡(luò)結(jié)構(gòu)以及具體算法有關(guān)。分享網(wǎng)絡(luò)是一個(gè)高度中心化的網(wǎng)絡(luò),由少數(shù)緊密相連的中心節(jié)點(diǎn)與大量邊緣節(jié)點(diǎn)構(gòu)成,呈現(xiàn)出一種明顯的中心-邊緣趨勢(shì)。度中心算法會(huì)將網(wǎng)絡(luò)的中心節(jié)點(diǎn)作為種子節(jié)點(diǎn),由于中心節(jié)點(diǎn)是緊密相連的,因此隨著節(jié)點(diǎn)數(shù)目的增加,種子節(jié)點(diǎn)間的平均距離會(huì)減少;當(dāng)中心節(jié)點(diǎn)全部找出之后,度中心算法才會(huì)加入邊緣節(jié)點(diǎn),導(dǎo)致種子節(jié)點(diǎn)平均距離的逐漸增加。
(a) 郵件網(wǎng)絡(luò)(a) E-mail network (b) 合作網(wǎng)絡(luò)(b) Collaboration network
(c) 購物網(wǎng)絡(luò)(c) Shopping network (d) 分享網(wǎng)絡(luò)(d) Sharing network
(e) 信任網(wǎng)絡(luò)(e) Trust network (f) 社交網(wǎng)絡(luò)(f) Social network圖2 不同種子節(jié)點(diǎn)比例時(shí)的影響力傳播范圍Fig.2 Spreading scope with different fractions of seed nodes
(a) 郵件網(wǎng)絡(luò)(a) E-mail network (b) 合作網(wǎng)絡(luò)(b) Collaboration network
(c) 購物網(wǎng)絡(luò)(c) Shopping network (d) 分享網(wǎng)絡(luò)(d) Sharing network
(e) 信任網(wǎng)絡(luò)(e) Trust network (f) 社交網(wǎng)絡(luò)(f) Social network圖3 不同種子節(jié)點(diǎn)比例時(shí)的種子節(jié)點(diǎn)平均距離Fig.3 Average distance among seed nodes with different fractions of them
種子節(jié)點(diǎn)冗余覆蓋率是衡量種子節(jié)點(diǎn)傳播重疊程度的直觀指標(biāo),冗余覆蓋率越大,說明種子節(jié)點(diǎn)相互間的傳播范圍重疊程度越大,它們構(gòu)成集群時(shí)的影響力損耗也越多。各算法在不同網(wǎng)絡(luò)上的種子節(jié)點(diǎn)冗余覆蓋率結(jié)果見表2,除了在分享網(wǎng)絡(luò)上快速評(píng)估算法的表現(xiàn)略差于投票排名以外,在其他網(wǎng)絡(luò)中該算法均能得到最優(yōu)的結(jié)果。
表2 種子節(jié)點(diǎn)冗余覆蓋率
本文實(shí)現(xiàn)基于種子集擴(kuò)展的影響力極大化快速評(píng)估算法。在6個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)證分析,驗(yàn)證了快速評(píng)估算法的有效性。而且快速評(píng)估算法具有很好的可拓展性。例如,對(duì)于節(jié)點(diǎn)傳播能力異質(zhì)的情況,可以將式(3)中的傳播概率p替換為節(jié)點(diǎn)傳播概率pu;當(dāng)所考慮的網(wǎng)絡(luò)為時(shí)序網(wǎng)絡(luò)時(shí)[23-24],也可以將式(3)中的鄰居集Γv替換為不同時(shí)間片r時(shí)的鄰居集Γv(r)。仿照本算法中的推導(dǎo)過程,可以得到前述情況下的快速評(píng)估算法。在下一步的工作中,將對(duì)算法進(jìn)行進(jìn)一步優(yōu)化,從圖1中可以看出,算法對(duì)于傳播范圍的估計(jì)精度偏低,還有較大的改進(jìn)空間。