张聿博, 张锡哲, 徐超, 张斌
东北大学 计算机科学与工程学院, 辽宁 沈阳 110819
收稿日期: 2015-05-14
基金项目: 国家科技支撑计划项目(2014BAI17B00);国家关键科技研发基金资助项目(2015BAH09F02,2015BAH47F03);中央高校基本科研业务费专项资金资助项目(N140404011,N120804001,N120204003);国家自然科学基金资助项目(61572116,61572117,61502089).
作者简介: 张聿博(1984-),男,辽宁沈阳人,东北大学博士研究生; 张 斌(1964-),男,辽宁沈阳人,东北大学教授,博士生导师.

摘要: 针对在线社交网络中普遍存在的信息传播部分路径，在现有的基于观察点的信息源定位方法的基础上，提出一种基于部分路径的信息源点快速定位方法.该方法分析了利用观察点记录的部分传播路径对候选传播源点进行筛选的4种情况.通过筛选候选源点，达到了减小计算量，提高源点定位效率的目的.在模型网络上对改进算法进行实验，验证了该方法的有效性.
关键词: 社交网络信息传播源定位部分路径候选源点筛选
Fast Source Localization Method for Social Network
ZHANG Yu-bo, ZHANG Xi-zhe, XU Chao, ZHANG Bin
School of Computer Science & Engineering, Northeastern University, Shenyang 110819, China
Corresponding author: ZHANG Xi-zhe, E-mail: zhangxizhe@ise.neu.edu.cn

Abstract: Considering the phenomenon that several partial paths were recorded by the users in most social networks, a fast source localization method based on partial paths was provided by using the previous source localization method based on observers. The four cases of screening candidate sources were analyzed based on the proposed method, which made use of the partial paths recorded by the observers. By screening candidate sources, the purpose of reducing the computing expense and improving the location efficiency was achieved. The results of experiments on model network showed the effectiveness of the method.
Key words: social networkinformation diffusionsource localizationpartial pathscandidate source screen 在线社交网络已经成为当前被广泛使用的信息传播载体之一^[1]，带来了巨大的商业价值和社会价值.然而，在线社交网络上的谣言传播问题也逐渐显现出来，并受到了社会的广泛关注，成为当前的研究热点之一^{[2, 3]}.
如果能够及时准确地定位网络中的谣言传播源头，对控制网络上的谣言传播具有重要意义^{[4, 5]}.现有的信息源定位方法主要分为两类^[5]：一类是通过多次获取网络中信息传播各阶段的网络快照，利用这些信息定位信息源.Prakash等^[6]针对SI模型提出一种基于最小描述长度的定位方法，能够自动地确定传播源点的数目，并识别网络中的多个传播源点.Zhu等^[7]采用样本路径方法，寻找最有可能形成网络快照中样本路径的根节点作为信息源点.然而，多次获取网络传播快照需要消耗大量资源，不适用于规模庞大的社交网络.另一类方法是由Pinto等^[8]提出的基于观察点的信息源定位方法.该方法在网络中部署少量观察点，通过观察点记录的传播信息，构建似然估计函数，计算网络中各候选源点(网络中除观察点以外的其他节点称为候选源点)的似然估计值，似然估计值最大的即为信息源.这类方法仅需要获取少量节点的传播信息，在大规模社交网络上具有较好的适用性.
在实际应用中，定位效率是评价一个源点定位算法适用性好坏的重要指标.基于观察点的信息源定位方法,其算法复杂度为O(N³)，其中N为网络中节点的数量.显然，随着节点数量的增加，定位计算所需要的时间成倍增长.对于社交网络这样的大规模网络来说，定位计算所需要的时间将大大影响其定位效率.造成计算量过大的一个重要原因，是网络中候选源点的规模过于庞大，导致需要计算似然估计值的节点过多.如果能够找到一种对候选源点进行筛选的方法，将有效提高定位效率.
在当前社交网络上的信息传播过程中，往往会存在这样一种现象，用户会将信息的来源附加到信息本身中，继续传播下去.例如，在微博信息中，会用“@”符号表示这个信息在转发过程中所经过的用户.通过这些附加信息，可以得到信息在传播过程中经过的部分传播路径，这些路径能够描述信息的真实传播过程，有效地利用这些部分路径信息可以为筛选候选源点提供依据，达到缩小候选源点范围，提高定位效率的目的.
1 传播模型与定位方法在本文所采用的传播模型与定位方法中，G表示整个网络，V={v₁,v₂,…，v_n}表示节点集，N(v)表示节点v的邻居节点集，θ_uv表示u与v之间的传播延迟，μ表示G中全部θ_uv的均值，σ表示θ_uv的方差，O={o_i}表示观察点集，t_i表示o_i首次收到信息的时间，S表示候选源点集合，|p(u,v)|表示u与v之间的最短路径的长度.具体传播过程如下.
以s^*∈V为源点，s^*将消息发送给N(s^*).对于普通节点v，其首次收到该消息时，会将该消息发送给N(v)，否则不发送.对于观察点o_i，其首次收到该消息时，除了转发消息，还会记录t_i和信息来源节点.以此类推，直到G中节点全部收到该信息为止.
本文参考了Pinto等^[8]提出的基于观察点的信息源定位方法，该方法逐个假设每个候选源点(非观察点)为实际信息源，对比各观察点收到信息的理论时间与实际时间，然后计算似然估计值，找到似然估计值最大的候选源点即为实际信息源.似然估计值的计算方法如下：


式中：d=[d₁,d₂,…，d_k]^T是已收到信息的观察点的实际传播延迟向量；μ_s是理论传播延迟向量.计算方法如下：
2 基于部分传播路径的信息源快速定位方法2.1 算法思路基于观察点的信息源定位方法^[8]，对候选源点构建广度优先生成树，然后计算该节点的似然估计值.但是，如果对每个候选源点都进行这样的计算，会造成巨大的计算时间开销.因此，如果能够在构建生成树之前，先将候选源点中真实信息源可能性很小的节点筛选掉，就可以达到减少候选源点数量，提升源点定位效率的目的.
基于观察点的信息源定位算法，其基本假设是信息沿着最短路径传播.以此假设为基础，本文结合信息传播过程中观察点所记录的部分传播路径，提出了一种筛选候选观察点的思路.以这些路径的首尾节点对为两端，可以得到节点对间存在的全部路径.对于任意节点a,b，若观察点记录了从a到b的一条路径P，那么从a到b的其他路径长度与P进行比较，只能存在小于、等于、大于3种可能，此外，还需要考虑P上的节点.因此，本文从以下4种情况对候选源点的筛选方法进行描述.
1) 部分传播路径上的节点.如图 1所示，观察点o记录了一条部分传播路径1→2→3→4→5，很显然，除了节点1外，这条路径上的其他节点都不可能是信息源.
图1(Fig. 1)

图1 部分传播路径上的节点 Fig. 1 Nodes on partial path

2) 等于部分路径长度的路径.如图 2所示，观察点o记录了一条部分传播路径1→2→3→4→5，记为P₁，长度为4.在节点1与节点5之间还存在一条路径1→6→7→8→5，与P₁长度相等，记为P₂.如果信息源在P₂上，假设是节点6，根据最短路径假设，信息从节点6传播到节点5的路径应该是6→7→8→5，该路径的长度小于P₁.若节点6是信息源，那么节点5应该首先接收到节点8传入的信息，这与观察点记录的传播信息不符.同理，P₂上的其他节点也是这样的结果.可以得出，网络中与记录的部分传播路径有着相同首尾节点的等长路径上的节点(除首节点)，是信息源的可能性很小.
图2(Fig. 2)

图2 等于部分路径长度的路径 Fig. 2 Paths equal to partial path

3) 小于部分路径长度的路径.如图 3所示，观察点o记录了一条部分传播路径1→2→3→4→5，记为P₁，长度为4.在节点1与节点5之间还存在一条路径1→6→7→5，小于P₁的长度，记为P₂.与情况2类似，如果信息源在P₂上，那么节点5应该首先接收到节点7传入的信息，这与观察点记录的传播信息不符.可以得出，网络中与记录的部分传播路径有着相同首尾节点，但长度小于该路径的路径上的节点(除首节点)，是信息源的可能性很小.
图3(Fig. 3)

图3 小于部分路径长度的路径 Fig. 3 Paths shorter than partial path

4) 大于部分路径长度的路径.如图 4所示，观察点o记录了一条部分传播路径1→2→3→4，记为P₁，长度为3.在节点1与节点4之间还存在一条路径1→5→6→7→8→9→4，大于P₁的长度，记为P₂.通过对情况2与情况3的分析，网络中节点6，7，8，9不可能是信息源点.图 4中只给出了以节点1与节点4为首尾的路径，若以节点5为首节点时，存在路径5→1，那么就存在一条路径5→1→2→3→4，该路径小于5→6→7→ 8→9→4的长度，那么节点5就可能是信息源.可以得出，大于部分路径长度的路径为P，长度为|P|，部分路径为P’，长度为|P’|，则筛选出的候选源点是沿着P路径方向第|P|-|P’|-1节点到第|P|+1节点之间的所有节点.
图4(Fig. 4)

图4 大于部分路径长度的路径 Fig. 4 Paths longer than partial path

2.2 算法描述根据上节所述的筛选方法，本文对基于观察点的信息源定位方法进行改进.与原算法相比，本文所提出的定位方法，结合观察点记录的部分传播路径，先对候选源点进行筛选，缩小候选源点的范围，然后再进行定位计算.其中，筛选候选源点的步骤如下.
步骤1 设观察点集合为O，候选源点集合为C.遍历O，获取所有部分路径，并加入集合P.
步骤2 对P中的每个部分路径P_i ，获取网络所有与其首尾节点相同的路径，并加入集合T.
步骤3 遍历T，取出T中的一条路径T_i，如果路径长度T_i小于等于部分路径长度P_i，则将T_i中首节点以外的所有节点加入集合F.如果|T_i|>|P_i|，则将T_i中按T_i的方向顺序第|T_i|-|P_i|-1节点到第|T_i|+1个节点加入集合F.
步骤4 集合C与F做差集得到集合O_f，即为筛选后的候选源点集合.
具体伪代码如下：
observers=graph.getObervers() //获取所有观察点
candidate=graph.getNodes() - observers;
for(0≤i≤observers.size) do
Node n=observers.get(i);
fragments=n.getFragments();//获取所有部分路径
for(0≤f≤fragments.size) do
nodesShorter=fragments.getShortestPath(i);
nodesEqual=fragments.getShortestPath(i);
nodesLonger=fragments.getShortestPath(i);//
将全部符合条件的路径上的节点加入过滤集合
filter.add(nodes in shorter paths);
filter.add(nodes in equal paths);
filter.add(nodes in longer paths);//
部分路径上除首节点以外节点加入过滤集合
filter.add(nodes in partial paths);
end for
end for
filteredCandidate =candidates - nodes in filter ;//得到筛选后的候选源点集合
return;
3 实验与分析为了验证快速定位算法的定位效率及影响因素，本文选用经典的ER模型^[9]网络和BA模型^[10]网络进行实验.具体实验数据如表 1所示，其中N表示网络节点数，L表示边数，<k>表示网络平均度，d表示网络直径，Apl表示网络平均路径长度.
表1(Table 1)

表1 实验数据 Table 1 Experimental data 网络 N L <k> d Apl ERNetwork1 6 000 180 804 30.134 14 3.092 ERNetwork2 8 000 256 690 32.086 17 3.160 BANetwork1 6 000 150 000 25 5 3.010 BANetwork2 8 000 200 000 25 5 3.098

表1 实验数据 Table 1 Experimental data

在实际应用中，不是所有用户会记录传播路径，并且所记录的传播路径长度也不同.本文设能够记录传播路径的观察点占观察点总数的比例为f_p，部分路径的最大长度为F，观察点的选取策略按照网络中节点的入度排列，选取入度大的节点作为观察点，观察点占全部节点的比例为p.在下面的各部分实验中，p的取值范围为0.05~0.4(递加0.05)，f_p的取值范围为0.05~0.3(递加0.05)，F取值为3.
1) 改进算法与原算法定位准确率比较.为了考查改进算法对原算法(基于观察点的信息源定位方法)定位准确率的影响，选取ERNetwork1与BANetwork1作为实验数据集.对每种观察点比例下取每种f_p做1 000次实验，得到对应的定位命中率，实验结果如图 5所示.
图5(Fig. 5)

图5 改进算法与原算法定位准确率比较 Fig. 5 Comparison of localization accuracy between improved and original algorithms(a)—ERNetwork1； (b)—BANetwork1.

由图 5可知，在各观察点比例下，改进的快速定位算法与原算法的定位准确率相差很小，可以忽略不计.此外，改进算法的命中率随着观察点比例的增大而升高，趋势也与原算法的定位准确率变化趋势相吻合.
2) 改进算法的候选源点筛选效果.为了分析改进算法对定位效率的提升，选取ERNetwork1-2，BANetwork1-2作为实验数据集.对每种观察点比例下取每种f_p做2 000次实验，得到对应的筛选比均值(筛选出的节点占原来候选节点的比例)，实验结果如图 6所示.分析实验结果可知，部分传播路径比例与筛选比成正比，对于同一观察点比例，f_p越大筛选比越高.这是因为f_p越大，观察点获取的部分传播路径信息越多，可以筛选掉的候选源点越多.
图6(Fig. 6)

图6 改进算法的候选源点筛选结果 Fig. 6 Results of screening candidate source nodes with improved algorithm (a)—ERNetwork1； (b)—ERNetwork2; (c)—BANetwork1； (d)—BANetwork2.

3) 改进算法与原算法定位时间比较.改进算法最主要的作用就是提升原算法的定位效率，为了考察改进算法的定位效率提升效果，选择ERNetwork1与BANetwork1作为实验数据.对每种观察点比例下取每种f_p做2 000次实验，得到对应的定位效率提升比例(原算法与改进算法的平均定位时间之间差除以原算法的平均定位时间)，实验结果如图 7所示.可以得出，在ER模型网络上，改进算法对原算法的定位效率有5%~25%左右的提升；在BA模型网络上，改进算法对原算法的定位效率有15%~35%左右的提升.并且提升效率随观察点比例的增大而增大.观察点比例在0.05~0.2左右时，效率上升趋势明显，当观察点比例达到0.25后，效率增速减缓，并在某一值范围内波动，且f_p值越大，其定位效率提升越大.
图7(Fig. 7)

图7 改进算法的定位效率提升结果 Fig. 7 Results of localization efficiency improvement with improved algorithm (a)—ERNetwork1； (b)—BANetwork1.

4 结 论本文针对现有的基于观察点的信息源定位方法定位效率较低，不适用于大规模社交网络这一问题，结合社交网络信息传播过程中会记录部分传播路径这一现象，提出了一种基于部分传播路径的信息源快速定位方法.该方法对传播模型及基于观察点的信息源定位方法进行分析，得出了通过已知部分路径对候选源点进行筛选的方法，以达到减少定位计算量，提高定位效率的目的.在模型网络上进行实验，结果表明，本文所提出的改进算法能够在基本不影响定位命中率的情况下，有效提高定位效率.

参考文献

[1]	Dong W,Zhang W,Tan C W.Rooting out the rumor culprit from suspects[C]// IEEE International Symposium on Information Theory.Istanbul:IEEE,2013:2671-2675.(1)
[2]	Budak C,Agrawal D,El-Abbadi A.Limiting the spread of misinformation in social networks[C]//Proceedings of the 20th International Conference on World Wide Web.Hyderabad:ACM,2011:665-674.(1)
[3]	Shah D,Zaman T.Detecting sources of computer viruses in networks:theory and experiment[C]//ACM SIGMETRICS Performance Evaluation Review.New York:ACM,2010:203-214.(1)
[4]	Lokhov A Y,Mezard M,Ohta H.Inferring the origin of an epidemic with dynamic message-passing algorithm[J].Physical Review E,2014 ,90(1):012801.(1)
[5]	张聿博,张锡哲,张斌.面向社交网络信息源定位的观察点部署方法[J].软件学报,2014,25(12):2837-2851. (Zhang Yu-bo,Zhang Xi-zhe,Zhang Bin.Observer deployment method for locating the information source in social network[J]. Journal of Software,2014,25(12):2837-2851.)(1)
[6]	Prakash B A,Vreeken J,Faloutsos C.Spotting culprits in epidemics:how many and which ones?[C]// IEEE 12th International Conference on Data Mining.Brussels:IEEE,2012:11-20.(1)
[7]	Zhu K,Ying L.Information source detection in the SIR model:a sample path based approach[J].IEEE/ACM Transactions on Networking,2014,11(20):1-14.(1)
[8]	Pinto P C,Thiran P,Vetterli M.Locating the source of diffusion in large-scale networks[J].Physical Review Letters,2012,109(6):068702.(3)
[9]	Erd6s P,Rényi A.On random graphs I[J].Publications Mathematician, 1959,6:290-297.(1)
[10]	Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.(1)

1

本文献在全文中的定位：
... 在线社交网络已经成为当前被广泛使用的信息传播载体之一^[1]，带来了巨大的商业价值和社会价值.然而，在线社交网络上的谣言传 ...



1

本文献在全文中的定位：
... 也逐渐显现出来，并受到了社会的广泛关注，成为当前的研究热点之一^{[2, 3]}. ...



1

本文献在全文中的定位：
... 泛关注，成为当前的研究热点之一^{[2, 3]}. ...



1

本文献在全文中的定位：
... 地定位网络中的谣言传播源头，对控制网络上的谣言传播具有重要意义^{[4, 5]}.现有的信息源定位方法主要分为两 ...



1

本文献在全文中的定位：
... 制网络上的谣言传播具有重要意义^{[4, 5]}.现有的信息源定位方法主要分为两 ...



1

本文献在全文中的定位：
... 网络中信息传播各阶段的网络快照，利用这些信息定位信息源.Prakash等^[6]针对SI模型提出一种基于最小描述长度的定位方法，能够自动地确定传 ...



1

本文献在全文中的定位：
... ，能够自动地确定传播源点的数目，并识别网络中的多个传播源点.Zhu等^[7]采用样本路径方法，寻找最有可能形成网络快照中样本路径的根节点作 ...



3

本文献在全文中的定位：
... 要消耗大量资源，不适用于规模庞大的社交网络.另一类方法是由Pinto等^[8]提出的基于观察点的信息源定位方法.该方法在网络中部署少量观察点 ...

... 参考了Pinto等^[8]提出的基于观察点的信息源定位方法，该方法逐个假设每个候选源点( ...

... 于观察点的信息源定位方法^[8]，对候选源点构建广度优先生成树，然后计算该节点的似然估计值.但 ...



1

本文献在全文中的定位：
... 验证快速定位算法的定位效率及影响因素，本文选用经典的ER模型^[9]网络和BA模型^[10]网络进行实 ...



1

本文献在全文中的定位：
... 经典的ER模型^[9]网络和BA模型^[10]网络进行实验.具体实验 ...