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

于　婧　王　晶　張校輝

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

?

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

于婧王晶張校輝

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

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

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

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

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

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

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

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

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

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

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

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

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

2消息擴(kuò)散模型

2.1基本思想

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

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

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

圖1　OSN消息擴(kuò)散模型示意圖

2.2模型描述

1) 定義

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

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

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

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

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

(1)

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

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

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

(2)

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

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

(3)

3) 算法描述

消息擴(kuò)散算法以節(jié)點(diǎn)主題影響力為切入點(diǎn)，計(jì)算節(jié)點(diǎn)對(duì)消息的轉(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實(shí)驗(yàn)仿真

3.1實(shí)驗(yàn)方法

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

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

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

(4)

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

(5)

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

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

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

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

圖2　事件擴(kuò)散仿真對(duì)比圖

模擬仿真過程τλσα1100.110.5250.310.53100.310.8

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

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

4結(jié)語

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

參考文獻(xiàn)

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

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

[3] 李棟,徐志明,李生,等.在線社會(huì)網(wǎng)絡(luò)中信息擴(kuò)散[J].計(jì)算機(jī)學(xué)報(bào),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é)報(bào),2009,20(5):1384-1392.

中圖分類號(hào)TP3

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

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

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