论文部分内容阅读
长期以来,传染病一直是人类社会面临的巨大挑战。近年来,全球爆发了多起传染病事件,对人类的财产和健康造成了巨大的损失。当前传染病的研究主要在于对其进行预防和控制。在资金和疫苗有限的情况下,无法对接触网络中的所有人进行免疫。因此,高效地选择网络中部分具有较高影响力的人进行提前免疫,切断传染病在人群中传播的路径,成为预防传染病大规模爆发的重要手段。而随着技术的发展,尤其是各类移动终端设备的普及,数据的获取比以往任何一个时期更加容易,因此现有的传染病免疫算法需要加以改进,以获取更好的免疫效果。本文首先介绍了社会网络图的基本概念,包括网络图的各种性质和定义,并在此基础上介绍了用于传染病研究的传播模型,包括SIR传播模型等,分析了模型存在的现实意义。接着本文对常用的传染病免疫方法进行了研究,包括随机免疫、熟人免疫和目标免疫方法,分析了现有算法各自的优缺点。本文在此基础上提出了两种改进算法:一方面,为了解决现有算法中存在的未考虑传播概率、影响力节点聚集等问题,提出了基于权值覆盖的免疫算法(WCBA);另一方面,根据影响力节点不同的定义,应用社区划分思想,提出了基于社区划分的免疫算法(CDBA),挖掘网络中的“奇异”节点,并根据挖掘的结果对现有算法选择出的影响力节点进行了分析,增加了结果的准确性和完整性。本文在多个数据集上进行了算法测试与分析。实验结果表明:1)在本文提出的基于权值的算法中,计算有效路径的算法取得了较好的效果,而基于k步范围内权值和覆盖的算法也表现出了比现有的启发式算法更优的效果,并且算法的运行时间在可以接受的范围之内;2)在基于社区划分的免疫算法中,算法选择出的“奇异”节点比现有启发式算法选择出的节点更为重要;3)在基于社区划分的免疫算法中选择出来的节点的社区属性,例如节点连接的社区个数和节点连接的社区规模,对于现有的启发式算法的结果有重要的影响。在节点度相同的情况下,节点的影响范围和社区个数,社区规模成正相关关系。