節點傳播能力的偏好隨機行走的信息傳播方法

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

1.南京信息職業技術學院 網絡與通信學院，南京210023

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

1 引言

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

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

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

而隨機行走是一種不規則的、布朗運動的數學理想狀態，在許多領域都有重要的應用，其中在計算機領域一個很有名的例子就是Google的PageRank算法。近年來，在信息傳播領域中加入了一種基于隨機行走的概率方法，但是當隨機行走偏向于遠離穩定狀態所占的區域方向時就產生了一個有趣的問題，在什么條件下傳播速率和偏向會導致傳播的結果停滯不前呢。或者從相反的方向來說，當普通的隨機行走在不同的方向上具有偏差時，維持正常的傳播速率的偏差臨界值是多少呢。因此，本文提出了一種基于節點傳播能力的偏向性隨機行走的信息傳播方法，該方法的創新性體現在以下3個方面：

（1）將每個節點的信息傳播能力，即網絡中節點能承受的傳播的信息的內容量，納入信息傳播的關鍵因素。

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

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

2 相關研究

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

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

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

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

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

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

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

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

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

3 偏向性隨機行走的定義

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

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

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

4 DCID算法

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

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

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

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

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

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

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

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

算法1 信息傳播最大化

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

輸出：消息節點和活躍節點總和I

1. for a do

3. End for

4. 輸出I

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

5 實驗分析

實驗采用的電腦是英特爾第八代酷睿處理器，內存為16 GB DDR3，Windows 10 操作系統以及Matlab R2012a數據分析工具。

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

5.1 確定隨機行走的偏向性參數

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

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

為了使傳播的曲線更加平滑，選取λ=0.05，然后從被傳播節點的傳播能力C以及偏向性隨機行走的參數α兩個方面分別對Facebook 網絡進行這2 個參數的選取，首先選取了C=1,α=-1、C=1,α=-5、C=1,α=-10 以及C=1,α=-15 得出在Facebook 網絡中信息傳播的范圍，如圖1所示。

圖1 Facebook網絡中C=1 對應的不同α 值的傳播范圍

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

圖2 Facebook網絡中C=2 對應的不同α 值的傳播范圍

圖3 Facebook網絡中C=5 對應的不同α 值的傳播范圍

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

下面在大型網絡Google+網絡中用同樣的方法來進行參數的選取，利用公式（8），同樣選取λ=0.05，從被傳播節點的傳播能力C以及偏向性隨機行走的參數α兩個方面分別對Google+網絡進行這2 個參數的選取，首先是選取了C=1,α=-1、C=1,α=-5、C=1,α=-10 以及C=1,α=-15 得出在Google+網絡中信息傳播的范圍，如圖4所示。

圖4 Google+網絡中C=1 對應的不同α 值的傳播范圍

同時又選取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+網絡中信息傳播的范圍，如圖5和圖6所示。

圖5 Google+網絡中C=2 對應的不同α 值的傳播范圍

圖6 Google+網絡中C=5 對應的不同α 值的傳播范圍

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

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

圖7 Facebook網絡中不同α 值對應的傳播范圍

圖8 Google+網絡中不同α 值對應的傳播范圍

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

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

圖10 Facebook網絡、Google+網絡中三種算法的運行時間對比

5.2 算法的精確率

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

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

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

6 結束語

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