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

李鑫 趙城利 劉陽洋

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

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

1 引 言

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

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

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

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

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

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

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

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

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

2.1 輔助算法一

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

Step 1確定一個種子節(jié)點作為 P0代節(jié)點;

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

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

Step 4若 Pk+1代個體數(shù)量大于 0,則令 k=k+1,返回 Step 3;否則,P0到 Pk個體對應(yīng)的樹即為網(wǎng)絡(luò)的傳播樹.

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

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

2.2.1 傳播度的計算公式

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

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

2.2.2 輔助算法二

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

進一步計算不同雙親間的聯(lián)合概率,

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

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

2.3 傳播度遞推求解

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

表1 聯(lián)合概率算法Table 1.Joint probability algorithm.

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

2.4 仿真驗證

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

圖2 (a)不同仿真次數(shù)下的近似傳播期望值和傳播度隨時間的變化;(b)不同仿真次數(shù)的近似傳播期望值與傳播度的方差變化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可知,模型計算的期望值是精確的.有了傳播度的指標后,便可以用該指標來反應(yīng)節(jié)點的傳播影響力.

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

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

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

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

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

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

3.1 單個節(jié)點的影響力排序

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

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

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

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

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

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

3.3 模型總述

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

4 效果分析

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

4.1 數(shù)據(jù)集

為了評價模型,采用如下3個不同領(lǐng)域的真實網(wǎng)絡(luò)數(shù)據(jù)集(無向)進行仿真實驗.

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

2 Email-Enron[18]:數(shù)據(jù)來源于安然電子郵件網(wǎng)絡(luò),下載于 SLNDC,共有 36692 個節(jié)點,平均度為10.020.

3) Facebook[17]:數(shù)據(jù)來源 Facebook 朋友網(wǎng)絡(luò),下載于 SLNDC,共有 13866 個節(jié)點,平均度為12.528.

4.2 單源影響力排序效果

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

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

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

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

圖5 (a)?(c) 分別反映了 Deezer網(wǎng)絡(luò)隨機挑選若干節(jié)點的傳播能力與度,二階傳播度,三階傳播度的關(guān)系,其中 β=0.06;(d)?(f) 分別反映了Deezer網(wǎng)絡(luò)隨機挑選若干節(jié)點全局傳播概率(參見文獻[12])與度,二階傳播度,三階傳播度的對應(yīng)情況,其中β=0.12(這里通過仿真實驗不難發(fā)現(xiàn)該網(wǎng)絡(luò)的滲流閾值介于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 不同傳播概率下度,二階、三階傳播度與仿真?zhèn)鞑ツ芰Φ?kendall’s tau 系數(shù)Fig.6.Kendall’s tau coefficient for different propagation probabilities,second-order,third-order propagation and simulation propagation ability.

圖7 (a)在Email-Enron網(wǎng)絡(luò)中,傳播概率為0.02的情況下二階傳播度和全局傳播概率p的關(guān)系;(b)各指標在不同概率下與傳播能力的 kendall’s tau 系數(shù)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網(wǎng)絡(luò)中,傳播概率為0.09的情況下二階傳播度和全局傳播概率p的關(guān)系;(b)各指標在不同概率下與傳播能力的 kendall’s tau 系數(shù)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 多源影響力極大化效果

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

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

圖9 在Deezer網(wǎng)絡(luò)中(a)不同算法下傳播范圍隨所選種子節(jié)點數(shù)量的變化和(b)不同算法下全局傳播概率隨種子節(jié)點數(shù)量的變化,其中候選節(jié)點為度為 6,7,8 的 9792 個節(jié)點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 網(wǎng)絡(luò)在不同算法下所選種子節(jié)點的傳播性能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 總 結(jié)

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

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