在線社交超網絡的信息全局傳播模型

鞏云超，李發旭，周麗娜，胡 楓*

(1.青海師范大學計算機學院 西寧810008；2.青海省藏文信息處理與機器翻譯重點實驗室 西寧810008；3.藏語智能信息處理及應用國家重點實驗室 西寧810008)

隨著互聯網的發展與普及，以QQ、微信、微博、Twitter、Facebook為代表的在線社交平臺，使數以億計的互聯網用戶不再受時間、地域的限制就能夠快速發布、接收和分享信息。同時，在線社交網絡中信息傳播的速度快和范圍廣的特點，給信息傳播帶來了前所未有的影響。因此，研究在線社交網絡中信息傳播的機理及規律，對網絡中信息傳播的預測和控制有著重要的理論依據和現實意義。

鑒于在線社交網絡中的信息傳播過程類似于傳染病傳播過程，以傳染病傳播模型為基礎建立的信息傳播模型的研究最為廣泛[1-2]，經典模型有SIS模型[3]、SIR模型[4-5]、SIRS模型[6]和SEIR模型[7]。在此基礎上，許多信息傳播模型被提出，如H-SEIR模型[8]、SHIR模型[9]和ESIS模型[10]等。與此同時，信息傳播過程中的影響因素也被分析，如記憶效應與社會強化效應[11-13]、節點屬性與信息價值[14-16]和節點影響力[17-18]等。目前，關于信息傳播的研究主要基于普通圖結構構建在線社交網絡，但這類網絡并不能準確地描述在線社交網絡中的群聚特性。例如，在微信或QQ中，用戶可以私發信息給某個好友用戶，也可群發信息到多個社交群組；在微博中，用戶能同時被多個用戶所關注。當用戶發布或轉發一條信息時，其被關注群組中的多個用戶都能夠轉發和評論該信息。為了更精準地描述真實在線社交網絡中用戶之間復雜的社交關系和信息交互行為，文獻[19]引入了超圖中的超邊表示多個個體之間的群聚關系，且考慮反應過程策略和接觸過程策略，提出了兩種策略下的SIS信息傳播模型。文獻[20]基于超圖的超網絡模型構建動態社交超網絡，建立了一種基于SIS的信息傳播模型。

迄今為止，超網絡中信息傳播模型的研究均在文獻[21]提出的超網絡演化模型基礎上構建社交網絡，該模型每次增加多個用戶與網絡中已存在的單個用戶組成社交群組。分析現實在線社交網絡，更多的情形是用戶與網絡中已存在的多個用戶組成社交群組，即基于BA無標度的超網絡演化模型更契合現實在線社交網絡的群組特性。針對這一問題，本文在文獻[22]提出的基于BA無標度網絡的超網絡動態演化模型基礎上構建在線社交超網絡，結合基于反應過程策略的SIS模型，對在線社交超網絡中信息全局傳播過程進行理論分析和仿真實驗。

1 相關理論

1.1 超網絡相關概念

設 Ω=(V,E)是 有限超圖，G是 從[0,∞)到 Ω的映射，則對于給定的t≥0，G(t)=(V(t),E(t))是一個有限超圖[24]。超網絡G(t)是 一個隨時間t演化的超圖集合，其中，節點vi的超度dH(i)定義為該節點所在超邊的數量。例如在線社交超網絡中，節點代表個體，超邊代表個體參與的社會關系，如朋友關系、家人關系、同學關系、同事關系等，節點的超度表示個體參與的社會關系數量。如圖1所示超網絡，節點集合V={v1,v2,v3,v4,v5,v6,v7,v8,v9}，超邊集合E={e1,e2,e3,e4,e5}，其 中e1={v1,v2,v3,v4,v5}，e2={v1,v2,v3,v4,v6}，e3={v3,v4,v5,v6,v7}，e4={v1,v3,v4,v5,v8}，e5={v2,v3,v6,v7,v9}。節點v1和v2同屬于超邊e1，則 節 點v1和v2鄰 接，超 邊e1和e4的 交 集 為{v1,v3,v4,v5}，則 超 邊e1和e4鄰 接。|ei|=5(i=1,2,3,4,5)，則該超網絡為5一致超網絡。節點v1和v4的超度分別為3和4。

圖1 超網絡示意圖

1.2 RP策略的SIS模型超網絡相關概念

反應過程策略(reactive process strategy,RP)[25-26]表現為全局傳播，即初始傳播節點所在的所有超邊中的節點均為初始傳播節點的鄰居節點，并對所有鄰居節點進行信息傳播。例如，在企業微信群中，領導在本部門群組中發布信息，那么該群組中所有員工都能夠接受并傳播該信息?；赗P策略的SIS模型描述如下：

1)網絡中的個體劃分為易感者(S狀態)和染病者(I狀態)。

2)初始時，隨機選擇網絡中的一個或者多個節點為染病者，其他節點均為易感者。

3)每個時間步內，染病者與其相鄰的所有易感者接觸后，染病者依照事先設定的概率β將易感者感染為染病者，該概率β被稱為傳播率。同時網絡中的染病者依照事先設定的概率 γ將染病者治愈為易感者，該概率 γ被稱為恢復率，治愈后的易感者仍有可能會再次感染變成新的染病者。

4)隨著疾病在網絡中不斷傳播，染病者所占密度將會達到一個相對穩定值，并在這個相對穩定值附近進行小幅度波動，這意味著網絡中的疾病傳播達到穩定狀態，簡稱為穩態。

2 超網絡中的信息全局傳播

2.1 超網絡的構造過程

在線社交超網絡模型構建基于文獻[22]提出的BA無標度超網絡演化模型，構造算法如下：

1)初始化：初始時網絡中包含m0個個體，這m0個 個體構成一種社交群組關系，即m0個節點構成一條超邊。

2)增長：每個時間步t內，添加一個個體，新加入的個體與超網絡中的m1個已存在的個體構成一種新的社交群組關系，即新添加的節點與m1個舊節點構成一條新超邊。

3)優先連接：從已有的超網絡中按照超度優先選取m1個舊節點，與新添加的節點結合生成超邊。每次選取連接的節點vi的概率 Πd H(i)等 于節點vi的超度dH(i)與超網絡中的已有節點vj的超度dH(j)總和之比，即：

式中，d H(i)為節點vi參與的超邊數量，即為節點vi的超度。

超度分布P(k)[22]指超網絡中超度為k的節點在整個網絡中所占的比例，經過t個時間步后，超網絡中節點的超度分布獨立于時間t，P(k)為：

2.2 超網絡中的信息全局傳播過程

根據信息在社交群組中傳播的特點，在線社交超網絡中信息全局傳播的動態過程可以近似地用基于RP策略的SIS模型來描述。

1)在線社交超網絡中的個體劃分為不知情者(S狀態)和知情者(I狀態)。其中，不知情者為尚未獲得信息或者不關心且不愿意傳播信息的個體，知情者為已獲得信息并愿意繼續向其他人傳播信息的個體。

2)初始時，從超網絡中隨機選擇一個節點為傳播節點，該節點為超網絡中第一個獲得信息的知情者，處于I狀態，其他節點則處于S狀態。

3)每個時間步內，超網絡中處于I狀態的節點向其所在超邊中的所有鄰接節點傳播信息。其中，處于S狀態的節點以概率β接收信息后轉變為I狀態，處于I狀態的節點以概率γ 恢復到S狀態。

4)隨著信息在網絡中不斷傳播，處于I狀態節點所占密度將會達到一個相對穩定值，并在這個相對穩定值附近進行小幅度波動，這意味著網絡中的信息全局傳播達到穩態。

信息全局傳播過程描述如圖2所示。其中，黑色節點表示該個體處于S狀態，白色節點表示該個體處于I狀態。t=0時刻，超網絡中的全部節點處于S狀態；t=1時刻，從超網絡中隨機選擇一個節點(編號為v5) 處于I狀態；t=2時刻，由于節點v5被超邊e1、e3和e4所包圍，所以其鄰接節點v2、v7和v8獲得信息處于I狀態；t=3時刻，由于節點v2、v5、v7和v8被 超邊e1、e2、e3、e4和e5所包圍，所以其鄰接節點v1、v3、v6和v9獲 得信息處于I狀態，而節點v2和v5恢 復為S狀態。

圖2 超網絡結構下的信息全局傳播示意圖

2.3 理論分析

根據平均場理論，超網絡中的信息全局傳播動力學的平均反應速率方程可記為：

式(4)表明鄰居數越多的節點，其被感染的概率越大，獲得信息的機會越高。

在 θ(β,γ)的計算中，超邊中超度為s的節點的概率與sP(s)成正比，因此：

解式(7)可得：

其中式(9)左項為：

結合式(9)和式(10)，可解得：

由式(12)可得：

式(13)表明，信息在超網絡中的全局傳播到達穩態時，ρ是一個獨立于時間t的函數。如果已知超網絡的傳播率、恢復率和網絡結構等參數，就能得到超網絡中I狀態節點的密度ρ。

3 仿真分析

采用2.1節中的方法構造在線社交超網絡，在模型構造過程中每個時間步內添加的超邊數也可擴展到m條。依據2.1節的構造算法，本文對在線社交超網絡中信息全局傳播的動態過程進行了計算機仿真。仿真實驗側重于超網絡規模N、傳播率β、恢復率γ、新節點進入時選擇舊節點數m1和生成的超邊數m，以及初始傳播節點對超網絡中信息全局傳播的影響，同時對超網絡和復雜網絡結構下的信息全局傳播的動態過程進行了對比分析。為了消除隨機影響，以下每組仿真實驗都是在相同初始條件下，獨立重復運行50次取均值的結果。

3.1 不同參數下的理論結果與穩態仿真結果

固定參數為N=1 000，m0=4,6,8，m1=3,5,7，m=1， γ=0.06。圖3為不同參數下模型的理論結果與穩態下仿真結果的對比圖。仿真過程直到達到穩態結束，獲得知情節點所占密度ρ。根據式(13)計算理論值，圖3中曲線為理論結果，離散點為仿真結果。在不同參數下，理論結果與仿真結果相吻合。隨著傳播率β值逐漸增大，信息在超網絡中的全局傳播到達穩態時，知情節點所占密度越大，波及范圍越廣。即使傳播率很小，信息也會傳播到整個網絡。

圖3 理論結果與穩態下的仿真結果

3.2 超網絡規模 N對信息全局傳播的影響

為描述信息全局傳播的動態過程，獲得知情節點所占密度隨時間的變化趨勢。固定參數為m0=4，m1=3，m=1， β=0.3， γ=0.06。圖4為不同超網絡規模下的信息全局傳播曲線。超網絡中節點總數分別為1000、5000和10000時，3條曲線幾乎是重疊的，信息在超網絡中的傳播時間和穩態下知情節點所占密度基本一致，表明超網絡規模對信息全局傳播的動態過程的影響極小。因此，下面的仿真實驗均在N=1 000的超網絡結構中進行。

圖4 不同超網絡規模下的信息全局傳播曲線

3.3 傳播率β、恢復率γ 對信息全局傳播的影響

固定參數為N=1 000，m0=4,6,8，m1=3,5,7，m=1，測試傳播率、恢復率對信息全局傳播的影響。在線社交超網絡中信息全局傳播的動態過程分為前期增長階段和后期穩定階段。傳播率代表個體的信息傳播能力，傳播率β值越大，信息全局傳播的速度越快，波及范圍越大?；謴吐蚀韨€體對信息的抵抗能力，恢復率 γ值越大，信息全局傳播的速度越慢，波及范圍越小。

1)傳播率β 的影響

圖5所示傳播率 β=0.1,0.2,0.3，恢復率γ=0.06時，在線社交超網絡中知情節點所占密度隨時間的變化趨勢。如圖5所示，對于不同的傳播率，信息在超網絡中的傳播行為極其相似。隨著傳播率β逐漸增大，即個體的信息傳播能力逐漸增強。前期增長階段，知情節點所占密度到達穩態時所需時間步逐漸減小，即不知情節點獲得信息的時間逐漸縮減，信息傳播的速度逐漸加快。到達穩態時峰值逐漸增大，即信息的波及范圍逐漸擴大。后期穩定階段，知情節點所占密度到達穩態，并在峰值附近進行振幅較小的波動。隨著信息在超網絡中不斷傳播，一部分處于I狀態的個體將進入遺忘期，恢復為S狀態，而恢復為S狀態的個體可能會再次獲得信息進入I狀態。由此可見，信息一旦在超網絡中傳播，就會擴散到整個超網絡。

2)恢復率γ 的影響

圖6為恢復率γ =0.06,0.1,0.2，傳播率 β=0.3時，在線社交超網絡中知情節點所占密度隨時間的變化趨勢。如圖6所示，對于不同的恢復率，信息在超網絡中的傳播行為極其相似。隨著恢復率 γ值逐漸增大，即個體對信息的抵抗能力逐漸增強。前期增長階段，知情節點所占密度到達穩態時所需時間逐漸增大，到達穩態時峰值逐漸減小。后期穩定階段，知情節點所占密度到達穩態，并在峰值附近進行振幅較小的波動。由此可見，隨著恢復率 γ值逐漸增大，網絡中知情節點所占密度逐漸下降。

由圖5和圖6在不同的m1值顯示的傳播曲線可以看出，相同傳播率和恢復率下，隨著超邊中舊節點數量m1逐漸增大，知情節點所占密度到達穩態時的時間逐漸減小，表明信息的傳播速度越來越快，也就是說超邊中所含的節點數目越多，意味著每個時間步內可能感染的個體會越多，即使傳播率很小，信息也能夠在短時間內迅速波及擴散到整個網絡。

圖5 不同傳播率下的信息全局傳播曲線

圖6 不同恢復率下的信息全局傳播曲線

3.4 超網絡結構參數對信息全局傳播的影響

固定參數為N=1 000，m0=4,6,8，m1=3,5,7，β=0.4， γ=0.06，測試超網絡結構參數m1和m對信息全局傳播的影響。m1表示超網絡中新節點進入時選擇的舊節點數，m1值越大，意味著節點所在超網絡中的鄰居越多。m表示超網絡中新節點進入時生成的超邊數，m值越大，意味著節點所參與的社交群組越多。圖7為m=1,2,3時，在線社交超網絡中知情節點所占密度隨時間的變化趨勢。如圖7所示，對于不同的m1和m，信息在超網絡中的傳播行為極其相似。隨著m1和m值逐漸增大，前期增長階段，知情節點所占密度到達穩態時所需時間逐漸減小，到達穩態時峰值逐漸增大。后期穩定階段，知情節點所占密度到達穩態，并在峰值附近進行振幅較小的波動。由此可見，個體在超網絡中的鄰居越多，參與的社交群組越多，都將會使個體有更多的機會獲得和傳播信息，即個體獲得和傳播信息的速度越快，信息的波及范圍越廣。

圖7 不同m下的信息全局傳播曲線

3.5 初始傳播節點對信息全局傳播的影響

固定參數為N=1 000，m0=6，m1=5，m=1，分別選擇超度值最大的節點(超度最大值為309，節點編號為14)和超度值最小的節點(超度最小值為9，節點編號為195)作為初始傳播節點進行仿真實驗。如圖8所示，初始傳播節點的選擇只對信息全局傳播的前期增長階段存在影響，不影響后期穩定階段。前期增長階段，參數設置為β=0.1，γ=0.06的情況下，選擇超度值較大的節點作為初始傳播節點，到達穩態時所需時間較少，而選擇超度值較小的節點作為初始傳播節點，到達穩態則需要一定時間；參數設置為β=0.3， γ=0.06的情況下，選擇超度值較大的節點與選擇超度值較小的節點到達穩態的時間差很小。后期穩定階段，兩種情況分別收斂到相同的值。根據節點超度的定義可知，超度值大的節點會出現在多條超邊中，對應于現實生活中個體具有多種社交關系，具有較大的傳播影響力。例如在線社交網絡中的名人、明星和大V發表的信息能夠在網絡中迅速傳播，造成較大的社會影響。

圖8 不同初始傳播節點下的信息全局傳播曲線

3.6 超網絡和復雜網絡結構下信息全局傳播對比

針對信息在不同網絡結構下的全局傳播過程，分別生成兩個規模為1000的網絡：復雜網絡和超網絡。復雜網絡按照BA模型構造，其中參數設置為m=2。超網絡按照2.1節模型構造，其中參數設置為m0=6，m1=5，m=2。固定參數為傳播率β=0.4，恢復率γ =0.06。圖9為兩個網絡結構下的信息全局傳播曲線。如圖9所示，復雜網絡結構中的信息全局傳播需要一定時間，而超網絡結構中的信息能夠迅速擴散到整個網絡，同復雜網絡結構相比較，超網絡結構下的信息全局傳播到達穩態時，波及范圍較廣，即獲得信息的人數較多。事實上，復雜網絡中每個個體只受其鄰居節點的影響，而超網絡中每個個體都會受到社交關系中其他所有鄰居的影響。因此，超網絡結構中的信息全局傳播能夠更精準地反映在線社交網絡中信息傳播的規律。

圖9 不同網絡結構下的信息全局傳播曲線

進一步，超網絡按照2.1節模型構造，其中參數設置為m0=2，m1=1，m=2。固定參數傳播率β=0.4，恢復率γ=0.06。如圖10所示，在傳播率、恢復率相同的情況下，超網絡和復雜網絡中的信息全局傳播曲線在前期增長階段和后期穩定階段基本吻合。仿真結果表明，當超網絡結構參數設置為m0=2，m1=1，m=2時，該超網絡模型就退化為BA模型。因此，BA模型上的信息全局傳播可視為本文模型的特例。

圖10 退化的超網絡和復雜網絡結構下的信息全局傳播曲線

4 結束語

本文為刻畫現實在線社交網絡中的信息全局傳播規律，在基于BA無標度網絡的超網絡動態演化模型的基礎上構造在線社交超網絡，結合基于RP策略的SIS模型，研究了超網絡結構下的信息全局傳播的動態過程。仿真發現，理論分析和仿真實驗完全吻合。超網絡的規模對信息全局傳播的影響極小，而傳播率和恢復率不僅影響信息在前期增長階段的傳播，還影響信息在后期穩定階段的傳播。超網絡中新節點進入時每次選擇的舊節點數和每次生成的超邊數越多，信息傳播速度越快，波及范圍越廣。初始傳播節點的選擇只對信息在前期增長階段的傳播時間存在影響，不影響信息在后期穩定階段的傳播。同復雜網絡結構相比，基于超圖結構的超網絡中的信息全局傳播速度更快，波及范圍更廣。本文的研究側重于在線社交超網絡的信息傳播的動態過程，而信息傳播的動態過程往往受多種復雜因素的影響，如信息的時效性、個體的從眾心理等等。研究復雜因素下的信息傳播規律并建立驗證模型，以及在真實網絡數據上展開研究將是今后的研究方向。