基于成本效益的影响最大化算法分析与设计

发布时间：2017-08-26 05:41

  本文关键词：基于成本效益的影响最大化算法分析与设计

  更多相关文章： 社交网络 影响最大化 成本效益 概率覆盖范围 子模函数特性

【摘要】：随着近些年互联网的飞速发展,社交网络应运而生,例如国外的Facebook、Twitter以及国内的人人网和新浪微博等等,这些在线社交网络给人们提供了一种全新的社交模式,并且真实的反映了人们现实生活中的社会关系。同时依托社交网络产生了一种全新的营销模式——“病毒营销”,它依靠人与人之间的口碑效应使信息在网络中扩散,达到产品推广的目的。针对这种特定的营销模式,学术界也进行了许多研究,关注点在如何选择最初的用户作为信息源,通过口碑传播使得被影响的受众最多,Domingos和Richardson首次把该问题形式化为一个算法问题引入到社会网络领域进行研究,也即影响最大化问题。然而对传统影响最大化问题的研究在选择初始信息源时忽略了用户之间的差异性,没有考虑到选择用户作为信息源所要花费的成本,而实际营销中的推广活动都有预算的约束,选择不同的用户需要不同的花费,如何在这样的条件下获得最好的推广效果需要对问题重新考虑和定义。基于以上考虑,本文给出了对用户成本的定义方法,并提出了基于成本效益的影响最大化问题。针对这个问题,本文综合考虑网络拓扑和传播模型的特点,提出了基于概率覆盖范围的启发式算法(ProbCover Algorithm),并在此基础上利用子模函数特性和惰性计算技术提出基于概率覆盖范围的惰性节点选择算法(ProbCoverLF Algorithm)。在本文研究成果的基础上,设计实现了基于成本效益的影响最大化原型系统。本文在三个数据集和独立级联模型上进行了实验,并且分别采用了固定概率和变概率两种方式的独立级联模型,实验结果表明：(a)在影响范围方面,本文所提出的算法优于传统的启发式算法,并且在变概率条件下的独立级联模型中优势尤其明显；(b)在时间效率方面,本文所提出的算法虽然运行时间比传统的启发式算法要长,但仍在可以接受的范围之内。综合影响范围和时间效率两方面,证明了本文算法的有效性。
【关键词】：社交网络 影响最大化 成本效益 概率覆盖范围 子模函数特性
【学位授予单位】：东南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP301.6;TP393.09
【目录】：

• 摘要4-5
• ABSTRACT5-8
• 第一章 绪论8-17
• 1.1 研究背景与意义8-9
• 1.2 国内外研究现状9-14
• 1.2.1 原始影响最大化问题研究现状10-12
• 1.2.2 基于成本效益的影响最大化问题研究现状12-13
• 1.2.3 现状总结13-14
• 1.3 研究目标及内容14-15
• 1.4 论文组织结构15-17
• 第二章 相关理论知识17-23
• 2.1 社会网络17-18
• 2.2 影响力传播模型18-20
• 2.2.1 独立级联模型18-19
• 2.2.2 线性阈值模型19-20
• 2.2.3 其他传播模型20
• 2.3 基于成本效益的影响最大化问题20-22
• 2.3.1 形式化定义20-21
• 2.3.2 评价指标21
• 2.3.3 问题难度21-22
• 2.4 本章小结22-23
• 第三章 概率覆盖算法23-31
• 3.1 节点成本建模23-26
• 3.1.1 成本的意义23-24
• 3.1.2 成本的定义24-26
• 3.2 节点概率覆盖范围26-29
• 3.2.1 节点影响力分析26-27
• 3.2.2 算法思想27
• 3.2.3 算法描述27-29
• 3.3 选择初始节点集合29-30
• 3.4 本章小结30-31
• 第四章 利用子模函数特性的惰性节点选择算法31-36
• 4.1 子模函数特性31-32
• 4.2 惰性节点选择算法32-35
• 4.3 本章小结35-36
• 第五章 实验设计与分析36-48
• 5.1 实验环境36
• 5.2 实验数据集36-38
• 5.3 实验设计38-39
• 5.4 实验结果及分析39-47
• 5.4.1 固定概率的IC模型实验结果与分析40-45
• 5.4.2 变概率下的IC模型实验结果与分析45-47
• 5.4.3 实验结果小结47
• 5.5 本章小结47-48
• 第六章 系统实现48-54
• 6.1 原型系统整体架构48-49
• 6.2 原型系统实现49-53
• 6.2.1 开发环境49
• 6.2.2 系统实现49-53
• 6.3 本章小结53-54
• 第七章 总结与展望54-56
• 7.1 工作总结54
• 7.2 研究展望54-56
• 致谢56-57
• 参考文献57-60
• 作者简介60

【相似文献】

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

1 赵钊;基于成本效益的影响最大化算法分析与设计[D];东南大学;2015年

，

本文编号：740016