传播源估计中有效观察点部署策略研究

刘 栋，赵 婧，聂 豪

(1. 河南师范大学 计算机与信息工程学院，河南 新乡 453007; 2. 教学资源与教育质量评估大数据河南省工程实验室，河南 新乡 453007)

0 引言

伴随着Facebook、微信等在线社交网络服务的出现，社交网络已经成为当今社会人们信息交流的重要渠道和载体，且这些社交网络允许用户建立自己的“媒体”，对外发布、传播信息。可靠的信息能够给人们的生活带来便捷，但谣言在互联网上的传播所带来的负面影响也不可估量。传染病的传播也可看作网络上的传播现象，如2009年由流感病毒新型变体甲型H1N1流感所引发的全球性流行病疫情[1]，在很短时间内便蔓延全球。

谣言或疾病的传播都是依赖于具体网络而存在的。例如，谣言传播依赖于社交网络，疾病传播则依赖于人际交互网络。这些网络一般具有规模大，节点之间的联系复杂等特征。在此类网络上，如何快速准确地确定疾病的传染源、谣言的源头就显得十分重要。如果在短时间内确定出疾病的传染源，就能够更好地控制整个疾病的传播，缩小其传播范围，减少传染病对人们生命安全的威胁。如果能在散布谣言后的关键时期迅速定位谣言来源，就能减少谣言对政治、人类切身利益和社会稳定的负面影响。因此，在这个背景下，如何在一个网络上定位一个传染源或者谣言的源头就成为一件非常有意义且十分具有挑战性的事情。

对于网络上的源点定位问题，一种较为朴素的方法是通过获取网络中每个节点在网络传播中的状态，根据其相关记录，确定信息传播的源点。虽然这种方法能够准确定位信息源，但成本极高，可行性差，对于大规模网络来说几乎无法实施。因此，需要一种有效可行的方法来估计和预测信息源的准确位置。最新的研究趋势是通过在网络中部署少量观察点，根据其接收的节点信息，推断出信息源点在网络中的位置。在该任务下，如何有效地部署观察点，从而提高传播源定位精度，成为了亟待解决的关键问题。本工作针对上述问题展开研究，力图揭示网络中观察点部署策略与源点估算精度的关系。

本工作提出了几种观察点部署策略，包括随机、度、聚类系数、特征向量、紧密度和介数。并且采用SI传播模型和反向贪心溯源算法在合成网络和真实网络中进行模拟仿真。通过分析不同观察点部署策略对于传播源定位精度的影响，期望寻找到有效的观察点部署策略。

1 相关研究

目前，估计传播源在传染病控制、舆情控制等方面的应用越来越广泛，国内外研究人员对于估计传播源相关问题的研究也越来越深入。根据快照信息范围可以分为完整节点信息定位和部分节点信息定位。其中有的是关于定位传染病的源头、有的是关于定位谣言的源头等等，但根据快照信息范围大致可以归为以上两类。

Shah等人[2]针对正则树上的SI模型提出一个基于传播中心性的极大似然估计算法来确定传播源。Fioriti等人[3]提出了计算感染图中每个节点的动态年龄的溯源算法DA。Comin等人[4]在雪崩传播模型下提出了无偏中介算法。Prakash等人[5]提出了基于最小描述长度的NetSleuth算法解决溯源问题。还有Nino Antulov-Fantulin 等人[6]提出了基于蒙特卡洛模拟的定位算法。

以上工作都需要明确所有节点的传播状态，在大型网络中这将要消耗很大的成本。为了克服这些困难，Pinto[7]设计了一个基于少量观察点的精细极大似然估计算法来定位传播源。Shen等人[8]开发了基于压缩感知的构建方法并提出了一种基于观察点反向传播的一种定位条件[9]。Luo等人[10]提出了一种适用于一般网络的反向贪心算法。这些方法的基本思想都是基于选择的部分节点进行传播源的估计。定位传播源的精度在很大程度上取决于观察点的选择。

近几年来国内外研究人员在观察点部署策略上也取得了一定的进展。Brunella Spinelli等人[11]提出了一种在线迭代的部署最佳观察点的方法来定位传播源。Brunella Spinelli等人[12]还提出了基于传播延迟方差的最大值和最小值来部署观察点的方法。Celis等人[13]提出基于双重解决集的部署观察点策略。张锡哲等人[14-17]基于Pinto的极大似然估计溯源算法提出的一系列观察点部署策略。上述研究均未基于反向贪心溯源算法提出观察点部署策略。

其中，张锡哲等人[17]分析了基于节点中心性的观察点部署策略对定位传播源的精度的影响，他们的研究结果表明基于节点中心性的观察点部署策略对于估计传播源的精度并无显著影响。与他们的研究结果不同的是，本工作同样采用基于节点中心性的观察点部署策略，但仿真结果表明采用特征向量的观察点部署策略更有利于提高传播源估计的精度。

分析与张锡哲等人研究的不同之处，主要在于他们的工作采用了基于少量观测节点的极大似然估计算法定位传播源，而本工作采用了基于传播路径的反向贪心算法。因此，估计传播源的溯源算法也是关系到基于节点中心性观察点部署策略适用性的重要因素。

本工作中，首先利用SI传播模型模拟传播。然后，根据传播信息利用反向贪心算法定位传播源，本文将在第二节中介绍所采用的传播模型和定位方法。我们的主要工作是在模拟传播完成后，提出了基于节点中心性的观察点部署策略，根据各种策略选择的部分观察点进行传播源定位，本文将在第三节介绍基于节点中心性的观察点部署策略。第四节介绍实验部分，最后在第五节做出结论。

2 所采用的传播模型与定位方法

2.1 SI传播模型

网络可建模为一个无向图G=(V,E)。其中V是顶点或节点的集合，E是边的集合，代表两节点之间有联系。在本工作中，假设在图G中最开始只有一个节点被“感染”，这个节点开始向它的邻居节点传播。本工作就是利用网络中部分感染节点信息来确定这个传播源。

在人群中的疾病传播模型已经在文献[18-20]中得到广泛的研究，这些模型也被用来模拟在线社交网络中信息的传播[21-24]。SI模型是作为模拟疾病传播的一种自然现象出现的。在SI模型中，节点有三种状态： 已感染状态、易感染状态和不易感染状态。已感染节点将会感染其他节点并且一直保持被感染的状态；易感染节点表示目前未被感染，但至少有一个邻居节点被感染；不易感染的节点也是未被感染的节点但是它的邻居都未被感染。类似于传染性疾病的传播，该模型也能描述谣言的传播，在模型中的单个人可分为两种类型： 第一类人是不知情者，他们对谣言是浑然不知的；第二类人是传播者，他们是谣言的知情者，并且喜欢对谣言进行传播。

本工作中,采用的SI模型的时间是被划分了的离散时间段，在时间段t内节点u的状态用随机变量X(u,t)表示。在时间t=0时，假设只有一个节点v*∈V被感染，称这个节点为传播源。假设感染过程是一个在离散时间内概率测度为P的马尔可夫过程，且假设在下一个时间段开始。一个易感染节点被感染的概率为p,其中p∈(0,1)。 假设每个易感染节点是否会被感染都是相互独立的，且不易感染节点始终都不会被感染。

在这个SI模型中，任何与被感染节点相邻的健康节点被感染的概率都相同，与被感染的邻居数量无关。传播一段时间后，在所有节点的状态信息中，健康节点的状态都能正确地显示出来，但是被感染节点的状态只有一部分能正确显示，称为显式状态，另一部分将与健康状态混淆，称为隐式状态。当易感染节点u被感染并且为显式状态时用X(u,t)=e表示，并且被感染后为显示状态的节点集用Ve表示；当易感染节点u被感染并且为隐式状态时用X(u,t)=i表示。

用qu表示节点u被感染后为显式状态的概率，假设节点被感染后是否为显式状态与其他节点是相互独立的。对于所有节点u∈V,如果qu=1，那么该模型本质上会和文献[25-26]中的一致；然而对于所有节点u∈V如果qu趋近于0，则大多数节点将会表现为未感染状态。在这种情况下，估计传播源将会变的十分困难，并且在实际中估计传播源的精度将很低。直观地说，对于所有节点u如果qu≥p，则将会在这个SI模型中观察到更多的被感染后为显式状态的节点，有利于提高估计传播源的精度。在本工作中提出一个较弱的假设，对于所有节点u∈V，假设qu满足

当p>1/2时，对于任意节点u，假设中的qu需要满足足够大。这是因为在足够长的一段时间内，大部分节点将会被感染，若被感染的节点大都为隐式状态，那么将很难估计传播源；另一方面，如果p≤1/2，那么假设将微不足道。此时，对于任意节点u，该模型允许qu=0或者1，当qu=1时，意味着将要观察所有被感染的节点，这种情况类似于文献[27]中的情况。故总结一个易感染节点的概率转换图如图1 所示。

图1 易感染节点的概率转换图

2.2 反向贪心溯源算法

本工作采用Luo等人[10]提出的方法估计传播源。首先寻找与被感染节点集合一致的感染树，然后计算可生成该感染树的最可能传播路径，最后估计该树的Jordan感染中心[28]作为网络的传播源。

在网络G中，假设一个易感染节点只能随机地被已感染邻居节点中的一个节点感染，则在传播源传播结束后，被感染的节点组成的所有路径将会是一个树。经过传播t时间后，任意一条感染路径用Xt=X(u,τ):u∈V,1≤τ≤t表示，则由Xt形成的T(Xt)为G的一棵子树。Tv表示以节点v为根节点的树，则在G的所有子树中肯定存在一个与被感染节点集合组成的感染树一致的树。Tv表示由已感染且为显式状态的节点Ve组成的感染树的集合。假设节点v为源点，该传播源的最可能感染路径，如式(2)所示。

假设G为一般网络，且v∈V是传播源。那么，对于任意一个以v为根节点且由节点集合Ve组成的感染树T有：

其中pa(u)表示节点u的父母节点，令

3 基于节点中心性的观察点部署策略

在网络G中，当传播源利用SI传播模型感染结束后，将得到为显式状态的节点集合Ve。在文献[17]中，Luo等人是在随机选择部分节点上部署观察点来收集信息。而本工作中，提出了基于节点中心性的观察点部署策略，含节点的度、聚类系数、特征向量、紧密度、介数。下面介绍这五种指标信息。

(1) 度

用于描述在静态网络中节点产生的直接影响力，其值为与该节点直接相连的节点数。则度定义为式(7)。

其中，d(i)表示与节点i直接相连的节点数。

(2) 紧密度

用于描述网络中的节点通过网络到达其他节点的难易度，其值为该节点到其他所有节点的距离之 和的倒数。则紧密度定义为式(8)。

其中，dij表示节点i到节点j的最短距离。

(3) 介数

节点的介数反映了其在整个网络中的作用和影响力，具有比较强的实际意义。则介数定义为式(9)。

其中，ljk表示节点j到节点k的最短路径条数，ljk(i) 表示节点j与节点k之间经过点i的最短路径条数。

(4) 聚类系数

在复杂网络中，假设网络中的一个节点i有ki条边将它和其他节点相连，这ki个节点就称为节点i的邻居。由于在这ki个节点之间最多可能有ki(ki-1)/2条边，而这ki个节点之间实际存在的边数Ei和总的可能的边数ki(ki-1)/2之比就定义为节点i的聚类系数Ccl(i)，Ei为这ki个节点之间实际存在的边数总和即

聚类系数用于描述节点邻居之间连接的紧密程度。整个网络的聚类系数Ccl就是所有节点i的聚类系数Ccl(i)的平均值。显然0≤Ccl≤1，当且仅当所有节点都为孤立节点，即没有任何连接边的情况下Ccl=0；当网络是全局耦合时，即网络中任意两个节点都直接相连此时Ccl=1。

(5) 特征向量

用于描述节点周围邻居节点的重要性对该节点产生的影响。若λ为网络邻接矩阵A的主特征值，e=(e1,e2,...,en)为矩阵A对应于主特征值λ的特征向量，则特征向量定义，如式(11)所示。

从上面可以看出度、聚类系数、特征向量、紧密度以及介数这些指标信息，在网络结构中的意义差别还是很大的。有的指标信息反映节点在整个网络中的地位，有的指标信息揭示周围邻居对中心节点的影响等。这些差别在信息扩散的过程中都有所体现，在传播过程都发挥了各自不同的作用，这也使得这几类节点成为网络中的重点研究对象。同时，正是这种在传播时所表现出来的差异，显得有必要按照这几种指标信息选择观察点。因它们能从各自不同的方面揭示网络中的信息传播过程，能够更全面地感知信息在网中的扩散，而这些对于准确定位网络中的信息源来说是十分必要的。所以可利用以上指标信息作为选择观察点的标准。下面的工作通过实验来分析这些部署策略对合成网络和实际网络的定位传播源精度的影响。

4 实验

4.1 实验设置

本工作选取两类网络进行实验。第一类是合成网络，分别为从BA模型构造的无标度网络、从WS模型构造的小世界网络和从ER模型构造的随机网络；第二类为真实网络，分别为属于社会网络的仓鼠网络[29]，即在仓鼠网站中用户的友谊与家庭之间的联系网络；属于技术网络的美国电力网络[30]；属于信息网络的合著关系网络[31]，选择了其中最大连通子图379个作者的关系网络；属于生物网络的线虫代谢网络[32]。表1列出了这些网络的规模。

本工作根据度、介数、紧密度、聚类系数以及特征向量五种网络节点指标信息就可以产生五种观察点部署策略。即在选择观察点之前，根据网络节点指标信息的定义，计算网络中每个节点的指标信息。之后将该指标进行从大到小排序，最后根据所需要的观察点数量按照指标从大到小选择节点作为观察点。除此五种观察点部署策略之外，还有一种就是随机选择节点作为观察点，将此种部署策略作为与其他部署策略的对比。之后提到的观察点部署策略也就是指的以上六种。

本工作中，设置选择节点集Ve中50%的节点作为观察点。如根据节点度大小来选择50%的节点作为观察点，则对网络中所有节点按照度的大小排序，最后选择排在前50%的节点作为观察点。如果是在随机选择观察点的情况下，就不需要排序，直接根据观察点的数量在网络中随机选择即可。

表1 实验网络的规模

在每种网络上，仿真模拟运行1 000次。在每次模拟运行中，先随机选择一个节点作为传播源，再使用SI模型模拟传播。对于任意节点v，p和qv分别是在(0,1)和[max(0,2-1/p),1]中均匀选择的。

4.2 实验结果和分析

通过研究在合成网络和真实网络上估计传播源精度的结果，探索了观察点部署策略与估计传播源精度的关系。从而发现观察点部署策略对于估计传播源精度产生的具体影响。

图2是小世界网络在各种观察点部署策略下溯源算法的错误距离分布图，错误距离是估计的传播源与真实的传播源之间的跳数。在观察点部署策略随机、度、聚类系数、介数、紧密度以及特征向量下估计传播源的精度分别为0.23、0.12、0.24、0.21、0.25以及0.27。实验结果表明采用特征向量观察点部署策略估计传播源的精度高于其他策略。

图2 小世界网络在各种观察点部署策略下溯源算法的错误距离分布

图3是随机网络在各种观察点部署策略下溯源算法的错误距离分布图。在观察点部署策略随机、度、聚类系数、介数、紧密度以及特征向量下估计传播源的精度分别为0.03、0.01、0.02、0.01、0.02以及0.08。实验结果表明采用特征向量观察点部署策略估计传播源的精度高于其他策略；另外，相比随机选择策略，采用特征向量观察点部署策略，准确定位传播源的精度可以提高到两倍多。

图3 随机网络在各种观察点部署策略下溯源算法的错误距离分布

图4是无标度网络在各种观察点部署策略下溯源算法的错误距离分布图。在观察点部署策略随机、度、聚类系数、介数、紧密度以及特征向量下估计传播源的精度分别为0.10、0.21、0.05、0.15、0.21以及0.27。实验结果表明，采用特征向量观察点部署策略估计传播源的精度高于其他策略；另外，相比随机选择策略，采用特征向量观察点部署策略，准确定位传播源的精度可以提高到两倍多。

图4 无标度网络在各种观察点部署策略下溯源算法的错误距离分布

图5是仓鼠网络在各种观察点部署策略下溯源算法的错误距离分布图。在观察点部署策略随机、度、聚类系数、介数、紧密度以及特征向量下估计传播源的精度分别为0.06、0.00、0.11、0.00、0.14以及0.16。实验结果表明，采用特征向量观察点部署策略估计传播源的精度高于其他策略；另外，相比随机选择策略，采用特征向量观察点部署策略，准确定位传播源的精度可以提高到两倍多。

图5 仓鼠网络在各种观察点部署策略下溯源算法的错误距离分布

图6是美国电力网络在各种观察点部署策略下溯源算法的错误距离分布图。需要说明的是，在文献[10] 中指出在真实美国电力网络上采用基于传播中心性溯源算法的精度只有3%，在实验中利用这六种观察点部署策略估计真实传播源的精度最高的也只有1%。因为精度极低再加上错误距离最大的已经达到20跳，而美国电力网络的精度用的是错误距离在3跳以内的比例。在观察点部署策略随机、度、聚类系数、介数、紧密度以及特征向量下估计传播源的精度分别为0.23、0.12、0.24、0.21、0.25以及0.27。实验结果表明，采用特征向量观察点部署策略估计传播源的精度高于其他策略；另外，相比随机选择策略，采用特征向量观察点部署策略，准确定位传播源的精度可以提高到两倍多。

图6 美国电力网络在各种观察点部署策略下溯源算法的错误距离分布

图7是合著关系网络在各种观察点部署策略下溯源算法的错误距离分布图。在观察点部署策略随机、度、聚类系数、介数、紧密度以及特征向量下估计传播源的精度分别为0.02、0.02、0.01、0.00、0.02以及0.05。实验结果表明，采用特征向量观察点部署策略估计传播源的精度高于其他策略；另外，相比随机选择策略，采用特征向量观察点部署策略，准确定位传播源的精度可以提高到两倍多。

图7 合著关系网络在各种观察点部署策略下溯源算法的错误距离分布

图8是线虫代谢网络在各种观察点部署策略下溯源算法的错误距离分布图。在观察点部署策略随机、度、聚类系数、介数、紧密度以及特征向量下估计传播源的精度分别为0.06、0.01、0.05、0.00、0.00以及0.08。实验结果表明，采用特征向量观察点部署策略估计传播源的精度高于其他策略。

图8 线虫代谢网络在各种观察点部署策略下溯源算法的错误距离分布

本实验在上述七种网络拓扑结构上测试了这六种观察点部署策略对采用反向贪心溯源算法定位传播源精度的影响，将测试结果整理在表2中，并在表中将最优的性能值加粗表示。从表2可看出，采用特征向量观察点部署策略更有利于提高估计传播源的精度。另外，在无标度网络、随机网络、美国电力网络、仓鼠网络以及合著关系网络这些网络上。相比随机选择策略，采用特征向量部署策略，准确定位传播源的精度可以提高到两倍多。从这些错误距离分布图中可以看出每个网络都随着观察点部署策略的改变而改变，但是在各个网络中错误距离分布的趋势很相似。

表2 各种网络在六种观察点部署策略下定位传播源的精度

5 总结

在网络中估计传播源是一项重要的研究课题。估计传播源的一种可行的方法，即是利用观察点收集的部分节点信息来定位传播源。故而，估计传播源与观察点的部署策略紧密相关。本研究评估了几种观察点部署策略，含度数、介数、紧密度、聚类系数、特征向量和随机。利用SI传播模型和反贪心溯源算法，在合成网络和真实网络上仿真模拟。实验结果表明，采用特征向量观察点部署策略更有利于提高估计传播源的精度，且与随机选择观察点部署策略相比，在某些网络上估计的传播源精度可以提高到两倍多。

基于节点中心性的观察点部署策略与采用的估计传播源的算法相关，而这些观察点部署策略对于其他溯源算法精度的影响需要进一步研究。是否能找到一种策略可以适用各种溯源算法，这些问题将会在以后的工作中做进一步的讨论。