基于群体智能优化的社会网络影响最大化研究

摘要

随着各种在线社交平台的蓬勃发展，它们已经逐渐成为社会成员进行信息分享和传播的重要媒介。近年来，越来越多的企业和商家选择了各种线上社交网络进行产品和服务的推广，而这种利用社会关系进行“口口相传”的营销方式往往能够以较低的成本而带来巨大的利润。影响最大化问题旨在挖掘出社会网络中具有影响力的群体作为信息源，通过它们的影响力使得网络中的信息达到最大范围的传播。影响最大化是社会网络中信息传播研究领域的核心问题，它具有广泛的应用场景，比如广告投放、市场营销、水质监测和舆情控制等，因此具有重要的研究价值和社会意义。
　　在影响最大化问题中，节点组合的选择策略对应的准确度和运行效率是需要考虑的两个重要问题，如何从社会网络中高效地挖掘出目标组合是解决影响最大化问题的首要目标。在已有的解决影响最大化问题的算法中，贪婪算法具有较高的准确率，但是其运行效率较为低下，不能被用于求解大规模社会网络的影响最大化问题。相反，一些启发式的方法具有很高的运行效率，然而这些算法往往存在准确率不高、算法不稳定等问题。
　　针对上述影响最大化研究中存在的问题，本文从以下几个方面对社会网络影响最大化问题进行了研究：
　　在社会网络中计算节点或者节点集合的影响传播范围被证明是一种＃P难（sharp-Phard）问题，传统的影响最大化算法均采用计算复杂度极高的蒙特卡洛模拟来获得。本文通过深入分析社会网络的传播特性，针对独立级联模型和权重级联模型构造了一种局部影响力评估方程来近似计算节点的影响传播范围。在此基础上，我们将社会网络影响最大化问题建模为一种目标函数的优化问题，并提出了一种基于离散形式的粒子群优化算法。在提出的算法中，我们针对问题的特性设计了基于度中心性的初始化方法和基于邻域的局部搜索算子，从而在很大程度上加速了算法的收敛，提高了算法的运行效率。
　　此外，我们针对之前影响最大化的研究中没有考虑节点选择代价的问题，通过引入节点选择代价的概念提出了一种预算影响最大化模型。为了能以较低的选择代价来达到社会网络的影响最大化，我们将预算影响最大化问题作为一种多目标优化问题来解决，并提出了一种进化多目标优化算法。实验证明，该算法所选的初始激活节点集合在保持最大影响范围的同时，还具有较低的选择代价。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1 研究背景和意义

1.2 国内外研究现状

1.3 本文主要的研究内容

1.4 本文章节安排

第二章 影响最大化相关概念及算法

2.1 社会网络

2.2 信息传播模型

2.3 影响最大化问题

2.4 影响最大化相关算法

2.5 本章小结

第三章 基于离散粒子群优化的影响最大化算法

3.1 引言

3.2 粒子群优化

3.3 基于离散粒子群优化的影响最大化算法

3.4 实验分析

3.5 本章小结

第四章 基于进化多目标优化的预算影响最大化算法

4.1 引言

4.2 进化多目标优化

4.3 预算影响最大化问题

4.4 基于进化多目标优化的预算影响最大化算法

4.5 实验分析

4.6 本章小结

第五章 总结与展望

5.1 总结

5.2 展望

参考文献

致谢

作者简介