李鑫 趙城利 劉陽(yáng)洋

(國(guó)防科技大學(xué)文理學(xué)院,長(zhǎng)沙 410073)

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

1 引 言

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

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

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

本文的主要貢獻(xiàn)在以下幾個(gè)方面:

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

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

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

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

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

2.1 輔助算法一

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

Step 1確定一個(gè)種子節(jié)點(diǎn)作為 P0代節(jié)點(diǎn);

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

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

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

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

2.2 傳播度的計(jì)算公式及輔助算法二

2.2.1 傳播度的計(jì)算公式

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

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

2.2.2 輔助算法二

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

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

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

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

2.3 傳播度遞推求解

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

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

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

2.4 仿真驗(yàn)證

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

圖2 (a)不同仿真次數(shù)下的近似傳播期望值和傳播度隨時(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可知,模型計(jì)算的期望值是精確的.有了傳播度的指標(biāo)后,便可以用該指標(biāo)來(lái)反應(yīng)節(jié)點(diǎn)的傳播影響力.

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

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

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

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

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

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

3.1 單個(gè)節(jié)點(diǎn)的影響力排序

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

3.2 傳播度折扣解決多源影響力極大化問(wèn)題

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

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

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

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

3.3 模型總述

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

4 效果分析

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

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

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

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

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

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

4.2 單源影響力排序效果

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

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

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

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

圖5 (a)?(c) 分別反映了 Deezer網(wǎng)絡(luò)隨機(jī)挑選若干節(jié)點(diǎn)的傳播能力與度,二階傳播度,三階傳播度的關(guān)系,其中 β=0.06;(d)?(f) 分別反映了Deezer網(wǎng)絡(luò)隨機(jī)挑選若干節(jié)點(diǎn)全局傳播概率(參見(jiàn)文獻(xiàn)[12])與度,二階傳播度,三階傳播度的對(duì)應(yīng)情況,其中β=0.12(這里通過(guò)仿真實(shí)驗(yàn)不難發(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)各指標(biāo)在不同概率下與傳播能力的 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)各指標(biāo)在不同概率下與傳播能力的 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 多源影響力極大化效果

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

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

圖9 在Deezer網(wǎng)絡(luò)中(a)不同算法下傳播范圍隨所選種子節(jié)點(diǎn)數(shù)量的變化和(b)不同算法下全局傳播概率隨種子節(jié)點(diǎn)數(shù)量的變化,其中候選節(jié)點(diǎn)為度為 6,7,8 的 9792 個(gè)節(jié)點(diǎn)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é)點(diǎn)的傳播性能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可以看出,傳播度折扣算法能夠較好的解決多源影響力極大化問(wèn)題,因此在利用局部信息去除影響力重疊時(shí),傳播度折扣算法具有不錯(cuò)的效果.

5 總 結(jié)

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

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