陳云芳，夏濤,2，張偉，李晉

（1. 南京郵電大學(xué)計(jì)算機(jī)學(xué)院，江蘇 南京 210003；2. 中國(guó)電信濟(jì)寧分公司，山東 濟(jì)寧272000；3. 北京信息科技大學(xué)公共管理與傳媒學(xué)院，北京 100192）

基于親和傳播的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)影響力擴(kuò)散模型

陳云芳1，夏濤1,2，張偉1，李晉3

（1. 南京郵電大學(xué)計(jì)算機(jī)學(xué)院，江蘇 南京 210003；2. 中國(guó)電信濟(jì)寧分公司，山東 濟(jì)寧272000；3. 北京信息科技大學(xué)公共管理與傳媒學(xué)院，北京 100192）

影響力最大化模型研究是近來(lái)社會(huì)網(wǎng)絡(luò)的一個(gè)熱點(diǎn)問(wèn)題，然而傳統(tǒng)的獨(dú)立級(jí)聯(lián)模型以靜態(tài)網(wǎng)絡(luò)中為基礎(chǔ)，且激活概率一般設(shè)定為固定值。提出一種加入衰減因數(shù)的動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)影響力擴(kuò)散模型—DDIC模型，其采用親和傳播來(lái)計(jì)算節(jié)點(diǎn)之間的激活概率，依據(jù)時(shí)間片對(duì)社會(huì)網(wǎng)絡(luò)進(jìn)行動(dòng)態(tài)切分，使激活概率在不同時(shí)間片中實(shí)現(xiàn)了有效關(guān)聯(lián)。實(shí)驗(yàn)結(jié)果表明DDIC模型中種子節(jié)點(diǎn)有更多機(jī)會(huì)激活它的鄰居節(jié)點(diǎn)，且采用親和傳播計(jì)算出的影響力值能更準(zhǔn)確地體現(xiàn)DDIC模型的傳播過(guò)程。

動(dòng)態(tài)社會(huì)網(wǎng)絡(luò)；影響力擴(kuò)散；親和傳播

1 引言

虛擬社會(huì)所形成的人際關(guān)系網(wǎng)絡(luò)以及各種各樣的社會(huì)網(wǎng)絡(luò)越來(lái)越多地出現(xiàn)在人們面前，通過(guò)這些社會(huì)網(wǎng)絡(luò)所表現(xiàn)出來(lái)的社會(huì)以及人際關(guān)系互動(dòng)是許多領(lǐng)域的研究熱點(diǎn)。在社會(huì)影響力傳播中，社會(huì)網(wǎng)絡(luò)作為傳播的媒介，在個(gè)體之間相互影響、個(gè)體之間傳播觀點(diǎn)與信息等方面發(fā)揮著巨大的作用。一條信息可以在人群中迅速地蔓延，也有可能在很短時(shí)間內(nèi)就消失。了解信息被人們所接受的程度是很有必要的，這就需要了解信息是如何在社會(huì)網(wǎng)絡(luò)中動(dòng)態(tài)傳播的，即人們?cè)诤畏N程度上能夠受到好友的影響而去做某件事情，“口碑效應(yīng)”在什么程度下會(huì)發(fā)生。

影響力最大化模型研究是近來(lái)社會(huì)影響力領(lǐng)域的一個(gè)熱點(diǎn)問(wèn)題。“病毒式營(yíng)銷”開始只是針對(duì)為數(shù)不多的幾個(gè)相對(duì)于其他個(gè)體具有“影響力”的個(gè)體。將一種商品首先推薦給這樣的群體，然后在人群中進(jìn)行擴(kuò)散，大多數(shù)個(gè)體會(huì)把此商品推薦給朋友，通過(guò)口口相傳使這種商品得到推廣。這種首先找到一定個(gè)數(shù)的具有“影響力”的節(jié)點(diǎn)，然后通過(guò)這些具有“影響力”的節(jié)點(diǎn)去影響別的節(jié)點(diǎn)的問(wèn)題被稱為影響力最大化問(wèn)題。

關(guān)于影響力最大化問(wèn)題的研究大多都是在靜態(tài)網(wǎng)絡(luò)上展開。然而，網(wǎng)絡(luò)本身是動(dòng)態(tài)的，其中的個(gè)體和它們之間的交互會(huì)隨時(shí)間的推移而變化。相比于動(dòng)態(tài)網(wǎng)絡(luò)，靜態(tài)網(wǎng)絡(luò)損失了節(jié)點(diǎn)之間的交互信息，不能很好地適應(yīng)網(wǎng)絡(luò)的變化情況。因此，研究在動(dòng)態(tài)網(wǎng)絡(luò)中進(jìn)行影響力最大化模型的擴(kuò)散很有必要。

2 相關(guān)工作

2002年，Richardson等[1]將影響力最大化問(wèn)題引入到社會(huì)網(wǎng)絡(luò)領(lǐng)域后引起了眾多學(xué)者的關(guān)注。Kempe等[2]在 2003年第一次比較系統(tǒng)地研究了影響力最大化模型，其總結(jié)了影響力最大化模型：獨(dú)立級(jí)聯(lián)（IC, independent cascade）模型和線性閾值（LT, linear thresholds）模型，并且證明了獨(dú)立級(jí)聯(lián)模型、線性閾值模型是NP難題，同時(shí)證明了2個(gè)模型的擴(kuò)散結(jié)果函數(shù)是一個(gè)子模函數(shù)，滿足收益遞減原則。

自從影響力模型提出以后，許多文獻(xiàn)都是圍繞著怎么找到影響力最大化問(wèn)題中的種子節(jié)點(diǎn)來(lái)研究的。這部分算法大體上可以分為2類：貪心算法和探索式算法。貪心算法由Kempe等提出，許多文獻(xiàn)對(duì)貪心算法進(jìn)行了改進(jìn)：Leskovec等[3]提出的CELF算法運(yùn)用了影響力最大化問(wèn)題的子模特性，很大程度上降低了評(píng)價(jià)節(jié)點(diǎn)影響力；Chen等[4]提出了NewGreedy算法和MixGreedy算法。貪心算法的高時(shí)間復(fù)雜度使其在大型網(wǎng)絡(luò)的應(yīng)用受到了限制，另一種可能的方法就是使用探索式算法。在社會(huì)網(wǎng)絡(luò)分析中，度和一些其他的基于中心性的探索式算法經(jīng)常被用來(lái)評(píng)價(jià)節(jié)點(diǎn)的影響力。在影響力最大化問(wèn)題中節(jié)點(diǎn)度經(jīng)常被用來(lái)選擇種子節(jié)點(diǎn)，文獻(xiàn)[2]的實(shí)驗(yàn)選擇具有最大度數(shù)的節(jié)點(diǎn)為種子節(jié)點(diǎn)，能夠比其他探索式算法得到更好的效果。以往文獻(xiàn)都沒有考慮網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)特性。Galstyan等[5]第一次提出了一種基于社區(qū)結(jié)構(gòu)的影響力最大化問(wèn)題的解決方案，但是該方法只是局限于2個(gè)連接稀疏的社區(qū)網(wǎng)絡(luò)，而實(shí)際中的網(wǎng)絡(luò)一般包括很多社區(qū)網(wǎng)絡(luò)。Cao等[6]把影響力最大化問(wèn)題轉(zhuǎn)化為最佳資源分配問(wèn)題，將整個(gè)網(wǎng)絡(luò)根據(jù)社區(qū)發(fā)現(xiàn)算法劃分為若干個(gè)社區(qū)；然后將數(shù)個(gè)節(jié)點(diǎn)按照最佳資源分配問(wèn)題的解決方法分配給每個(gè)社區(qū)節(jié)點(diǎn)；每個(gè)社區(qū)根據(jù)分配的節(jié)點(diǎn)利用影響力最大化模型來(lái)找到種子節(jié)點(diǎn)。

關(guān)于節(jié)點(diǎn)之間邊的影響力分析也有很多文獻(xiàn)進(jìn)行了相關(guān)研究，Saito等[7]在研究信息傳播的獨(dú)立級(jí)聯(lián)模型時(shí)討論了這類問(wèn)題，將影響力模型轉(zhuǎn)化成了一種最大似然問(wèn)題進(jìn)行求解。因?yàn)樵撃Ｐ兔看蔚^(guò)程都要對(duì)每條鏈接上的影響力系數(shù)進(jìn)行計(jì)算，時(shí)間復(fù)雜度較高，所以并不適合大規(guī)模社交網(wǎng)絡(luò)中的影響力度量。Barbieri等[8]在Saito等的基礎(chǔ)上討論了多個(gè)主題下的影響力最大化模型，其采用了最大似然估計(jì)。以上這些方法都是基于網(wǎng)絡(luò)中的節(jié)點(diǎn)以往的行為進(jìn)行的估計(jì)。Tang等[9]提出了基于主題的社會(huì)影響力分析的一種方法——TAP（topical affinity propagation）算法。該算法是一種親和傳播[11]聚類算法，首先使用隱藏狄利克雷模型（LDA）將合著者網(wǎng)絡(luò)進(jìn)行主題分布，然后使用親和傳播方法分析節(jié)點(diǎn)間不同主題之間的影響力。相比于以往的算法，TAP算法求解主題間的影響力比較簡(jiǎn)單可行，而且可以定量地分析節(jié)點(diǎn)間的影響力。

無(wú)論是基于節(jié)點(diǎn)還是基于邊的影響力分析，上述影響力最大化問(wèn)題的研究都是在靜態(tài)網(wǎng)絡(luò)中進(jìn)行擴(kuò)散的，然而網(wǎng)絡(luò)本身是動(dòng)態(tài)的，其中的個(gè)體和它們之間的交互隨時(shí)間的推移而變化。Habiba等[10]提出了一種在動(dòng)態(tài)網(wǎng)絡(luò)中進(jìn)行影響力最大化問(wèn)題擴(kuò)散的模型，該模型將在每個(gè)時(shí)間片中進(jìn)行一次擴(kuò)散，上一個(gè)時(shí)間片的激活節(jié)點(diǎn)作為下一個(gè)時(shí)間片的初始激活節(jié)點(diǎn)進(jìn)行擴(kuò)散，直到最后一個(gè)時(shí)間片或者沒有新的被激活節(jié)點(diǎn)時(shí)，擴(kuò)散過(guò)程結(jié)束。然而，上述模型中的每個(gè)時(shí)間片是相互獨(dú)立的，沒有考慮到時(shí)間片之間影響力的聯(lián)系，并且，模型中將影響力值設(shè)置為同一個(gè)值，很顯然是違背實(shí)際情況的。

綜上所述，社會(huì)網(wǎng)絡(luò)是動(dòng)態(tài)的，影響力的傳播在時(shí)間片中的激活概率也不是一成不變的。為此，本文提出一種加入衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)獨(dú)立級(jí)聯(lián)（DDIC，decay dynamic network independent cascade）模型。本文工作主要體現(xiàn)在2個(gè)方面：1) 影響力在某個(gè)時(shí)間片中建立以后，在后續(xù)的時(shí)間片中如果這2個(gè)節(jié)點(diǎn)依然存在連接，那么這2個(gè)節(jié)點(diǎn)之間的影響力不應(yīng)該只考慮這個(gè)時(shí)間片中的影響力，需要考慮以前影響力的累加，針對(duì)這個(gè)問(wèn)題 DDIC模型引入衰減因數(shù)；2) 在社會(huì)網(wǎng)絡(luò)中由于存在著個(gè)體差異，個(gè)體之間的影響力不會(huì)是相同的，針對(duì)這個(gè)問(wèn)題，DDIC模型中個(gè)體之間的影響力采用親和傳播的方法來(lái)計(jì)算節(jié)點(diǎn)之間的影響力值。

3 動(dòng)態(tài)網(wǎng)絡(luò)中影響力擴(kuò)散問(wèn)題

3.1 動(dòng)態(tài)網(wǎng)絡(luò)

靜態(tài)網(wǎng)絡(luò)獨(dú)立級(jí)聯(lián)模型都是基于一種合成網(wǎng)絡(luò)來(lái)進(jìn)行擴(kuò)散的，這種合成網(wǎng)絡(luò)展現(xiàn)了在一定的時(shí)間內(nèi)所觀察到的全部個(gè)體和個(gè)體之間的交互。這種網(wǎng)絡(luò)只能展現(xiàn)一段時(shí)間內(nèi)所有個(gè)體之間交互的疊加，并不能反映出節(jié)點(diǎn)和邊出現(xiàn)的時(shí)序信息。

動(dòng)態(tài)網(wǎng)絡(luò)是由有限個(gè)靜態(tài)網(wǎng)絡(luò)按照一定的時(shí)間序列構(gòu)成的一組網(wǎng)絡(luò)。其中，每一個(gè)靜態(tài)網(wǎng)絡(luò)是網(wǎng)絡(luò)中所有個(gè)體以及個(gè)體之間相互交互的在某個(gè)時(shí)間的一個(gè)快照。動(dòng)態(tài)網(wǎng)絡(luò)描述了在一段時(shí)間內(nèi)網(wǎng)絡(luò)的演化過(guò)程。如圖1所示，上半部分前3個(gè)圖表示了從時(shí)間序列T1到時(shí)間序列T3節(jié)點(diǎn)A至節(jié)點(diǎn)E之間的相互聯(lián)系，最后一個(gè)圖是時(shí)間片T1、T2、T3合成的靜態(tài)網(wǎng)絡(luò)，下半部分的圖也是一樣的。由圖1可以看出，節(jié)點(diǎn)A至節(jié)點(diǎn)E在2個(gè)部分時(shí)間片T1、T2、T3中邊是不同的，而合成的靜態(tài)網(wǎng)絡(luò)是一樣的。由此，可以清晰地看出合成靜態(tài)網(wǎng)絡(luò)會(huì)損失網(wǎng)絡(luò)演化中的時(shí)序信息。

圖1基于時(shí)間片的網(wǎng)絡(luò)與靜態(tài)網(wǎng)絡(luò)

3.2 加入衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)獨(dú)立級(jí)聯(lián)模型

DDIC模型中的節(jié)點(diǎn)狀態(tài)采用與靜態(tài)網(wǎng)絡(luò)中的節(jié)點(diǎn)狀態(tài)一致的方式，也具有2種狀態(tài)：激活態(tài)和未激活態(tài)，每個(gè)節(jié)點(diǎn)的狀態(tài)只能從未激活態(tài)轉(zhuǎn)為激活態(tài)而不能反轉(zhuǎn)。

在DDIC模型中，首先輸入的是種子節(jié)點(diǎn)集合A0∈I。在加入衰減因數(shù)動(dòng)態(tài)網(wǎng)絡(luò)中每個(gè)已經(jīng)激活的節(jié)點(diǎn)vt在時(shí)間序列t的網(wǎng)絡(luò)中去嘗試激活它的未被激活的鄰居節(jié)點(diǎn)wt，wt是否被激活取決于vt和wt之間的影響力概率。

在DDIC模型中激活概率定義如下：如果在時(shí)間片t?1中節(jié)點(diǎn)v和節(jié)點(diǎn)w有鏈接，而在時(shí)間片t中，節(jié)點(diǎn)v和節(jié)點(diǎn)w也有鏈接時(shí)，那么在時(shí)間片t中節(jié)點(diǎn)v和節(jié)點(diǎn)w之間的激活概率為

如果當(dāng)wt有多個(gè)鄰居節(jié)點(diǎn)處于激活狀態(tài)時(shí)，這些激活節(jié)點(diǎn)對(duì)wt的影響是隨機(jī)的、獨(dú)立的。如果在時(shí)刻t的網(wǎng)絡(luò)中vt成功地把它的鄰居節(jié)點(diǎn)wt激活，那么在下一個(gè)時(shí)間片中不管vt+1和wt+1之間是否存在邊(vt+1,wt+1)∈Et+1，wt+1都是具有影響力的節(jié)點(diǎn)。如果在時(shí)間序列t的靜態(tài)網(wǎng)絡(luò)中vt沒有將wt成功激活，那么在以后的時(shí)間序列中，如果vT和wT中存在邊(vT, wT)∈ET，vT將嘗試激活wT。如果整個(gè)擴(kuò)散過(guò)程沒有新的被激活節(jié)點(diǎn)或者擴(kuò)散已經(jīng)達(dá)到最后一個(gè)時(shí)間片，那么擴(kuò)散結(jié)束。

圖2基于時(shí)間片網(wǎng)絡(luò)的獨(dú)立級(jí)聯(lián)模型

圖2簡(jiǎn)單描述了DDIC模型的過(guò)程，開始選擇節(jié)點(diǎn)A為種子節(jié)點(diǎn)，在T=1的網(wǎng)絡(luò)中節(jié)點(diǎn)A激活了它的鄰居節(jié)點(diǎn)B。在T=2的網(wǎng)絡(luò)中節(jié)點(diǎn)A又激活了它的鄰居節(jié)點(diǎn)D，此時(shí)節(jié)點(diǎn)A和節(jié)點(diǎn)B中已經(jīng)沒有了邊，而節(jié)點(diǎn)B一樣具有影響力并且激活了它的2個(gè)鄰居節(jié)點(diǎn)。在T=3的網(wǎng)絡(luò)中種子節(jié)點(diǎn)A和它的鄰居節(jié)點(diǎn)C又重新連接，并且節(jié)點(diǎn)A成功激活了節(jié)點(diǎn)C。

DDIC模型可以分為2個(gè)步驟來(lái)理解。1) 對(duì)于每個(gè)時(shí)刻對(duì)應(yīng)的靜態(tài)網(wǎng)絡(luò)采取“拋硬幣”來(lái)確定網(wǎng)絡(luò)中對(duì)應(yīng)的節(jié)點(diǎn)間的通路邊。節(jié)點(diǎn)v和節(jié)點(diǎn)w在時(shí)刻t的邊概率值pvtwt表征了這個(gè)邊在多大程度上能夠被選為通路邊，圖3簡(jiǎn)單描述了圖2的3個(gè)時(shí)間序列的時(shí)間片網(wǎng)絡(luò)通過(guò)“拋硬幣”的方式產(chǎn)生的通路邊。2) 選擇合適的節(jié)點(diǎn)作為模型開始的種子節(jié)點(diǎn)也就是那些能夠使更多的節(jié)點(diǎn)被激活的節(jié)點(diǎn)。首先在T=1的靜態(tài)網(wǎng)絡(luò)中種子節(jié)點(diǎn)進(jìn)行擴(kuò)散，此時(shí)的擴(kuò)散就是根據(jù)步驟1)找到的通路邊進(jìn)行的擴(kuò)散，如果種子節(jié)點(diǎn)的鄰居節(jié)點(diǎn)與種子節(jié)點(diǎn)之間有通路邊，該鄰居節(jié)點(diǎn)就會(huì)被激活。在T=1的靜態(tài)網(wǎng)絡(luò)中擴(kuò)散后已經(jīng)處于激活態(tài)的節(jié)點(diǎn)集合作為T=2的靜態(tài)網(wǎng)絡(luò)的種子節(jié)點(diǎn)，按照同樣的方法在T=2的靜態(tài)網(wǎng)絡(luò)中進(jìn)行擴(kuò)散，重復(fù)這一過(guò)程直到模型結(jié)束，最終得到的節(jié)點(diǎn)集合為最后一個(gè)時(shí)間序列中激活的節(jié)點(diǎn)總數(shù)。

圖3基于時(shí)間片網(wǎng)絡(luò)的通路邊

Kempe等證明了靜態(tài)網(wǎng)絡(luò)中的獨(dú)立級(jí)聯(lián)模型是一個(gè)NP難題。靜態(tài)網(wǎng)絡(luò)中的獨(dú)立級(jí)聯(lián)模型相當(dāng)于在同一個(gè)時(shí)間序列網(wǎng)絡(luò)中展開的，而加入衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)獨(dú)立級(jí)聯(lián)模型在每個(gè)時(shí)間序列中的擴(kuò)散過(guò)程和在靜態(tài)網(wǎng)絡(luò)中的擴(kuò)散過(guò)程是一樣的。所以，加入衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)獨(dú)立級(jí)聯(lián)模型也是一個(gè)NP難題。Kempe等證明了對(duì)于應(yīng)用靜態(tài)網(wǎng)絡(luò)中獨(dú)立級(jí)聯(lián)模型的任意實(shí)例，影響力結(jié)果函數(shù)具有子模特性。對(duì)于基于時(shí)間片網(wǎng)絡(luò)的獨(dú)立級(jí)聯(lián)模型來(lái)說(shuō)，影響力結(jié)果函數(shù)也具有子模特性。

3.3 基于親和傳播的激活概率

獨(dú)立級(jí)聯(lián)模型在進(jìn)行影響力的擴(kuò)散時(shí)節(jié)點(diǎn)間的激活概率為了簡(jiǎn)化模型統(tǒng)一設(shè)置成 0.01或其他的一個(gè)定值，這顯然是不符合現(xiàn)實(shí)情況的，在現(xiàn)實(shí)中每個(gè)人對(duì)他的朋友的影響程度是不同的。

本節(jié)對(duì)TAP算法進(jìn)行了改進(jìn)，使節(jié)點(diǎn)相似性函數(shù)只涉及單個(gè)主題，具體如式(2)所示。

其中，NB(i)表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合，wij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的邊的權(quán)重值，這個(gè)權(quán)重值的定義可以有多種形式，如在通話記錄網(wǎng)絡(luò)中可以定義為節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的通話時(shí)長(zhǎng)。式(2)可以解釋為：如果節(jié)點(diǎn) vi和節(jié)點(diǎn) vj之間有較高的相似性或者權(quán)重，那么節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間有比較大的影響力；如果節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)都認(rèn)為節(jié)點(diǎn)vi對(duì)自己有較高的影響力，那么節(jié)點(diǎn)vi對(duì)自己具有較大影響力是有信心的。

對(duì)節(jié)點(diǎn)相似性函數(shù)g(vi,vj)進(jìn)行對(duì)數(shù)歸一化得到相似性矩陣。

其中，bij表示節(jié)點(diǎn)j和節(jié)點(diǎn)i之間的特征函數(shù)值與節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)的特征函數(shù)值的比值，這個(gè)比值越大說(shuō)明在節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)中節(jié)點(diǎn)j相對(duì)于其他節(jié)點(diǎn)對(duì)節(jié)點(diǎn)i越有影響力。

TAP算法利用因子圖理論推導(dǎo)出了基于主題的親和傳播影響力算法的更新規(guī)則，在此基礎(chǔ)上對(duì)更新規(guī)則做了調(diào)整使更新規(guī)則只在一個(gè)主題內(nèi)展開，即不考慮主題的影響。

更新規(guī)則r表示了節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)j對(duì)其有影響的積累證據(jù)。更新規(guī)則a表示節(jié)點(diǎn)j認(rèn)為自己可以影響節(jié)點(diǎn)i的積累證據(jù)。

更新規(guī)則a和r說(shuō)明了節(jié)點(diǎn)j對(duì)節(jié)點(diǎn)i的影響力，而對(duì)于一個(gè)社會(huì)網(wǎng)絡(luò)圖希望得到的影響力概率值是一個(gè)介于[0,1]之間的值pij，并且表示節(jié)點(diǎn)i對(duì)于節(jié)點(diǎn)j的影響程度，所以定義為

算法1基于親和傳播的激活概率算法

輸入社會(huì)網(wǎng)絡(luò)圖G(V, E)

輸出節(jié)點(diǎn)間的影響力概率值

1) 計(jì)算節(jié)點(diǎn)間特征函數(shù)值(vi, vj) //計(jì)算節(jié)點(diǎn)間的相似性值

2) 計(jì)算bij//根據(jù)式(3)計(jì)算bij的值

3) 初始化所有rij←0//初始化所有rij的值為0

4) Repeat //進(jìn)行迭代計(jì)算

5)for eijdo

6) 更新 rij；//根據(jù)式(4)計(jì)算 rij的值

7)end

8)for vjdo

9) 更新 ajj；//根據(jù)式(5)計(jì)算 ajj的值

10)end

11)for eijdo

12)更新 aij；//根據(jù)式(6)計(jì)算 aij的值

13)end

14) until convergence//直到收斂

15) for eijdo

16)計(jì)算 pij； //根據(jù)式(7)計(jì)算 pij的值

17) end// pij為計(jì)算出的節(jié)點(diǎn)間影響力

4 實(shí)驗(yàn)分析

實(shí)驗(yàn)采用“9·11事件”的數(shù)據(jù)集，該數(shù)據(jù)集一共包含400個(gè)節(jié)點(diǎn)以及這400個(gè)節(jié)點(diǎn)之間相互聯(lián)系的10個(gè)時(shí)間片。在每個(gè)時(shí)間片中，如果2個(gè)人之間有電話聯(lián)系，那么2個(gè)人之間就會(huì)有一條邊且通話時(shí)長(zhǎng)為邊的權(quán)重值。每個(gè)時(shí)間片中所含有的邊數(shù)如表1所示。本文一共進(jìn)行了3組對(duì)比實(shí)驗(yàn)，分別是：靜態(tài)網(wǎng)絡(luò)和動(dòng)態(tài)網(wǎng)絡(luò)中的獨(dú)立級(jí)聯(lián)模型與DDIC模型貪心算法對(duì)比；動(dòng)態(tài)網(wǎng)絡(luò)與加入衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)獨(dú)立級(jí)聯(lián)模型3種算法對(duì)比；激活概率設(shè)置為固定值0.04與親和傳播概率對(duì)比。在實(shí)驗(yàn)中設(shè)定模擬傳播次數(shù)R為100次，為了簡(jiǎn)化計(jì)算將衰減因數(shù)α的值設(shè)置為0.5。

表1每個(gè)時(shí)間片中所含有的邊數(shù)

4.1 靜態(tài)網(wǎng)絡(luò)與DDIC模型使用貪心算法的對(duì)比

該實(shí)驗(yàn)選擇3種網(wǎng)絡(luò)：T1時(shí)間片網(wǎng)絡(luò)、10個(gè)時(shí)間片合成的靜態(tài)網(wǎng)絡(luò)、加入衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)。圖4(a)表示了在3種網(wǎng)絡(luò)中使用貪心算法最終的激活節(jié)點(diǎn)數(shù)目進(jìn)行對(duì)比?？梢钥闯?，在加入衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)中獨(dú)立級(jí)聯(lián)模型中激活的節(jié)點(diǎn)數(shù)目比在單一的時(shí)間片中以及合成靜態(tài)網(wǎng)絡(luò)中激活的節(jié)點(diǎn)數(shù)目要多很多，這主要是因?yàn)樵陟o態(tài)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)只有一次機(jī)會(huì)去激活它的鄰居節(jié)點(diǎn)，而在加入衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)，可以有多次機(jī)會(huì)去激活它的鄰居節(jié)點(diǎn)，所以加入衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)激活的節(jié)點(diǎn)數(shù)目要比靜態(tài)網(wǎng)絡(luò)中激活的數(shù)目多。

圖43種網(wǎng)絡(luò)中使用貪心算法進(jìn)行擴(kuò)散對(duì)比

圖4(b)表示了在3種網(wǎng)絡(luò)中使用貪心算法最終的所用時(shí)間對(duì)比。可以看出，在加入衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)中，使用貪心算法進(jìn)行確定種子節(jié)點(diǎn)集比在靜態(tài)網(wǎng)絡(luò)中使用貪心算法確定種子節(jié)點(diǎn)集所用的時(shí)間要長(zhǎng)。這是因?yàn)樵陟o態(tài)網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)只有一次機(jī)會(huì)去影響它的鄰居節(jié)點(diǎn)，所以整個(gè)擴(kuò)散過(guò)程一般在擴(kuò)散 3輪左右就可完成，而在加入衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)有多次機(jī)會(huì)去激活它的鄰居節(jié)點(diǎn)，所以激活的節(jié)點(diǎn)數(shù)目多，整個(gè)擴(kuò)散過(guò)程比較長(zhǎng)，一般要擴(kuò)散 7輪左右才可以結(jié)束擴(kuò)散過(guò)程，而貪心算法要進(jìn)行 100次的模擬傳播。所以這樣加入衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)在使用貪心算法進(jìn)行確定種子節(jié)點(diǎn)的傳播中要比靜態(tài)網(wǎng)絡(luò)所使用的時(shí)間要長(zhǎng)。

由圖4還可以看出，在合成靜態(tài)網(wǎng)絡(luò)中的激活節(jié)點(diǎn)數(shù)目和所用時(shí)間都比在一個(gè)時(shí)間片中要大，這是因?yàn)楹铣傻木W(wǎng)絡(luò)中的邊比單一的時(shí)間片網(wǎng)絡(luò)要多，所以激活節(jié)點(diǎn)的數(shù)目要多。

4.2 貪心算法、NewGreedy算法、HT算法在DDIC模型中擴(kuò)散的情況

該實(shí)驗(yàn)選擇文獻(xiàn)[4]中提出的 NewGreedy和文獻(xiàn)[8]提出的HT算法與貪心算法進(jìn)行對(duì)比。由于DDIC模型和靜態(tài)網(wǎng)絡(luò)中的獨(dú)立級(jí)聯(lián)模型一樣都是 NP難題，同時(shí)都具有子模特性，貪心算法以及改進(jìn)后的貪心算法同樣能夠在DDIC模型中使用。

如圖5(a)所示，在加入衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)中使用貪心算法、NewGreedy算法、HT算法以及隨機(jī)選擇算法（在400個(gè)節(jié)點(diǎn)中隨機(jī)選擇n個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)集）對(duì)獨(dú)立級(jí)聯(lián)模型進(jìn)行種子節(jié)點(diǎn)集的確定的結(jié)果對(duì)比。由圖5(a)可以看出，在準(zhǔn)確率上，貪心算法和NewGreedy相差不大，而HT算法表現(xiàn)比前面2種算法要稍差一些，這是因?yàn)镠T算法在進(jìn)行種子節(jié)點(diǎn)確定的時(shí)候是基于去邊的方法，這種方法會(huì)損失掉很多邊所以造成結(jié)果不準(zhǔn)確。而隨機(jī)選擇算法的結(jié)果會(huì)出現(xiàn)震蕩，因?yàn)橥ㄟ^(guò)隨機(jī)數(shù)的方法找的點(diǎn)是不可靠的。圖5(b)表示了3種算法及隨機(jī)選擇算法所用時(shí)間對(duì)比，可以看出貪心算法所用的時(shí)間是最長(zhǎng)的，比NewGreedy和HT算法要長(zhǎng)很多，其次是NewGreedy算法，最好的是HT算法。因?yàn)殡S機(jī)選擇算法比前3種算法所用時(shí)間少很多，故在圖5(b)中不能表現(xiàn)出來(lái)。

在靜態(tài)網(wǎng)絡(luò)中也同樣做了這 3個(gè)算法的對(duì)比，得到的結(jié)果和在加入衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)上的結(jié)果是一致的。可以得出結(jié)論：貪心算法在靜態(tài)網(wǎng)絡(luò)和基于時(shí)間片網(wǎng)絡(luò)中確定種子節(jié)點(diǎn)集是準(zhǔn)確的，但是由于時(shí)間復(fù)雜度太大，貪心算法不適合節(jié)點(diǎn)和鏈接較多的網(wǎng)絡(luò)；NewGreedy在2種網(wǎng)絡(luò)中確定種子節(jié)點(diǎn)集時(shí)準(zhǔn)確程度和貪心相差不大而且具有較小的時(shí)間復(fù)雜度，適合在大型網(wǎng)絡(luò)中使用；HT算法雖然有較好的時(shí)間復(fù)雜度，但結(jié)果的準(zhǔn)確性稍差一點(diǎn)。

圖5在加入衰減因數(shù)動(dòng)態(tài)網(wǎng)絡(luò)中3種算法及隨機(jī)選擇算法的對(duì)比

4.3 親和傳播的比較分析

圖6在DDIC模型中2種設(shè)定激活概率方法進(jìn)行擴(kuò)散的對(duì)比

在DDIC模型使用固定激活概率和使用親和傳播的影響力之間的結(jié)果對(duì)比，該實(shí)驗(yàn)中分別對(duì)2種節(jié)點(diǎn)間激活概率值的設(shè)定方法進(jìn)行實(shí)驗(yàn)對(duì)比。其中，方法1是將節(jié)點(diǎn)間的激活概率統(tǒng)一設(shè)置為平均概率值0.04，方法2是使用親和傳播求出的概率值作為節(jié)點(diǎn)間激活概率值，如表2所示，在這部分實(shí)驗(yàn)中使用貪心算法來(lái)確定種子節(jié)點(diǎn)集。

表2親和傳播概率的平均值

表3為在DDIC模型中用2種方法所確定的排名前20的影響力節(jié)點(diǎn)，通過(guò)對(duì)比可以發(fā)現(xiàn)2種方法所找到的節(jié)點(diǎn)的排名是不一樣的。

圖6所示為DDIC模型中2種設(shè)定激活概率進(jìn)行擴(kuò)散的對(duì)比，可以看出在激活概率設(shè)定為0.04的擴(kuò)散結(jié)果中，激活節(jié)點(diǎn)數(shù)目要比使用親和傳播影響力概率值所激活的節(jié)點(diǎn)數(shù)目多，這可能是因?yàn)槭褂糜H和傳播所求出的一部分影響力是大于平均影響力0.04，而大部分影響力是低于0.04，這樣造成了第一種方法要比第二種方法所激活的節(jié)點(diǎn)數(shù)目多。而且，使用親和傳播求出的概率值是根據(jù)邊與邊的權(quán)重值計(jì)算出來(lái)的相鄰節(jié)點(diǎn)之間的影響力概率值，比統(tǒng)一設(shè)置成 0.04能更加準(zhǔn)確地表現(xiàn)出DDIC模型的傳播過(guò)程。

表3在DDIC模型中用2種方法所確定的排名前20的影響力節(jié)點(diǎn)

5 結(jié)束語(yǔ)

本文以獨(dú)立級(jí)聯(lián)模型為基礎(chǔ)，研究了獨(dú)立級(jí)聯(lián)模型在動(dòng)態(tài)網(wǎng)絡(luò)中的擴(kuò)散問(wèn)題，并且提出了加入衰減因數(shù)的獨(dú)立級(jí)聯(lián)模型。與傳統(tǒng)的動(dòng)態(tài)網(wǎng)絡(luò)中的獨(dú)立級(jí)聯(lián)模型不同，本文提出的加入衰減因數(shù)的獨(dú)立級(jí)聯(lián)模型 DDIC將動(dòng)態(tài)網(wǎng)絡(luò)中各時(shí)間片之間的影響力關(guān)聯(lián)起來(lái)，并采用親和傳播來(lái)計(jì)算相鄰節(jié)點(diǎn)之間的影響力概率值，使模型更能貼近真實(shí)的社會(huì)網(wǎng)絡(luò)影響力的傳播。本文通過(guò)對(duì)比實(shí)驗(yàn)可以得到以下結(jié)論：加入衰減因數(shù)的獨(dú)立級(jí)聯(lián)模型中由于每個(gè)節(jié)點(diǎn)有多次機(jī)會(huì)激活它的鄰居節(jié)點(diǎn)，所以比靜態(tài)網(wǎng)絡(luò)中激活的節(jié)點(diǎn)數(shù)目要多；DDIC模型由于引入衰減因數(shù)使平均激活概率比不引人衰減因數(shù)的動(dòng)態(tài)網(wǎng)絡(luò)要高，所以激活的節(jié)點(diǎn)數(shù)目也多；在靜態(tài)網(wǎng)絡(luò)中適用的貪心算法在 DDIC模型中也同樣適用；在 DDIC模型中采用親和傳播計(jì)算節(jié)點(diǎn)之間的影響力與將影響力值設(shè)置為固定值所得到的種子節(jié)點(diǎn)是不同的，親和傳播能更好地體現(xiàn)出DDIC模型的傳播過(guò)程。

[1]RICHARDSON M, DOMINGOS P. Mining knowledge-sharing sites for viral marketing[C]//KDD '02 Proceedings of the Eighth ACM SIGKDD International Conference. 2002: 61-70.

[2]KEMPE D, KLEINBERG J M, TARDOS A. Maximizing the spread of influence through a social network[C]//The 9th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2003: 137-146.

[3]LESKOVEC J, KRAUSE A, GUESTRIN C. Cost-effective outbreak detection in networks[C]//The 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2007: 420-429.

[4]CHEN W, WANG Y, YANG S. Efficient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference. 2009: 199-208.

[5]GALSTYAN A, MUSOYAN V, COHEN P R. Maximizing influence propagation in networks with community structure[J]. Physical Review E Statistical Nonlinear amp; Soft Matter Physics, 2009, 79(2): 711-715.

[6]CAO T Y, WU X D, WANG S, et al. OASNET: an optimal allocation approach to influence maximization in modular social networks[J].ACM Symposium on Applied Computing, 2010: 1088-1094.

[7]SAITO K, NAKANO R, KIMURA M. Prediction of information diffusion probabilities for independent cascade model[J]. Knowledge-Based Intelligent Information and Engineering Systems Lecture Notes in Computer Science, 2008: 67-75.

[8]BARBIERI N, BONCHI F, MANCO G. Topic-aware social influence propagation models[J].Knowledge and Information Systems, 2013:2012,37(3): 81-90.

[9]TANG J, SUN J M, WANG C. Social influence analysis in large-scale networks[C]//The 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2009: 807-816.

[10]FREY B J, DUECK D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976.

[11]HABIBA T W B, BERGER-WOLF T Y. Maximizing the extent of spread in a dynamic network[J].Technical Report 20. DIMACS, 2007.

Influence diffusion model based on affinity of dynamic social network

CHEN Yun-fang1, XIA Tao1,2, ZHANG Wei1, LI Jin3
(1. School of Computer Science and Technology, Nanjing University of Posts and Telecommunications, Nanjing 210003, China;2. Jining Branch of China Telecom., Jining 272000, China;3. School of Public Administration and Communication, Beijing University of Information Science and Technology, Beijing 100192, China)

Recently, influence maximization model is a hot issue in the field of social network influence, while the traditional independent cascade model is generally based on static network with a fixed value of activation probability. DDIC model, which was a dynamic network influence diffusion model with attenuation factor was proposed. It calculated the activation probability between nodes via affinity propagation, and according with dynamic segmentation of social network time slice, calculation of influence on proliferation of next time slice with the current time slice of activation probability performance decay. The experimental results show that the nodes in the DDIC model have more chances to active the neighbor and the average probability of activing of the DDIC model is higher. Further experiments show that influence value via computing with affinity propagation can reflect the process of the spread model more accurately.

dynamic social network, influence diffusion, affinity propagation

s:The National Natural Science Foundation of China (No.61272422), Humanistic and Social Science Research Plan Project of Beijing Municipal Education Commission (No. SM201411232005)

TP393

A

10.11959/j.issn.1000-436x.2016194

2015-09-08；

2016-08-29

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61272422）；北京市教育委員會(huì)人文社會(huì)科學(xué)研究計(jì)劃面上基金資助項(xiàng)目（No.SM201411232005）

陳云芳（1976-），男，江蘇鎮(zhèn)江人，博士，南京郵電大學(xué)副教授，主要研究方向?yàn)榫W(wǎng)絡(luò)安全、社會(huì)網(wǎng)絡(luò)、大數(shù)據(jù)分析等。

夏濤（1989-），男，山東濟(jì)寧人，碩士，中國(guó)電信濟(jì)寧分公司工程師，主要研究方向?yàn)樯鐣?huì)計(jì)算、社會(huì)影響力。

張偉（1973-），男，江蘇泰興人，博士，南京郵電大學(xué)教授，主要研究方向?yàn)樯鐣?huì)網(wǎng)絡(luò)分析、隱私保護(hù)、惡意代碼分析等。

李晉（1977-），女，山西長(zhǎng)治人，北京信息科技大學(xué)講師，主要研究方向?yàn)榫W(wǎng)絡(luò)與新媒體傳播。