劉 宇，梁 循，楊小平

(中國人民大學(xué)信息學(xué)院，北京 100872)

1 引言

在線社交網(wǎng)絡(luò)隨著互聯(lián)網(wǎng)的發(fā)展越來越受到人們的關(guān)注，它能夠允許用戶建立個人資料，并在系統(tǒng)內(nèi)與其他相連接的用戶進行交流[1]。用戶可以通過社交網(wǎng)絡(luò)獲取感興趣或者具有一定價值的信息。微博就是典型的在線社交網(wǎng)絡(luò)平臺之一。微博網(wǎng)絡(luò)中的信息傳遞問題是微博網(wǎng)絡(luò)不可或缺的研究問題。微博網(wǎng)絡(luò)中的信息如何在網(wǎng)絡(luò)結(jié)構(gòu)中傳播，信息在網(wǎng)絡(luò)中的傳播路徑是什么，信息傳播到某一個用戶時用戶的反應(yīng)行為是什么，一條信息發(fā)出后在某一時間點傳播了多少用戶，這些用戶之間的關(guān)系如何等問題都是信息傳播過程中需要關(guān)注的問題。同時，微博網(wǎng)絡(luò)的信息傳播問題在一定程度上反映的是資源流動問題，例如，一條微博信息在微博網(wǎng)絡(luò)中傳播，則是該信息在用戶構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)中由一個用戶傳播到多個用戶，再由多個用戶傳播到更多的用戶，在此期間傳播的信息可能會通過用戶的轉(zhuǎn)發(fā)行為傳遞回發(fā)布微博帖子的原用戶之處，這就形成了微博網(wǎng)絡(luò)中的資源流動。

在目前的微博等社交網(wǎng)絡(luò)信息傳播的研究中，研究人員提出了多種信息傳播模型?；谟绊懜怕实莫毩⒓壜?lián)模型[2-3]和線性閾值模型[2,4-5]是兩種最基本的傳播模型[6]。除此之外，傳播模型的研究還包括基于病毒傳播模型進行應(yīng)用以及建立擴散模型[7-8]，或增加時間因素對模型進行改進[9-10]；李勇建等人[11]研究了基于Petri網(wǎng)的傳染病傳播模型；另外，還可以根據(jù)博弈論而進行信息傳播動態(tài)研究[12]以及基于博弈論對輿情傳播建模[13]；王光輝和劉怡君[14]考慮信息擴散的影響因子，建立輿論擴散的一般性模型。

由于微博網(wǎng)絡(luò)的信息傳播過程具有明顯的動態(tài)性，這也是資源流動問題中的一個關(guān)鍵問題，因此在目前的很多研究中都包含了信息傳播的時間動態(tài)特征。包括從信息本身角度或者從用戶屬性角度研究。例如Bian Jingwen等人[15]提出了一種擴散目標的影響模型來預(yù)測微博信息未來的傳播狀態(tài)。Iribarre和Moro[16]研究了人類活動方式對動態(tài)信息傳播模式的影響。除此之外，用戶是微博網(wǎng)絡(luò)中的關(guān)鍵因素之一。微博類社交網(wǎng)絡(luò)主要研究了用戶關(guān)注行為(被轉(zhuǎn)發(fā)次數(shù)、被提及次數(shù))對衡量用戶影響力的作用[17]；通過社交網(wǎng)絡(luò)中的用戶轉(zhuǎn)發(fā)行為預(yù)測信息的流行程度[18]；分析在線社交網(wǎng)絡(luò)中的用戶行為特征[19]；基于用戶的社會關(guān)系和用戶影響力推薦好友[20]；通過關(guān)系特征和時間特征因素識別用戶身份(微博水軍)[21]等。目前，在以往的研究中，國內(nèi)外學(xué)者對微博網(wǎng)絡(luò)的信息傳播過程進行了多方面的研究，為探討社交網(wǎng)絡(luò)的信息傳播的規(guī)律問題提供了研究基礎(chǔ)和支持，但是已有的研究還存在以下不足之處：(1)已有的信息傳播規(guī)律研究缺乏對傳播過程的結(jié)構(gòu)化描述，尤其從微觀角度(也就是從用戶關(guān)注關(guān)系結(jié)構(gòu)和用戶行為變化的角度)對信息傳播過程的直觀描述。(2)已有的研究往往缺乏對傳播過程的動態(tài)性分析，缺乏對信息傳播過程中的用戶動態(tài)行為分析和傳播條件分析。

基于此，本文根據(jù)微博網(wǎng)絡(luò)中的信息傳播問題，以及Petri網(wǎng)是一個針對并發(fā)系統(tǒng)建模和分析具有獨特優(yōu)勢的工具，能有效描述和研究并發(fā)的、異步的、分布式的系統(tǒng)[22]，提出了一種基于Petri網(wǎng)的描述微博信息傳播系統(tǒng)的動態(tài)模型，從一種全新的框架直觀地描述微博信息傳播的動態(tài)過程。該模型通過首先根據(jù)Petri網(wǎng)原理對微博網(wǎng)絡(luò)基本元素進行定義，包括組成網(wǎng)系統(tǒng)的結(jié)構(gòu)部分，包括三元組N=(S,T;F) (S是庫所，T是變遷，F(xiàn)是流關(guān)系)，以及能夠反應(yīng)系統(tǒng)運行狀態(tài)的標識部分，包括標識M和標志token[23]。為了使建模更加方便，我們使用庫所/變遷系統(tǒng)[24]。同時，由于微博的用戶關(guān)注行為種類較多，我們引入了顏色Petri網(wǎng)[25]和時延Petri網(wǎng)[26]描述微博用戶行為的多樣性和動態(tài)特點。顏色Petri網(wǎng)的實質(zhì)是針對token進行分類，通過n維向量表示帶n種顏色的Petri網(wǎng)，能夠使微博信息傳播過程中的用戶行為表現(xiàn)得更加清晰；時延Petri網(wǎng)引入時間因素，能夠表示變遷發(fā)生的時間，這使微博信息傳播中動態(tài)地描述用戶的行為更加符合現(xiàn)實情況。在此基礎(chǔ)上，研究微博信息傳播網(wǎng)絡(luò)的動態(tài)性質(zhì)以及傳播條件。同時動態(tài)地根據(jù)用戶不同的關(guān)注行為具體描述信息傳播過程中的網(wǎng)絡(luò)狀態(tài)和變化。最終根據(jù)模型基本特點給出算法的詳細步驟，以及具體算例和真實數(shù)據(jù)驗證。本文的主要貢獻包括以下幾個方面：(1) 結(jié)合Petri網(wǎng)和微博用戶之間的“關(guān)注”關(guān)系以及用戶關(guān)注行為(包括發(fā)帖/轉(zhuǎn)發(fā)、評論、回復(fù)、刪除、忽略)等特征，建立一種基于Petri網(wǎng)的微博信息傳播系統(tǒng)動態(tài)模型。將信息傳播中的基本對象(包括用戶關(guān)注行為、轉(zhuǎn)發(fā)時間、轉(zhuǎn)發(fā)規(guī)模等)用Petri網(wǎng)的形式進行解釋和定義。(2) 引入變遷(用戶關(guān)注行為)發(fā)生的隨機性，能夠根據(jù)實際情況定義權(quán)函數(shù)接口和延時函數(shù)，同時從Petri網(wǎng)的角度提出了優(yōu)化傳播條件的方法，并利用Petri網(wǎng)的研究方法進行新浪微博中的信息傳播驗證。(3)本文提出的動態(tài)模型更加直觀地反映了微博信息傳播的結(jié)構(gòu)特點、傳播方式和時間動態(tài)特性，為輿情態(tài)勢分析和用戶行為的分析奠定基礎(chǔ)，并且對其他社交網(wǎng)絡(luò)的信息傳播研究具有一定的借鑒意義。

2 基于Petri網(wǎng)的微博信息傳播動態(tài)模型

2.1 微博信息傳播的動態(tài)模型概述

根據(jù)微博中的用戶之間的“關(guān)注”關(guān)系特征，以及Petri網(wǎng)的基本特征，例如能夠描述并發(fā)的行為，能夠表示資源的流動問題等，本文提出了一種依據(jù)Petri網(wǎng)對微博信息傳播進行描述的基本模型。該模型使用Petri網(wǎng)的基本元素，并與微博網(wǎng)絡(luò)中的用戶關(guān)注行為、用戶之間的關(guān)系、微博信息等相互對應(yīng)，在此基礎(chǔ)上給出模型的相關(guān)定義。

定義1.微博用戶庫所表示微博網(wǎng)絡(luò)中具有信息傳播能力的用戶。

微博用戶庫所在圖中用圓形表示，記為s。

定義2. 行為變遷表示微博用戶對信息的具體關(guān)注動作，所有的用戶關(guān)注行為記為集合Ω= { 發(fā)帖/轉(zhuǎn)發(fā)，點贊，回復(fù)，評論，刪除，忽略 }，在圖中用正方形表示，記為t。

定義1和定義2的關(guān)系如圖1所示。用戶庫所s2與用戶庫所s1對應(yīng)兩個實際用戶，并通過行為變遷t12相連接，在實際網(wǎng)絡(luò)中表示用戶s2是用戶s1的粉絲。從而，我們稱用戶s2為粉絲用戶。同時，本文規(guī)定，若用戶s2是用戶s1的粉絲，那么有且僅有一條有向連接線連接兩個用戶。

圖1 微博用戶之間的關(guān)系示意圖

定義3. 微博用戶行為狀態(tài)向量token. 用戶庫所s擁有的token數(shù)表示用戶s采取的關(guān)注行為情況，圖中用黑點表示。若用戶s采取了關(guān)注行為，則s具有的token個數(shù)為1，否則token個數(shù)為0。并且規(guī)定每個用戶的token數(shù)只能取0或1。

用戶行為狀態(tài)向量是一個6維向量，記為M(si)=(a1,a2,a3,a4,a5,a6)，分別表示用戶的行為：發(fā)帖/轉(zhuǎn)發(fā)、評論、回復(fù)、點贊、刪除及忽略6個基本動作。

定義4(標識狀態(tài)M). 網(wǎng)絡(luò)當前標識狀態(tài)表示在k時刻時每個用戶擁有token的數(shù)目，記為Mk；用戶當前標識狀態(tài)表示k時刻用戶si的行為狀態(tài)向量，記為Mk(si)。

如圖2，給出用戶s2是用戶s1的粉絲，用戶s1在標識狀態(tài)M0下轉(zhuǎn)發(fā)了微博信息(見圖2(a))，M0(s1)=(1, 0, 0, 0, 0, 0)。粉絲用戶s2從用戶s1獲得信息，并進行轉(zhuǎn)發(fā)和評論，標識狀態(tài)變?yōu)镸1(見圖2(b))，M1(s2) =(1, 1, 0, 0, 0, 0)。

定義5(輸入權(quán)函數(shù)W(s,t)). 由于一個用戶s在狀態(tài)M0采取關(guān)注之后，得到的token數(shù)為1，并且在以后的任意狀態(tài)中都保持原有關(guān)注狀態(tài)，即?M∈R(M0)。為了滿足該要求，輸入權(quán)函數(shù)權(quán)值W(s,t) = 0。即行為變遷的發(fā)生將消耗用戶0個token。

圖2 不同標識狀態(tài)下的微博用戶行為情況

定義6(輸出權(quán)函數(shù)W(t,s)).W(t,s)表示關(guān)注行為發(fā)生后粉絲用戶產(chǎn)生的token數(shù)量滿足的條件?？紤]關(guān)注行為的發(fā)生條件并與輸入權(quán)函數(shù)保持一致，本文規(guī)定輸出權(quán)函數(shù)權(quán)值W(t,s) ={0, 1}6。

定義7(微博用戶容量K(s)). 規(guī)定微博用戶描述中的容量函數(shù)為K(s)={1}6，也就表明每個用戶最多只能擁有一個token。

定義8.微博用戶行為變遷發(fā)生條件M[t>表示用戶采取發(fā)帖/轉(zhuǎn)發(fā)、評論、回復(fù)、點贊、刪除、忽略6個基本動作行為所滿足的條件。

定義9(行為變遷操作延時DI(t)).指微博信息在傳播過程中用戶采取關(guān)注行為之間的時間間隔。DI(t)是一些離散的值。

根據(jù)操作延時和關(guān)注行為發(fā)生條件M[t>，規(guī)定當一個行為變遷滿足發(fā)生條件M[t>時(見圖3(a))，由于微博用戶的參與行為具有隨機性特點，因此根據(jù)實際情況給定用戶行為發(fā)生時間，將分配給行為變遷t一個操作延時DI(t)(見圖3(b))。當時間到達DI(t)時，行為變遷t將發(fā)生(見圖3(c))。具體如圖3。

圖3 分配操作延時DI(t)后用戶關(guān)注行為發(fā)生過程舉例

2.2 微博信息傳播網(wǎng)絡(luò)的定義

下面我們給出微博信息傳播網(wǎng)絡(luò)Σp的定義。

定義10.稱Σp=(S，T，F(xiàn)，K，W，M，DI)是微博信息Petri網(wǎng)，其中

(1)(S，T；F)是一個網(wǎng)，

P表示權(quán)函數(shù)和延時函數(shù)是隨機函數(shù)。

(2)Σp滿足

(a)Σp是S-簡單純網(wǎng)，即對于?x,y∈S∪T，都有(?x=?y)∧(x?=y?)→x=y(?x,?y表示變遷或庫所的輸入集，x?,y?表示變遷或庫所的輸出集)，且對?t∈T，有|?t|=|t?|=1且?t∩t?=φ，其中φ表示空集；

(b)對?s∈S，有K(s)={1}6；

(c)對于?t∈T，設(shè)s=?t，s′=t?，有W(s,t) = 0，W(t,s′)= {0, 1}6≠0；

(d)對?t∈T，M為任意標識，s′=t?，若M[t>，則M(s′)≤W(t,s′)；

(e)對?t∈T，M為任意標識，s=?t，s′=t?，若M(s′)≠0，則有M(s)≥(1, 0, 0, 0, 0, 0)。

由定義10可以驗證，Σp符合2.1節(jié)的所有定義。其中，S-簡單純網(wǎng)是指一個網(wǎng)中的元素(用戶庫所和行為變遷)不含有自環(huán)(兩個元素互以對方為輸入輸出)且兩個不同的元素不具有相同的輸入和相同的輸出。

2.3 Σp的變遷發(fā)生條件

結(jié)合Σp的定義，可得到微博信息傳播網(wǎng)絡(luò)Σp的變遷發(fā)生條件M[t>：

(1)

以上是Σp網(wǎng)變遷的發(fā)生條件。其中①的修改是為了滿足定義10的(5)，也就是只有用戶轉(zhuǎn)發(fā)了微博信息，其粉絲用戶才能繼續(xù)傳播信息；②的修改滿足定義10的(4)，即粉絲用戶的token向量要小于等于輸出權(quán)函數(shù)的token向量，也就是粉絲用戶s′在其關(guān)注行為發(fā)生之前，該用戶沒有從其他用戶那里獲得信息并采取關(guān)注行為；增加④為了滿足時延條件。

3 微博信息傳播系統(tǒng)動態(tài)模型特征和描述

3.1 微博信息傳播網(wǎng)絡(luò)Σp的動態(tài)性質(zhì)

利用微博信息Petri網(wǎng)Σp對實際微博信息傳播系統(tǒng)進行建模，主要目的之一就是借助模型來分析實際系統(tǒng)的性質(zhì)和功能，下面討論Σp的可逆性、可覆蓋性、有界性、活性、可持續(xù)性、公平性及可達性，這些性質(zhì)不僅與實際系統(tǒng)運行過程有著密切的聯(lián)系，更為運行時的優(yōu)化和變遷發(fā)生條件的簡化提供依據(jù)。

性質(zhì)1(可逆性).Σp是不可逆網(wǎng)系統(tǒng)。

該性質(zhì)表示在微博網(wǎng)絡(luò)的信息傳播過程中，一個用戶獲知了某信息后，該用戶將保持始終知曉該信息。

性質(zhì)2(可覆蓋性).若M和M′為Σp的兩個標識，且存在變遷序列σ∈T*使M[σ>M′，則M′是M的一個覆蓋。

性質(zhì)3(有界性).Σp是有界網(wǎng)且B(Σp) =K(s) ={1}6。

性質(zhì)4(活性).Σp的任意標識都可能成為死標識，且Σp一定會達到死標識。

性質(zhì)4說明了在一條微博信息傳遞過程中，參與信息傳播的用戶是有限的，因此微博網(wǎng)絡(luò)總能達到一個相對穩(wěn)定狀態(tài)，此時該網(wǎng)絡(luò)中的任意用戶都不會采取關(guān)注行為。

性質(zhì)5.Σp中任意變遷最高是一級活的。

性質(zhì)5表明在微博信息傳播過程中的任意狀態(tài)下，行為變遷都有權(quán)發(fā)生，也就是用戶均可以采取關(guān)注行為。

性質(zhì)6(可持續(xù)性).對于?t1，t2∈T，若t1?=t2?，則t1，t2之間不具有可持續(xù)性。若t1?≠t2?，則t1，t2之間具有可持續(xù)性。

此性質(zhì)規(guī)定指向相同用戶的兩個有向連接線中的行為變遷(用戶關(guān)注行為)最多只能發(fā)生一個。

性質(zhì)7(公平性).Σp是公平Petri網(wǎng)。由性質(zhì)4可知Σp不存在無限的變遷序列，再由公平性的定義顯然得證。

3.2 Σp變遷發(fā)生的簡化條件M[t>

3.2.1 Σp變遷發(fā)生條件的簡化

由于Σp定義有較強的限定性，根據(jù)Σp的性質(zhì)可以進一步的簡化變遷發(fā)生條件M[t>，目的是保證計算機在模擬時具有更高的效率。在化簡前先引入定理1。

定理1.對于?t∈T，s′=t?，若M[t>，則M(s′)=0。

證明.

由Σp的發(fā)生條件M[t>的定義，可知

② ?s∈t?-?t:M(s)+W(t,s)≤K(s)

M(s)≤W(t,s)

由于M(s)≥ 0，先假設(shè)M(s)> 0：

不妨設(shè)M(s)的第i個分量為1(i=1,2,3,4,5,6)，因為M(s)≤W(t,s)，其中W(t,s) ={0,1}6，則能夠說明W(t,s)的第i個分量也是1。所以能得到M(s) +W(t,s)的第i個分量為2，與已知條件M(s) +W(t,s)≤K(s)矛盾。故M(s)=0。

由Σp網(wǎng)的定義，Σp網(wǎng)是S-簡單純網(wǎng)，并且?t∩t?=φ，再根據(jù)定理1可將Σp網(wǎng)變遷發(fā)生條件M[t>化簡為：

(2)

3.2.2 關(guān)于DI(t)進一步的討論

根據(jù)性質(zhì)6，指向相同用戶的兩個有向弧的變遷(用戶關(guān)注行為)最多只能發(fā)生一個。所以為變遷t分配延時，可以視作為t指向的用戶分配延時。若DI(tij) =a，其中a∈R0，tij指向的用戶為sj，不妨記為DI(sj) =a。

這樣可以將時延DI重新定義為：

這樣做的好處是，減少了計算機在執(zhí)行M[t>判斷時查找DI(tij)的時間。由于在微博信息傳播的系統(tǒng)中變遷的數(shù)量遠遠大于庫所(用戶)的數(shù)量。以庫所的形式保存延時要比以變遷的形式保存延時更優(yōu)。由此討論，最終可將Σp網(wǎng)變遷發(fā)生條件M[t>化簡為：

(3)

3.3 微博信息傳播過程的用戶關(guān)注行為動態(tài)描述

針對基于Σp的微博信息傳播系統(tǒng)動態(tài)模型，對微博信息傳播過程的用戶關(guān)注行為進行詳細描述。

在網(wǎng)絡(luò)中給定用戶si，其中，i=1, 2, 3, 4, 5；用戶行為變遷tij，i,j=1, 2, 3, 4, 5；標識狀態(tài)M。它們的關(guān)系為：用戶s2、s3、s4是用戶s1的粉絲，用戶s2是用戶s3的粉絲，s5是s3和s4的粉絲。對應(yīng)的用戶關(guān)注行為及具體關(guān)系如圖4(a)所示。根據(jù)用戶行為的特點，我們將用戶關(guān)注行為分為3類：圖中帶有斜線的行為變遷和用戶庫所表示用戶采取了轉(zhuǎn)發(fā)或發(fā)帖行為，且信息能夠從該用戶繼續(xù)傳播；圖中的深灰色行為變遷和用戶庫所表示用戶對微博信息已經(jīng)采取關(guān)注行為并且其粉絲用戶不能從該用戶處繼續(xù)轉(zhuǎn)發(fā)微博信息，包括的關(guān)注行為有：評論、點贊、回復(fù)、刪除；圖中的淺灰色行為變遷和用戶庫所表示該用戶看到了信息很感興趣(或不感興趣)但未采取任何關(guān)注行為，或該用戶看到了該信息但直接忽略。

給定一個初始標識狀態(tài)M0。在M0標識狀態(tài)下，用戶s1產(chǎn)生了發(fā)帖行為，發(fā)布一條微博信息。此時用戶s1的粉絲，用戶s2、s3、s4無狀態(tài)。標識狀態(tài)M0情況下的用戶行為描述如圖4(b)所示。

當粉絲用戶s2、s3、s4根據(jù)實際情況和實際時間分別采取關(guān)注行為忽略、回復(fù)、轉(zhuǎn)發(fā)時，此時的標識狀態(tài)記為M1。標識狀態(tài)M1情況下的用戶行為描述如圖4(c)所示。

時間繼續(xù)進行，此時網(wǎng)絡(luò)中已經(jīng)有4個用戶對這條微博信息做出關(guān)注行為的反應(yīng)，并且用戶s3采取了回復(fù)行為，其粉絲用戶s5無法從s3獲得信息，同時其粉絲用戶s2忽略了這條微博信息。根據(jù)實際情況，對于給定的網(wǎng)絡(luò)，此微博信息只能從用戶s4的粉絲繼續(xù)傳播。當網(wǎng)絡(luò)中的用戶s5從用戶s4獲得信息并做出關(guān)注行為“轉(zhuǎn)發(fā)”時，當前標識狀態(tài)記為M2。標識狀態(tài)M2情況下的用戶行為描述如圖4(d)所示。此時網(wǎng)絡(luò)中的用戶均已存在狀態(tài)。

根據(jù)上述描述過程，在實際的微博用戶網(wǎng)絡(luò)中，以定義和用戶關(guān)注行為發(fā)生條件為基礎(chǔ)，我們能夠較清晰地描述微博社交網(wǎng)絡(luò)中的微博信息傳播以及用戶關(guān)注行為情況，并呈現(xiàn)出網(wǎng)絡(luò)中的信息傳播路徑、網(wǎng)絡(luò)當前狀態(tài)，以及便于更加深入分析微博信息傳播系統(tǒng)的特征。

圖4 微博信息傳播過程中的用戶關(guān)注行為描述

4 Σp動態(tài)模型算法步驟

根據(jù)第2部分和第3部分給出的微博信息傳播系統(tǒng)的模型定義以及Σp相關(guān)性質(zhì)和發(fā)生條件，現(xiàn)給出模型的算法具體步驟，其中用戶sj是用戶si的粉絲，兩個用戶之間的用戶關(guān)注行為是tij。T*表示即將要發(fā)生的行為變遷tij的集合，也就是已經(jīng)被分配操作延時的用戶sj的關(guān)注行為tij。具體步驟如下：

1)尋找用戶si的粉絲sj；如果用戶si存在粉絲用戶，轉(zhuǎn)到步驟2，如果用戶si沒有粉絲則算法結(jié)束或轉(zhuǎn)到步驟4；

2)針對粉絲用戶sj，判斷tij是否滿足發(fā)生條件M[tij>，滿足發(fā)生條件時進入步驟3，否則返回步驟1；

3)為關(guān)注行為tij指向的用戶sj分配操作延時DI(sij) (當用戶sj沒有從si獲得信息時，為用戶sj分配操作延時DI(sj)<0 (本文賦值-1)且DI(sj)<0時可以被新的DI(sj)>0代替。若sj能夠從si獲得信息，則分配操作延時DI(sj)>0)，并將tij存入關(guān)注行為集合T*中；

4)將每個關(guān)注延時DI(sj)減去所有關(guān)注延時中延時為正數(shù)的最小值min(DI(sj)>0)；

5)從T*中找出所有在當前標識狀態(tài)可以發(fā)生的用戶關(guān)注行為tij，也就是找到操作延時DI(sj)=0的關(guān)注行為；

6)發(fā)生關(guān)注行為tij，設(shè)置粉絲用戶sj的token顏色狀態(tài)；

7)將已經(jīng)發(fā)生的用戶關(guān)注行為tij從T*中刪除，并尋找已經(jīng)發(fā)生的關(guān)注行為tij所指向用戶sj的粉絲，重復(fù)步驟1直至信息傳播完成。

5 實驗

5.1 算例分析

根據(jù)提出的微博信息傳播系統(tǒng)動態(tài)模型以及算法的具體步驟，給出具體算例。算例的詳細過程見圖5。給定網(wǎng)絡(luò)及初始標識狀態(tài)如圖5(a)所示。

用戶s1發(fā)出一條微博信息，即初始狀態(tài)為M0[1, 0, 0, 0, 0]，尋找用戶s1的粉絲，找到粉絲用戶s2，s3，s4，對于粉絲s2，連接用戶s1和s2的關(guān)注行為t12滿足關(guān)注行為發(fā)生條件M[t12>，因此為用戶s2分配操作延時DI(s2)=3，并將關(guān)注行為t12存入集合T*中，完成表1中的第1步；對于s1的粉絲用戶s3，連接用戶s1和s3的關(guān)注行為t13滿足關(guān)注行為發(fā)生條件M[t13>，因此為用戶s3分配操作延時DI(s3)=3，并將關(guān)注行為t13存入集合T*中，完成第2步；同理，為粉絲用戶s4分配操作延時DI(s4)=2并將關(guān)注行為t14存入集合T*中，完成第3步。如圖5(b)所示。

將所有操作延時進行處理，能夠得到DI(si)=DI(si)-min(DI(sj)>0)；此時找到能發(fā)生的關(guān)注行為，即DI(s4)=0。為用戶s4確定關(guān)注行為是轉(zhuǎn)發(fā)，因此用戶s4的token狀態(tài)向量為M(s4)=(1, 0, 0, 0, 0, 0)，完成第4步。得到標識狀態(tài)M1(1)。如圖5(c)所示。

將關(guān)注行為t14從集合T*中刪除，完成第5步。

尋找用戶s4的粉絲，發(fā)現(xiàn)粉絲用戶s5，判斷連接用戶s4和s5的關(guān)注行為t45滿足關(guān)注行為發(fā)生條件M[t45>，但是用戶s5并未從用戶s4看到信息。因此為用戶s5分配操作延時DI(s5)= -1，并將關(guān)注行為t45存入集合T*中，完成第6步。得到標識狀態(tài)M1(2)，如圖5(d)所示。

將所有操作延時進行處理，能夠得到DI(si)=DI(si)-min(DI(sj)>0)；此時找到能夠發(fā)生的關(guān)注行為，即DI(s2)=DI(s3)=0。為用戶s2確定關(guān)注行為是評論，因此用戶s2的token狀態(tài)向量為M(s2)=(0, 1, 0, 0, 0, 0)，為用戶s3確定關(guān)注行為是轉(zhuǎn)發(fā)，因此用戶s3的token狀態(tài)向量為M(s3)=(1, 0, 0, 0, 0, 0)，完成第7步。得到標識狀態(tài)M2。如圖7(e)所示。

將關(guān)注行為t12和t13從集合T*中刪除，完成第8步。

用戶s2沒有粉絲，也就沒有信息繼續(xù)傳播的對象，用戶s3的粉絲s2已經(jīng)采取了關(guān)注行為，粉絲s5的操作延時DI(s5)= -2，也就是還能夠采取關(guān)注行為。因此判斷連接用戶s3和s5的關(guān)注行為t35滿足關(guān)注行為發(fā)生條件M[t35>。為用戶s5分配操作延時DI(s5)=1，并將關(guān)注行為t35存入集合T*中，替代關(guān)注行為t45。完成第9步。

繼續(xù)將所有操作延時進行處理，我們得到DI(si)=DI(si)-min(DI(sj)>0)；此時找到能發(fā)生的關(guān)注行為t35，即DI(s5)=0。為用戶s5確定關(guān)注行為是點贊，因此用戶的token狀態(tài)向量為M(s5) = (0, 0, 0, 1, 0, 0)，完成第10步。得到標識狀態(tài)M3。如圖5(f)所示。

我們可以得到表1所示的各個指標的值及其變動情況表示。為了更加清晰地顯示出微博網(wǎng)絡(luò)的狀態(tài)變化以及行為變遷(用戶關(guān)注行為)的發(fā)生情況，給出可達標識圖(如圖6所示)和關(guān)聯(lián)矩陣(如式(5)所示)，便于分析網(wǎng)絡(luò)性能。其中，關(guān)聯(lián)矩陣用A表示。

在圖6所示的可達標識圖中，有界微博網(wǎng)絡(luò)Σp存在死標識。其中，狀態(tài)[1, 1, 1, 1, 1]是一個死標識。此時網(wǎng)絡(luò)中在[1, 1, 1, 1, 1]狀態(tài)下不存在能夠可達的狀態(tài)。

圖5 微博信息傳播算例的詳細過程

與此同時，由于微博網(wǎng)絡(luò)中用戶可能采取的關(guān)注行為(轉(zhuǎn)發(fā)、回復(fù)、評論、點贊等)具有隨機性，因此在實際微博網(wǎng)絡(luò)中不止一個標識狀態(tài)可能成為死標識。并且，在圖6中顯示的實線代表該算例在給定的權(quán)函數(shù)和操作延時情況下的標識圖；虛線表示的是針對給定的網(wǎng)絡(luò)，其他可能達到的標識狀態(tài)。

在式(4)的關(guān)聯(lián)矩陣A中，1表示用戶(庫所)是對應(yīng)關(guān)注行為(行為變遷)的輸入用戶(用戶庫所)，-1表示用戶(用戶庫所)是對應(yīng)關(guān)注行為(行為變遷)的輸出用戶(用戶庫所)。由此我們可以清晰地看出該微博網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)，從而驗證狀態(tài)之間的可達性。

圖6 Σp的可達標識圖

(4)

5.2 新浪微博數(shù)據(jù)集驗證

為了驗證本文所提出的基于Petri網(wǎng)的微博信息傳播系統(tǒng)動態(tài)模型的可行性，本文使用新浪微博網(wǎng)絡(luò)中的真實數(shù)據(jù)進行模型的驗證。針對微博信息傳播中的具體情景進行模擬實驗：給定一條微博信息的轉(zhuǎn)發(fā)情況，利用真實的微博信息傳播數(shù)據(jù)及其特點，采用本文提出的算法流程，模擬一條微博信息在一段時間內(nèi)的動態(tài)傳播情況，其中新浪微博數(shù)據(jù)使用北京大學(xué)PKUVIS可視化分析工具[27]獲取。

通過編程實現(xiàn)Σp動態(tài)模型算法流程，模擬出微博用戶轉(zhuǎn)發(fā)消息的時間序列，結(jié)合Gephi軟件，最終實現(xiàn)消息的可視化動態(tài)傳播模擬。在消息傳播仿真過程中，需要為用戶的關(guān)注行為分配操作延時，本文實驗中隨機分配操作延時，并取0≤DI(s)≤48(其中單位時間為1)。

通過實驗?zāi)M，得到了本次模擬實驗的結(jié)束時間點是在第102個時間點，實驗結(jié)果能夠反映每個時刻的傳播情況，以及反映傳播停止的總時間.由于不同傳播模式(存在一個或者多個明顯的中心節(jié)點)下呈現(xiàn)的模擬結(jié)果形式幾乎相同，本文給出一種傳播情況(具有兩個較為明顯的中心節(jié)點)的動態(tài)模擬結(jié)果，截取5個時間點的微博消息轉(zhuǎn)發(fā)動態(tài)情況，如圖7所示。

針對實驗結(jié)果，我們與真實的信息傳播情況進行了對比，使用Modularity class對節(jié)點數(shù)據(jù)進行分組，比較模擬實驗與實際傳播情況中的每組節(jié)點數(shù)所占總數(shù)的百分比，發(fā)現(xiàn)模擬結(jié)果和實際結(jié)果每組節(jié)點的數(shù)量較為接近，如表2所示。

需要特別說明的是，該實驗是針對所提出的微博信息傳播動態(tài)模型的具體場景應(yīng)用，針對一條微博信息傳播數(shù)據(jù)，獲取了信息的轉(zhuǎn)發(fā)用戶ID和轉(zhuǎn)發(fā)時間等，以上實驗沒有對M[t>的具體細節(jié)進行實現(xiàn)。

表1 用戶行為各指標值及其變化情況描述

表2 模擬結(jié)果與實際結(jié)果的節(jié)點數(shù)量分組比較

圖7 新浪微博消息傳播動態(tài)模擬結(jié)果

由于獲取的真實數(shù)據(jù)僅保留了轉(zhuǎn)發(fā)用戶列表，因此將用戶token狀態(tài)向量形式M(s)=(1,0,0,0,0,0)簡化為0和1，其中0表示未轉(zhuǎn)發(fā)，1表示轉(zhuǎn)發(fā)。總體來說，該驗證實驗重在模擬算法流程，僅僅是針對已獲取到數(shù)據(jù)的簡化實驗。

6 結(jié)語

微博網(wǎng)絡(luò)信息傳播過程的研究是在線社交網(wǎng)絡(luò)研究的重要問題之一。以對微博網(wǎng)絡(luò)信息傳播的結(jié)構(gòu)化描述出發(fā)，本文為信息傳播對象的研究提出了一種新思路和新方法，根據(jù)微博信息傳播的網(wǎng)絡(luò)結(jié)構(gòu)特點、傳播方式和動態(tài)特性，以Petri網(wǎng)絡(luò)的結(jié)構(gòu)為基礎(chǔ)，提出了一種直觀的動態(tài)描述模型。本文定義了針對微博的網(wǎng)絡(luò)系統(tǒng)Σp以及其中的參數(shù)、函數(shù)等對象，使其準確地反映微博信息傳播的結(jié)構(gòu)特點、傳播方式和時間動態(tài)特性。本文模型不僅表現(xiàn)出微博網(wǎng)絡(luò)中信息傳播的不同路徑，同時直觀地描述了微博信息傳播的動態(tài)過程，能夠展現(xiàn)出信息傳播過程中的多種用戶在線行為情況，從而分析信息傳播過程中的輿情態(tài)勢。

更進一步地，通過研究Σp網(wǎng)絡(luò)的動態(tài)特性，定義微博信息傳播中的基本對象(包括用戶關(guān)注行為、轉(zhuǎn)發(fā)時間、轉(zhuǎn)發(fā)規(guī)模等)，根據(jù)實際情況定義權(quán)函數(shù)和延時函數(shù)，權(quán)函數(shù)和延時函數(shù)均具有一定的隨機性。同時提出了優(yōu)化傳播條件的方法和算法流程步驟，通過算例以及新浪微博真實網(wǎng)絡(luò)的信息傳播情況對Σp進行信息傳播實際分析，驗證了模型工具的有效性，表明模型能夠直觀簡單地描述微博網(wǎng)絡(luò)信息傳播過程，這使得Σp網(wǎng)絡(luò)具有實際的可行性以及一定的可擴展性，并為社會網(wǎng)絡(luò)中的用戶行為研究和輿情分析提供了一定的支持。

在后續(xù)的研究工作中，我們將在其它社交網(wǎng)絡(luò)中擴展本文模型的研究，探討其在更加豐富多彩的場景中的應(yīng)用。