在线社交网络的信息传播具有方向性，即只有“关注者”用户节点才能从“被关注者”用户节点收到信息，因此本文采用有向图G(V,E,W)对社交网络进行建模。其中，V为节点集合，E为边集，W为权集，表示每条边上信息传播的延迟时间。

对于节点u∈V，$\gamma (u)$表示其邻居节点集合，${{t}_{u}}$表示u首次收到某一指定信息的时间；对于边${{e}_{ij}}\in E$，${{e}_{ij}}$为节点i和节点j之间的连边；${{w}_{ij}}\in W$为随机变量，表示边${{e}_{ij}}$的传播延迟，本文考虑传播延迟服从均值为$\mu $和方差为${{\sigma }^{2}}$的高斯分布的情况^[10]。

在某一未知时刻t^*，未知源点${{s}^{*}}\in V$发送消息M给其邻居节点$\gamma ({{s}^{*}})$。节点u有两种可能状态：

1) 知情状态，该节点已经接收到信息。

2) 不知情状态，该节点没有接收到信息。当节点u收到指定消息M时，若此时u为知情状态，则不做变化；否则由不知情状态变为知情状态，并将消息M发送给$\gamma (u)$。

选取社交网络上部分节点记录其传播状态，称这些节点为观察点，记为$O=\{{{o}_{k}}\}_{k=1}^{K}$，观察点会记录3类信息：1) 发送者，表示消息是从哪个节点传入的。2) 时间，信息首次到达该节点的时间。3) 消息内容，包括消息之前传播所附加的部分路径信息。

对于基于部分观察点集的传播源点定位方法，文献^[10]提出了一种最大似然估计方法，利用观察点搜集的时间及发送者信息定位传播源点。该方法的一个基本假设是信息沿着最短路径进行传播，所以对每个潜在源点(网络中除观察点外的节点)n，以n为中心构造广度优先搜索树，以此重构信息的传播过程，然后计算其似然估计值，似然估计值最大的潜在源点即为信息源。

图  1  构建广度优先生成树举例

上述方法的一个缺点在于，很多情况下，节点间的最短路径不只一条，信息会沿着哪条路径进行传播，与很多复杂因素如节点间的交互强度、可信任性、权威性、影响力等密切相关。因此，上述方法在真实在线社交网络中，很难构建符合真实传播过程的搜索树，也得不到准确的定位结果。经过观察，社交网络中传播的信息，往往会附加其经过的部分传播路径。有效的利用这些路径，更准确的重构信息传播过程，可以提高定位的准确率。

本文算法的基本思路是，在最短路径传播假设的基础上，结合观察点搜集到的部分传播路径，建立更准确的广度优先搜索树，从而提高源点定位的准确度。具体做法是，当从潜在源点构造广度优先树时，如果遍历到记录了部分传播路径的观察点时，首先判断观察点记录的接收信息节点方向与生成树中待连接的父节点是否为同一节点，然后判断从树根节点到当前待加入节点的路径是否与部分传播路径完全一致。如果不一致，则需从路径不一致的起始处选择其他路径构建生成树路径，直到符合观察点记录的路径信息为止。如果某一潜在源点无法构建出符合要求的生成树，则将该节点排除，不再进行似然估计值计算。

如图 1所示，${{s}^{*}}$是信息源点，${{o}_{1}}$是观察点。观察点${{o}_{1}}$记录从${{v}_{2}}$接收到消息。在此情况下，以${{s}^{*}}$为根可以构建3种可能的生成树，如图 1b～图 1d所示。若${{o}_{1}}$收到的信息记录了部分路径${{v}_{1}}\to {{v}_{2}}$。那么，在判断生成树是否满足${{o}_{1}}$记录的信息时，除比较接收信息的方向是否为${{v}_{2}}$，还需判断已经加入生成树的节点是否符合部分传播路径。按照上述规则，图 1b和图 1d两种情况被排除，只有图 1c符合。在构建生成树时参照部分路径的策略能够筛除一些不符合实际传播情况的生成树，保留符合实际传播情况的生成树。

基于上节中提出的算法思路，本文在文献^[10]的信息源定位方法基础上，提出了基于部分传播路径的信息源定位方法，该算法充分利用了社交网络中传播的信息会记录传播路径这一特征，对现有算法的生成树方法进行了改进。

社交网络中，信息附加的部分路径可以包括一个或者若干个节点，可以是一段或者多段，并且不会所有用户在转发过程中都会附加传播路径信息。本文考虑观察点只记录一段部分传播路径的情况，假设只有部分观察点会记录部分传播路径，用${{f}_{p}}$表示记录部分路径的观察点占所有观察点的比例。${{f}_{p}}$的取值与信息的内容和长度都有关，由于在线社交系统会限定信息的长度，对于本身内容较长的信息，用户会删除部分传播路径以符合系统的要求。令observers为观察点集合，fragment为部分路径集合，tree为构建的生成树。对于某一潜在源点n，其构造生成树的具体过程如下：

1) 遍历observers集合，将所有观察点记录的部分路径存入fragment。

2) 令n为生成树tree的根节点；获取n的所有外邻节点，并将其存入queue中。

3) 从queue中取出节点m，令m的父节点为q，做如下判断：

① 若fragment中不包括节点m，则将边${{e}_{qm}}$加入生成树tree；计算m的外邻节点并将其存入queue；

② 若fragment中包括节点m，且边${{e}_{qm}}$也在fragment中，则将边${{e}_{qm}}$加入生成树tree；计算m的外邻节点并将其存入queue；

③ 若fragment中包括节点m，但边${{e}_{qm}}$不在fragment中，则不做任何操作。

4) 重复执行过程3)，直到queue为空。

5) 若tree包含所有收到消息的观察点，则返回以n为根的生成树tree，否则返回null。

构建了以n为根的广度优先树之后，可以利用文献^[10]的最大似然估计进行源点定位，找出具有最大似然估计值的节点作为传播源点。最大似然估计的计算为：

式中，

式中，$k,i=1,2,\cdots ,K$；$|P(u,v)|$表示连接节点u和节点v的最短路径长度。

为了验证算法的有效性，本文采用模型网络与实际网络进行模拟实验。其中，模型网络采用了ER模型网络^[11]和BA模型网络^[12]。具体实验数据如表 1所示。表中N表示网络节点数，L表示边数，<k>表示网络平均度，d表示网络直径，Apl表示网络平均路径长度。ERNETWORK1～ERNETWORK4是ER模型网络，BANETWORK1～BANETWORK4是BA模型网络，SinaWeibo和Twitter是通过新浪微博和Twitter公开的API分别抓取一条微博信息在用户中传播所经过的所有节点进而得到的实际网络数据。

本文按照节点在网络中的入度排列，选取入度最大的部分节点为观察点，观察点的比例为0.05～0.40(每次递加0.05)。能够记录部分路径的观察点比例${{f}_{p}}$的取值为0.1～0.3(每次递加0.1)，F取值为2。在网络中随机选取一个非观察点为信息源进行信息传播，然后分别应用原算法(文献^[10]提出的方法)和本文的方法进行比较，对不同的观察点比例和${{f}_{p}}$，在每个网络上进行2 000次定位实验，取均值得到命中率，模型网络实验结果如图 2所示。图 2a～图 2d是ERNETWORK1-4的实验结果，图 2e～图 2h是BANETWORK1-4的实验结果。

图  2  模型网络命中率比较

可以看到各个观察点比例下改进算法的定位命中率均高于原算法。分析图中具体数据，当网络的观察点比例从0.05提高到0.10时，各个模型网络的定位命中率都有较大的提升，但是随后观察点比例的增加并没有对定位命中率提高造成较大影响，当观察点达到0.15后ER和BA网络的命中率上升缓慢并趋于平滑，接近最大值。可以得出，对于同一观察点比例，${{f}_{p}}$越大定位命中率越高。这是因为${{f}_{p}}$越大，部分路径越多，在以潜在源点为根构建传播生成树时，能够得到更加真实反映信息传播过程的广度优先生成树，进而提高了算法的定位准确性。

从曲线中观察点变化引起定位命中率变化的趋势看，随着观察点比例的增加，定位命中率随之提高，因为观察点比例的增加使更多的节点记录真实传播过程，同时也增加了部分传播路径的数量，进而提高定位准确性。

在SinaWeibo和Twitter两个实际网络上也进行了对比实验，取F值为2，${{f}_{p}}$为0.2，结果如图 3和图 4所示。

图  3  SinaWeibo网络命中率比较

图  4  Twitter网络命中率比较

从两个网络的实验结果来看，在不同观察点比例下改进算法都比原算法定位命中率高。其中，SinaWeibo网络的定位命中率改进算法平均高于原算法17%，Twitter网络的定位命中率改进算法平均高于原算法14%。可见改进的源点定位算法对于实际网络是有效的，可以提升一定幅度的定位命中率。

进一步，通过实验，对部分路径长度和部分路径比例对定位命中率的影响进行分析。选取ERNETWORK1作为实验数据集。对于ER网络，改变观察点比例，得到在指定观察点比例下，源点定位命中率随${{f}_{p}}$变化的实验结果，如图 5所示。其中图 5a～图 5f分别为观察点比例从0.05～0.30的实验结果，横坐标为部分路径比例${{f}_{p}}$，纵坐标为源点定位的命中率。由图 5可以得出，在不同观察点比例及不同${{f}_{p}}$下，F=2均比F=1时定位命中率高，由此可知部分路径越长，源点定位命中率越高。原因是观察点能够记录的部分路径长度越长，观察点获取真实的传播路径信息则越多，可以构造更符合真实传播路径的广度优先生成树，定位命中率更高。

图  5  不同部分路径长度的定位准确率

本文分析了在线社交网络中的信息传播过程，发现消息中携带的部分传播路径可以有效地提高信息源点定位的准确度。因此，提出一种基于部分传播路径的源点定位算法，根据观察点记录的信息，提取部分传播路径，并基于部分传播路径的约束，建立更接近信息传播过程的广度优先搜索树，从而定位信息源。

本文提出的方法利用了在线社交网络上的信息传播特点，有效地提高了信息源点的定位准确率。在模型网络和实际网络上的实验结果表明，改进算法的定位准确率明显高于原有算法，充分验证了该方法的有效性。并且，从部分路径长度和观察点记录部分路径比例两个方面，分析了对该方法定位准确率产生影响的因素。本文提出的方法，对于有效定位在线社交网络中谣言等信息源点具有重要的应用意义。