面向在线社交网络的扩散源定位方法研究

摘要

在线社交网络的出现，使得网络中的用户不仅是信息的接收者，也可以成为信息的发布者。其不仅为用户提供了良好的互动交流平台，还提供了方便的即时转发与评论功能。因此，在线社交网络受到用户的广泛认可，已经成为最重要的信息交流途径之一。然而，诸如计算机病毒、网络谣言等不良信息的传播，也给人们的生活带来了极大危害。准确定位网络中的信息扩散源点，能够有效控制并减少不良信息造成的危害，已经成为相关研究领域的热点问题。 现有的在线社交网络上的扩散源定位方法大多是在网络中部署少量观察点，通过观察点记录的传播数据定位扩散源。这类方法只需要观测网络中的少部分节点，即观察点，占用网络资源很少，对在线社交网络具有较强的适用性。然而，这类方法仍然存在一些关键问题有待深入研究。首先，定位准确率直接取决于网络拓扑结构和观察点部署方法。但是，现有工作尚未对这三者之间的关系进行系统分析，也没有明确的结论。其次，现有的观察点部署方法都是从节点的中心性出发，考虑了单个节点在网络中的重要性。但在定位计算过程中，观察点集是一个整体。因此，为了得到最优的观察点集，应该从整体的角度进行部署。再次，在实际应用中，经常会出现网络中有多个扩散源的情况。此时，基于观察点的扩散源定位方法，既不能确定扩散源点的数量，又不能区分扩散源点的传播范围，无法准确定位。最后，一些在线社交网络中，可以通过用户转发信息时附加的评论，获取到部分传播路径。充分利用这些路径数据，可以更真实地重现信息的扩散过程，对定位计算有极大帮助。但现有工作尚未给出部分传播路径的使用方法。 针对上述问题，本文对在线社交网络上的扩散源定位方法进行了研究。通过仿真实验，对观察点部署方法、网络拓扑结构与定位准确率的关系进行了分析;通过分析定位计算的过程，对观察点部署方法的优化问题、多扩散源定位问题和部分传播路径的使用方法等三个关键问题进行了研究，并提出了相应的解决方法。具体内容如下: (1)基于中心性的定位准确率影响分析。为了分析观察点部署方法、网络拓扑结构和定位准确率之间的关系，本文设计了一个仿真实验分析体系。该体系中，选用了五种经典的节点中心性作为选取观察点的度量指标，然后在不同类型的模型网络和真实网络上进行定位仿真实验。通过对不同类型网络上不同观察点部署方法的实验结果进行总结分析，得出了相关结论。 (2)面向社交网络扩散源定位的观察点优化部署方法。针对观察点部署的优化问题，将观察点集合作为一个整体，分析了观察点部署位置对指定源点和任意源点的定位准确率的影响。在此基础上，提出了一种基于r覆盖率优先的观察点优化部署方法，并详细描述该方法的思路和过程。通过仿真实验，对理论分析的正确性和优化部署方法的有效性进行验证。实验结果表明，与现有部署方法相比，优化部署方法具有更高的定位准确率。 (3)基于子图抽取的在线社交网络多扩散源点定位方法。针对网络中存在多个扩散源点传播同一信息的情况，对多扩散源信息传播过程和社团网络上的多扩散源传播特征进行分析。在此基础上，提出了一种基于子图抽取的多扩散源定位方法，并详细描述该方法的思路和过程。通过仿真实验，对所提出方法的定位准确性进行验证。实验结果表明，提出的多扩散源定位方法可以有效地判断网络中扩散源点的数量，区分扩散源点的传播范围，并对扩散源准确定位。 (4)基于部分传播路径的扩散源定位优化方法研究。针对部分传播路径如何使用的问题，从提高定位准确率和提高定位效率两个方面，对基于观察点的扩散源定位方法的过程进行分析。在此基础上，提出了基于部分传播路径的生成树优化算法和基于部分传播路径的候选源点筛选算法。前者的目的是使用部分传播路径数据对信息传播树的构建方法进行优化，进而提高定位准确率;后者的目的是使用部分传播路径对候选源点集合进行筛选，进而提高定位效率。通过仿真实验，分别对所提出的两种算法的有效性进行验证。实验结果表明，两种算法均达到了预期目的。

目录

声明

摘要

1．1研究背景

1．1．1在线社交网络上的信息扩散

1．1．2在线社交网络上的扩散源定位

1．2面向在线社交网络的扩散源定位问题

1．3本文的主要研究内容

1．4论文的组织结构

第2章相关理论与相关研究

2．1网络定义与结构度量指标

2．1．1网络定义

2．1．2网络拓扑结构度量指标

2．2网络拓扑结构类型

2．2．1随机网络

2．2．2无标度网络

2．2．3社团网络

2．3社会网络扩散模型

2．3．1传染病模型

2．3．2独立级联模型

2．2．3线性阈值模型

2．4扩散源定位方法概述

2．4．1基于完全观察的扩散源定位方法

2．4．2基于网络快照的扩散源定位方法

2．4．3基于观察点的扩散源定位方法

2．5本章小结

第3章基于中心性的定位准确率影响分析

3．1基于观察点的扩散源定位方法

3．1．1随机传播模型

3．1．2基于观察点的扩散源定位方法

3．2节点中心性基本概念

3．2．1度中心性

3．2．2紧密中心性

3．2．3介数中心性

3．2．4特征向量中心性

3．2．5聚类系数

3．3仿真实验

3．3．1实验体系与实验过程

3．3．2实验数据

3．3．3仿真实验及结果分析

3．4仿真实验分析结论

3．4．1观察点部署方法与定位准确率的关系

3．4．2网络拓扑结构与定位准确率的关系

3．5本章小结

第4章面向社交网络扩散源定位的观察点优化部署方法

4．1观察点部署位置与定位准确率的关系

4．1．1观察点部署位置对指定源点定位准确率的影响

4．1．2观察点部署位置对任意源点定位准确率的影响

4．2基于r覆盖率优先的观察点优化部署方法

4．3仿真实验及结果分析

4．3．1实验数据

4．3．2 r覆盖率与定位准确率的关系实验

4．3．3优化部署方法有效性实验

4．3．4算法性能实验

4．4本章小结

第5章基于子图抽取的在线社交网络多扩散源点定位方法

5．1多扩散源点信息传播特征分析

5．1．1多扩散源点信息传播过程及问题分析

5．1．2社团网络上的多源点传播特征分析

5．1．3模块度对社团网络上的多源点传播影响分析

5．2基于子图抽取的多扩散源定位算法

5．2．1算法思路

5．2．2算法描述

5．3仿真实验及结果分析

5．3．1实验数据

5．3．2算法定位准确性实验

5．3．3算法执行效率影响因素实验

5．4本章小结

第6章基于部分传播路径的扩散源定位优化方法研究

6．1在线社交网络传播特征分析

6．2基于部分传播路径的生成树优化算法

6．2．1算法思路

6．2．2算法描述

6．2．3仿真实验及结果分析

6．3基于部分传播路径的候选源点筛选算法

6．3．1算法思路

6．3．2算法描述

6．3．3仿真实验及结果分析

6．4本章小结

7．1本文工作总结

7．2下一步的研究工作

参考文献

致谢

攻读博士学位期间的主要成果