面向社交网络中的影响力最大化问题的高效算法

摘要

社交网络中的影响力最大化问题在市场营销、舆情预警等方面都具有重要作用。给定一个社交网络图和特定的信息传播模型，影响力最大化问题是研究如何选取初始的种子节点使得最终被影响的节点数目最多的问题。在研究中最常用的传播模型有独立级联模型和线性阈值模型。无论选用哪种影响力传播模型，种子节点的影响力的计算都非常复杂。用蒙特卡洛法多次模拟信息传播过程取平均是研究中常用的计算影响力的方法。这是一个非常耗时的过程，当处理大规模的社交网络时代价过于昂贵，难以在算法中应用。贪心算法是影响力最大化问题中最经典的算法，但因为非常耗时难以应用于大规模的社交网络。近年来有很多应用于影响力最大化问题的元启发式算法，它们在实验中有非常出色的表现。Pareto优化子集选择算法(POSS算法)是其中之一。 本文将POSS算法应用于影响力最大化问题并设计了两个改进版本。动态变异算子具有更灵活的变异概率，能够更好地处理局部最优情况。作者设计了基于动态变异算子的Pareto优化子集选择算法(DM-POSS算法)，并从理论上证明了DM-POSS算法能得到影响力最大化问题的理论最优解。实验结果显示，DM-POSS算法提高了解的质量。交叉算子是遗传算法中另一个非常重要的算子。本文将交叉算子与POSS算法结合，设计了影响力最大化问题的Pareto优化算法(POIM算法)。实验显示POIM算法比POSS算法更快地找到更好的解。

目录

声明

摘要

第1章绪论

1．1 社交网络中的影响力最大化问题概述

1．2背景知识介绍

1．2．1．基本概念

1．2．2．研究现状

1．2．3． 影响力最大化问题面临的主要困难

1．3本文的主要工作

1．4本文的组织结构

1．5 本章小结

第2章面向社交网络中的影响力最大化问题的算法综述

2．1信息传播模型

2．1．1．信息传播的独立级联模型

2．1．2． 信息传播的线性阈值模型

2．1．3．独立级联模型下的影响力的近似公式

2．2贪心算法及其改进算法

2．2．1．贪心算法

2．2．2．CELF算法及其改进算法

2．2．3．独立级联模型下的混合贪心算法

2．2．4．贪心算法小结

2．3基于社交网络拓扑结构的启发式算法

2．3．1．基于中心性的选择策略

2．3．2．改进的基于度中心性的选择策略

2．3．3．启发式算法小结

2．4元启发式算法

2．4．1．模拟退火算法及其改进算法

2．4．2． 离散粒子群算法及其改进算法

2．4．3．文化基因算法

2．4．4．Pareto优化子集选择算法

2．4．5． 元启发式算法小结

2．5本章小结

第3章基于动态变异算子的Pareto优化子集选择算法

3．1 子模函数

3．2 Pareto优化子集选择算法介绍

3．3基于动态变异算子的Pareto优化子集选择算法

3．3．1．动态变异算子

3．3．2．重尾变异算子

3．3．3．基于动态变异算子的Pareto优化子集选择算法

3．3．4． 算法分析

3．4 实验

3．4．1．实验数据集

3．4．2．对比算法

3．4．3．实验设置

3．4．4． 参数设置

3．4．5．实验结果与分析

3．5 本章小结

第4章影响力最大化问题的Pareto优化算法

4．1 交叉算子

4．1．1．基本概念

4．1．2．单点交叉算子

4．2影响力最大化问题的Pareto优化算法

4．3 实验

4．3．1．实验数据

4．3．2．实验设置

4．3．3．参数设置

4．3．4．实验结果分析

4．4本章小结

第5章总结

5．1 工作总结

5．2未来的工作方向

参考文献

致谢

在读期间发表的学术论文与取得的研究成果