网络中信息的传播

网络中信息的传播主要内容第一部分传染病模型第二部分信息级联模型第三部分博弈演化第四部分网络结构与信息传播一、传染病模型

社会关系网络中，信息如何传播、用户观点如何交互演化等问题受到研究者们的关注．在社会关系网络上信息传播研究中，研究者们认为社会关系网络上的信息传播与传染病在人群的扩散类似，因此经典信息传播模型是SIR模型和SIS模型，它们都以传染性疾病传播为问题原型．SIR及其改进模型在研究信息传播方面得到广泛应用，但是在信息传播过程中依赖于网络用户的信息传播行为，网络用户不仅是信息的接受者，同时也是信息的传播者．网络用户信息需求得到满足之后，会根据其自身的经验以及与其他用户的交互所得到的信息进行判断，然后根据判断结果进行行为决策，从而使得网络信息再次传播．一、传染病模型1、SI、SIS、SIR模型1.1在SI模型中,节点有两种状态：S(Susceptible)易感态表示该节点可能被其邻居节点中处于感染态的节点感染。I(Infected)感染态表示节点被感染.节点一旦被感染,就会永远处于感染态初始时刻单个节点作为感染源（将单个节点的状态设为I态，其他节点设为S态）以p的概率去感染其节点,可以观测不同时间时网络中被感染节点的数量,从而得到该节点的传播速度.

tT=1tT=10一、传染病模型算法1.1SI模型模拟图G中的信息传播一、传染病模型Python实现，T=10，beta=0.1,以3号节点作为初始感染节点为例一、传染病模型1.1SI模型模拟图G中的信息传播一、传染病模型1.2SIS模型

在SIS模型中,节点可以被反复感染.处于I感染态的节点可能会重新变为S易感态。1.3SIR模型在SIR模型中，节点除了有上述两种状态外，还有第３种免疫R状态．免疫状态是说，节点受到感染被治愈后具有了免疫性，不再被感染，也不会感染其它节点。一、传染病模型1、SIR在传染病动力学中，主要沿用的由Kermack与McKendrick在1927年用动力学的方法建立了SIR传染病模型。直到现在SIR模型仍被广泛地使用和不断发展。易感者(susceptibles)，其数量记为S(t)，表示t时刻未染病但有可能被该类疾病传染的人数；染病者(infectives)，其数量记为I(t)，表示t时刻已被感染成为病人而且具有传染力的人数；恢复者(recovered)，其数量记为R(t)，表示t时刻已从染病者中移出的人数。设总人口为N(t)，则有N(t)=S(t)+I(t)+R(t)。一、传染病模型SIR模型的建立基于以下三个假设：⑴不考虑人口的出生、死亡、流动等种群动力因素。人口始终保持一个常数，即N(t)≡K。⑵一个病人一旦与易感者接触就必然具有一定的传染力。假设t时刻单位时间内，一个病人能传染的易感者数目与此环境内易感者总数S(t)成正比，比例系数为β，从而在t时刻单位时间内被所有病人传染的人数为βS(t)。⑶t时刻，单位时间内从染病者中移出的人数与病人数量成正比，比例系数为γ，单位时间内移出者的数量为γI(t)。一、传染病模型

SIR基础模型用微分方程组表示如下：

一、传染病模型

可通过对SIR模型的分析和解的渐近性态来初步研究传染病的流行规律。SIR模型是比较简单粗糙的模型，这个模型得到了历史上发生过的大规模的传染病，如上个世纪初在印度孟买发生的瘟疫数据的有力支持。后来很多研究人员对SIR模型做了推广。 在不考虑出生与死亡等种群动力学因素的情况下，传染病若无潜伏期，动力学模型可表示为：(1)SI模型，患病后难以治愈；(2)SIS模型，患病后可以治愈，恢复者不具有免疫力；(3)SIR模型，患病者治愈后获利终身免疫力；(4)SIRS模型，病人康复后只有暂时免疫力，单位时间内将有部分康复者丧失免疫力而可能再次被感染。 传染病动力学模型不仅可用于传染病研究，而且也可用于生物种群分布、植病、寄生虫病、新技术的传播和扩散、网络病毒的传播、谣言的传播等自然和社会科学问题的研究，反之其他学科，如流体动力学、分子化学反应扩散等的研究方法也可被借鉴来用于传染病扩散的研究。一、传染病模型SIR模型一、传染病模型算法1.2SIR模型模拟图G中的信息传播一、传染病模型SIR模型二、信息级联模型独立级联模型（ICM）在该模型中，每个初始激活节点会产生自己独立的扩散级联，级联之间是互相独立、互不干扰的.在一个有向或无向图上，任何一条边(u，v)都被分配一个属于[0,1]之间的特定值PU,V，这个值代表边(u,v)上的扩散概率.初始时，部分节点被激活，信息这些节点开始扩散.在时间t，每个当前激活的节点u都会以一定概率PU,V去激活它的每个邻居节点v．如果在时刻t，节点v的多个邻居节点要激活它，这些邻居节点会随机排列地去尝试激活，所有激活尝试都在时刻t内完成．无论邻居节点u是否成功，在随后的时刻都不能再去激活v．如果v在t时刻被激活，那么该节点会在t＋1时刻去激活它的邻居们．该进程直到不再有激活行为发生而终止.二、信息级联模型ICM与SIR的区别

没有T变量算法2.1ICM模型二、信息级联模型二、信息级联模型终止条件：所有激活态节点都完成尝试激活其邻居节点二、信息级联模型级联范围最大化（影响力最大化）背景

假设存在一个用户网络,某公司想要在此用户网络中进行产品营销。公司的预算有限，因此营销不能覆盖所有用户。然而，一旦覆盖的用户发现产品不错，他们可以向朋友（近邻）宣传此产品。他们的朋友也会将此产品宣传给自己的邻居。随着这个过程持续进行，有关此产品的消息将会在网络中大肆传播开来。该公司计划选择一批初始用户，使得最终了解这个产品的人数最大化。二、信息级联模型级联范围最大化（影响力最大化）形式化定义

二、信息级联模型级联范围最大化（影响力最大化）

[1]KempeD,KleinbergJ,TardosÉ.Maximizingthespreadofinfluencethroughasocialnetwork.[C]KDD2003.ACMPress,2003.1二、信息级联模型级联范围最大化（影响力最大化）贪心法求解

二、信息级联模型级联范围最大化（影响力最大化）算法2.2级联范围最大化-贪心法求解二、信息级联模型级联范围最大化（影响力最大化）temp=[]最终感染范围为1000次，取均值每条边的感染率都为0.05二、信息级联模型第一个种子节点第三个种子节点第二个种子节点二、信息级联模型级联范围最大化（影响力最大化）

在实际计算中贪心法使用蒙特卡洛方法求解影响力最大化问题得到近似最优解，然而当网络规模较大时，算法的运行效率特别低。研究者普遍使用启发式算法来提高贪心法的效率。近年来，主要从以下角度去做改进和变形：1、提高算法效率2、结合节点影响力度量算法3、动态网络的影响力最大化问题4、时间窗口限制条件MoroneF,MakseHA.Corrigendum:Influencemaximizationincomplexnetworksthroughoptimalpercolation.Nature,2015,527(7579):65-8.曹玖新,董丹,徐顺,郑啸,刘波,罗军舟.一种基于k-核的社会网络影响最大化算法.计算机学报,2015,02:238-248.二、信息级联模型

曹玖新。。。。.一种基于k-核的社会网络影响最大化算法.计算机学报2015一、选取K值最大的节点中度数最大的节点加入S二、将上一步选取节点的邻居节点置于覆盖范围之内二、信息级联模型

曹玖新。。。。.一种基于k-核的社会网络影响最大化算法.计算机学报2015三、在未覆盖的范围内重复步骤一第3个贪心法前三：二、信息级联模型

曹玖新。。。。.一种基于k-核的社会网络影响最大化算法.计算机学报2015四、当初始种子集合S中的数量为K结束算法结束，初始种子集合为:[34,1,26]或[34,1,25]CCA算法与贪心法结果几乎相同,nice!为什么不选择节点33?节点33的影响力同样很大。二、信息级联模型线性阀值模型线性阈值模型

(LinearThresholdModel)体现了影响力的累积过程,该模型可以描述为:在社交网络G＝(V,E)中,对任意节点v都有一个对应阀值表示只有当节点v的邻居节点对节点v的影响力之和超过阀值,节点v才能被激活.节点v对其邻居节点u的影响力都存在一个权重,且节点v对所有邻居节点的影响力权重之和不超过1。

给定初始时刻处于活跃状态的用户集合为A,传播过程和独立级联模型类似,不活跃节点v状态受其所有活跃状态节点的影响.如果t时刻节点v处于不活跃状态,且其所有处于活跃状态的邻居节点对节点v的影响力之和大于节点V的阀值,即则节点v从t+1时刻起变为活跃状态。.三、博弈演化群体行为分析三、博弈演化博弈演化对于社会关系网络中的一个节点，当它对信息进行传播时，该节点从某种意义上来说将会获得一定的收益，如受欢迎度的提高等；当其他节点对该节点传播的信息提供负反馈时，它需要付出一定的成本，如声誉的降低等．出于自私性和理性的考虑，当节点收益少于付出时，它将没有动机去参与信息的传播，但是不参与信息的传播，节点将得不到任何的收益．

这个矛盾的关系可以用博弈模型来描述和分析，社会关系网络上的节点在寻求自身利益最大化的交互过程中相互制约，此消彼长，需要寻找一个平衡点．三、博弈演化观点交互模型观点交互模型旨在描述一定的社会环境中个体通过观点交互形成和更新自身观点的规律，并在此基础上研究和解释群体观点信息的演化现象．

信息传播模型着眼于群体行为在中观层面展现的整体效果，未特别关注个体观点交互的细节问题．研究者们提出了各种模型来描述观点交互过程，通常假设参与交互的个体之间具有某种拓扑关系，观点是用户对于某条信息的态度倾向值，所以通常用连续或离散的实数来表达．从混乱的个体意见到具有明显倾向的群体态度出现，是一个从微观层面到中观层面，再到宏观层面的演化过程．这个过程与很多因素相关，比如网络的拓扑结构、用户的心理特性、观点的传播规律、个体间的交互规则等．观点交互模型着重描述了用户间交互规则在观点演化过程中带来的影响三、博弈演化博弈演化下面举出一个简单的个体说服演化博弈模型来说明建模观点交互的方法．首先，个体按照特征分为三类：意见领袖、水军和一般用户．个体的策略集为｛保持观点，同意对方｝，针对个体特征构建不同的收益矩阵．定义用于计算机仿真的演化博弈规则：（１）定义个体观点的取值区间，区间内的数值代表个体观点值；（２）初始时，随机赋予个体观点值；（３）在每一时间步长（博弈回合），个体与另一随机选择的个体进行博弈；（４）每个个体存储前几个时间步长回合的博弈结果；（５）博弈时，双方交换彼此观点数值与个体类型，并取得对方存储的博弈结果；（６）计算对手采取每种策略的概率，并根据收益矩阵计算自身采取每种策略的期望收益；（７）个体默认采取期望收益最高的策略．三、博弈演化信息传播和观点交互是在线社会关系网络中群体形成的基础，信息传播和观点交互模型要能刻画信息传播的过程，分析信息扩散随时间变化的情况，同时，信息传播的过程还包含了传播者对消息内容和观点接受的过程，信息传播和观点交互是网络群体形成的基础，信息传播和观点交互模型也是研究网络群体行为演化的重要基础模型．三、博弈演化随机演化博弈随机性的演化博弈模型将有限人口中的演化博弈动态描述成一个随机过程，再渐近寻找能够使用复制动态方程的条件．构建一个随机演化博弈通常分为以下几个步骤．步骤１．博弈的基本参数设定．博弈过程的４个元素包括：决策人、策略集、收益矩阵和次序．决策人（Player）：又称局中人，指博弈中能独立决策、独立行动并承担决策结果的个人或组织．决策人的数量必须大于等于两个．策略集（Strategy）：又称策略空间，指的是供决策人选择的策略集合．决策人在博弈的过程中可以根据实际情况不断调整策略以达到最优收益．收益矩阵（Payoff）：又称效用（Utility），也就是决策人之间争夺的利益．在策略有限的情况下，所有可能的策略组合都将导致一种收益结果，所有的结果可以用矩阵表示，也可以用函数形式表示．三、博弈演化随机演化博弈步骤２．决策人策略更新过程．在演化博弈的过程中，决策人通过试错的过程达到博弈均衡．在实际情况中，不同的策略更新规则必将导致不同的博弈均衡结果．步骤３．参数求解．随机演化博弈的求解参数主要是固定概率和固定时间步骤４．纳什均衡策略求解．确定性演化博弈的均衡策略求解工具为复制动态方程，在随机性演化博弈中，不能直接采用复制动态方程的解ＥＳＳ作为稳定策略．随机性稳定策略的计算过程比较复杂.参考：[王元卓。。.网络群体行为的演化博弈模型与分析方法.计算机学报，2015]

社会因素是指与用户有社会关系的邻居，邻居们的策略选择会影响到用户的行为，而用户可能某时刻单独考虑每个邻居的选择，也有可能同时考虑多个邻居的选择；

信息因素是指信息本身所包含的内容及其扩散性（例如信息流行度）对用户的影响。几种模型在信息扩散模型中的对比在独立级联模型中，节点３、７、９在时刻t分别以一定概率去激活节点１，如果其中一个成功，那么节点１在t＋１时刻将变成激活状态，如果不成功，节点３、７、９在以后的时刻也不能再去激活节点１．几种模型在信息扩散模型中的对比在传染病模型中，当节点１周围有节点是激活状态时，该节点就会以一定概率被激活，在时刻t＋１成为激活态，而且在一段时间之后，节点１可以重新回归未激活态，而前模型中激活态节点是不能回归未激活态的.几种模型在信息扩散模型中的对比博弈论模型中，节点１被视为一个智能个体，它会同时考虑它周围激活态节点（３、７和９）和未激活态节点（２和４），计算选择哪种状态自己可以获取更大利益，此外还会考虑信息内容对自身带来的利益，最终做出让自身利益最大的选选择。几种模型在信息扩散模型中的对比四、网络结构与信息传播无标度网络

平局度=2平局度=4四、网络结构与信息传播聚类系数P=0.02ICM模型

初始节点数量聚类系数感染数量初始节点数量聚类系数感染数量初始节点数量聚类系数感染数量10.171.9420.1812.0550.1975.2410.221.8920.2110.3350.2386.9210.28220.2919.550.2687.8310.281.7120.2715.4350.3390.0210.321.7320.3417.4850.3586.9810.382.1920.3518.1550.3587.4910.391.6720.4215.1450.3694.4710.472.4220.428.3850.4287.8210.51.820.4911.250.4591.6610.532.4920.5410.17