基于智能优化的影响力最大化算法研究

• 作 者: 徐涛
• 出 处: 安徽大学
• 发表日期: 2020年07期
• 关键词: 社会网络 影响力最大化 蒙特卡洛模拟 智能优化

在过去互联网信息技术在各行各业迅速普及的十几年中,各种社交即时通信软件应用扮演着重要的生活服务角色,这些通信服务已涉及到人们生活的各个方面。人们之间的互动和沟通变得越来越方便和密集,在线社交网络也逐渐演变成信息发布传播的工具和载体。在线社交网络的盛行吸引了社会各个群体对信息传播的普遍重视,因为一条信息可以通过网络朋友之间的社交关系迅速传遍整个社交圈。和传统信息传播媒介不同的是,在线社交网络这种信息传播载体的优势在于其不受时间空间限制和极广的影响范围。因此,社交网络中的信息扩散吸引了计算机科学、物理学、流行病学等多个领域的广泛研究。目前,社会复杂网络的分析在学术界是不断追踪研究的热点,其中社会网络影响力最大化是其研究领域的一个重要分支。影响力最大化问题是在复杂社会网络中选择一小部分用户,这些用户在具体传播模型下拥有最大的影响扩散范围。基于贪心的蒙特卡洛模拟方法在理论上保证近乎最优的解决方案,但算法运行效率很低。虽然已经开发出许多启发式方法,但都大大降低了解决方案的质量。目前影响力最大化问题研究的挑战就是如何在复杂大型的社会网络更好地平衡影响传播范围和算法运行时间。针对此问题,本文研究重点基于种子节点候选池的构建和智能优化算法相结合思路的解决影响力最大化问题。本文主要工作包括:1、本文首先系统地阐述影响力最大化问题的定义以及与其相关理论概念,调研国内外有关影响力最大化的研究工作并且分析目前研究工作存在的不足之处。剖析部分具有代表性的影响力最大化算法。2、经过大量关于影响力最大化问题的调研,认识到该问题本质上可转化为离散组合优化问题。启发式智能优化算法在处理复杂优化问题具有明显的优势。因此,本文提出基于和声搜索的影响力最大化算法(HSIM)。该算法利用节点结构相似性得分较大的节点初始化和声记忆库,并采用二阶平均度启发式策略构造候选种子节点集加速算法寻找种子节点。在四个学术合作网络数据集的实验表明,HSIM算法运行效率具有高效性并且挖掘出的种子节点传播影响范围排在第一梯队。3、当前大部分算法运行时间慢是因为节点集的影响力计算采用数万次的蒙特卡洛模拟。本文提出局部概率解节点集影响力评价策略近似代替蒙特卡洛模拟并且提出基于免疫遗传的影响力最大化算法(IGIM)。局部概率解节点集影响力评价策略只需一次精确计算,有效地避免节点集数万次的影响传播模拟计算。通过在四个学术领域合作网络的数据集上,表明所提算法在求解影响力最大化问题的高效性和准确度。在影响力传播范围上,要和当前表现最好的CELF算法有极其相近的性能,而且运行时间比CELF算法有大约5个数量级的降低。