李涵曼　張志勇　趙長偉

(河南科技大學信息工程學院　河南 洛陽 471023)

?

基于SIR模型的社交網(wǎng)絡推手節(jié)點發(fā)現(xiàn)及信息傳播抑制

李涵曼張志勇趙長偉

(河南科技大學信息工程學院河南 洛陽 471023)

摘要推手節(jié)點對社交網(wǎng)絡信息傳播有非常重要的作用。在傳統(tǒng)SIR模型中引入“推手節(jié)點”概念，研究該類節(jié)點所造成的熱門話題在網(wǎng)絡中的傳播規(guī)律，以及對社交網(wǎng)絡信息傳播的影響和控制。利用YouTube數(shù)據(jù)構建社交網(wǎng)絡拓撲結(jié)構，實驗發(fā)現(xiàn)，當節(jié)點傳播概率大于0.7時，可設置為推手節(jié)點，對于信息傳播抑制可采用目標免疫算法。而在一個社交網(wǎng)絡中傳播節(jié)點的整體信息免疫大于0.2時能有效抑制信息傳播，該值為使用重要熟人免疫策略對信息傳播進行抑制的參數(shù)值。

關鍵詞社交網(wǎng)絡信息傳播SIR傳染病模型推手節(jié)點

0引言

社交網(wǎng)絡是以互聯(lián)網(wǎng)為平臺，為用戶提供各種方便快捷的交互，如電子郵件、實時消息服務等。主要作用是為那些擁有相同興趣與活動的人創(chuàng)建在線社區(qū)。社交網(wǎng)絡在全球的迅速普及，使得人們更適應于從網(wǎng)絡中獲取各式各樣所需的信息。社交網(wǎng)絡的信息傳播在人們的日常生活中扮演著越來越重要的角色并在逐步改變著人們的生活、交際和思考方式。

基于社交網(wǎng)絡下的信息傳播研究有很多，Sudbury[1]通過在隨機網(wǎng)絡上使用SIR模型來研究謠言傳播問題；Watts等[2]提出了WS小世界網(wǎng)絡，并在此基礎上研究了謠言傳播機制；Kuperman等[3]在WS小世界網(wǎng)絡基礎上使用SIR模型對信息傳播進行了進一步的研究；張彥超等[4]使用SIR模型研究了信息在SNS網(wǎng)絡上的信息傳播并進行了仿真；Earn等[5]使用SEIR模型詳細介紹了不同地區(qū)、不同季節(jié)以及不同政權對病毒傳播以及人口的影響，對于我們研究信息在不同社區(qū)不同時間段以及政府導向?qū)π畔鞑サ挠绊懹泻艽蟮慕梃b意義；熊熙等[6]在社交網(wǎng)絡基礎上對SIR模型進行了研究并使用仿真實驗與Deffuant模型和Hegselmann-Krause模型進行了對比；Chen等[7]主要對網(wǎng)絡上的熱點信息研究，通過不同時間話題的變化規(guī)律，來找出熱點形成的規(guī)律；顧亦然等[8]和夏玲玲[9]在對SEIR模型研究的基礎上，對信息傳播使用了重要熟人免疫策略對其進行了控制，并證明了策略的有效性；Watts等[10]提出在網(wǎng)絡中，引起信息的大規(guī)模傳播往往跟那些度數(shù)很大的節(jié)點有關的，而是其周圍那些大量群體推動的；Nekovee等[11]通過研究復雜網(wǎng)絡喜愛的謠言傳播，發(fā)現(xiàn)在無標度網(wǎng)絡中謠言的傳播速率要比在隨機網(wǎng)絡上高；程軍軍[12]使用SIR模型為基礎，通過仿真發(fā)現(xiàn)網(wǎng)絡拓撲特征會影響信息傳播強度和范圍。社會輿論參與度越高,信息在網(wǎng)絡中成功擴散的幾率就越大；在平均度和聚類系數(shù)較大的網(wǎng)絡中,免疫節(jié)點起到信息防火墻的作用,在一定程度上抑制信息擴散。社會輿論參與度越大,個體平均接觸信息次數(shù)越少。李合莉[13]構建了S-SEIR模型，通過模型分析出信息價值是影響社交網(wǎng)絡信息傳播過程中的重要因素，從信息內(nèi)容、信息傳播途徑、信息主體、信息環(huán)境四個方面探討了社交網(wǎng)絡信息傳播控制與干預策略。Lee[14]采用仿真實驗研究信息在社交網(wǎng)絡內(nèi)的傳播發(fā)現(xiàn)在線社交網(wǎng)絡圖比傳播的網(wǎng)絡圖更密集，只需要三次傳播就可以覆蓋帶有初始節(jié)點的社交網(wǎng)絡。Freeman[15]將SIR模型描述應用于Digg.com，研究信息在Digg.comd中的傳播并成功預測了部分用戶的行為。

本文在SIR模型的基礎上引入了推手節(jié)點。研究節(jié)點的傳播規(guī)律，發(fā)現(xiàn)當傳播節(jié)點向外傳播信息的概率大于0.7時，整個社交網(wǎng)絡表現(xiàn)良好的傳播性能，可以把0.7設置為推手節(jié)點的閾值，對于信息傳播的抑制可采用目標免疫算法；當整個社交網(wǎng)絡內(nèi)傳播節(jié)點變?yōu)槊庖吖?jié)點的概率大于0.2時，整個社交網(wǎng)絡對于信息免疫表現(xiàn)明顯，是使用重要熟人免疫策略抑制社交網(wǎng)絡內(nèi)的信息傳播的一個重要參數(shù)值。

1改進的SIR模型

1.1傳統(tǒng)的SIR模型

在社交網(wǎng)絡中，信息傳播的主體是人，人們根據(jù)自己的喜好來對自己接收到的信息選擇接受再傳播或者不接受，另外一類人可能沒有接觸過此類信息。在社交網(wǎng)絡中，對于這三種人可以使用經(jīng)典的傳染病模型的三種類型的節(jié)點來描述：傳播節(jié)點、免疫節(jié)點、未感染節(jié)點。對于信息A，傳播節(jié)點已經(jīng)接受了此類信息，并且有一定幾率傳播該信息；免疫節(jié)點雖然接受了此類信息，但是因為與自己觀點相?；蛘呤钦J為對自己或者好友幫助不大，而不對信息進行傳播；未感染節(jié)點指的是在一個社交網(wǎng)絡中還沒有接觸過該類信息的節(jié)點。不管是哪類節(jié)點，都會隨著時間增長對信息免疫面為免疫節(jié)點。

圖1　SIR模型

如圖1所示，使用SIR模型來描述信息的傳播，把社交網(wǎng)絡中的節(jié)點分為三類：傳染節(jié)點(I)、未感染節(jié)點(S)、免疫節(jié)點(R)。未接觸節(jié)點S不會感染別人，但是有可能被接觸到的信息所感染，變?yōu)閭鞑ス?jié)點；傳播節(jié)點已經(jīng)接受了該信息并具有感染別人的能力；免疫節(jié)點可能沒有接觸信息也可能接受了信息但是對信息并不感興趣，免疫節(jié)點缺乏信息的傳播能力。

從圖1可以看出，未接觸信息的節(jié)點在接觸信息后可以變?yōu)閭鞑ス?jié)點，而不管是未感染節(jié)點還是傳播節(jié)點最后都會變?yōu)槊庖吖?jié)點。

把節(jié)點分為傳播節(jié)點(I)、未感染節(jié)點(S)、免疫節(jié)點(R)，在t時刻這三類人在人群中所占據(jù)的比例分別為I(t)、S(t)和R(t)。當t=0時，傳播節(jié)點和免疫節(jié)點的比例為I0和S0，每天每個傳播節(jié)點有效接觸的人數(shù)為α，即有α個人變?yōu)閭鞑ス?jié)點，β是每天傳播節(jié)點變?yōu)槊庖吖?jié)點的數(shù)目，γ是未感染節(jié)點變?yōu)槊庖吖?jié)點的數(shù)目。傳播動力學方程表達式如下：

(1)

1.2對SIR模型的改進

新形勢下的社交網(wǎng)絡保持著傳統(tǒng)社交網(wǎng)絡的模式下，也慢慢地開始向不同方面進行巨大的變化。電子商務策劃商開始考慮如何使用社交網(wǎng)絡為商品服務，網(wǎng)絡推手隨之應運而生。網(wǎng)絡推手就是那些熟悉網(wǎng)絡推廣并且能夠熟練應用的人。如今網(wǎng)絡推手已經(jīng)從草根狂放的模式向?qū)I(yè)化轉(zhuǎn)變中，當然也越來越復雜，尤其是網(wǎng)絡謠言推手對于社交網(wǎng)絡影響力巨大，有些推手為了謀求利益散發(fā)一些負面信息，對受害人造成較大負面影響。

圖2　引入推手節(jié)點的SIR模型

由于社交網(wǎng)絡中傳播節(jié)點推手節(jié)點的存在，使得社交網(wǎng)絡對于不同傳播節(jié)點的信息保持不同的傳播狀態(tài)，所以將傳播節(jié)點分為兩類:一般的傳播節(jié)點和特殊的傳播節(jié)點(推手節(jié)點)，如圖2所示。由于網(wǎng)絡推手強大的傳播能力，與傳統(tǒng)節(jié)點迥異的傳播模式，本文用數(shù)據(jù)仿真的方法來研究網(wǎng)絡推手的傳播規(guī)律。

(2)

2算法與實驗分析

2.1算法

針對改進后的SIR模型，本文使用YouTube數(shù)據(jù)構建社交網(wǎng)絡，在Mac系統(tǒng)下使用Xcode程序仿真處理數(shù)據(jù)，實驗算法如下：

INPUT：

count

//信息傳播的次數(shù)

probability

//節(jié)點收到信息的概率

normalProbability

//普通節(jié)點傳播信息的概率

specialProbability

//傳播節(jié)點傳播信息的概率

OUTPUT：

time

//信息傳播次數(shù)

normal

//未收到信息節(jié)點比例

special

//傳播節(jié)點比例

immunity

//免疫節(jié)點比例

begin

for(inti=0;i

Step1 從datadic取出一組新的鍵值對key:nodeValue:arr

//datadic里邊存的是以節(jié)點為key好友節(jié)點為value的鍵值對

Step2User*user=[newUser];

//創(chuàng)建新的user對像

user.probability=probability;

//給user對象的收到信息的屬性probability賦值

user.spreadProbability=normalProbability;

//給user對象的傳播信息的屬性spreadProbability賦值

user.num=node;

//給user編號

user.linker=arr;

//給user的好友節(jié)點數(shù)組賦值arr

}

for(inti=0;i

for(intj=0；j

//當前所有的傳播節(jié)點給自己的所有好友發(fā)送消息

for(intk=0;k

//user給自己所有的好友發(fā)送消息

Step3 從spdic中取出一個新的傳播節(jié)點user

//spdic儲存當前傳播狀態(tài)為傳播的節(jié)點

Step4 從user.linker中取出一個好友節(jié)點link

Step5userpostlink

//user給自己的好友節(jié)點link發(fā)信息

}

}

}

Step9for(User*nodeinallnodedic){

//循環(huán)遍歷所有節(jié)點

swith(node.spe){

//判斷當前節(jié)點對信息的態(tài)度(是否收到或免疫)

case-1:spdicremovenode;

//若果免疫，則把該節(jié)點從傳播字典中移除并加入免疫字典

imdicaddnode;

break;

case0:break;

//如果未收到信息，不執(zhí)行任何操作

case1:user.spreadProbability=specialProbability

//如果傳播則改變該節(jié)點傳播信息的概率并加入傳播字典

spdicaddnode;

break;

}

}

Step10return[spdic.count,odic.count,imdic.count];

//返回當前傳播、免疫、未收到信息三種節(jié)點的比例

}

2.2實驗結(jié)果分析

對構建的社交網(wǎng)絡定義如下的傳播規(guī)則：

1) 如果一個傳播節(jié)點以P1概率接觸未感染節(jié)點，則未感染節(jié)點會以概率P2成為傳播節(jié)點，(1-P2)變?yōu)槊庖吖?jié)點；

2) 如果一個傳播節(jié)點與一個免疫節(jié)點接觸，則傳播節(jié)點會以概率P3成為免疫節(jié)點；

3) 假設當節(jié)點沒有接觸信息的時候，是不存在免疫節(jié)點的，即R(0)=0。

實驗一對于傳播節(jié)點進行了分類，一類是正常的傳播節(jié)點，一類是推手節(jié)點，即網(wǎng)絡中設置了四種節(jié)點：推手節(jié)點、正常傳播節(jié)點、未接觸信息節(jié)點和免疫節(jié)點。對于推手節(jié)點，設置為在1 000個節(jié)點中可能會出現(xiàn)1個推手節(jié)點，可能因為數(shù)據(jù)量并不充分，最后結(jié)果表明，即便是傳播30次以上，推手節(jié)點對于整個社交網(wǎng)絡的影響也并不是很大。

根據(jù)這個結(jié)論發(fā)現(xiàn)這種對于推手節(jié)點的概率設置并不能有效地描述信息的傳播。所以嘗試對傳播節(jié)點的概率從0～1進行研究，那么能夠使得網(wǎng)絡表現(xiàn)良好性能的傳播節(jié)點概率可以認為是推手節(jié)點表現(xiàn)的性能。

實驗二取消了社交網(wǎng)絡中的推手節(jié)點設置，網(wǎng)絡中僅僅設置了三種節(jié)點：傳播節(jié)點、未接觸信息節(jié)點和免疫節(jié)點。設置傳播節(jié)點以P1的概率向外傳播信息，而未接觸節(jié)點接觸信息后分別以P2變?yōu)閭鞑ス?jié)點，(1-P2)變?yōu)槊庖吖?jié)點，依次迭代數(shù)次，來找出社交網(wǎng)絡中信息傳播多少次可以達到覆蓋最大值。試驗對P1數(shù)據(jù)采取從0.1～0.9，P2數(shù)據(jù)依次從0.1～0.9得到共81組數(shù)據(jù)，對81組數(shù)據(jù)記性了分析，得到81個數(shù)據(jù)組下信息傳播多少次才能夠在社交網(wǎng)絡中達到最大的傳播覆蓋面的數(shù)據(jù)，如表1所示。表中第1行第1列表示當P1=0.2,P2=0.1時數(shù)據(jù)指數(shù)太小，沒有表現(xiàn)良好的性能，沒有得到有效數(shù)據(jù)記為X，表中的X均為此意。其中第4行第1列的數(shù)據(jù)表明當P1為0.4時，P2為0.1時，在第12次時候信息在整個社交網(wǎng)絡內(nèi)的傳播達到了最大值。從P1概率為0.2可以看出，這個概率過低，不管是P2處于任何數(shù)值，對于信息在網(wǎng)絡中的傳播與現(xiàn)實情況誤差太大。同樣對于P1=0.1的模擬測試數(shù)據(jù)數(shù)據(jù)也不具有可進行研究的價值，沒有進行總結(jié)分析。從圖表可以發(fā)現(xiàn)當P1=0.7開始，數(shù)據(jù)已經(jīng)比較符合實際社交網(wǎng)絡中數(shù)據(jù)的六度傳播理論。

表1　社交網(wǎng)絡傳播最大化次數(shù)表

實驗三分析圖2，當傳播節(jié)點以P1概率向外傳播信息，α=P2,γ=1-P2,而傳播節(jié)點是以P1為概率向外傳播節(jié)點的。也就是說當傳播節(jié)點向外傳播信息時，未接觸信息的節(jié)點有P1概率接收到信息，而接收到信息后，未接觸節(jié)點以P2概率變?yōu)閭鞑ス?jié)點，(1-P2)概率變?yōu)槊庖吖?jié)點。

圖3　實驗2和實驗3的對比圖

如圖3所示，實驗二只考慮了信息的傳播，沒有考慮當傳播節(jié)點變?yōu)槊庖吖?jié)點的概率。因為實驗二是為了研究信息如何能在網(wǎng)絡中達到最大化傳播的，所以對于傳播節(jié)點變?yōu)槊庖吖?jié)點即使沒有進行設置，只能更好地描述信息的傳播，尤其是潛在存在的推手節(jié)點的信息的傳播，所以并不影響實驗結(jié)果的正確性。

考慮免疫對于整個網(wǎng)絡的影響，可以從實驗二選出能在社交網(wǎng)絡中能夠最優(yōu)達到最大化的數(shù)據(jù)來研究免疫對于網(wǎng)絡中信息傳播的影響。從表1可以看出，當P1=0.7時，整個社交網(wǎng)絡已經(jīng)處于相對完美的傳播，P1概率越大，更傾向于推手節(jié)點，那么可以認為P1=0.7是一個閾值。同樣地，發(fā)現(xiàn)當P1固定時候，其實P2的概率對于整個網(wǎng)絡的傳播都沒有特別大的影響，這一點也符合對于信息傳播的猜測，即推手節(jié)點強大的推手功能，使得網(wǎng)絡中其他節(jié)點的作用變得不那么明顯。根據(jù)表1可以發(fā)現(xiàn)，當P2=0.5～0.7時，整個網(wǎng)絡的傳播更趨于穩(wěn)定，所以進行了實驗三。當P1=0.7，P2=0.6時，傳播節(jié)點變?yōu)槊庖吖?jié)點的概率β設置為從0.1～0.9的變量，進行試驗來探索傳播節(jié)點免疫對于社交網(wǎng)絡信息傳播的影響，如表2所示。

表2　傳播最大化次數(shù)表

從表2可知，對于一個網(wǎng)絡來說，當傳播節(jié)點的免疫從0.2到0.3進行變動時，整個網(wǎng)絡內(nèi)的信息傳播要想達到最大值需要的次數(shù)就變小了很多?？梢岳斫鉃槊庖咴谶@個概率時候，整個社交網(wǎng)絡內(nèi)信息傳播時候已經(jīng)很容易接觸到免疫節(jié)點，網(wǎng)絡的信息傳播就很容易被抑制，這對于下一步進行信息在網(wǎng)絡中的傳播進行控制有一定的意義。

圖4和圖5給出了在P1=0.7,P2=0.6時候在實驗二和實驗三情況下信息在網(wǎng)絡中的傳播圖，實驗三在實驗二基礎上增加了傳播節(jié)點變?yōu)槊庖吖?jié)點的概率。對比圖4和圖5可以看出信息免疫對于社交網(wǎng)絡信息傳播的影響。

圖4　無傳播節(jié)點免疫時信息傳播圖

圖5　傳播節(jié)點免疫時的信息傳播圖

3結(jié)語

對于SIR模型來說，傳播節(jié)點的信息傳播速率對于整體社交網(wǎng)絡內(nèi)的信息傳播有很大的主導作用。當傳播節(jié)點的影響力足夠大時，信息很容易在節(jié)點的推動下在整個網(wǎng)絡中進行傳播，這也反映出了社交網(wǎng)絡中明星結(jié)點所具有的顯著作用，也是一些商家使用推手節(jié)點傳播自己的產(chǎn)品進行推廣的一個好的辦法。對于傳播節(jié)點的控制，從實驗看，傳播節(jié)點的概率大于0.7這個閾值時表現(xiàn)為推手節(jié)點的性質(zhì)，對于社交網(wǎng)絡內(nèi)信息的傳播推動明顯。在對網(wǎng)絡內(nèi)信息傳播進行抑制時，采取目標免疫算法可以對度數(shù)大的節(jié)點進行控制，該值是一個參數(shù)值。當整個社交網(wǎng)絡內(nèi)傳播節(jié)點的免疫率大于0.2時，對于整個網(wǎng)絡中信息的傳播很不利，對信息傳播的抑制可以采取重要熟人免疫策略，在網(wǎng)絡中隨機選取一個節(jié)點，對節(jié)點的節(jié)點進行免疫。而如何使傳播節(jié)點免疫，或者如何有效抑制信息的傳播，是下一步需要具體研究的方向。

參考文獻

[1]SudburyA.Theproportionofthepopulationneverhearingarumour[J].Journalofappliedprobability,1985,22(2):443-446.

[2]WattsDJ,StrogatzSH.Collectivedynamicsof‘small-world’networks[J].Nature,1998,393(6684):440-442.

[3]KupermanM,AbramsonG.Smallworldeffectinanepidemiologicalmodel[J].PhysicalReviewLetters,2001,86(13):2909.

[4] 張彥超,劉云,張海峰,等.基于在線社交網(wǎng)絡的信息傳播模型[J].物理學報,2011,60(5):66-72.

[5]EarnDJD,RohaniP,BolkerBM,etal.Asimplemodelforcomplexdynamicaltransitionsinepidemics[J].Science,2000,287(5453):667-670.

[6] 熊熙,胡勇.基于社交網(wǎng)絡的觀點傳播動力學研究[J].物理學報,2012,61(15):104-110.

[7]ChenKY,LuesukprasertL,ChouS.Hottopicextractionbasedontimelineanalysisandmultidimensionalsentencemodeling[J].KnowledgeandDataEngineering,IEEETransactionson,2007,19(8):1016-1025.

[8] 顧亦然,夏玲玲.在線社交網(wǎng)絡中謠言的傳播與抑制[J].物理學報,2012,61(23):544-550.

[9] 夏玲玲.基于在線社交網(wǎng)絡的謠言控制策略研究[D].南京郵電大學,2013.

[10]WattsDJ,DoddsPS.Influentials,networks,andpublicopinionformation[J].Journalofconsumerresearch,2007,34(4):441-458.

[11]NekoveeM,MorenoY,BianconiG,etal.Theoryofrumourspreadingincomplexsocialnetworks[J].PhysicaA:StatisticalMechanicsanditsApplications,2007,374(1):457-470.

[12] 程軍軍.社交網(wǎng)絡中信息傳播模式及話題趨勢預測研究[D].北京交通大學,2013.

[13] 李合莉.多層在線社交網(wǎng)絡信息傳播模型研究[D].山東財經(jīng)大學,2013.

[14]LeeI.Analyzingcharacteristicsofinformationpropagationonsocialnetworkgraphs[C]//Southeastcon,2013ProceedingsofIEEE.IEEE,2013:1-4.

[15]FreemanM,McVittieJ,SivakI,etal.ViralinformationpropagationintheDiggonlinesocialnetwork[J].PhysicaA:StatisticalMechanicsanditsApplications,2014,415:87-94.

DISCOVERY OF PUSHING HANDS NODE IN SOCIAL NETWORKS BASED ON SIRMODELANDINFORMATIONDISSEMINATIONRESTRAINT

Li HanmanZhang ZhiyongZhao Changwei

(School of Information Engineering,Henan University of Science and Technology,Luoyang 471023,Henan,China)

AbstractPushing hands node plays a very important role in social networks information dissemination. We introduced the “pushing hands node” concept into traditional SIR model, studied the dissemination law of the hot topics caused by such kind of nodes in networks and their influence and control on social network information dissemination. Using YouTube data to build a social network topology, we found in experiment that when the node dissemination probability was greater than 0.7, it could be set as the pushing hands node, and that the target immune algorithm could be used for restraining information dissemination. While the entire information immunisation of the dissemination node in social networks was greater than 0.2, it could effectively inhibit the information dissemination. This value is the parameter value of the important acquaintance immunisation strategy used to suppress the information dissemination.

KeywordsSocial networksInformation disseminationSIR epidemic modelPushing hands node

收稿日期：2014-11-19。國家自然科學基金項目(61370220)；河南省科技創(chuàng)新人才計劃杰出青年基金項目(134100510006)；河南省科技攻關項目(142102210425)；河南省教育廳科學技術研究重點項目基礎研究計劃(13A520240，14A520048)。李涵曼，碩士，主研領域：社交網(wǎng)絡。張志勇，教授。趙長偉，副教授。

中圖分類號TP3

文獻標識碼A

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