于　婧　王　晶　張校輝

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

?

一種在線社會網(wǎng)絡(luò)消息擴散模型

于婧王晶張校輝

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

摘要在線社會網(wǎng)絡(luò)的消息擴散研究對社會經(jīng)濟、政治等方面都具有較大的現(xiàn)實意義。針對當(dāng)前在線社會網(wǎng)絡(luò)消息擴散模型存在的獨立、封閉等問題，引入時間、主題以及合作與競爭關(guān)系、非封閉世界環(huán)境等實際因素，提出一種消息擴散概率計算方法以及消息擴散模型。將此模型應(yīng)用于實際在線社會網(wǎng)絡(luò)拓?fù)溥M(jìn)行網(wǎng)絡(luò)仿真，通過與網(wǎng)絡(luò)真實消息擴散過程對比，結(jié)果表明該模型能夠很好地擬合現(xiàn)實在線社會網(wǎng)絡(luò)的消息擴散過程。

關(guān)鍵詞在線社會網(wǎng)絡(luò)消息擴散主題影響力合作與競爭

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引言

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

近年對在線社會網(wǎng)絡(luò)的研究日益深入，研究內(nèi)容包括網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)、用戶行為分析、用戶隱私與安全、系統(tǒng)架構(gòu)、社團(tuán)發(fā)現(xiàn)以及消息擴散等方面。本文主要研究在線社會網(wǎng)絡(luò)的消息擴散機制。在線社會網(wǎng)絡(luò)中的消息擴散研究對于消息的推廣、商業(yè)營銷、網(wǎng)絡(luò)輿情引導(dǎo)及控制等具有重要的實際意義。

本文首先簡要介紹當(dāng)前在線社會網(wǎng)絡(luò)消息擴散的研究現(xiàn)狀及目前存在的問題，針對問題提出了一種在線社會網(wǎng)絡(luò)的消息擴散概率的計算方法以及消息擴散模型，并對此模型進(jìn)行了仿真分析，最后給出了全文總結(jié)。

1研究現(xiàn)狀及問題引出

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

消息擴散模型研究的主要任務(wù)是充分考慮各種影響消息擴散的因素，理解、模擬并預(yù)測消息擴散過程[3]。針對現(xiàn)實網(wǎng)絡(luò)提出的經(jīng)典模型在在線社會網(wǎng)絡(luò)中有一定的適用性，但在線社會網(wǎng)絡(luò)之上進(jìn)行的消息擴散與傳統(tǒng)社會網(wǎng)絡(luò)消息擴散不盡相同，它與在線社會網(wǎng)絡(luò)的特點及體系架構(gòu)有密不可分的關(guān)系。

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

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

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

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

2消息擴散模型

2.1基本思想

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

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

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

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

2.2模型描述

1) 定義

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

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

2) 轉(zhuǎn)發(fā)概率

節(jié)點u的鄰居節(jié)點v轉(zhuǎn)發(fā)消息Infor的概率表示為：

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

(1)

其中θv是節(jié)點v的主題分布，tcurrent是當(dāng)前時間，β是指OSN之外外部環(huán)境對轉(zhuǎn)發(fā)概率的影響因子。

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

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

(2)

其中，τ代表節(jié)點對消息轉(zhuǎn)發(fā)時延的平均值，λ是節(jié)點轉(zhuǎn)發(fā)消息的平均概率，0≤λ≤1，σ是瑞利分布參數(shù)。

另外，若節(jié)點v有多個鄰居節(jié)點發(fā)布消息Infor，則節(jié)點v轉(zhuǎn)發(fā)消息Infor的概率需綜合考慮這多個鄰居節(jié)點的影響，則轉(zhuǎn)發(fā)概率：

(3)

3) 算法描述

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

輸入：網(wǎng)絡(luò)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實驗方法

獲取在線社會網(wǎng)絡(luò)數(shù)據(jù)，選取關(guān)鍵事件的數(shù)據(jù)，研究該事件的實際擴散過程。以該網(wǎng)絡(luò)拓?fù)錇榛A(chǔ)，初始化網(wǎng)絡(luò)中節(jié)點初始主題分布及主題影響力分布及消息轉(zhuǎn)發(fā)主題門限值，在網(wǎng)絡(luò)中注入消息，采用本文所述消息擴散模型進(jìn)行消息擴散，以發(fā)布消息的節(jié)點個數(shù)的變化趨勢來描述消息在網(wǎng)絡(luò)中的擴散過程。

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

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

(4)

歸一化擴散速率r′(tn)定義為擴散速率r(tn)與網(wǎng)絡(luò)內(nèi)節(jié)點總數(shù)N的比值，即：

(5)

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

3.2仿真結(jié)果及分析

通過運行網(wǎng)絡(luò)爬蟲腳本，獲取新浪微博的詳細(xì)用戶數(shù)據(jù)，具體包括用戶名、好友、粉絲、發(fā)表的微博及發(fā)表時間等信息，整理得到節(jié)點數(shù)為4039的在線社交網(wǎng)絡(luò)數(shù)據(jù)集及網(wǎng)絡(luò)拓?fù)洹?/p>

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

圖2　事件擴散仿真對比圖

模擬仿真過程τλσα1100.110.5250.310.53100.310.8

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

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

4結(jié)語

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

參考文獻(xiàn)

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

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

[3] 李棟,徐志明,李生,等.在線社會網(wǎng)絡(luò)中信息擴散[J].計算機學(xué)報,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] 趙麗,袁睿翕,管曉宏,等.博客網(wǎng)絡(luò)中具有突發(fā)性的話題傳播模型[J].軟件學(xué)報,2009,20(5):1384-1392.

中圖分類號TP3

文獻(xiàn)標(biāo)識碼A

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

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