有限步傳播范圍期望指標判別節點傳播影響力

李鑫 趙城利 劉陽洋

(國防科技大學文理學院,長沙 410073)

在線社交網絡逐漸成為人們不可或缺的重要工具,識別網絡中具有高影響力的節點作為初始傳播源,在社會感知與謠言控制等方面具有重要意義.本文基于獨立級聯模型,給出了一個描述有限步傳播范圍期望的指標—傳播度,并設計了一種高效的遞推算法.該指標在局部拓撲結構信息的基礎上融合了傳播概率對影響力進行刻畫,能夠較好地反映單個節點的傳播影響力.對于多傳播源影響力極大化問題,本文提出了一種基于傳播度的啟發式算法—傳播度折扣算法,使得多個傳播源的聯合影響力最大.最后,將上述方法應用到三個真實網絡中,與經典指標和方法相比,該方法不需要知道網絡的全局結構信息,而是充分了利用網絡的局部結構信息,可以較快地篩選出高傳播影響力的傳播源.

1 引 言

隨著網絡科學的快速發展,節點的傳播影響力越來越受到人們的關注.在信息的傳播過程中,具有高傳播影響力的節點可以加速信息的傳播,這對于宣傳產品,推送廣告等方面具有重要的作用.因此,該領域的一個核心問題就是如何選擇網絡中的若干節點作為傳播源,使其傳播影響力極大化,又具體可分為單個傳播源影響力排序問題和多個傳播源影響力極大化問題(需要考慮不同傳播源之間影響力的重疊).

對于網絡中節點影響力排序問題,最簡單高效的方法是度中心性[1],它反映節點的鄰居數,例如微博中擁有粉絲數多的大V用戶就具有很高的傳播影響力.后來,Chen等[2]又給出了一個局部中心性指標,該指標考慮了二階鄰居數,但這兩個指標在反映節點傳播影響力時沒有考慮傳播概率的影響,也無法充分反映節點的局部拓撲結構.對于全局性的指標有介數中心性[3]、接近度中心性[4]、K核[5]、特征向量中心性[6]等.而對于多源影響力極 大 化 (influence maximization)問 題,最 初 由Domingos和 Richardson[7]提出,后被 Kempe等[8]證明該問題是NP-Hard難問題.一種最簡單的選取策略就是選出某指標值最大的若干節點作為傳播源,但這種算法選出的各傳播者之間可能會有較大影響力重疊.因此,Leskovec 等[9]采用貪心算法來尋求初始傳播集,但這種算法的復雜度較大不適用于大型網絡.Chen等[10]提出兩種改進的貪心算法新貪心算法和最大貪心算法,這兩種改進算法均比貪心算法的算法復雜度要低,但在大型網絡中仍具有較高算法復雜度.后來,一些特殊的啟發式算法被提出,度折扣算法[11]就是其中一種高效的啟發式算法,它是對探索式算法的一種優化策略的改進,具有較高的實用價值,其基本思想為當節點的鄰居節點已被選為傳播源時,會對該節點的度指標產生折扣效應,從而達到了去重疊的目的.再后來,Kimura等[12]利用分解極大連通子圖來尋找最優傳播源,基于此,又提出了利用最大影響路徑的方法[13],這種方法雖然大大降低了了算法復雜度,但限制了只能在最短路徑上傳播.Wang等[14]提出了一種結合動態規劃的算法選擇最優傳播源,提升了算法效率,Li等[15]考慮積極消極影響力,提出了一種新的模型,盡管這些算法效率都很高,但很容易陷入局部最優的情況,效果不及貪心算法.

在線社交網絡具有規模龐大,結構復雜的特點,運用節點的局部信息指標描述節點的傳播影響力更具現實意義.但目前的局部性指標均不能夠很好的刻畫節點的局部拓撲結構,因此本文基于獨立級聯模型,提出一種描述節點有限步傳播范圍期望的指標—傳播度.對于網絡中的任一節點作為傳播源,我們充分分析信息在局部網絡中的傳播路徑,設計了一種精確的遞推算法計算有限步后傳播范圍的期望值,之后通過真實網絡數據集仿真驗證了該指標與節點傳播影響力具有更高一致性.另一方面,在考慮多傳播源影響力極大化問題時,選擇的各傳播源影響力會發生重疊,因此基于傳播度提出了一種啟發式算法—傳播度折扣算法,同樣通過真實網絡數據集仿真驗證了該算法相較于經典方法具有更好的效果.

本文的主要貢獻在以下幾個方面:

1)提出了描述網絡節點傳播能力的指標—傳播度,用于描述節點在有限步后能夠傳播到網絡節點范圍的期望值.并設計了計算該指標的迭代算法,可以高效的計算節點的任意階(步數)的傳播度.

2)相較于傳統指標,傳播度指標考慮了傳播概率對節點傳播的影響.對于小型網絡,可以直接利用該算法計算節點的最終傳播期望;對于大型網絡,可利用低階傳播度刻畫節點的傳播影響力,充分利用了節點的局部拓撲結構信息.

3)對于多傳播源問題,基于傳播度指標提出了一種傳播度折扣的算法,能有有效地去除不同初始傳播源間的影響力重疊,相較于原有的度折扣算法有更好的選擇效果.

2 有限步傳播范圍期望的算法

獨立級聯模型(IC模型)是網絡信息傳播的一種最常用的模型,當一個節點v被激活時,它會以概率將其鄰居節點u激活,這種嘗試僅進行一次,在此之后,節點v仍處于激活狀態,但不具有傳播信息的能力.根據該傳播模型,定義s階傳播度表示傳播s步后所有節點被激活的概率之和.由于網絡結構十分復雜,為了保證概率的計算不重不漏,先提出兩個輔助算法,最終給出一個高效的遞推算法.

2.1 輔助算法一

為了更清楚地反映初始傳播源的傳播情況,將節點的局部拓撲結構轉化成樹的形式,并定義為該傳播源的傳播樹,該算法稱為傳播樹算法.根據信息在網絡中的傳播路線,傳播樹是基于特定的單個種子節點的網絡的另一種拓撲表示(簡單的例子見圖1).圖1(b)為圖1(a)的傳播樹,傳播樹的生成規則如下:

Step 1確定一個種子節點作為 P0代節點;

Step 2將種子節點的鄰居作為種子節點的孩子,記為 P1代節點,令 k=1;

Step 3對于 Pk代個體的任一個節點i,將節點i的鄰居且非節點i的祖先的節點作為節點i的孩子.則將所有 Pk代個體的孩子記為 Pk+1代個體;

Step 4若 Pk+1代個體數量大于 0,則令 k=k+1,返回 Step 3;否則,P0到 Pk個體對應的樹即為網絡的傳播樹.

圖1 一個簡單網絡例子 (a)網絡圖;(b)圖 (a)對應的傳播樹Fig.1.A simple network example:(a) The network diagram;(b) the corresponding propagation tree of (a).

2.2 傳播度的計算公式及輔助算法二

2.2.1 傳播度的計算公式

在2.1節傳播樹概念的基礎上,先引入幾個參量,用 pt(u) 表示節點 u 在 t時間內 (包含 t時刻)被感染的概率;ft(ui) 表示 Pt代的第 i個 u 節點在t時刻被感染的獨立概率;ft(ui1,···,in) 表示Pt代的第 i1,···,in個u節點在t時刻被感染的聯合概率;ft(u) 表示 Pt代的所有的 u節點在 t時刻被感染的聯合概率.那么獨立概率計算公式為

那么種子節點seed的s階傳播度的計算公式為

2.2.2 輔助算法二

由2.2.1節的介紹,關鍵問題在于如何計算聯合概率 ft(u),因此提出了輔助算法二—聯合概率算法.在介紹算法前,首先分析概率的傳播公式,假設u節點在t時刻(傳播樹的 Pt代個體中)出現N次,此時節點u的雙親節點也有N個,不失一般性,記其雙親節點為 v1,v2,···vn,其出現次數分別為 m1,m2,···mn次,因 此 共 有m1+m2+···+mn=N條傳播路徑在t時刻可能傳播到節點u,那么對于任意的 j ∈ {1,2,···n},節點u的雙親節點 vj有 mj條路徑通向 u.在 Pt-1代個體中,這mj條路徑經過的節點 vj在所有 vj中的序號保存在集合Xj中;在 Pt代個體中,這 mj條路徑經過的節點u在所有 u中的序號保存在集合 Yj中.在計算ft(u)時,首先考慮相同雙親節點間的聯合概率,

進一步計算不同雙親間的聯合概率,

其中集合 Xj只有一個元素時,即為公式(1)所得的獨立概率,當 Xj含有多個元素時,仍用該方法計算聯合概率.進一步,

事實上,該算法在編程時是一個計算聯合概率ft(uw)可調用函數,當 t – 1 時間內傳播樹中各點的獨立概率已遞推求得,用 F (t,u,W) 表示調用函數,其算法的偽代碼如表1所列.

2.3 傳播度遞推求解

由方程 (6)可知,在計算 pt(u) 時,需要知道ft(u)和 pt-1(u).而計算 ft(u) 時,根據 2.2 節中的分析,最終轉化為計算 t–1 時間內 (包含 t–1 時刻)傳播樹中各點的獨立概率的計算式.因此,可以用遞推算法最終求得傳播度.求解s階傳播度的算法流程偽代碼如表2所列.有了表2所列的遞推算法,便可以編程高效的計算節點的任意階的傳播度.

表1 聯合概率算法Table 1.Joint probability algorithm.

表2 種子節點s階傳播度的算法流程偽代碼Table 2.Pseudocode of the algorithm flow for s order progpagation of the seed node.

2.4 仿真驗證

綜上所述,對于一個網絡,確定初始種子節點,先用傳播樹算法得到相應的傳播樹,在利用遞推算得到任何時刻任意節點的期望值 pt(i),進而得到任意時刻的傳播度值.為了進一步驗證算法的精確性,我們基于獨立級聯模型對圖1所示網絡進行傳播仿真.選擇不同的仿真次數,比較情況見圖2.

圖2 (a)不同仿真次數下的近似傳播期望值和傳播度隨時間的變化;(b)不同仿真次數的近似傳播期望值與傳播度的方差變化Fig.2.(a) Approximate propagation expectation and the degree of propagation over time for different simulation times;(b) variance of the approximate propagation expectation and the degree of propagation of different simulation times.

由圖2可知,模型計算的期望值是精確的.有了傳播度的指標后,便可以用該指標來反應節點的傳播影響力.

對于小型網絡,可以直接計算最高階的傳播度來反應節點的傳播影響力,該方法有兩方面優勢.一方面,在現實中,出于商業考慮,可能不會選取明顯較優的核心節點,如圖1小型網絡中的1號節點,因此,進一步比較 2,3 號,甚至 5,6,7,8 號節點的傳播影響力優劣具有重要意義.另一方面,網絡中節點的傳播影響力是與傳播概率相關的,而傳播度指標可以很好地將傳播概率融入到刻畫節點傳播影響力中去.

如圖1所示,節點最多傳遞四步,因此利用上述方法計算所有節點的四階傳播度來反映節點的傳播影響力.為了比較各節點傳播影響力的大小以及驗證節點的傳播影響力與傳播概率相關,圖3給出了不同傳播概率下各節點四階傳播度的變化情況.

圖3 圖1 中的網絡各節點 4 階傳播度 (歸一化)隨傳播概率變化Fig.3.Changes of the 4th degree of propagation (normalized) of network node in Fig.1 with the propagation probability.

由圖3可知,隨著傳播概率不斷增加,各節點的傳播影響力排序會發生明顯變化,且可以量化比較各節點傳播影響力大小.當傳播概率較大時,可以選擇普通的節點作為傳播源,兼顧成本和傳播能力兩個方面.后文將主要關注傳播度在大型網絡中識別高傳播影響力傳播源的作用展開詳細討論.

3 基于傳播度的節點影響力最大化方法

初始種子節點的傳播影響力最大化問題分為單源和多源兩種情況,下面分別給出判別算法.

3.1 單個節點的影響力排序

由傳播度的定義知道,一階傳播度為d1=1+βdseed,其中 dseed種子節點的度,因此一階傳播度和節點度是等價的.而二階傳播度事實上不僅反映了種子節點的一階鄰居和二階鄰居情況,還反映了一階鄰居之間的連邊拓撲關系,例如,種子節點的鄰居節點很有可能實在第二步通過另一個鄰居節點被傳播的.類似地,考慮更高階傳播度時,不僅反映了高階鄰居的情況,還反映了較低階鄰居之間的拓撲關系.

3.2 傳播度折扣解決多源影響力極大化問題

關于多源傳播影響力極大化問題,一般采用啟發式算法,然而不同傳播源的傳播影響力會有較多“重疊”部分,因此在算法進行的過程中需要采用去重疊過程.由于定義的傳播度是基于概率期望的,基于這一特性,去重疊過程是十分簡便的,下面進行理論分析.

考慮s階傳播度,計算出所有節點的s階傳播度,選擇最大的一個節點加入種子節點集R的第一個節點,其各節點的傳播期望為ps(i),i∈1,2,···,N}.記 ptotal為 N 階向量,表示考慮種子節點集R中所有節點的s階傳播度,網絡中所有節點未患病的概率.不失一般性,假設R中已有k個節點,這些節點到網絡中所有節點的傳播期望值 為(i),i∈ {1,2,···N},j ∈ {1,2,···,k},表示R中的第j號種子節點到節點i的傳播概率(僅考慮節點的 s階鄰居內的節點).則相應的ptotal值變為

下面需要選擇第k+1個節點,任選一個節點v,需要考慮節點v與已選種子節點集R的重疊情況,進而求得節點v的有效貢獻值.一方面,節點v是有效的,說明已選節點沒有傳播到節點v,ptotal向量記錄了已選節點未傳播到其他節點的概率,因此可以得到節點集R未傳播到節點v的概率,記為ptotal(v).另一方面,由于節點v可能傳播到的節點可能已被傳播,因此需要引入折扣因子,若節點v到節點u的傳播期望值為 ps(u),則引入折扣因子后變為 ps(u)×ptotal(u),因此在選擇第k+1個節點前,先計算節點v的傳播折扣度為

其中 G.neis(v) 表示節點v的s階鄰居內的節點(不包括v節點本身).將候選者按傳播折扣度排序,選出最優者加入種子節點集合.多次執行上述操作,即可得到近似最優的傳播影響力節點集.

3.3 模型總述

綜上所述,算法的總流程圖如圖4所示.從新定義的傳播度指標出發,充分考慮節點所有可能就近的傳播路徑和傳播概率的大小,分別對單源節點影響力排序問題和多源影響力極大化問題給出了解決方案.對于小型網絡,我們在 2.4 節中指出,可以計算最高階的傳播度從而可以精確的找出最優傳播源.對于大型網絡,將在第4節詳細驗證該模型的優勢.

4 效果分析

由滲流理論可知,當傳播概率較大且高于滲流閾值時,單個節點就具有傳播到全局的能力,此時可以用全局傳播概率(參見文獻[16])反映節點的傳播能力.因此,在檢驗算法效果時,應分兩種情況考慮:一種是傳播概率較小且低于滲流閾值,此時用平均傳播范圍表示節點傳播能力;當傳播概率較大時,用全局傳播概率來反映.

4.1 數據集

為了評價模型,采用如下3個不同領域的真實網絡數據集(無向)進行仿真實驗.

1) Deezer[17]:數據來源于音樂流服務網站Deezer提供的數據,表示羅馬尼亞用戶朋友網絡.數據下載于:http://snap.stanford.edu/data/(簡稱SLNDC),共有41773個節點,平均度為6.024.

2 Email-Enron[18]:數據來源于安然電子郵件網絡,下載于 SLNDC,共有 36692 個節點,平均度為10.020.

3) Facebook[17]:數據來源 Facebook 朋友網絡,下載于 SLNDC,共有 13866 個節點,平均度為12.528.

4.2 單源影響力排序效果

采用節點的仿真影響力值和傳播度值的kendall’s tau 系數[19]來反映單源影響力的排序效果.該指數反映了兩個序參量的一致性,大小介于–1和1之間,當該系數越大時,兩個序參量越趨于一致.該算法排序效果見圖5和圖6.

由圖5和圖6可知,傳播度相較于度,高階傳播度相較于低階傳播度與節點的傳播能力之間具有更高的一致性,特別是在傳播概率偏大時,這種效果是明顯的,這種現象同樣適用其他的真實網絡.

目前最常用的節點重要度排序指標有k核[20](coreness),特征向量中心性[6](eigenvenctor),考慮節點最近鄰居核次近鄰居的多級鄰居信息指標[2](local centrality),而介數中心性和接近度中心性由于其算法復雜度較高,不適用于大型網絡.不同方法下的比較情況見圖7和圖8.

由圖7和圖8可以看出,對于大型網絡,二階傳播度相較于其他指標在不同的傳播概率和網絡下具有更好的效果和更高的穩定性.因此,我們給出的傳播度能更好地利用節點的局部拓撲結構來描述單源影響力排序.

圖5 (a)?(c) 分別反映了 Deezer網絡隨機挑選若干節點的傳播能力與度,二階傳播度,三階傳播度的關系,其中 β=0.06;(d)?(f) 分別反映了Deezer網絡隨機挑選若干節點全局傳播概率(參見文獻[12])與度,二階傳播度,三階傳播度的對應情況,其中β=0.12(這里通過仿真實驗不難發現該網絡的滲流閾值介于0.06和0.12之間)Fig.5.(a)?(c):Respectively reflects the relationship between the propagation capacity and degree,second-order propagation,and third-order propagation of several nodes randomly selected by the Deezer network,where β=0.06;(d)?(f):Respectively reflects the global propagation probability of randomly selected nodes by the Deezer network (see reference[12]) Correspondence with degrees,second-order propagation,and third-order propagation,where β=0.12 (here,it is not difficult to find through the simulation experiments that the percolation threshold of the network is between 0.06 and 0.12).

圖6 不同傳播概率下度,二階、三階傳播度與仿真傳播能力的 kendall’s tau 系數Fig.6.Kendall’s tau coefficient for different propagation probabilities,second-order,third-order propagation and simulation propagation ability.

圖7 (a)在Email-Enron網絡中,傳播概率為0.02的情況下二階傳播度和全局傳播概率p的關系;(b)各指標在不同概率下與傳播能力的 kendall’s tau 系數Fig.7.(a) The relationship between the second-order propagation degree and the global propagation probability p in the case of the Email-Enron network with a propagation probability of 0.02;(b) the kendall's tau coefficient of each indicator with different propagation rates and propagation capabilities.

圖8 (a)在Facebook網絡中,傳播概率為0.09的情況下二階傳播度和全局傳播概率p的關系;(b)各指標在不同概率下與傳播能力的 kendall’s tau 系數Fig.8.(a) The relationship between the second-order propagation degree and the global propagation probability p in the case of a Facebook network with a propagation probability of 0.09;(b) the kendall's tau coefficient of each indicator with different propagation rates and propagation capabilities.

4.3 多源影響力極大化效果

通過實驗發現,分解極大連通子圖等方法雖然算法復雜度低,但由于做了過多近似,效果不如算法復雜度較高的貪心算法,因此這些方法不是本文研究的重點,而是致力于貪心算法的一種改進算法.為了驗證傳播度折扣算法的效果,將該算法與最大度[1](degree),核[20](coreness),特征向量[6](eigenvenctor),介數[3](betweeness),折扣度算法[11]

(degreediscount)進行仿真比較.同樣,也分兩種情況來比較:一種取傳播概率較小且低于滲流閾值,另一種取傳播概率較大且高于滲流閾值.算法效果見圖9和圖10所示.

圖9 在Deezer網絡中(a)不同算法下傳播范圍隨所選種子節點數量的變化和(b)不同算法下全局傳播概率隨種子節點數量的變化,其中候選節點為度為 6,7,8 的 9792 個節點Fig.9.In the Deezer network,(a) the variation of the propagation range with the number of selected seed nodes under different algorithms;(b) the variation of the global propagation probability with the number of seed nodes under different algorithms.The candidate nodes are 9792 nodes with a degree of 6,7 and 8.

圖10 (a),(b)和 (c),(d)分別比較了 Email-Enron,Facebook 網絡在不同算法下所選種子節點的傳播性能Fig.10.(a),(b),and (c),(d),respectively,compare the propagation performance of Email-Enron,the selected seed node of the Facebook network under different algorithms.

由圖9和圖10可以看出,傳播度折扣算法能夠較好的解決多源影響力極大化問題,因此在利用局部信息去除影響力重疊時,傳播度折扣算法具有不錯的效果.

5 總 結

在充分考慮節點局部拓撲結構信息的基礎上,提出了有限步傳播范圍期望的指標—傳播度,并設計了高效精確的遞推計算方法.在此基礎上,將該指標用于單源影響力排序問題,實驗證明,該指標與節點的傳播能力具有更高的一致性.另外,對于多源影響力極大化問題,本文基于傳播度的概念,設計了一種啟發式算法—傳播度折扣算法,相較于經典的算法,具有更好的篩選效果.

給出了一種精確計算有限步傳播范圍期望的遞推算法,事實上,當傳播到達一定步數后,即當傳播步數較大時,節點被傳播的概率往往很小,因此,如何設置局部的遞推終止條件,引入較小的誤差,可以進一步優化算法,計算更高階的傳播度,這一問題有待進一步研究.