基于Memetic算法和Spark分布式并行计算的社交网络影响最大化研究

摘要

随着互联网技术的发展和大数据时代的到来，社交网络已逐渐成为人们进行信息交互和分享的主要媒介。近年来，越来越多的商家和企业开始利用社交网络进行产品推广和宣传。这种新型的营销模式往往能够以更低的成本带来更好的营销效果。影响最大化问题旨在从社交网络中挖掘出一定数量的有影响力的个体并作为信息的传播源，使信息在整个网络中的影响传播范围达到最大。除了在社交网络信息传播研究领域之外，影响最大化问题还被应用于舆论传播监控和传染病防疫等领域。 近年来，越来越多的学者投身到影响最大化问题的研究当中，并提出了许多解决方法。这些算法大致可以分为以下三类：基于爬山机制的贪婪算法及其改进算法；基于社交网络特性的启发式算法；基于目标函数的优化算法。其中，贪婪算法及其改进算法具有较高的准确率，但是其运行效率较低，不适合求解大规模社交网络的影响最大化问题。相反，启发式算法具有很高的运行效率，但是在准确度和稳定性方面这些算法表现欠佳。针对上述影响最大化问题及现有算法存在的不足，本文的主要从以下几个方面对社交网络影响最大化问题进行了研究： 本文创新性地提出了一种基于社区划分和Memetic算法的社交网络影响最大化算法。该算法充分利用社交网络的社区结构特性，通过对重要社区和候选节点的筛选，有效地缩小了初始激活节点的选择空间，提升了算法的运行效率。同时，该算法利用Memetic算法对二级邻域影响传播函数进行优化。为了有效地解决初始激活节点之间影响传播范围的重叠问题，该算法提出了节点度相似性的概念，并将此策略运用到Memetic算法的初始化、交叉、变异和局部搜索操作中。通过在真实网络中的对比实验可以证明，该算法不仅可以有效地解决社交网络影响最大化问题，而且具有较好的运行效率。 为了应对超大规模社交网络带来的挑战，本文在Spark计算平台的基础上提出了一种用于解决社交网络影响最大化问题的分布式并行算法框架。该算法利用Spark GraphX分布式并行图计算框架对上文提出的算法进行了实现与改进。该分布式并行算法借鉴并行遗传算法的思路，在算法中设计了迁移算子，这一创新性的改进不仅有效地避免了子种群的未成熟收敛，而且提升了算法的准确度和运行效率。通过在超大规模网络上的实验，证明了该分布式并行算法能够在可以接受的时间范围内有效地解决超大规模社交网络的影响最大化问题，为大数据时代下对超大规模社交网络进行研究提供了借鉴。

目录

第一个书签之前

摘要

ABSTRACT

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪论

1.2研究现状

1.3本文研究内容

1.4本文章节安排

第二章 相关概念及理论知识

2.2信息传播模型

2.2.1独立级联模型

2.2.3线性阈值模型

2.3影响最大化问题及相关算法

2.3.2相关算法

2.4本章小结

第三章 基于社区划分和 Memetic 算法的 CMA 社交网络影响最大化算法

3.3社区划分

3.3.1社区划分的意义

3.3.2社区划分算法

3.4选出候选节点

3.5一种用于社交网络影响最大化问题的 Memetic 算法

3.5.2MIM 算法框架

3.5.3编码方式和种群初始化

3.5.4遗传操作

3.5.5局部搜索算子

3.6实验仿真与结果分析

3.6.2实验结果分析

3.6.3算法参数分析

3.7本章小结

第四章 基于 Spark 分布式并行计算的 DP-CMA 社交网络影响最大化算法

4.2.1Spark 简介

4.2.2GraphX 图计算框架

4.3基于 Spark 分布式并行计算的 DP-CMA 社交网络影响最大化算法

4.3.1算法基础

4.3.2算法框架

4.3.3编码方式和种群初始化

4.3.4适应度计算

4.3.5遗传操作和局部搜索算子

4.4实验仿真与结果分析

4.4.2实验结果分析

4.5本章小结

第五章 总结与展望

5.2展望

参考文献

致谢

作者简介