一種在線社會網絡消息擴散模型

于　婧　王　晶　張校輝

(解放軍信息工程大學　河南 鄭州 450002)

?

一種在線社會網絡消息擴散模型

于婧王晶張校輝

(解放軍信息工程大學河南 鄭州 450002)

摘要在線社會網絡的消息擴散研究對社會經濟、政治等方面都具有較大的現實意義。針對當前在線社會網絡消息擴散模型存在的獨立、封閉等問題，引入時間、主題以及合作與競爭關系、非封閉世界環境等實際因素，提出一種消息擴散概率計算方法以及消息擴散模型。將此模型應用于實際在線社會網絡拓撲進行網絡仿真，通過與網絡真實消息擴散過程對比，結果表明該模型能夠很好地擬合現實在線社會網絡的消息擴散過程。

關鍵詞在線社會網絡消息擴散主題影響力合作與競爭

AN INFORMATION DIFFUSION MODEL FOR ONLINE SOCIAL NETWORKS

Yu JingWang JingZhang Xiaohui

(PLA Information Engineering University,Zhengzhou 450002,Henan,China)

AbstractResearch on information diffusion of online social networks has a greater relevance in both social economy and politics. In order to solve the problems of being independent and closed existed in current online social network information diffusion, this paper proposes an information diffusion probability calculation approach and information diffusion model by introducing the practical factors such as time, topic, cooperation and competition relationship, and non-closed world environment, etc. Applying the model to actual online social network topology to conduct network simulation, by comparing with the information diffusion process in reality, result shows that the model can commendably fit the information diffusion process in real online social networks.

KeywordsOnline social networkInformation diffusionTopic influenceCooperation and competition

0引言

當前互聯網最熱的應用無疑當屬在線社會網絡OSN[1](Online Social Network)。在線社會網絡的主體是用戶，用戶可以創建主頁及發布信息，可以與其他用戶建立社會關系。可以說在線社會網絡是一個用戶創建的自由通信及共享信息的內容分發系統。在線社會網絡的出現為互聯網用戶提供了一種新的交互手段，這不僅使得互聯網的信息總量以一種前所未有的速度巨大的膨脹，而且極大地提高了消息傳播的速度及影響覆蓋范圍。在線社會網絡已經在世界的方方面面發揮了不可忽視的作用，如2010年的Arab Spring等具有影響世界格局的政治活動等都有在線社會網絡應用的身影。

近年對在線社會網絡的研究日益深入，研究內容包括網絡拓撲發現、用戶行為分析、用戶隱私與安全、系統架構、社團發現以及消息擴散等方面。本文主要研究在線社會網絡的消息擴散機制。在線社會網絡中的消息擴散研究對于消息的推廣、商業營銷、網絡輿情引導及控制等具有重要的實際意義。

本文首先簡要介紹當前在線社會網絡消息擴散的研究現狀及目前存在的問題，針對問題提出了一種在線社會網絡的消息擴散概率的計算方法以及消息擴散模型，并對此模型進行了仿真分析，最后給出了全文總結。

1研究現狀及問題引出

在線社會網絡是由消息傳播路徑組成的復雜網絡，消息傳播反過來又促進在線社會網絡結構的變化。消息傳播是用戶行為活動的表現，在線社會網絡中消息的擴散本質上是用戶對消息的擴散。用戶作為信息接受、消化和傳播的主體，由于其特有的社會屬性和個人特質，形成了對不同信息內容的不同關注度及信息傳播行為模式[2]。通過對用戶的屬性信息以及信息瀏覽歷史進行歸納、統計和抽象，建立消息擴散模型，對于研究消息的傳播及在線社會網絡演化機制具有重要的研究意義。

消息擴散模型研究的主要任務是充分考慮各種影響消息擴散的因素，理解、模擬并預測消息擴散過程[3]。針對現實網絡提出的經典模型在在線社會網絡中有一定的適用性，但在線社會網絡之上進行的消息擴散與傳統社會網絡消息擴散不盡相同，它與在線社會網絡的特點及體系架構有密不可分的關系。

消息擴散模型研究中，消息擴散概率的研究是重中之重。社會網絡中的消息擴散概率是指消息沿著社會鏈接從一個用戶擴散到另外一個用戶的概率，可以直觀理解為社會網絡中邊的權重。最初的文獻[4]采用通過節點度來計算邊的權重或者隨機分配邊的權重的方法進行消息擴散的研究，現在看來這些方法過于簡單和隨意，并不能代表現實中的真實信息擴散機制。另外，雖然很多研究將用戶之間的消息擴散概率視為是恒定不變的，但是實際上它是與時間[5]及消息主題[6,7]密切相關的，會隨著時間或者主題的變化而變化。

另外，當前對擴散進程的研究都是假定消息傳播是獨立的，而文獻[8]的研究得出，消息的傳播是存在合作與競爭的關系。競爭會導致傳播的可能性降低，而合作則使得彼此的消息更容易被接納。

當前對消息擴散的研究是在假定在線社會網絡是一個封閉世界的前提下進行的，并沒有考慮線下其他因素包括人際交往、電視、報紙等媒體對它的影響，文獻[9]研究得出在Twitter中只有71%的消息是由于Twitter內部影響而擴散的，而剩余29%均來自于外部事件的影響。因此，研究消息擴散時需考慮用戶身處的多個環境的影響。

因此，本文針對上述問題提出了考慮時間、主題、合作與競爭以及非封閉世界環境下的消息擴散概率計算方法，并提出了消息擴散模型。

2消息擴散模型

2.1基本思想

根據上述分析，我們考慮影響在線社會網絡中用戶對消息的傳播的主要因素包括：1) 消息的發布者與用戶的鄰接關系；2) 消息的發布者與用戶的交往程度；3) 消息所屬主題對用戶的吸引力；4) 消息的發布者在消息所屬主題上的影響力；5) 消息發布的時間；6) 外界對用戶的影響。

由此提出消息擴散模型的基本思想：用戶只接受鄰居節點的消息，即只考慮對鄰居節點發布的消息是否進行擴散；OSN之外的媒體、社交等對用戶的消息擴散起部分作用；每個消息歸屬于一定的主題，消息在網絡內的流動受消息所屬主題及節點主題分布的驅使，用戶只對自己感興趣的主題的消息進行擴散；消息的發布者在消息主題上的影響力直接影響用戶對消息擴散的可能性；消息的發布者與用戶之間的合作或競爭的關系對消息擴散起關鍵作用；消息發布的時間也就是消息的新鮮程度也影響消息擴散成功性。

具體擴散流程歸結為兩個步驟，如圖1所示(圖中標識Info的用戶表示該用戶發布了消息Info)：1) 用戶從鄰居節點接收消息，綜合考慮上述因素判斷是否進行消息擴散；2) 若消息成功擴散，需對鄰居節點進行影響力反饋，提高發布節點的主題影響力。

圖1　OSN消息擴散模型示意圖

2.2模型描述

1) 定義

定義1在線社會網絡可以使用一個有向或者無向圖G=(V,E)表示，V是節點集合，E?V×V是節點間鏈路集合。圖中節點代表用戶，邊代表用戶之間存在關聯。對?euv=1，若節點u與v之間存在鏈接，否則euv=0。

定義4定義節點u的對主題T的轉發門限值為pu(T)thresh，采用線性閾值模型進行信息擴散，即當計算得到的轉發概率大于pu(T)thresh時，對消息進行轉發。

2) 轉發概率

節點u的鄰居節點v轉發消息Infor的概率表示為：

pv(Infor|u)=f(Infor,tcurrent,θv,ξ)

(1)

其中θv是節點v的主題分布，tcurrent是當前時間，β是指OSN之外外部環境對轉發概率的影響因子。

轉發消息的時間間隔對轉發概率的影響服從指數分布，即從消息發布到消息轉發的時間越長轉發概率越低。β從兩方面考慮，一是與轉發時間間隔的關系符合瑞利分布，即影響力隨著時間的增長會迅速出現一個高峰期，然后快速下降，二是消息本身帶來的外部影響因子，記作α，0≤α≤1。

根據2.1節中的描述及上述分析，得出pv(Infor|u)的表達式：

(2)

其中，τ代表節點對消息轉發時延的平均值，λ是節點轉發消息的平均概率，0≤λ≤1，σ是瑞利分布參數。

另外，若節點v有多個鄰居節點發布消息Infor，則節點v轉發消息Infor的概率需綜合考慮這多個鄰居節點的影響，則轉發概率：

(3)

3) 算法描述

消息擴散算法以節點主題影響力為切入點，計算節點對消息的轉發概率，確定消息的傳播范圍。具體算法描述如下：

輸入：網絡G初始主題影響力集合E0；

輸出：最終主題影響力集合Ef；

1 Initialize：Ef=E0；

2 foreach u∈V do

3 foreach information I in u, do

4 foreach v∈Nb(u) do

5 calculate pv(I);

6 if(pv(I)≥pv(TI)thresh)

7 issue the information I;

8 updateEu(TI);

9 end

10 end

11 end

12 end

13 return Ef;

3實驗仿真

3.1實驗方法

獲取在線社會網絡數據，選取關鍵事件的數據，研究該事件的實際擴散過程。以該網絡拓撲為基礎，初始化網絡中節點初始主題分布及主題影響力分布及消息轉發主題門限值，在網絡中注入消息，采用本文所述消息擴散模型進行消息擴散，以發布消息的節點個數的變化趨勢來描述消息在網絡中的擴散過程。

以離散時間模型描述[10]，t0表示初始時刻，t1,t2,…,tn,…表示經過1,2,…,n,…個單位時間后的時刻。定義NI(tn)為tn時刻已發布該消息的節點數，擴散速率r(tn)表示(tn-1,tn]時間段內新發布消息的節點數，則：

NI(tn)=NI(tn-1)+r(tn)

(4)

歸一化擴散速率r′(tn)定義為擴散速率r(tn)與網絡內節點總數N的比值，即：

(5)

考慮模型中參數的選取對擴散的影響，計算擴散速率，給出擴散速率對時間的曲線，與實際在線社會網絡的消息擴散圖進行比較，若曲線符合，則說明模型的可用性。

3.2仿真結果及分析

通過運行網絡爬蟲腳本，獲取新浪微博的詳細用戶數據，具體包括用戶名、好友、粉絲、發表的微博及發表時間等信息，整理得到節點數為4039的在線社交網絡數據集及網絡拓撲。

從中聚焦某焦點事件的所有微博，統計得到該事件隨時間的擴散情況如圖2所示，橫坐標表示時間，以天為單位，縱坐標表示歸一化擴散速率。以此數據集為基礎，選取模型參數如表1所示，得到模型仿真擴散過程如圖2所示。

圖2　事件擴散仿真對比圖

模擬仿真過程τλσα1100.110.5250.310.53100.310.8

從圖2中可以看出，模型仿真結果與實際擴散過程總的擴散趨勢是基本相符的，即擴散速率會在一段時間內迅速上升，隨后下降至平穩。

雖然從數據集中可以提取用戶主題分布等信息，但無法得到用戶間的關系信息，仿真時采用隨機生成的關系向量替代實際用戶關系信息，這在一定程度上影響了仿真的效果。

4結語

本文從消息傳播的機理出發，引入主題影響力、節點主題分布等與主題相關的參數，節點間的合作與競爭關系，非封閉世界環境下外部環境影響因子，充分考慮了時間對消息擴散的影響，提出了一種消息擴散模型。仿真實驗表明，該模型能夠模擬消息的擴散過程，擴散趨勢與實際擴散過程相符，對在線社會網絡中消息擴散的研究具有一定的借鑒意義。

參考文獻

[1] 徐恪,張賽,陳昊,等.在線社會網絡的測量與分析[J].計算機學報,2014,37(1):165-188.

[2] 楊士強,孫立峰,崔鵬.Web社會網絡分析[J].中國計算機學會通訊,2011,7(2):52-58.

[3] 李棟,徐志明,李生,等.在線社會網絡中信息擴散[J].計算機學報,2014,37(1):189-206.

[4] Kempe D,Kleinberg J M,Tardos E.Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD 2003).Washington DC,USA,2003:137-146.

[5] Goyal A,Bonchi F,Lakshmanan L V S.Learning influence probabilities in social networks[C]//Proceedings of the 3rd ACM International Conference on Web Search and Data Mining(WSDM2010),New York,USA,2010:241-250.

[6] Tang J,Sun J M,Wang C,et al.Social influence analysis in large-scale networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD 2009).Paris,France,2009:807-816.

[7] Liu L,Tang J,Han J W,et al.Mining topic-level influence in heterogeneous networks[C]//Proceedings of the 19th ACM Conference on Information and Knowledge Management (CIKM2010).Toronto,Canada,2010:199-208.

[8] Myers S,Leskovec J.Clash of the contagions:Cooperation and competition in information diffusion[C]//Proceedings of the IEEE International Conference on Data Mining (ICDM2012).Brussels,Belgium,2012:539-548.

[9] Myers S A,Zhue C,Leskovec J.Information diffusion and external influence in networks[C]//Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (SIGKDD2012),Beijing,China,2012:33-41.

[10] 趙麗,袁睿翕,管曉宏,等.博客網絡中具有突發性的話題傳播模型[J].軟件學報,2009,20(5):1384-1392.

中圖分類號TP3

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.02.026

收稿日期：2014-07-16。國家重點基礎研究發展計劃項目(2012 CB315901，2012CB315905)。于婧，講師，主研領域：計算機網絡。王晶，講師。張校輝，講師。