社会网络中影响最大化问题的研究

发布时间：2017-06-22 12:02

  本文关键词：社会网络中影响最大化问题的研究，由笔耕文化传播整理发布。

【摘要】：社会网络相关研究领域的一个关键问题就是影响最大化问题。影响最大化问题旨在通过算法发现社会网络中最有影响力的节点集合,广泛应用于市场营销、广告发布、舆情预警等场景,具有极高的研究意义和应用价值。由于影响最大化问题本身的NP-Hard复杂度,决定了这是一个优化问题,寻找与最优解有高近似比的快速求解算法和使算法实用化是主要的两个研究方向。本文作者对影响最大化问题做了相关研究,提出了自己的算法,主要研究成果及贡献如下:对多因素组合的影响最大化问题进行了研究。通过向传统影响最大化问题加入地理位置约束和时间约束来解决现实生活中对某特定区域特定时间段最大化影响的问题。提出朴素的基于贪心的Multi Factor-Greedy算法和基于MIA模型的动态规划TG-IM算法。通过一系列实验证明,算法在保证运行时间复杂度不增高的情况下成功解决了多因素组合的影响最大化问题。对基于MapReduce模型的并行影响最大化问题做了研究。通过分析影响最大化问题的可并行性,发掘层次依赖关系,解耦合,提出了一种基于MapReduce的MP-IM算法,加速问题求解。实验结果证明,该并行算法极大提升了影响力计算过程的效率,大大减少用户得到种子集合S的等待时间且具有良好的可扩展性。将MapReduce模型应用于解决多因素组合的影响最大化问题。由于TG-IM算法不能直接用于并行计算,本文提出了应用新模型并行求解多因素组合影响最大化问题的MPTG-IM算法。通过实验证明了算法的有效性和高效性,为解决可应用的影响最大化问题铺平了道路。
【关键词】：社会网络 影响最大化 多因素 并行
【学位授予单位】：黑龙江大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP393.09
【目录】：

• 中文摘要4-5
• Abstract5-10
• 第1章 绪论10-21
• 1.1 社会网络研究概述10-14
• 1.2 社会网络影响最大化问题14-18
• 1.2.1 研究意义14-15
• 1.2.2 算法度量标准15-17
• 1.2.3 面临的挑战17-18
• 1.3 本文主要研究内容18-19
• 1.4 本文的组织安排19-21
• 第2章 相关研究21-34
• 2.1 社会网络影响最大化问题基本定义21-22
• 2.2 影响传播模型22-25
• 2.2.1 独立级联模型22-23
• 2.2.2 线性阈值模型23-24
• 2.2.3 其它影响传播模型24-25
• 2.3 影响最大化问题求解算法25-31
• 2.3.1 贪心算法25-28
• 2.3.2 启发式算法28-31
• 2.4 影响最大化问题的延伸31-33
• 2.5 本章小结33-34
• 第3章 多因素组合的影响最大化算法34-51
• 3.1 引言34-36
• 3.2 算法设计36-42
• 3.2.1 问题定义36-37
• 3.2.2 MultiFactor-Greedy算法37-39
• 3.2.3 TG-IM算法39-42
• 3.3 实验与分析42-50
• 3.3.1 实验设置42-43
• 3.3.2 算法精度分析43-45
• 3.3.3 算法时间分析45-47
• 3.3.4 参数评估47-50
• 3.4 本章小结50-51
• 第4章 基于MapReduce模型的并行影响最大化算法51-64
• 4.1 背景理论51-54
• 4.1.1 影响最大化问题的并行性51-52
• 4.1.2 MapReduce模型和相关框架52-54
• 4.2 算法设计54-60
• 4.2.1 问题定义54-56
• 4.2.2 MP-IM算法56-60
• 4.3 实验与分析60-63
• 4.3.1 实验设置60-61
• 4.3.2 算法精度分析61-62
• 4.3.3 算法时间分析62-63
• 4.4 本章小结63-64
• 第5章 并行的多因素组合影响最大化算法64-71
• 5.1 引言64-65
• 5.2 算法设计65-67
• 5.2.1 问题定义65
• 5.2.2 MPTG-IM算法65-67
• 5.3 实验与分析67-70
• 5.3.1 实验设置67
• 5.3.2 实验结果67-70
• 5.4 本章小结70-71
• 结论71-72
• 参考文献72-79
• 致谢79

【相似文献】

中国硕士学位论文全文数据库 前7条

1 张巍;基于社会网的影响传播技术研究[D];黑龙江大学;2015年

2 陈雪峰;网络中影响力传播的最大化[D];电子科技大学;2015年

3 耿灵;基于EPC网络的社会影响力最大化问题[D];上海交通大学;2015年

4 尚兴;社会网络中影响力最大化问题的研究[D];南京大学;2013年

5 吕文渊;面向主题耦合的影响力最大化研究[D];云南大学;2016年

6 杨智博;社会网络中影响最大化问题的研究[D];黑龙江大学;2016年

7 杨鸿超;社会网络营销中基于成本控制的影响最大化问题研究[D];南京大学;2013年

  本文关键词：社会网络中影响最大化问题的研究，由笔耕文化传播整理发布。

，

本文编号：471707