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

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

2.南京郵電大學 計算機學院，南京210023

1 引言

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

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

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

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

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

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

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

2 相關(guān)研究

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

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

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

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

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

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

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

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

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

3 偏向性隨機行走的定義

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

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

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

4 DCID算法

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

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

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

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

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

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

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

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

算法1 信息傳播最大化

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

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

1. for a do

3. End for

4. 輸出I

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

5 實驗分析

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

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

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

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

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

為了使傳播的曲線更加平滑，選取λ=0.05，然后從被傳播節(jié)點的傳播能力C以及偏向性隨機行走的參數(shù)α兩個方面分別對Facebook 網(wǎng)絡(luò)進行這2 個參數(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 對應(yīng)的不同α 值的傳播范圍

從圖1 中可以看出C=1,α=-10 時信息傳播的范圍最大，但是由于無法從一種固定的參數(shù)選取中確定這2 個參數(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 對應(yīng)的不同α 值的傳播范圍

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

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

下面在大型網(wǎng)絡(luò)Google+網(wǎng)絡(luò)中用同樣的方法來進行參數(shù)的選取，利用公式（8），同樣選取λ=0.05，從被傳播節(jié)點的傳播能力C以及偏向性隨機行走的參數(shù)α兩個方面分別對Google+網(wǎng)絡(luò)進行這2 個參數(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 對應(yīng)的不同α 值的傳播范圍

同時又選取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 對應(yīng)的不同α 值的傳播范圍

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

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

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

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

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

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

圖9 DCID算法和其他2個算法的傳播范圍對比

圖10 Facebook網(wǎng)絡(luò)、Google+網(wǎng)絡(luò)中三種算法的運行時間對比

5.2 算法的精確率

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

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

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

6 結(jié)束語

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