基于和声搜索的影响力最大化算法研究

发布时间：2023-10-04 00:01

　　自从影响力最大化问题提出以来,就引起了很多学者的研究,提出了各式各样的算法来解决这一问题。其中,尤以贪心算法最为常见。然而,由于贪心及其改进算法的运算复杂度较高,即不适宜在大型网络上运行,也不能满足人们对时间的要求;而以度为基础的一些算法虽然运行速度较快,但结果却不能得到有效的保证。启发式算法在各种复杂问题的优化上都可以取得不错的效果,本文使用基于和声搜索的启发式算法来解决影响力最大化问题。和声搜索算法是一种模拟音乐的创作过程而形成的启发式算法,相比其他的启发式算法,具有收敛速度快、效果好、适应性强等优点。但直接将和声搜索算法应用到影响力最大化问题上,发现其存在两方面的不足:一方面,因为和声搜索算法需要对每次产生的新解进行评估来决定优化的方向,而传统的评估方式都是通过模拟传播来完成,所以每一次的评估都要耗费大量的时间;另一方面,由于节点数目众多,和声搜索算法在影响力最大化问题上的优化速度过慢,需要大量的迭代才能生成不错的解,这又加剧了运行速度过慢的问题。本文针对这两方面的问题对和声搜索算法进行了改进。针对第一个问题,通过计算解的邻居节点的激活期望来作为效果评估的指标。由于原本的评估方式...

【文章页数】：60 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 研究背景
    1.2 研究现状
    1.3 主要研究工作和内容安排
    1.4 本章小结
第二章 相关知识介绍
    2.1 复杂网络相关知识
    2.2 影响力最大化相关知识
    2.3 影响力传播的主要模型
        2.3.1 线性阈值模型
        2.3.2 独立级联模型
        2.3.3 权重级联模型
        2.3.4 其他的一些模型
    2.4 影响力最大化问题的相关算法
        2.4.1 贪心算法
        2.4.2 CELF算法
        2.4.3 最大度算法
        2.4.4 SCG算法
        2.4.5 其他算法
    2.5 本章小结
第三章 基于和声搜索的影响力最大化算法设计
    3.1 和声搜索算法简介
        3.1.1 和声搜索算法步骤
        3.1.2 和声搜索算法分析
    3.2 和声搜索算法应用到影响力最大化问题
        3.2.1 和声搜索应用到影响力最大化问题
        3.2.2 算法的复杂性分析
    3.3 和声搜索算法的改进
        3.3.1 HM大小
        3.3.2 阶梯增长的HMCR
        3.3.3 按度排序的解空间
        3.3.4 BW的调整策略
    3.4 评估方式
        3.4.1 EDV在IC模型
        3.4.2 EDV在LT模型和WC模型
    3.5 HSEDV算法模型
    3.6 HSEDV算法分析
    3.7 本章小结
第四章 实验以及结果分析
    4.1 实验数据及环境
        4.1.1 实验环境
        4.1.2 实验数据
    4.2 HS参数选择及实验
        4.2.1 HS优化实验
        4.2.2 HM大小的影响
    4.3 原始网络实验
        4.3.1 人类蛋白质网络(HumanProtein(Vidal))
        4.3.2 U.RoviraiVirgili邮件交往
        4.3.3 OpenFlight航线网络
        4.3.4 Digg网站信息回复图
    4.4 本章小结
第五章 总结与展望
    5.1 本文结论
    5.2 后续研究进展
参考文献
致谢



本文编号：3850912