微博轉發網絡中的節點特征和傳播模型

李晉，楊子龍

(1.北京信息科技大學，北京 100192;2.解放軍電子工程學院網絡系，安徽 合肥 230037)

微博轉發網絡中的節點特征和傳播模型

李晉1，楊子龍2

(1.北京信息科技大學，北京 100192;2.解放軍電子工程學院網絡系，安徽 合肥 230037)

微博作為重要的社交網絡平臺，具有傳播快速、平臺影響大的特點。微博用戶的節點特征決定了其網絡影響力。研究了微博轉發網絡中節點的度值特征和傳播模型。首先通過區分信息流動方向構建了微博轉發網絡;其次分別討論了出度—入度的均值和方差，明確二者的差異，并分析了考慮節點度值特征的信息傳播過程;最后通過仿真驗證可以看出:邊的有向性對信息傳播有著顯著的影響，在有向條件下，滲流閾值增加，同樣概率下傳播范圍變小，信息傳播更為困難。

轉發網絡;微博;度值特征;信息傳播

1 引言

隨著在線社會網絡的普及，微博、微信等平臺逐漸滲透進人們的生活，其影響力已經從虛擬網絡拓展到實際生活中［1］。因此，在線社會網絡越來越集中到人們日常行為模式等領域。微博短文本形式使得信息傳播更加快速，作為一種全新的在線社交應用，近年來得到了快速發展。由于微博這些前所未有的新特征以及其中信息傳播產生的巨大社會效應，它已經成為了一把“雙刃劍”。一方面微博為廣大網民提供了一個更加自由便捷的信息獲取和發布平臺，推動了我國信息化社會的發展;另一方面，微博中也包含了謠言、誹謗、偏激觀點、扭曲價值觀等一系列負面問題，并在一些別有用心的個人和組織的推動下，產生了極壞的影響。因此，提取、分析微博中的信息傳播特征，構建相應的傳播模型有著十分重要的理論和現實價值。對于已知的網絡，如何評價網絡的動力學性能一直是研究者關注的重點內容，當前主要利用網絡疾病傳播模型對信息傳播進行研究，但疾病傳播模型往往假設傳播時間是無限長的。在很多現實情況中，關注的往往是一個時間段內信息的傳播情況。SIR(susceptible infective removal)模型及其變型是研究信息傳播最為常用的模型，在該模型中，個體僅在有限時間內保持感染態，隨后便能恢復，甚至如果這些鄰居個體足夠幸運，就有可能永遠不會得這種疾病。根據傳染病模型中的SIR模型定義，利用積分可以求得傳播概率，在一個固定時間段τ內，這種概率為:

其中，β表示傳播速度。假設這些事件是獨立的，即疾病在網絡中沿任意一條邊的傳播是相互獨立的，將φ作為一個常數，那么整個疾病傳播過程可以認為是以概率占據每條邊或者以概率1-φ移除每條邊，整個過程就可以看作一個“鍵滲流”過程。

利用滲流理論對微博的信息傳播過程進行研究，通過構建動力學過程分析傳播的影響因素，已經取得一定的成果:參考文獻［2］主要分析度值對傳播范圍的映射關系，基于微博數據構建信息傳播的動力學過程，利用復雜網絡理論研究其機理;參考文獻［3］主要針對在線社會網絡中的觀點形成過程進行研究，將其抽象為擴散過程，提出了輿論傳播模型;參考文獻［4］借鑒傳染病模型，主要分析了不同的傳播主體對傳播結果的影響，對應3個不同狀態將用戶類型進行抽象，結合信息傳播方向的影響，分析度值分布的冪律特性對傳播行為的影響;參考文獻［5］在真實的微博數據中進行了滲流過程的仿真;參考文獻［6］在服從冪律分布的隨機網絡中，通過隨機刪除和目標刪除網絡節點或邊，計算不同占有概率下巨分支的大小來分析網絡性能。

無向網絡對于滲流閾值的求導依賴于鄰接矩陣的對稱性，因此原有的分析方法不能直接應用于有向網絡，這是因為有向網絡中的鄰接矩陣通常是非對稱的，無法得到正交特征向量。因此本文借鑒已有研究成果，利用數值方法分析有/無關聯特征情況下的滲流過程，通過對比，得到有向網絡下的傳播能力分析。

2 基于微博信息的有向轉發網絡度值特征

2.1 基于微博信息的有向轉發網絡

在微博的信息傳播過程中，用戶i發布一條信息，其所有粉絲用戶都會接到該信息，若其中一個用戶j轉發這條信息，則用戶j的所有粉絲用戶(如用戶k)都會繼續接到信息，以此類推，該信息沿著多條i→j→k→…的路徑在用戶之間呈網狀蔓延。實際中，微博用戶數量龐大，信息傳播過程復雜，如何衡量網絡的傳播能力是一個重要課題。本節通過采集微博用戶轉發行為的數據，抽象得到有向轉發網絡模型，分析信息傳播和滲流過程的映射關系，設計傳播能力的評估指標，為后續研究提供模型基礎。

首先對微博用戶及其行為進行抽象建模。微博轉發網絡抽象為 G=(V，E)，其中，G是全部節點 vi的集合，對應微博的用戶;E是邊eij的集合，對應用戶之間的關系，這里的關系是“轉發行為”，轉發行為是信息傳遞的基礎，如果節點vj轉發了鄰接節點 vi的信息，則在傳播過程中，vi→vj將在下一次以更大的概率成為信息傳遞的路徑，記為eij，否則 eij=0;指向 vi的節點數為節點vi的入度，記為 kiin;vi指向節點數為節點vi的出度，記為kiout。

在信息傳播過程中，只會有部分個體以及個體間部分關系會參與到傳播過程中來，所有的用戶關系中只有部分關系會發揮作用，而這個過程同樣能夠用滲流過程表示。

在微博轉發網絡中，有一些隨機均勻選擇的節點被刪除。微博轉發過程是刪除過程的“逆向”，一條邊被保留意味著一條消息被轉發，衡量的是保留概率，可以用概率參數φ表示，表示節點存在于網絡中。因此，φ=1就表示網絡中的所有節點都被保留(即沒有節點被刪除)，φ=0表示沒有節點被保留(即所有的節點都被刪除)。在實際情況中，網絡中不可能只存在一個分支，初始時，所有節點被保留，但是隨著節點被刪除以后網絡逐漸分割，如分裂為兩個分支或者更多，將其中最大的一個分支稱為巨分支。本文只考慮一個分支的情況，也就是分析巨分支的消亡過程，即從φ=1到φ=0的過渡。巨分支的形成和解體叫做滲流過渡。當網絡中包含一個巨分支時，稱這個網絡是可滲流的，而出現滲流過渡的臨界值就叫做滲流閾值。在很多方面，滲流過渡與泊松隨機圖中巨分支形成的相變很相似。在隨機圖中變化的不是被保留的節點，而是節點間連接的概率。然而，在這兩種情況下，當網絡中有足夠多的點被刪除時，巨分支就會分裂成一些小分支。

2.2 出度-入度分布

度(degree)是針對網絡中的節點來說的，節點i的度k(i)定義為與節點i相連的所有邊的數目。度描述了個體的特性，而度分布描述了網絡的整體特性?，F實中的很多網絡，如科學家合作網、捕食網絡、國際互聯網，都服從冪率分布，冪指數在-3.4和-2.0之間，而不是之前人們所認為的泊松分布。參考文獻［7］中，研究了含權科學家合作網的冪律分布等統計特性;參考文獻［8］中，將現實社交關系推廣到合作網絡中來衡量其特性;參考文獻［1］中，系統地研究了大量在線社會網絡的冪律分布特性。一般地，根據冪律分布可繪出一條向右偏斜得很厲害，拖著長長“尾巴”的累積分布曲線，它與鐘形的泊松分布曲線有顯著的不同。這種“長尾”分布表明，絕大多數個體的尺度很小，而只有少數個體的尺度相當大。

以往通常利用最小二乘法來擬合數據，但得出的結果經常會出現很大的誤差，這主要是由以下兩個原因引起的:

· 在“長尾”中出現的大的波動;

·很難確定冪律分布成立的范圍。

在分析度分布特性時可以從兩方面著手，一是設定冪律分布成立的范圍，二是和其他分布結合。這里假設度分布服從冪律分布和指數分布的雙分布:

綜上所述，需要在度分布特性分析中辨識兩個參數，分別是 α 和 xmin。

度分布參數辨識的流程如下。

(1)利用極大似然估計的方法，在給定xmin情況下，可求出:

(2)首先利用冪律分布的密度函數的1g-1g圖像或者利用圖像判定xmin的范圍，然后從這個范圍里選取對于實際數據最合適的xmin。選擇xmin，令:

取得最小值，其中S(x)、P(x)分別為擬合數據和原始數據的分布函數。

(3)對于擬合數據和原始數據，利用K-S統計量求出p-value，p的值越接近1，則擬合數據與原始數據越吻合，通常當p≤0.1時，認為利用冪律函數對原始數據進行的擬合失敗。在求p-value的過程中，由于認為當x≤xmin時，分布并不符合冪律分布，所以，利用冪律分布擬合出來的數據與原始數據相比是不完全的，忽略了x≤xmin的數據，那么利用K-S統計量計算p-value比較擬合情況的結果也不精確。筆者希望可以使擬合數據在x≤xmin時非常接近原始數據，而在x＞xmin時，符合冪律分布。

(4)根據實際數據，再找出其他可能符合的分布，并得出擬合數據。利用似然比檢驗比較不同分布的擬合情況，從而確定符合原始數據的最佳分布。其中似然比檢驗用來評估兩個模型中哪個模型更適合當前的數據分析。具體來說，一個相對復雜的模型與一個相對簡單的模型比較，檢驗哪個模型能夠顯著地適合一個特定的數據集。引入統計量LR表示兩種模型似然值的差異。

在這里，統計量LR近似服從卡方分布，自由度是兩個模型的參數個數之差。其中，L1和L2分別是兩個分布的似然函數。對于微博轉發網絡，節點vi的kiin和kiout是分析網絡的基本屬性，本節主要分析同一節點的kiin、kiout的統計特征和不同節點kiin、kiout之間的關系。擬合參數分別為出度為xmin=5，α=-2.060 0，入度為 xmin=4.7，α=-2.920 0。研究同一節點出度—入度值特征，可以看出:在雙對數坐標中，kiin、kiout與F(k)不存在明顯的線性關系(如圖1(a)所示)，即不服從嚴格的冪律分布;節點的kiin、kiout的分布不同(如圖1(a)所示)，kiin下降速度快于kiout，即kiout具有更顯著的長尾效應。圖1(b)橫軸為kiin和kiout的度值，縱軸為對應的方差?？梢钥闯?，當kiin固定時，kiout的方差明顯大于kiout固定時kiin的方差。這是因為，出度表征了節點的客觀影響力，更能體現節點間的差異。因此，在分析傳播能力時，應考慮網絡的出度—入度序列，保留出度—入度值特征，而不是簡單地用冪律分布表示。

圖1 微博轉發網絡節點度值特征

3 考慮度分布特性的微博信息傳播

Newman給出了無向網絡滲流后巨分支規模的解，并得到滲流閾值，本文考慮有向網絡情況。與無向的情況不同，有向滲流考慮的是巨出向分支而不是巨分支。假如信息是從某一個節點開始向外傳播，那么最終所有獲得信息的節點的集合實際上就是滲流之后的網絡中初始節點的出向分支，認為最終網絡中最大的出向分支規模就代表了最終接受信息的人數，但實際上只有當信息是從最大出向分支的初始節點開始傳播的時候，接收信息的人數才等于最大出向分支的節點數。研究的轉發網絡與現實當中的轉發關系相對應，如果一個用戶發出的信息具有影響力，那么他在網絡中出現分支的規模一定很大，那么相對應地，滲流后對應的節點在最終的網絡中依然會有一個很大的出向分支，所以滲流之后的最大出向分支規模就表示了信息傳播的最大可能影響范圍，具有一定的代表性。

節點是否屬于某個出向分支是由其入邊決定的，如果一個節點有一個入邊來自于巨出向分支，那么它肯定屬于巨出向分支，反之，則它所有入邊的另一端點都不屬于巨出向分支。假定uout是節點不經過特定一條與其相連的入邊與巨出分支相連接的平均概率，那么可以得到:

對于任意一個節點，一個鄰接節點通過出邊指向它，qin(k)表示鄰接節點入度為k的概率。利用聯合分布p(a，b)表示一個節點入度為a且出度為b的概率，那么通過出邊連接的節點的鄰接節點入度為k，出度為i的概率為:

那么，無論鄰接節點出度取何值，其入度為k的概率為:

可以利用圖解法，將式(6)左右兩邊分別構造方程，分別為方程y=uout與方程:

由于qin(k)為條件概率，其和為1，所以uout=1時為恒等式。在uout=1處相切得到滲流閾值:

［9］利用不同的方法，對有向網絡中巨強連通分支求得了同樣的滲流閾值，實際上巨出向分支、巨入向分支與巨強連通分支出現的條件是相同的。此時，出分支的規模為:

通過上面的推導，得到了考慮節點關聯性的有向滲流模型解法。接下來，將分別驗證有向性和關聯性對網絡信息傳播性能的影響以及所提出方法的正確性。

4 仿真驗證

本文將研究對象限定為新浪“名人堂”用戶?！懊颂谩庇脩羰切吕烁鶕颂玫南嚓P規定篩選出的認證用戶，是在信息傳播過程中有著重要價值的真實用戶。通過接口“statuses/user-timeline”爬取微博信息，若M-0為原創初始微博信息，信息M-1轉發自M-0，則接口所返回的M-1數據中包含了“retweeted-status”字段，其中記錄了包含初始發布用戶在內的M-0的全部內容，但若此時另一條消息M-2轉發自 M-1，M-2所返回的數據 “retweeted-status”字段中包含的依然是M-0而非M-1的內容。因此針對轉發長度大于1的轉發消息，需要通過分析信息中的轉發標志獲知其直接轉發信息來源。新浪微博中以前綴//@user-name(其中user-name表示用戶名)來標識直接轉發信息來源。分析2012年9月23日至10月23日這一個月內的名人堂用戶轉發信息，利用轉發關系來定義邊，利用賬號來定義節點。其中出度是轉發的數目，入度是被轉發的數目。最終得到了一個由92 933個節點、1 083 584條邊構成的轉發網絡。

首先，分別利用無向轉發和有向轉發網絡進行仿真，找出不同傳播概率下子網絡的最大出向分支，而這個最大出向分支的規模也就代表了最終的傳播范圍，通過這種方式可以粗略地模擬真實的傳播情況，對比兩種仿真結果，觀察有向性對于信息傳播的影響。同時利用Newman提出的無向滲流解法和本文提出的有向滲流解法預測出不同傳播概率下的巨出向分支規模以及滲流閾值，與真實有向轉發網絡仿真進行對比，驗證提出的有向滲流解法的正確性。圖2中4條曲線分別表示以下內容。

· 有向仿真:在有向微博轉發網絡利用滲流模型進行仿真得到的結果。

· 有向滲流解法:利用前面提到的有向滲流模型解法求解得到的結果。

· 無向仿真:在無向微博轉發網絡利用滲流模型進行仿真得到的結果。

· 無向滲流解法:利用前面提到的無向滲流模型解法求解得到的結果。

觀察圖2可以發現，有向性對信息傳播性能有著極大的影響，使得相同傳播概率下信息傳播范圍明顯變小，同時也可以發現，相比于無向滲流解法，提出的有向滲流解法與無向仿真結果較為吻合，但仍有明顯差異。接下來觀察滲流閾值，如圖3所示。

圖3中4條曲線與圖2相同，觀察圖3可以發現仿真結果并沒有一個十分明顯的閾值，這是由于有限規模效應(finite size effect)造成的，但通過觀察曲線的變化趨勢，還是可以得到一個大致的臨界區域，大致對應閾值，邊的有向性使得滲流閾值明顯變大，即使得信息爆發變得更加困難，同時還可以發現，相比于無向滲流解法，提出的有向滲流解法給出的滲流閾值接近實際仿真閾值，但依然有偏差。

圖2 滲流有向性全局對比

圖3 滲流有向性閾值對比

通過上面可以看出:

· 邊的有向性對信息傳播有著顯著的影響，在有向條件下，滲流閾值增加，同樣概率下傳播范圍變小，信息傳播更為困難;

· 提出的有向滲流解法較好地貼合了有向性特征，但與有向轉發網絡信息傳播仿真結果相比，依然存在一定差距。

5 結束語

本文通過區分信息傳播的方向性，利用滲流理論研究微博轉發網絡中節點度值特征。區分信息傳播的方向有助于更加細致地分析轉發概率對傳播性能的影響，有向滲流的關聯更能夠準確反映微博中的轉發場景，為進一步分析影響滲流閾值、傳播范圍的因素提供了理論支撐。

參考文獻:

［1］胡海波，王科，徐玲，等.基于復雜網絡理論的在線社會網絡分析［J］.復雜系統與復雜性科學，2008，5(2):1-14.HU H B，WANG K，XU L，et al.Analysis of online social networks based on complex network theory［J］.Complex Systems and Complexity Science，2008，5(2):1-14.

［2］張彥超，劉云，張海峰，等.基于在線社交網絡的信息傳播模型［J］.物理學報，2011，60(5):66-72.ZHANG Y C，LIU Y，ZHANG H F，et al.The research of information dissemination model on online social network ［J］.Acta Physica Sinica，2011，60(5):66-72.

［3］熊熙，胡勇.基于社交網絡的觀點傳播動力學研究 ［J］.物理學報，2012，61(15):104-110.XIONG X，HU Y.Research on the dynamics of opinion spread based on social network services ［J］.Acta Physica Sinica，2012，61(15):104-110.

［4］LIU D C，CHEN X.Rumor propagation in online social networks like Twitter- a simulation study［C］//Proceedings of the Third InternationalConference on Multimedia Information Networking and Security，November 4-6，2011，Washington DC，USA.New Jersey:IEEE Press，2011:278-282.

［5］GRABOWSKI A，KOSINSKI R A.Epidemic spreading in a hierarchical social network ［J］.Physical Review E，2004，70(3):1027-1035.

［6］CALLAWAY D S，NEWMAN M E，STROGATZ S H，et al.Network robustness and fragility:Percolation on random graphs［J］.Physical Review Letters，2000，85(25):5468-5471.

［7］LI M，FAN Y，CHEN J，et al.Weighted networks of scientific communication:the measurement and topological role of weight［J］.PhysicaAStatisticalMechanics&ItsApplications，2005，350(2):643-656.

［8］CHANG H，SU B B，LIU C P，et al.Community，hierarchy and interweavementin collaboration networks ［J］.International Journal of Modern Physics C，2011，19(10):1537-1554.

［9］SCHWARTZN，COHENR，BEN-AVRAHAM D，etal.Percolation in directed scale-free networks ［J］.Physical Review E，2002，66(1):015104.

Node characteristic and propagation model in microblog forwarding network

LI Jin1，YANG Zilong2
1.Beijing University of Information Science and Technology，Beijing 100192，China 2.School of Network，Electronic Engineering Institute，Hefei 230037，China

Microblog is an important social network with rapid propagation speed and great influence.The network influence is determined by users'node characteristic.Nodes'degree and propagation model in microblog forwarding network were investgated.Firstly，microblog forwarding network was constructed through distinguishing information flow direction.Secondly，the mean and variance of out-degree and in-degree were discussed.The difference between out-degree and in-degree was clarified.Finally，the simulation shows that the direction characteristic of edge has significantly influence on information propagation.The propagation becomes harder and propagation range diminishes while percolation threshold rises in directed graph under the same probability.

forwarding network，microblog，degree characteristic，information propagation

s:Humanistic and Social Science Research Plan Project of Beijing Municipal Education Commission(No.SM201411232005)，Young and Middle-Aged Backbone Teachers Training Program for Visiting Scholars Abroad in Universities Owned by the Municipal Government of Beijing in 2014(No.067145301400)

TN393

A

10.11959/j.issn.1000-0801.2016006

2015-07-15;

2015-12-17

北京市教育委員會人文社會科學研究計劃面上項目(No.SM201411232005);北京市屬高校教師專項培訓2014年中青年骨干教師一般國外訪問學者研修培訓項目(No.067145301400)

李晉(1977-)，女，北京信息科技大學講師，主要研究方向為網絡與新媒體傳播。

楊子龍(1977-)，男，解放軍電子工程學院助理工程師，主要研究方向為復雜網絡與信息傳播。