观察点部署策略对溯源算法影响的评价与研究

摘要

现实世界中很多现象都可以建模为传播源在复杂网络上的传播，如疾病在人际接触网络上的感染过程以及谣言在社交网络上的扩散，这些网络往往具有规模大和结构复杂的特征，因此，如何在复杂网络中定位传播源的位置是一项具有挑战性的任务。该任务往往根据部分观察点推断传播源的位置，因此，如何有效的选择观察点对准确定位传播源位置至关重要。本文主要针对观察点部署策略展开研究:
　　首先，研究了基于节点中心性的观察点部署策略对识别传播源准确率的影响。本工作分析了随机、度、聚类系数、特征向量、紧密度以及介数等观察点部署策略对传染源估计的影响。在实验中，采用SI传播模型和反向贪心算法估计传播源，并在三类合成网络和四个真实网络进行模拟仿真，实验结果表明采用特征向量的观察点部署策略更有利于提高传播源估计的精度。
　　其次，研究了基于社区结构的观察点部署策略对源点识别准确率的影响。Pinto提出了一种基于部分观测者的传染源识别方法。但是，该方法并没有分析观测者结点的选取对于算法精度的影响，同时也没有考虑网络中社区结构对传播源识别方法的影响。针对上述问题，使用LFR网络和GN网络作为数据集，分析了社区结构以及观察点选取策略对传播源识别方法的影响。通过大量实验发现了以下现象:选择和源点同一社区内的观察点比选择在源点外的社区内的观察点定位传播源的准确率要高;在网络中随机选择观察点时，识别传播源的准确率将介于二者之间。因此，基于社区结构的观察点部署策略会影响传播源的准确率。
　　观察点部署策略的选择对传播源的定位至关重要，本文首先从网络中节点的指标信息的角度出发部署观察点，然后从社区结构角度部署观察点，最后通过大量实验验证了观察点部署策略的重要性。

目录

摘要

第一章 绪论

1．1 研究背景

1．2 课题研究的目的和意义

1．3 国内外研究现状

1．3．1 观察点部署策略简述

1．3．2 传播源定位算法简述

1．4 论文组织结构

第二章 基础概念与理论

2．1 复杂网络的基本概念

2．1．1 复杂网络的特性

2．1．2 复杂网络的统计描述

2．1．3 复杂网络模型

2．1．4 现实世界网络

2．2 复杂网络中的传播模型

2．3 复杂网络中的社区结构

2．4 复杂网络中的传播源定位算法的评价指标

第三章 基于节点中心性的观察点部署策略研究

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

3．2 所采用的传播模型与定位算法

3．3 实验设计与结果分析

3．4 本章小结

第四章 基于社区结构的观察点部署策略研究

4．1 传播模型和观察点选取策略

4．2 基于部分观察点信息的传播源定位算法

4．2．1 极大似然估计算法

4．2．2 Jordan中心估计算法

4．3 实验设计与结果分析

4．3．1 数据集

4．3．2 结果分析

4．4 本章小结

第五章 总结与展望

5．1 总结

5．2 展望

参考文献

致谢

攻读硕士期间发表论文和参与科研项目

声明