基于SIR模型的社交網絡推手節點發現及信息傳播抑制

李涵曼　張志勇　趙長偉

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

?

基于SIR模型的社交網絡推手節點發現及信息傳播抑制

李涵曼張志勇趙長偉

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

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

關鍵詞社交網絡信息傳播SIR傳染病模型推手節點

0引言

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

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

本文在SIR模型的基礎上引入了推手節點。研究節點的傳播規律，發現當傳播節點向外傳播信息的概率大于0.7時，整個社交網絡表現良好的傳播性能，可以把0.7設置為推手節點的閾值，對于信息傳播的抑制可采用目標免疫算法；當整個社交網絡內傳播節點變為免疫節點的概率大于0.2時，整個社交網絡對于信息免疫表現明顯，是使用重要熟人免疫策略抑制社交網絡內的信息傳播的一個重要參數值。

1改進的SIR模型

1.1傳統的SIR模型

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

圖1　SIR模型

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

從圖1可以看出，未接觸信息的節點在接觸信息后可以變為傳播節點，而不管是未感染節點還是傳播節點最后都會變為免疫節點。

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

(1)

1.2對SIR模型的改進

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

圖2　引入推手節點的SIR模型

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

(2)

2算法與實驗分析

2.1算法

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

INPUT：

count

//信息傳播的次數

probability

//節點收到信息的概率

normalProbability

//普通節點傳播信息的概率

specialProbability

//傳播節點傳播信息的概率

OUTPUT：

time

//信息傳播次數

normal

//未收到信息節點比例

special

//傳播節點比例

immunity

//免疫節點比例

begin

for(inti=0;i

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

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

Step2User*user=[newUser];

//創建新的user對像

user.probability=probability;

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

user.spreadProbability=normalProbability;

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

user.num=node;

//給user編號

user.linker=arr;

//給user的好友節點數組賦值arr

}

for(inti=0;i

for(intj=0；j

//當前所有的傳播節點給自己的所有好友發送消息

for(intk=0;k

//user給自己所有的好友發送消息

Step3 從spdic中取出一個新的傳播節點user

//spdic儲存當前傳播狀態為傳播的節點

Step4 從user.linker中取出一個好友節點link

Step5userpostlink

//user給自己的好友節點link發信息

}

}

}

Step9for(User*nodeinallnodedic){

//循環遍歷所有節點

swith(node.spe){

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

case-1:spdicremovenode;

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

imdicaddnode;

break;

case0:break;

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

case1:user.spreadProbability=specialProbability

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

spdicaddnode;

break;

}

}

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

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

}

2.2實驗結果分析

對構建的社交網絡定義如下的傳播規則：

1) 如果一個傳播節點以P1概率接觸未感染節點，則未感染節點會以概率P2成為傳播節點，(1-P2)變為免疫節點；

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

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

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

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

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

表1　社交網絡傳播最大化次數表

實驗三分析圖2，當傳播節點以P1概率向外傳播信息，α=P2,γ=1-P2,而傳播節點是以P1為概率向外傳播節點的。也就是說當傳播節點向外傳播信息時，未接觸信息的節點有P1概率接收到信息，而接收到信息后，未接觸節點以P2概率變為傳播節點，(1-P2)概率變為免疫節點。

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

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

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

表2　傳播最大化次數表

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

圖4和圖5給出了在P1=0.7,P2=0.6時候在實驗二和實驗三情況下信息在網絡中的傳播圖，實驗三在實驗二基礎上增加了傳播節點變為免疫節點的概率。對比圖4和圖5可以看出信息免疫對于社交網絡信息傳播的影響。

圖4　無傳播節點免疫時信息傳播圖

圖5　傳播節點免疫時的信息傳播圖

3結語

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

參考文獻

[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] 張彥超,劉云,張海峰,等.基于在線社交網絡的信息傳播模型[J].物理學報,2011,60(5):66-72.

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

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

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

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

[9] 夏玲玲.基于在線社交網絡的謠言控制策略研究[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] 程軍軍.社交網絡中信息傳播模式及話題趨勢預測研究[D].北京交通大學,2013.

[13] 李合莉.多層在線社交網絡信息傳播模型研究[D].山東財經大學,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)；河南省科技創新人才計劃杰出青年基金項目(134100510006)；河南省科技攻關項目(142102210425)；河南省教育廳科學技術研究重點項目基礎研究計劃(13A520240，14A520048)。李涵曼，碩士，主研領域：社交網絡。張志勇，教授。趙長偉，副教授。

中圖分類號TP3

文獻標識碼A

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