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

发布时间：2017-10-30 21:19

  本文关键词：基于群体智能优化的社会网络影响最大化研究

  更多相关文章： 影响最大化 群体智能优化 粒子群优化 进化算法 社会网络分析

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

• 摘要5-6
• ABSTRACT6-10
• 符号对照表10-11
• 缩略语对照表11-14
• 第一章 绪论14-20
• 1.1 研究背景和意义14-15
• 1.2 国内外研究现状15-16
• 1.3 本文主要的研究内容16-17
• 1.4 本文章节安排17-20
• 第二章 影响最大化相关概念及算法20-34
• 2.1 社会网络20-23
• 2.1.1 社会网络的基本概念和表示20-21
• 2.1.2 社会网络的特性21-23
• 2.2 信息传播模型23-26
• 2.2.1 独立级联模型24
• 2.2.2 权重级联模型24-25
• 2.2.3 线性阈值模型25-26
• 2.3 影响最大化问题26
• 2.4 影响最大化相关算法26-33
• 2.4.1 基于网络特性的启发式方法26-29
• 2.4.2 贪婪方法及其改进方法29-31
• 2.4.3 基于目标函数优化的方法31-33
• 2.5 本章小结33-34
• 第三章 基于离散粒子群优化的影响最大化算法34-54
• 3.1 引言34
• 3.2 粒子群优化34-36
• 3.3 基于离散粒子群优化的影响最大化算法36-42
• 3.3.1 算法框架36
• 3.3.2 编码方式36-37
• 3.3.3 目标函数37-38
• 3.3.4 基于度中心性的启发式初始化方法38-39
• 3.3.5 位置和速度迭代算子39-41
• 3.3.6 局部搜索算子41-42
• 3.3.7 算法时间复杂度分析42
• 3.4 实验分析42-52
• 3.4.1 实验设置42-43
• 3.4.2 人工网络实验43-45
• 3.4.3 真实网络实验45-51
• 3.4.4 算法参数影响分析51-52
• 3.5 本章小结52-54
• 第四章 基于进化多目标优化的预算影响最大化算法54-66
• 4.1 引言54
• 4.2 进化多目标优化54-56
• 4.2.1 多目标优化的相关概念54-55
• 4.2.2 进化多目标优化算法55-56
• 4.3 预算影响最大化问题56-57
• 4.4 基于进化多目标优化的预算影响最大化算法57-60
• 4.4.1 算法框架57
• 4.4.2 编码方式和种群初始化57-58
• 4.4.3 非支配排序、拥挤度距离计算与个体选择58-59
• 4.4.4 交叉和变异算子59-60
• 4.4.5 算法时间复杂度分析60
• 4.5 实验分析60-64
• 4.5.1 实验设置61
• 4.5.2 实验结果评价指标61
• 4.5.3 实验结果分析61-64
• 4.6 本章小结64-66
• 第五章 总结与展望66-68
• 5.1 总结66-67
• 5.2 展望67-68
• 参考文献68-74
• 致谢74-76
• 作者简介76-77

【参考文献】

中国期刊全文数据库 前1条

1 俞靓亮;王万良;介婧;;基于混合粒子群优化算法的旅行商问题求解[J];计算机工程;2010年11期

，

本文编号：1119370