现有的工作从传播模型^[3]、特征分析^[4]、数据挖掘^[5]等方面对社交网络中的信息传播过程进行了研究，目的是找到可以使信息传播影响力最大化^[6]的方法.另一个重要问题是，如何根据现有的传播数据找到信息源，这对网络谣言和病毒控制等问题具有重要研究价值^[7，8].

现有的定位方法^{[7, 8, 9]}大多需要获取信息传播各个阶段的网络快照(该时刻网络中各节点所处的状态).这样虽然可以定位信息源，但由于社会网络的规模过于庞大，在实际应用中很难实现.

一种可行做法是由Pinto等^[10]提出的基于部署观察点的信息源定位方法.通过在网络中部署少量观察点，记录其传播过程数据，并以此计算网络中节点为信息源的最大似然估计值，得到信息源.这种方法的定位精度取决于观察点的部署位置，因此关于定位准确率与观察点部署位置关系的研究，对于如何确定观察点集的最优部署位置具有重要意义.

Pinto等^[10]所提出的定位方法，其核心是计算信息传播过程中各观察点间的理论传播延迟与实际传播延迟的相似程度.因此，观察点间的理论传播延迟是否能够准确地反映出实际的传播情况，是定位准确与否的关键.本文从实际信息源与观察点间的位置关系入手，分析了观察点部署位置与该源点的距离关系对于定位准确率的影响.对于某一指定信息源，观察点到该信息源的距离差的和增大时，理论传播延迟可以更准确地反映信息传播过程中的真实情况，那么在信息源定位计算过程中，产生的误差就更小，对于该信息源的定位准确率也就更高.

将一个社交网络记为一个有限无向图G=(V，E)，其中V是节点集合，E是边的集合.对于任意节点v∈V，N(v)表示v的邻居节点集合，t_v表示v首次收到信息的时间；对于边e_i∈E，有θ_i表示信息通过边e_i传播所需要的时间.在G中选取K个节点作为观察点，用O表示观察点的集合.在任意时刻，节点v有两种可能状态：知情状态，在当前时刻已收到信息；不知情状态，尚未收到信息.

传播过程如图 1所示，在某一未知时刻t^*，选取s^*为源点，将消息发送给N(s^*)中全部节点.在时刻t_v，v收到消息，若此时v为知情状态，则不做任何操作，否则v变成知情状态，并将消息发送给N(v).对于节点u∈N(v)，若e_j为u与v之间的边，则u在时刻t_v+θ_j接收到由节点v发送的消息，然后执行类似操作，依次类推，直到网络中的节点均为知情状态为止.在传播过程中，观察点还需要记录信息传播的过程，记为φ={(o_i,v,t_v,oi)}，其中v表示首次将信息发送给o_i的邻居节点，t_v,oi表示v将信息发送给o_i的时间.

图 1(Figure 1)

Fig. 1

图1 传播过程 Fig. 1 The propagation process

本文采用Pinto等^[10]提出的方法定位信息源.假设各候选源点为实际信息源，计算这种情况下各观察点收到信息的理论时间，然后与各观察点收到信息的实际时间作比较，最符合的候选源点即为实际信息源.本文假设观察点不会是实际信息源，那么网络中的全部非观察点均为候选源点.当信息传播到某一时刻t，设当前有K_a个观察点处于知情状态，用d=[d₁，d₂，…，d_K(a-1)]^T表示知情观察点的实际传播延迟向量，其中d_i表示观察点o_i+1与观察点o₁首次收到信息的实际时间差，o₁为第一个收到信息的观察点，则有[d]_k=t_k+1-t₁.

由中心极限定理可得^[10]，θ_i满足θ~N(μ,σ²).用p(u,v)表示u与v之间的最短路径，|p(u,v)|表示其长度，假设某一候选源点s_i为实际信息源，则各知情观察点首次收到消息的理论时间为

理论传播延迟向量μ_s={μ_s1,μ_s2,…,μ_sK(a-1)}^T为

应用多元正态分布概率密度计算d与μ_s的相似度ŝ，公式如下:

对候选源点逐个计算ŝ，得到maxŝ的候选源点，即为预期源点.

本文对指定信息源定位准确率做如下定义：

定义 在图G中部署一组观察点O，指定某一候选源点s_i固定为信息源，独立进行n次信息传播，若通过定位计算得到的预期源点为s_i，则认为定位命中，记n次实验中定位命中的次数为m，则称基于观察点集合O，s_i的定位准确率为P_Osi=m/n.

本文所采用的定位方法，是建立在信息在节点间按照最短路径进行传播的假设基础上的，通过计算候选源点到观察点间最短路径长度的差值|p(s_i,o_k+1)|-|p(s_i,o₁)|，估计信息到达时间的理论值，并以此为参考，与信息到达时间的实际观测值进行对比，通过计算相似度，找到实际信息源.候选源点与观察点之间的最短路径长度之差，是估算信息到达理论时间的基础.

图 2(Figure 2)

Fig. 2

图2 传播延迟示意图 Fig. 2 Schematic diagram for propagation delay

如图 2所示，信息源s到观察点o₁，o₂，o₃的最短路径为|p(s,o₁)|=1，|p(s,o₂)|=4，|p(s,o₃)|=2，则理论传播延迟为μ₂=μ(4-1)=3μ，μ₃=μ(2-1)=μ.而o₁，o₂，o₃的实际收到消息的时间为t_o1=t^*+θ₃，t_o2=t^*+θ₃+θ₄+θ₅+θ₆，t_o3=t^*+θ₁+θ₂，则实际传播延迟为d₂=θ₄+θ₅+θ₆，d₃=θ₁+θ₂-θ₃.其中，μ为网络中边的传播延迟θ_i的均值.以μ₂和d₂为例，θ₄，θ₅，θ₆的均值越接近μ，μ₂和d₂就越接近，那么理论传播延迟与实际传播延迟的相似度就越高.即θ₄，θ₅，θ₆可以被认为是网络中信息传播延迟的一组抽样.

本文通过对观察点理论延迟的分析认为：虽然θ_i是随机分布的，但由大数定律可知，当抽样样本较大时，抽样值会趋于接近其算数平均值.因此，对于网络中的一个指定信息源来说，其到观察点间的最短路径的差值越大，该点的理论传播延迟与实际传播延迟的相似度就越高，那么这个节点在定位过程中被选为实际信息源的概率(即定位准确率)也就越高.由此可得定理1.

定理1 设各观察点到信息源s的距离差的和为，对于不同的两个观察点集合O₁和O₂，那么当l(s,O₁)>l(s,O₂)时，O₁的理论传播延迟较小.

证明 选图G中某一候选源点s，消息在未知时刻t^*开始传播,o₁和o_i分别在时刻t₁和t_i收到消息,因为网络中各边传播延迟满足θ~N(μ,σ²) ,则有

设为基于O的p(s,o_i)和p(s,o₁)上边的传播延迟θ_i的算术均值,则有

由期望与方差的性质可知：

利用切比雪夫不等式可得

其中，ε为任意正数，因此有

因此，当l(s,O₁)>l(s,O₂)时，有|θ_O1-μ|＜|θ_O2-μ|，即θ_O1比θ_O2更接近于μ，因此基于O₁的实际信息传播延迟与理论信息传播延迟间的误差更小.

根据定理1，可以得到如下推论.

推论1 对于指定信息源s，当两组观察点集满足l(s,O₁)>l(s,O₂)时，那么对于s的定位准确率满足 P_O1s>P_O2s.

本文采用的信息定位方法，是通过计算理论传播延迟相对于实际信息传播延迟的概率密度分布来实现的，所以对于某一指定信息源，观察点到该信息源的距离差的和较大时，理论传播延迟可以更准确地反映出信息传播过程中的真实情况.实际传播延迟与理论传播延迟间的误差越小，该源点在计算过程中的相似度越高，被选为实际源点的概率越大.那么，对于信息源的定位准确率也就更高.因此对于O₁和O₂,有P_O1s>P_O2s.

3 实验与分析

本文选取ER模型和BA模型生成模型网络进行实验，其中ER网络的节点度符合正态分布^[11]，BA网络符合幂律分布^[12].实验数据如表 1所示.其中，N表示网络中节点的个数；L表示网络中边的条数;AD表示网络中节点的平均度;ND表示网络的直径.

表1

Table 1

表1(Table 1)

表1 实验数据 Table 1 Experimental data Network N L AD ND ERNetwork1 1000 3983 7.966 6 ERNetwork2 1000 6144 12.288 5 BANetwork1 1000 3990 7.980 6 BANetwork2 1000 5979 11.958 5

表1 实验数据 Table 1 Experimental data

具体实验过程是:在网络中选定一个指定节点为信息源，然后选取100组不同的观察点集(观察点占节点总数5 % ).从指定信息源进行信息扩散，然后进行定位计算作为一次独立实验，每组观察点集进行2000次独立的定位实验.

实验结果如图 3所示.其中，横轴表示观察点集的l(s,O)值，纵轴表示该组观察点集对于候选源点s的定位准确率，曲线部分表示线性回归方程曲线.可以看出，随着l(s,O)值增加，定位准确率也随之提高.当l(s,O)增大时，该组观察点的理论信息传播延迟可以更好地反映实际信息传播延迟，这样在信息源定位过程中产生的误差更小，因此其定位准确率也就更高，验证了上节结论的准确性.

图 3(Figure 3)

Fig. 3

图3 模型网络实验结果 Fig. 3 Experimental result of the model network

本文分析了观察点间的理论传播延迟与实际传播延迟之间相似度的计算方法，并以此为基础，得到了观察点与信息源的相对位置对定位准确率产生的影响.对于一个指定信息源，其到各观察点的距离差之和较大时，往往具有较高的定位准确率.如果一组观察点对任意信息源均具有较高的定位准确率，那么这组观察点就是一组优化观察点集合.显然，观察点部署与定位准确率之间关系的研究，对于网络中观察点部署的优化问题，具有重要意义.