网络中信息传播：信息源选择与检测的若干关键问题研究

发布时间：2019-04-17 12:19

【摘要】：在当今世界中,通过网络(尤其是移动社交网络)的信息、消息、病毒、谣言、思想、革新等的传播非常普遍。广义来说,这些情形都可以看做是某种流行性“信息”在一个网络上传播与扩散。近几十年以来,网络中流行性信息传播的相关问题持续吸引着研究者的广泛关注；在未来,这将仍然是多学科交叉的网络科学问题中一个长期的研究焦点。本文从信息传播源头的角度出发,研究信息源选择与检测的若干关键问题,这些研究成果将有助于促进网络中有益信息的传播和抑制网络中恶意信息的扩散。针对信息源选择问题,本文的主要贡献如下： 1)研究了谣言传播模型下非自适应的信息源选择问题：针对PUSH和PULL模型,分别构造信息传播过程的等价视角和含时映射,进而证明源选择问题具有子模性。进一步利用子模性,提出使用贪婪算法解决谣言传播最大化问题,这个次优的算法的性能保证因子是(1-1/e)。仿真实验结果表明,少量信息源在小的时延容忍限制下可以促成信息的广泛扩散,并且贪婪算法的扩散性能明显优于常用的启发式算法和随机算法。 2)研究了影响扩散模型下自适应的信息源选择问题：对于一类序贯贪婪的优化问题,提出序贯贪婪性的概念分析它并提出在线贪婪算法解决它,这个次优的算法的性能保证因子是(1-1/e)。针对LT和IC模型,使用实现生成算法构造自适应情形下信息传播过程的等价视角,进而证明LT模型下源选择问题具有序贯贪婪性,也定性讨论IC模型下序贯贪婪性。进一步利用序贯贪婪性,提出使用在线贪婪算法解决自适应的影响扩散最大化问题,在LT模型下其性能保证因子是(1-1/e)。结合谣言传播和影响扩散提出混合模型,并讨论混合模型下自适应的影响扩散最大化问题。仿真实验结果表明,利用自适应增益的贪婪算法明显优于非自适应的贪婪算法,并且具有小的播种时间间隔的在线贪婪算法的扩散性能接近于具有完全反馈的自适应的贪婪算法。 3)研究了信息源选择问题的应用,并重点考察无线业务分流问题：为基于近邻通信的无线业务分流问题提出一个理论框架,提出GSC模型对MSNets中信息传播过程建模,并使用本地移动性模型对时变网络建模。针对静态网络和移动网络情形,分别构造信息传播过程的等价视角和含时映射,进而证明业务分流问题具有子模性。进一步利用子模性,提出使用基于用户联系的仿真模拟的贪婪策略解决业务分流最大化问题,这个次优的算法的性能保证因子是(1-1/e)。仿真实验结果表明,少量信息源可以较大规模的卸载无线业务量,更强的社交参与性和更长的时延容忍可以卸载更多的无线业务量,并且移动性可以进一步增强分流效果。针对信息源检测问题,本文的主要贡献如下： 1)研究了病毒传播模型下无先验知识的信息源检测问题：针对具有规则树结构的网络中SI模型,使用最优的基于谣言向心性的ML估计器识别信息源,提出局部谣言中心的概念用于解源估计器,并利用波利亚罐子模型得到感染样本的概率分布。进一步,从感染规模的维度分析,得到在有限域和渐近域中正确检测概率的闭式表达式。在有限域中,正确检测概率随着已感染的节点数目增加而减少、随着节点度数增加而增加。在渐近域中,当节点度数为2、3和足够大时,正确检测概率分别为0、0.25和0.307。 2)研究了病毒传播模型下有先验知识的信息源检测问题：针对具有规则树结构的网络中SI模型,构造最优的基于谣言向心性的MAP估计器从先验给定的嫌疑节点中识别信息源,使用局部谣言中心的概念解源估计器,并利用由波利亚罐子模型得到的感染样本的概率分布,分析得到嫌疑节点构成不同连接模式下正确检测概率。当嫌疑节点构成网络的连通子图时,有限域中正确检测概率随着已感染的节点数目增加而减少、随着节点度数增加而增加,在节点度数超过2时渐近域中正确检测概率显著超过先验概率,并且在节点度数足够大时渐近域中可以实现可靠检测。当网络中只有两个嫌疑节点时,有限域中正确检测概率随着它们之间的距离而增加,在节点度数超过2时渐近域中正确检测概率不小于0.75,并且在节点度数足够大时渐近域中也可以实现可靠检测。当网络中有多个嫌疑节点时,在它们形成连通子图时正确检测概率取得最小值。 3)研究了信息源检测问题的应用,并重点考察计算机病毒源识别问题：针对计算机病毒传播过程,使用SI病毒传播模型建模；针对具有一般性拓扑结构的网络,使用BFS策略构造扩散树；进一步,针对有关于嫌疑节点的先验知识的情形,构造两个基于谣言向心性的MAP估计器识别计算机病毒源。此外,介绍关于多样本观察知识情形下和SIR/SIS模型下病毒源识别的一些工作。仿真实验结果表明,联合考虑BFS扩散树的感染概率和谣言向心性的MAP源估计器的检测性能优于仅考虑谣言向心性的MAP估计器,并且随着嫌疑节点数目的增多检测性能下降、随着嫌疑节点变得更加分散检测性能上升。
[Abstract]:......
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TP393.08

【共引文献】