基于非回溯矩阵最大特征值的信息源检测

论文摘要

科技的发展使得信息在网络中大规模传播非常普遍,例如交通网络的发展促进了人口流动,社交网络使得信息的传播更加便捷和广泛等等,但同时也带了很多潜在的风险,如传染病的大规模传播,虚假新闻在社交网络上的大行其道,计算机病毒的感染等,因此如何准确检测出信息在网络中传播的源节点,对防止和控制风险的发生有着重要意义。信息源检测问题是指,通过观察到的被信息源感染的节点图和网络的拓扑结构,结合信息的传播模型,来推断信息传播的源节点。本文研究了一般拓扑结构网络中的信息源检测问题。假设信息在网络中的传播模型为离散时间的易感染-已感染（SI）模型,并且源点个数已知。通过对消息传递等式的线性化分析,提出了基于非回溯矩阵最大特征值的信息源检测器,认为当节点为源点时,其相应的退化非回溯矩阵的最大特征值最小。另外,还通过对检测器做微扰近似降低了检测器的算法复杂度。然后,对基于非回溯矩阵最大特征值的信息源检测器做了近似理论分析。通过对由消息传递等式描述的非线性系统做逐步线性化,发现该非线性动态系统的变化与动态退化非回溯矩阵的最大特征值有关。利用乘幂法推导得到了动态退化非回溯矩阵的最大特征值的解析表达式,得到了当退化非回溯矩阵具有最小最大特征值时,系统最快趋于稳定状态的结论,验证了检测器的合理性。最后,通过仿真实验验证了基于非回溯矩阵最大特征值的信息源检测器的性能。仿真实验分为三部分:一般拓扑结构网络中的单信息源检测,一般拓扑结构网络中的多信息源检测和树型网络中的单信息源检测。仿真实验表明,在几种典型的一般拓扑结构网络中,基于非回溯矩阵最大特征值的检测器在单源点检测中与经典检测器相比具有竞争力,并且在多源点检测中也具有良好的检测性能。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
•   1.1 论文的研究背景与意义
•     1.1.1 研究背景
•     1.1.2 研究意义
•   1.2 相关工作与研究现状
•   1.3 本文的结构与主要贡献
• 第二章 信息源检测问题的预备知识
•   2.1 引言
•   2.2 基本概念
•   2.3 信息网络模型
•   2.4 信息传播模型
•   2.5 消息传递等式（Message Passing Equations）
•   2.6 经典检测器
•     2.6.1 Rumor Center
•     2.6.2 Jordan Center
•   2.7 图的非回溯矩阵以及应用
•   2.8 小结
• 第三章 基于非回溯矩阵最大特征值的信息源检测器
•   3.1 引言
•   3.2 信息传播模型和问题描述
•   3.3 易感染-已感染（SI）传播模型下的消息传递等式
•   3.4 线性近似
•   3.5 基于非回溯矩阵最大特征值的估计器
•   3.6 微扰近似
•   3.7 检测算法
•     3.7.1 多源点检测算法（MSI）
•     3.7.2 基于微扰近似的多源点检测算法（PMSI）
•   3.8 小结
• 第四章 近似理论分析
•   4.1 逐步线性化
•   4.2 基于乘幂法（Power Method）的近似分析
•   4.3 小结
• 第五章 仿真实验
•   5.1 引言
•   5.2 一般拓扑结构网络中的性能表现
•     5.2.1 单源点情况
•     5.2.2 多源点情况
•   5.3 规则树图下的性能表现
•     5.3.1 规则树图下的单源点检测器
•     5.3.2 仿真实验结果
•   5.4 小结
• 第六章 总结与展望
•   6.1 工作总结
•   6.2 未来研究计划与展望
•     6.2.1 未来研究计划
•     6.2.2 信息源检测问题的未来展望
• 参考文献
• 致谢
• 在读期间发表的学术论文与取得的研究成果

文章来源

类型: 硕士论文

作者: 潘佳纯

导师: 张文逸

关键词: 多信息源检测,易感染已感染模型,消息传递等式,非回溯矩阵,最大特征值,矩阵,乘幂法

来源: 中国科学技术大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 中国科学技术大学

分类号: O157.5

总页数: 60

文件大小: 3007K

下载量: 47