節(jié)點(diǎn)傳播能力的偏好隨機(jī)行走的信息傳播方法

李維勇，孔 楓，張 偉，陳云芳

1.南京信息職業(yè)技術(shù)學(xué)院 網(wǎng)絡(luò)與通信學(xué)院，南京210023

2.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，南京210023

1 引言

近年來(lái)，隨著社交網(wǎng)絡(luò)的發(fā)展，對(duì)于社交網(wǎng)絡(luò)中的信息傳播的研究一直很活躍。在實(shí)際的在線社交網(wǎng)絡(luò)中，用戶(hù)活動(dòng)一直是呈現(xiàn)出爆炸式的增長(zhǎng)的，例如在Facebook、Twitter 和Google+這些網(wǎng)絡(luò)和微博中，十幾億的用戶(hù)每天都處在分享熱點(diǎn)信息的過(guò)程中。使用這些交流工具，人們可以和世界各地的朋友和追隨者在圈子中交流想法、觀點(diǎn)、視頻和照片等等。這些互動(dòng)產(chǎn)生了空前的數(shù)據(jù)量，這些數(shù)據(jù)量可以作為衡量社交的觀察容器，并通過(guò)定量的方法來(lái)闡明人類(lèi)社交的交流機(jī)制[1-6]。

如何在復(fù)雜的社交網(wǎng)絡(luò)中找到最大的傳播范圍已成為許多領(lǐng)域的熱門(mén)話題，包括社會(huì)學(xué)、生物信息學(xué)和物理學(xué)。目前關(guān)于社交媒體的研究主要包含2個(gè)主題：傳播以及它的社會(huì)網(wǎng)絡(luò)結(jié)構(gòu)。大多數(shù)網(wǎng)絡(luò)模型都將重點(diǎn)放在系統(tǒng)的結(jié)構(gòu)增長(zhǎng)（稱(chēng)之為網(wǎng)絡(luò)的動(dòng)態(tài)）或信息傳播過(guò)程（在網(wǎng)絡(luò)上發(fā)生的動(dòng)態(tài)）上。社交網(wǎng)絡(luò)中的節(jié)點(diǎn)往往具有共同的興趣或背景，那么當(dāng)熱點(diǎn)信息吸引網(wǎng)絡(luò)中的用戶(hù)時(shí)，會(huì)導(dǎo)致網(wǎng)絡(luò)中的信息以一定的規(guī)則在用戶(hù)中進(jìn)行傳播，這些被傳播的網(wǎng)絡(luò)用戶(hù)集合可以簡(jiǎn)化對(duì)整個(gè)網(wǎng)絡(luò)的功能分析。

現(xiàn)有的很多模型都在描述消息的傳播過(guò)程，例如獨(dú)立級(jí)聯(lián)模型[7]、線性閾值模型[8]、基于數(shù)據(jù)的信用分部模型[9]和線性社交影響模型[10]等。在這些模型中，獨(dú)立級(jí)聯(lián)模型和線性閾值模型是隨機(jī)擴(kuò)散模型。上述模型中的節(jié)點(diǎn)只存在兩種狀態(tài)：活躍和非活躍。活躍節(jié)點(diǎn)可以被視為接受了這條消息并會(huì)再次傳播這條消息的節(jié)點(diǎn)；而非活躍節(jié)點(diǎn)則是未被激活且不會(huì)傳播這條消息的節(jié)點(diǎn)。然而，在實(shí)際傳播中非活躍節(jié)點(diǎn)也存在兩種類(lèi)型。例如，對(duì)于一條發(fā)布在Twitter 上的消息，有些用戶(hù)會(huì)轉(zhuǎn)發(fā)這條消息，有些用戶(hù)則不會(huì)。但是在沒(méi)有轉(zhuǎn)發(fā)的用戶(hù)中，有些人由于鄰居節(jié)點(diǎn)的轉(zhuǎn)發(fā)而得知了這條消息成為消息節(jié)點(diǎn)，其余節(jié)點(diǎn)為真正的非活躍節(jié)點(diǎn)。可以推斷，一個(gè)節(jié)點(diǎn)想要成為消息節(jié)點(diǎn)，那么它的鄰居節(jié)點(diǎn)中至少有一個(gè)為活躍狀態(tài)；相反，如果一個(gè)節(jié)點(diǎn)的全部鄰居節(jié)點(diǎn)都為非活躍狀態(tài)，那么此節(jié)點(diǎn)永遠(yuǎn)不可能成為消息節(jié)點(diǎn)?，F(xiàn)實(shí)世界中消息節(jié)點(diǎn)的數(shù)量非常龐大，但是由于影響力最大化問(wèn)題只考慮活躍節(jié)點(diǎn)而忽略了消息節(jié)點(diǎn)，所以它不能很好地模擬現(xiàn)實(shí)世界。為了更好地衡量信息覆蓋范圍，應(yīng)將這兩類(lèi)不會(huì)再次傳播消息的節(jié)點(diǎn)都列入考慮范圍。因此，考慮從非活躍節(jié)點(diǎn)中找出消息節(jié)點(diǎn)，并發(fā)掘消息節(jié)點(diǎn)的價(jià)值，以更好地衡量信息覆蓋范圍。

而隨機(jī)行走是一種不規(guī)則的、布朗運(yùn)動(dòng)的數(shù)學(xué)理想狀態(tài)，在許多領(lǐng)域都有重要的應(yīng)用，其中在計(jì)算機(jī)領(lǐng)域一個(gè)很有名的例子就是Google的PageRank算法。近年來(lái)，在信息傳播領(lǐng)域中加入了一種基于隨機(jī)行走的概率方法，但是當(dāng)隨機(jī)行走偏向于遠(yuǎn)離穩(wěn)定狀態(tài)所占的區(qū)域方向時(shí)就產(chǎn)生了一個(gè)有趣的問(wèn)題，在什么條件下傳播速率和偏向會(huì)導(dǎo)致傳播的結(jié)果停滯不前呢?；蛘邚南喾吹姆较騺?lái)說(shuō)，當(dāng)普通的隨機(jī)行走在不同的方向上具有偏差時(shí)，維持正常的傳播速率的偏差臨界值是多少呢。因此，本文提出了一種基于節(jié)點(diǎn)傳播能力的偏向性隨機(jī)行走的信息傳播方法，該方法的創(chuàng)新性體現(xiàn)在以下3個(gè)方面：

（1）將每個(gè)節(jié)點(diǎn)的信息傳播能力，即網(wǎng)絡(luò)中節(jié)點(diǎn)能承受的傳播的信息的內(nèi)容量，納入信息傳播的關(guān)鍵因素。

（2）提出了一種新的隨機(jī)行走方法，即偏向性隨機(jī)行走，通過(guò)偏向性參數(shù)來(lái)控制隨機(jī)行走的方向，使得隨機(jī)行走不再是漫無(wú)目的的無(wú)規(guī)則行走。

（3）利用以上兩個(gè)參數(shù)結(jié)合作為衡量節(jié)點(diǎn)成為活躍節(jié)點(diǎn)和消息節(jié)點(diǎn)的重要屬性，得到信息傳播范圍最大化函數(shù)來(lái)使得活躍節(jié)點(diǎn)和消息節(jié)點(diǎn)的集合達(dá)到最大。

2 相關(guān)研究

隨著社交網(wǎng)絡(luò)的發(fā)展，對(duì)于信息傳播模型的研究一直很活躍，社會(huì)網(wǎng)絡(luò)是由許多節(jié)點(diǎn)構(gòu)成的一種社會(huì)結(jié)構(gòu)，節(jié)點(diǎn)通常是指?jìng)€(gè)人或組織，商業(yè)領(lǐng)域中的“口碑營(yíng)銷(xiāo)”是社會(huì)網(wǎng)絡(luò)中重要的應(yīng)用場(chǎng)景，該種形式同樣適用于信息和影響力的傳播過(guò)程，因此，社會(huì)網(wǎng)絡(luò)在信息的傳播中起到至關(guān)重要的媒介作用[11]。其中通過(guò)在社會(huì)網(wǎng)絡(luò)中找到一個(gè)具有一定影響力的個(gè)體組成的小群體繼而能夠影響社會(huì)網(wǎng)絡(luò)中數(shù)量最多的人是以“口碑”[12-15]形式的信息傳播的根本目的。

Gomez 等[16]提出了依據(jù)激活節(jié)點(diǎn)和其每個(gè)鄰居節(jié)點(diǎn)之間的相關(guān)性，從而推斷出傳播級(jí)聯(lián)的結(jié)構(gòu)。假設(shè)活躍的節(jié)點(diǎn)以一定的概率影響其每個(gè)鄰居節(jié)點(diǎn)，并且節(jié)點(diǎn)之間是相互獨(dú)立的影響，他們稱(chēng)其為NETINF方法。該方法構(gòu)建一個(gè)概率模型，該模型需要解決在一個(gè)固定的假想網(wǎng)絡(luò)中，級(jí)聯(lián)是如何作為有向樹(shù)來(lái)傳播的（擴(kuò)散級(jí)聯(lián)即在一棵有向樹(shù)中，激活序列的第一個(gè)節(jié)點(diǎn)稱(chēng)其為有向樹(shù)的根節(jié)點(diǎn)，由于一個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)不會(huì)被重復(fù)感染，所以消息傳播的路徑中不存在回路，此時(shí)的消息傳播就可以被視為一種有向樹(shù)的傳播形式）。

后來(lái)Gomez 等人又?jǐn)U展了NETINF 算法[17]，稱(chēng)為NETRAT 算法，通過(guò)觀察傳染性來(lái)推斷底層傳播的過(guò)程，傳播的過(guò)程發(fā)生在未知的網(wǎng)絡(luò)圖中，節(jié)點(diǎn)是否感染只有2種狀態(tài)（1或0），即一個(gè)節(jié)點(diǎn)受到感染或未受到感染，不存在部分感染或信息的部分傳播概念，感染發(fā)生在不同的時(shí)間并且沿著網(wǎng)絡(luò)的邊彼此獨(dú)立的發(fā)生，最終推斷網(wǎng)絡(luò)的連通性，以及觀察節(jié)點(diǎn)被感染后，推斷通過(guò)邊傳播的可能性。

為了能夠觀察到網(wǎng)絡(luò)的動(dòng)態(tài)變化，如網(wǎng)絡(luò)的邊和邊的動(dòng)態(tài)變化，Gomez 等人又?jǐn)U展了NETRAT 算法，提出了一個(gè)隨時(shí)間變化的推論算法——INFOPATH[16-17]，這種算法使用隨機(jī)梯度來(lái)提供網(wǎng)絡(luò)結(jié)構(gòu)的在線估計(jì)和隨時(shí)間變化的狀態(tài)，它記錄了節(jié)點(diǎn)感染時(shí)間和傳播的事件，允許信息通過(guò)數(shù)據(jù)驅(qū)動(dòng)的方法以不同的速率在網(wǎng)絡(luò)中不同的邊緣傳播。

Saito等人提出了AsIC模型[18]，解決IC模型和LT模型存在的一個(gè)問(wèn)題，它們把信息傳播看作是節(jié)點(diǎn)的一系列狀態(tài)變化，而實(shí)際的傳播是沿著連續(xù)時(shí)間軸以異步方式進(jìn)行，并且觀察到的數(shù)據(jù)的時(shí)間標(biāo)記并非等距。

Guille 等人為在一個(gè)封閉環(huán)境中，用戶(hù)通過(guò)社交網(wǎng)絡(luò)交互，如何模擬這種環(huán)境并且預(yù)測(cè)傳播特性，提出了T-BaSIC模型[19]，它主要考慮傳播擴(kuò)散過(guò)程的時(shí)間動(dòng)態(tài)，能夠從一種更實(shí)際的角度出發(fā)通過(guò)機(jī)器學(xué)習(xí)的算法建立模型，預(yù)測(cè)社交網(wǎng)絡(luò)的信息傳播過(guò)程。它假設(shè)社交網(wǎng)絡(luò)中的信息傳播依賴(lài)于用戶(hù)之間的連接圖，并且是根據(jù)局部特性由節(jié)點(diǎn)之間的微相互作用解釋的。之后根據(jù)圖中個(gè)人的行為進(jìn)行統(tǒng)計(jì)分析，而非全局行為。

Leskovec 等為找到最簡(jiǎn)單、直觀的模型，并且參數(shù)盡可能少的模型，提出了一個(gè)簡(jiǎn)單而直觀的SIS 模型[20]（其中S 代表“敏感（或易感染）”，I 代表“感染”（接受了某信息），在SIS 情況下，在I 狀態(tài)的節(jié)點(diǎn)會(huì)以固定概率變回狀態(tài)S），僅需要一個(gè)參數(shù)。它假定所有節(jié)點(diǎn)都以相同的概率β被感染（激活），被感染的節(jié)點(diǎn)在下一時(shí)間段重新成為敏感節(jié)點(diǎn)。

在許多情況下，網(wǎng)絡(luò)上發(fā)生的傳播行為實(shí)際上是隱式的，甚至是未知的。Yang等人[21]為面對(duì)現(xiàn)實(shí)世界中的網(wǎng)絡(luò)進(jìn)行建模，提出了一種LIM 模型，它關(guān)注于模擬一個(gè)節(jié)點(diǎn)對(duì)全局的影響力，而不是預(yù)測(cè)哪個(gè)節(jié)點(diǎn)會(huì)感染其他節(jié)點(diǎn)，或是節(jié)點(diǎn)感染哪一個(gè)節(jié)點(diǎn)。它雖忽略時(shí)間和在離散時(shí)間段內(nèi)的工作，但是準(zhǔn)確模擬了每個(gè)節(jié)點(diǎn)的影響力并且描述了整個(gè)傳播擴(kuò)散過(guò)程。

本文提出了一種基于節(jié)點(diǎn)傳播能力的偏向性隨機(jī)行走的信息傳播模型，該模型結(jié)合了IC模型，與IC模型不同的是，一個(gè)節(jié)點(diǎn)w在第t被激活，其中v節(jié)點(diǎn)是w節(jié)點(diǎn)的某個(gè)鄰接點(diǎn)，當(dāng)節(jié)點(diǎn)v的活躍鄰居節(jié)點(diǎn)w嘗試激活節(jié)點(diǎn)v時(shí)，即使沒(méi)有激活成功，v節(jié)點(diǎn)也會(huì)得到該消息，故稱(chēng)v節(jié)點(diǎn)為消息節(jié)點(diǎn)。另外還加入了節(jié)點(diǎn)傳播信息的能力，更加符合真實(shí)的社交網(wǎng)絡(luò)交往。

3 偏向性隨機(jī)行走的定義

圖上的隨機(jī)行走是馬爾科夫鏈的一個(gè)子類(lèi)，傳統(tǒng)的方法都是用來(lái)處理無(wú)偏向隨機(jī)行走特性以及計(jì)算與網(wǎng)絡(luò)相關(guān)的轉(zhuǎn)移概率，一般使用G=(V,E)來(lái)表示一個(gè)網(wǎng)絡(luò)圖，其中V={v1,v2,…,vn} 和E={e1,e2,…,en} 分別表示節(jié)點(diǎn)集合和邊的集合，圖G的鄰接矩陣為W ，其中wij=1 表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在連接的邊，wij=0 表示不存在。在這里圖G被認(rèn)為是無(wú)向網(wǎng)絡(luò)圖，所以鄰接矩陣W 是對(duì)稱(chēng)矩陣。d(i)=表示節(jié)點(diǎn)i的鄰接點(diǎn)的個(gè)數(shù)。根據(jù)隨機(jī)行走是由一系列無(wú)規(guī)則的步數(shù)形成的路徑的數(shù)學(xué)化形式，假設(shè)節(jié)點(diǎn)i的鄰接點(diǎn)是節(jié)點(diǎn)j，那么節(jié)點(diǎn)i到節(jié)點(diǎn)j一步轉(zhuǎn)移概率即為Pij，此時(shí)Pij=為圖G的無(wú)偏向性隨機(jī)行走的一步轉(zhuǎn)移概率矩陣。

在真實(shí)的社會(huì)網(wǎng)絡(luò)中，不同的節(jié)點(diǎn)所具有的重要性也不相同，這就導(dǎo)致了每個(gè)節(jié)點(diǎn)也具有不同的傳播能力。很多文獻(xiàn)在研究社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)和信息傳播的過(guò)程中，會(huì)傾向于先通過(guò)某些方法去尋找社會(huì)網(wǎng)絡(luò)中的某些節(jié)點(diǎn)，這些節(jié)點(diǎn)在社會(huì)網(wǎng)絡(luò)中有著一定的影響力，例如：Saito等人[22]就是通過(guò)社會(huì)網(wǎng)絡(luò)中具有的特定社區(qū)結(jié)構(gòu)，從而發(fā)現(xiàn)了k個(gè)最具影響力的節(jié)點(diǎn)，他們認(rèn)為這k個(gè)最具影響力的節(jié)點(diǎn)會(huì)使得網(wǎng)絡(luò)中信息傳播的范圍達(dá)到最大化，但是在信息傳播的過(guò)程當(dāng)中，社區(qū)中還有一些節(jié)點(diǎn)往往是不可忽視的，和那些具有影響力的活躍節(jié)點(diǎn)相比，即使它們的傳播能力可能較弱，然而往往這些節(jié)點(diǎn)在信息傳播的過(guò)程中起著至關(guān)重要的作用。因而，與其耗費(fèi)大量的時(shí)間去尋找網(wǎng)絡(luò)中最具有影響力的節(jié)點(diǎn)，不如隨機(jī)在網(wǎng)絡(luò)中選擇任意一個(gè)節(jié)點(diǎn)作為傳播源，故基于現(xiàn)實(shí)的社交網(wǎng)絡(luò)，假設(shè)存在任意的一個(gè)傳播源節(jié)點(diǎn)a,m表示它的所有鄰接點(diǎn)的個(gè)數(shù)，K={k1,k2,…,km}是鄰接點(diǎn)度的集合，k1,k2,…,km分別是a的鄰接點(diǎn)的度，根據(jù)偏向性隨機(jī)行走的機(jī)制[23]，定義偏向性隨機(jī)行走的轉(zhuǎn)移概率為：

其中，節(jié)點(diǎn)i為傳播源節(jié)點(diǎn)a的其中一個(gè)鄰接點(diǎn)，Pai為節(jié)點(diǎn)i成為活躍節(jié)點(diǎn)或者消息節(jié)點(diǎn)的概率；α為偏向性隨機(jī)行走的控制參數(shù)。當(dāng)α=0 時(shí)，所有鄰居節(jié)點(diǎn)都有平等的機(jī)會(huì)接收從節(jié)點(diǎn)a傳播過(guò)來(lái)的信息，這意味著它們被傳播到的可能性相同。當(dāng)α＞0 時(shí)，度數(shù)較大的節(jié)點(diǎn)更有可能接收到被傳播的信息，當(dāng)α＜0 時(shí)，度數(shù)較小的節(jié)點(diǎn)更有可能接收到被傳播的信息。

4 DCID算法

社交網(wǎng)絡(luò)影響力最大化研究，其目的是選擇一組種子節(jié)點(diǎn)，使得傳播結(jié)束后獲得的活躍節(jié)點(diǎn)數(shù)最多，達(dá)到影響范圍最大化。但是最后的活躍節(jié)點(diǎn)數(shù)并不能完全代表真實(shí)的信息覆蓋情況。一種常見(jiàn)的情況是，當(dāng)某個(gè)節(jié)點(diǎn)的活躍鄰居節(jié)點(diǎn)嘗試激活它時(shí)，即使沒(méi)有激活成功，該節(jié)點(diǎn)也會(huì)得到該消息，故稱(chēng)之為消息節(jié)點(diǎn)。因此，當(dāng)研究社交網(wǎng)絡(luò)中信息覆蓋最大化時(shí)，除了需要考慮活躍節(jié)點(diǎn)的數(shù)量，消息節(jié)點(diǎn)的影響也不能忽略，進(jìn)而產(chǎn)生了信息覆蓋最大化的問(wèn)題，這個(gè)問(wèn)題的目的是找到最多的活躍節(jié)點(diǎn)和消息節(jié)點(diǎn)。

在本文中，每一次一個(gè)被傳播到的節(jié)點(diǎn)通過(guò)偏向性隨機(jī)行走將連續(xù)不斷地發(fā)送C個(gè)要傳播的信息給它的鄰接點(diǎn)，如果一個(gè)節(jié)點(diǎn)已不具有消息節(jié)點(diǎn)或者活躍節(jié)點(diǎn)的價(jià)值，那么該節(jié)點(diǎn)將永遠(yuǎn)不會(huì)被激活。如果一個(gè)節(jié)點(diǎn)接收到了被傳播的信息C，那么它會(huì)將該信息C在下一步繼續(xù)傳播下去。在已經(jīng)成為消息節(jié)點(diǎn)和活躍節(jié)點(diǎn)的這些節(jié)點(diǎn)中，依然會(huì)有某些節(jié)點(diǎn)有λ的概率被重復(fù)傳播，那么這些被重復(fù)傳播的節(jié)點(diǎn)應(yīng)該被剔除。

對(duì)于傳播源節(jié)點(diǎn)a，每次傳播信息C，節(jié)點(diǎn)i無(wú)法被傳播到的概率為：

假設(shè)Xi是一個(gè)隨機(jī)變量，代表節(jié)點(diǎn)i被傳播到的事件，Xi=0 表示節(jié)點(diǎn)i完全沒(méi)有從節(jié)點(diǎn)a收到任何傳播信息，Xi=1 表示節(jié)點(diǎn)i從節(jié)點(diǎn)a至少收到了一條被傳播的信息：

假設(shè)一個(gè)隨機(jī)變量Y代表被節(jié)點(diǎn)a傳播到的鄰接點(diǎn)的個(gè)數(shù)的事件，得到Y(jié)的平均值為：

其中，m是指節(jié)點(diǎn)a的所有鄰接點(diǎn)，但是在信息傳播的過(guò)程中，節(jié)點(diǎn)a的鄰接點(diǎn)并不僅僅是易被傳播的節(jié)點(diǎn)，為了有效地估計(jì)被節(jié)點(diǎn)a傳播到的鄰接點(diǎn)個(gè)數(shù)，還需要知道在節(jié)點(diǎn)a的所有鄰接點(diǎn)中容易被傳播到的節(jié)點(diǎn)的個(gè)數(shù)，為了估計(jì)在t步隨機(jī)行走后被傳播到的所有節(jié)點(diǎn)的個(gè)數(shù)，計(jì)算網(wǎng)絡(luò)中被傳播到節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中易被傳播節(jié)點(diǎn)的個(gè)數(shù)為：

其中，nj是被傳播到的節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)中易被傳播節(jié)點(diǎn)的個(gè)數(shù)，I(t)表示節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)在t步隨機(jī)行走之后被傳播到的節(jié)點(diǎn)個(gè)數(shù)，N(t)表示在t步隨機(jī)行走之后，被傳播到的所有節(jié)點(diǎn)的鄰接點(diǎn)中易被傳播到的節(jié)點(diǎn)個(gè)數(shù)，那么t步隨機(jī)行走后，被傳播到的節(jié)點(diǎn)總數(shù)為：

算法1記錄了DICD算法的整個(gè)過(guò)程，首先，在整個(gè)網(wǎng)絡(luò)圖中選擇一個(gè)初始的傳播源節(jié)點(diǎn)，然后根據(jù)公式（3）用偏向性隨機(jī)概率以及節(jié)點(diǎn)的信息傳播能力衡量一個(gè)節(jié)點(diǎn)是否能夠成為消息節(jié)點(diǎn)或者是活躍節(jié)點(diǎn)，最后根據(jù)公式（8）利用信息傳播最大化函數(shù)使得網(wǎng)絡(luò)中的消息節(jié)點(diǎn)和活躍節(jié)點(diǎn)的集合達(dá)到最大。

算法1 信息傳播最大化

輸入：圖G，初始傳播源節(jié)點(diǎn)a，被傳播節(jié)點(diǎn)的傳播能力C，偏向性隨機(jī)行走參數(shù)α

輸出：消息節(jié)點(diǎn)和活躍節(jié)點(diǎn)總和I

1. for a do

3. End for

4. 輸出I

從公式（8）中很明顯可以看出，被傳播節(jié)點(diǎn)的傳播能力C是本文的關(guān)鍵參數(shù)，已被傳播到的活躍節(jié)點(diǎn)或消息節(jié)點(diǎn)的傳播能力越大，那么易被傳播的節(jié)點(diǎn)被傳播的可能性就越大。參數(shù)α是本文傳播模型中的另一個(gè)關(guān)鍵因素，它決定了當(dāng)傳播能力C是一個(gè)有限常數(shù)時(shí)被傳播到的節(jié)點(diǎn)（即已成為活躍節(jié)點(diǎn)或消息節(jié)點(diǎn)）的鄰居節(jié)點(diǎn)被傳播的可能性。

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

實(shí)驗(yàn)采用的電腦是英特爾第八代酷睿處理器，內(nèi)存為16 GB DDR3，Windows 10 操作系統(tǒng)以及Matlab R2012a數(shù)據(jù)分析工具。

為驗(yàn)證本文提出的DCID 算法的準(zhǔn)確率以及算法運(yùn)行時(shí)間，實(shí)驗(yàn)選用Facebook 網(wǎng)絡(luò)以及Google+網(wǎng)絡(luò)，這2 個(gè)網(wǎng)絡(luò)都是描述人與人之間關(guān)系的友誼網(wǎng)絡(luò)，其中節(jié)點(diǎn)表示用戶(hù)，邊代表用戶(hù)與用戶(hù)之間的關(guān)系，在Facebook網(wǎng)絡(luò)中包含了2 888個(gè)節(jié)點(diǎn)和2 981條邊；其次選用Google+網(wǎng)絡(luò)作為大規(guī)模社交網(wǎng)絡(luò)，它包含了23 628個(gè)節(jié)點(diǎn)和39 242 條邊。使用1，2，3，…，來(lái)對(duì)網(wǎng)絡(luò)Facebook網(wǎng)絡(luò)以及Google+網(wǎng)絡(luò)進(jìn)行節(jié)點(diǎn)進(jìn)行編號(hào)。通過(guò)與KK（Kemple 和Kleinberg，KK）算法[24]以及ICGreedy算法[25]進(jìn)行對(duì)比，驗(yàn)證本文提出的DCID 算法在準(zhǔn)確率和運(yùn)行效率上有所提升。

5.1 確定隨機(jī)行走的偏向性參數(shù)

本文中，根據(jù)公式（8）可以看出信息傳播最大化的關(guān)鍵在于2個(gè)參數(shù)，被傳播節(jié)點(diǎn)的傳播能力C以及偏向性隨機(jī)行走的參數(shù)α，下面對(duì)傳播能力C以及偏向性隨機(jī)行走的參數(shù)α進(jìn)行選取。

從Facebook 網(wǎng)絡(luò)中隨機(jī)選取一個(gè)節(jié)點(diǎn)作為信息傳播源，然后利用公式（8），對(duì)公式（8）用微積分的方式進(jìn)行求解最大化問(wèn)題，公式（8）轉(zhuǎn)化為：

為了使傳播的曲線更加平滑，選取λ=0.05，然后從被傳播節(jié)點(diǎn)的傳播能力C以及偏向性隨機(jī)行走的參數(shù)α兩個(gè)方面分別對(duì)Facebook 網(wǎng)絡(luò)進(jìn)行這2 個(gè)參數(shù)的選取，首先選取了C=1,α=-1、C=1,α=-5、C=1,α=-10 以及C=1,α=-15 得出在Facebook 網(wǎng)絡(luò)中信息傳播的范圍，如圖1所示。

圖1 Facebook網(wǎng)絡(luò)中C=1 對(duì)應(yīng)的不同α 值的傳播范圍

從圖1 中可以看出C=1,α=-10 時(shí)信息傳播的范圍最大，但是由于無(wú)法從一種固定的參數(shù)選取中確定這2 個(gè)參數(shù)的值，因此又選取了C=2,α=-1、C=2,α=-5、C=2,α=-10 以及C=2,α=-15 得出在Facebook網(wǎng)絡(luò)中信息傳播的范圍，如圖2所示；最后選取了C=5,α=-1、C=5,α=-5、C=5,α=-10 以及C=5,α=-15得出在Facebook網(wǎng)絡(luò)中信息傳播的范圍，如圖3所示。

圖2 Facebook網(wǎng)絡(luò)中C=2 對(duì)應(yīng)的不同α 值的傳播范圍

圖3 Facebook網(wǎng)絡(luò)中C=5 對(duì)應(yīng)的不同α 值的傳播范圍

從圖1、圖2 和圖3 可以看出，首先C的值越大，信息傳播的范圍會(huì)越來(lái)越小，即當(dāng)節(jié)點(diǎn)傳播的信息量越大時(shí)，隨著隨機(jī)行走的步數(shù)增加時(shí)信息傳播的范圍會(huì)越來(lái)越?。黄浯卧诠?jié)點(diǎn)具有同樣的傳播能力下，當(dāng)α=-10時(shí)，隨著隨機(jī)行走的步數(shù)增加，信息傳播的范圍達(dá)到最大。此時(shí)在Facebook網(wǎng)絡(luò)中選取的參數(shù)為C=1,α=-10。

下面在大型網(wǎng)絡(luò)Google+網(wǎng)絡(luò)中用同樣的方法來(lái)進(jìn)行參數(shù)的選取，利用公式（8），同樣選取λ=0.05，從被傳播節(jié)點(diǎn)的傳播能力C以及偏向性隨機(jī)行走的參數(shù)α兩個(gè)方面分別對(duì)Google+網(wǎng)絡(luò)進(jìn)行這2 個(gè)參數(shù)的選取，首先是選取了C=1,α=-1、C=1,α=-5、C=1,α=-10 以及C=1,α=-15 得出在Google+網(wǎng)絡(luò)中信息傳播的范圍，如圖4所示。

圖4 Google+網(wǎng)絡(luò)中C=1 對(duì)應(yīng)的不同α 值的傳播范圍

同時(shí)又選取C=2,α=-1、C=2,α=-5、C=2,α=-10 以及C=2,α=-15 和C=5,α=-1、C=5,α=-5、C=5,α=-10 以及C=5,α=-15 得出在Google+網(wǎng)絡(luò)中信息傳播的范圍，如圖5和圖6所示。

圖5 Google+網(wǎng)絡(luò)中C=2 對(duì)應(yīng)的不同α 值的傳播范圍

圖6 Google+網(wǎng)絡(luò)中C=5 對(duì)應(yīng)的不同α 值的傳播范圍

從圖4、圖5 和圖6 中可以看出，在Google+網(wǎng)絡(luò)中同樣是隨著隨機(jī)行走的步數(shù)增加，C的值越大，信息傳播的范圍會(huì)越來(lái)越?。黄浯卧诠?jié)點(diǎn)具有同樣的傳播能力下，當(dāng)α=-10 時(shí)，隨著隨機(jī)行走的步數(shù)增加，信息傳播的范圍達(dá)到最大。因此通過(guò)在中等網(wǎng)絡(luò)以及大型網(wǎng)絡(luò)的實(shí)驗(yàn)中，確定出被傳播節(jié)點(diǎn)的傳播能力C=1 以及偏向性隨機(jī)行走的參數(shù)α=-10。

但是此時(shí)只能確定被傳播節(jié)點(diǎn)的傳播能力C=1 時(shí)的確是能夠使得信息傳播的范圍達(dá)到最大，但是上文中提到當(dāng)α＞0 時(shí)，度數(shù)較大的節(jié)點(diǎn)更有可能接收到被傳播的信息，當(dāng)α＜0 時(shí)，度數(shù)較小的節(jié)點(diǎn)更有可能接收到被傳播的信息。α=-10 只能說(shuō)明此時(shí)度數(shù)較小的節(jié)點(diǎn)更有可能接收到被傳播的信息，所以同樣也要選取α＞0 時(shí)的信息傳播的范圍，如圖7和圖8所示。

圖7 Facebook網(wǎng)絡(luò)中不同α 值對(duì)應(yīng)的傳播范圍

圖8 Google+網(wǎng)絡(luò)中不同α 值對(duì)應(yīng)的傳播范圍

從圖7 和圖8 中可以看出，當(dāng)C=1，α=-1 時(shí)，信息傳播的范圍比α=-1 時(shí)信息傳播的范圍更小，此時(shí)，才能真正確定出被傳播節(jié)點(diǎn)的傳播能力C=1 以及偏向性隨機(jī)行走的參數(shù)α=-10 時(shí)，在Facebook 網(wǎng)絡(luò)中和Google+網(wǎng)絡(luò)中的信息傳播范圍達(dá)到最大。

圖9 DCID算法和其他2個(gè)算法的傳播范圍對(duì)比

圖10 Facebook網(wǎng)絡(luò)、Google+網(wǎng)絡(luò)中三種算法的運(yùn)行時(shí)間對(duì)比

5.2 算法的精確率

由上文中選取的參數(shù)確定的傳播范圍，將本文算法和KK算法以及ICGreedy算法分別在Facebook網(wǎng)絡(luò)中和大規(guī)模的Google+網(wǎng)絡(luò)進(jìn)行傳播范圍的對(duì)比，如圖9所示。

由于本文算法和初始的種子節(jié)點(diǎn)無(wú)關(guān)，所以選取在DCID 算法傳播范圍最大的情況下和ICGreedy 算法以及KK算法進(jìn)行對(duì)比，圖9（a）記錄了在Facebook網(wǎng)絡(luò)中不同的初始種子節(jié)點(diǎn)下，KK 算法、ICGreedy 算法和DCID算法的傳播范圍，從圖9（a）中可以明顯地看出，隨著初始種子節(jié)點(diǎn)的數(shù)量增加，DCID 算法的傳播范圍已遠(yuǎn)遠(yuǎn)超過(guò)KK算法、ICGreedy算法的傳播范圍。圖9（b）記錄了在Google+網(wǎng)絡(luò)中不同的初始種子節(jié)點(diǎn)下，KK算法、ICGreedy算法和DCID算法的傳播范圍，同樣地，從圖中可以看出DCID算法的傳播范圍明顯優(yōu)于KK算法和ICGreedy算法。

此外，還比較了本文算法和ICGreedy算法以及KK算法的運(yùn)行時(shí)間，圖10記錄了在Facebook網(wǎng)絡(luò)和Google+網(wǎng)絡(luò)中三種算法的運(yùn)行時(shí)間，從圖10中可以看出，由于本文提出的DICD算法與初始的種子節(jié)點(diǎn)無(wú)關(guān)，所以選取了本文算法在兩種不同規(guī)模的網(wǎng)絡(luò)中達(dá)到傳播范圍最大時(shí)的運(yùn)行時(shí)間與ICGreedy 算法以及KK 算法的運(yùn)行時(shí)間進(jìn)行對(duì)比，因而，從圖10中看到在Facebook網(wǎng)絡(luò)和Google+網(wǎng)絡(luò)中的運(yùn)行時(shí)間沒(méi)有發(fā)生改變，是一條沒(méi)有波動(dòng)的直線。圖10（a）記錄了在中等規(guī)模Facebook網(wǎng)絡(luò)中ICGreedy算法和KK算法與DCID算法的運(yùn)行時(shí)間的對(duì)比，ICGreedy算法和KK算法在隨著初始節(jié)點(diǎn)增加的情況下，運(yùn)行的時(shí)間也隨之增大，初始種子節(jié)點(diǎn)個(gè)數(shù)小于40的情況下，本文的算法優(yōu)勢(shì)并不明顯，運(yùn)行的時(shí)間略大于ICGreedy算法，但始終低于KK算法的運(yùn)行時(shí)間，隨著初始種子節(jié)點(diǎn)個(gè)數(shù)不斷增加，ICGreedy 算法和KK算法的運(yùn)行效率明顯低于本文算法。圖10（b）記錄了在大規(guī)模Google+網(wǎng)絡(luò)中ICGreedy算法和KK算法與DCID 算法的運(yùn)行時(shí)間的對(duì)比，ICGreedy 算法和KK算法在隨著初始節(jié)點(diǎn)增加的情況下，運(yùn)行的時(shí)間也隨之增大，在初始種子節(jié)點(diǎn)個(gè)數(shù)小于60的情況下，本文算法的運(yùn)行時(shí)間同樣地略大于ICGreedy 算法；初始種子節(jié)點(diǎn)個(gè)數(shù)小于50的情況下，本文算法的運(yùn)行時(shí)間也略大于KK算法，但隨著初始種子節(jié)點(diǎn)個(gè)數(shù)不斷增加，ICGreedy算法和KK算法的運(yùn)行效率明顯低于本文算法。因此，可以看出本文算法在大規(guī)模的網(wǎng)絡(luò)中具有更快的運(yùn)行效率和更大的傳播范圍。

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

在本文中，提出了一種基于節(jié)點(diǎn)傳播能力的偏向性隨機(jī)行走的信息傳播方法，使用偏向性隨機(jī)行走參數(shù)和節(jié)點(diǎn)傳播能力參數(shù)來(lái)進(jìn)行網(wǎng)絡(luò)中的信息傳播，當(dāng)傳播的關(guān)鍵不再僅限于開(kāi)始選取的種子節(jié)點(diǎn)，而是利用節(jié)點(diǎn)本身所能夠傳播的信息的數(shù)量以及隨機(jī)行走具有的偏向特性，選擇網(wǎng)絡(luò)中的任意一個(gè)節(jié)點(diǎn)作為信息源的傳播節(jié)點(diǎn)，結(jié)合影響力最大化的傳播函數(shù)，最終通過(guò)選取最優(yōu)的被傳播節(jié)點(diǎn)的傳播能力C以及偏向性隨機(jī)行走的參數(shù)α來(lái)達(dá)到網(wǎng)絡(luò)信息傳播范圍的最大化，最優(yōu)參數(shù)的獲取讓本文的算法得到了較好的實(shí)驗(yàn)結(jié)果。在今后的工作中，將更加著重利用網(wǎng)絡(luò)的具體特點(diǎn)，選取更符合偏向性隨機(jī)行走的偏向性參數(shù)以及網(wǎng)絡(luò)中節(jié)點(diǎn)能夠傳播的信息的個(gè)數(shù)來(lái)獲取最大的信息傳播范圍。