基于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