在线社交网络中面向目标用户的最小节点问题

论文摘要

随着在线社交网络的蓬勃发展,通过大数据分析用户的行为属性,面向目标用户建立相应标签的精准营销和个性化推荐越来越具有应用价值。本文主要围绕面向目标用户的最小节点问题进行研究。本文采用用户画像区分目标用户与非目标用户,首先针对单一传播环境下面向目标用户的最小节点问题（NLC-TU）展开研究。NLC-TU问题旨在寻求最小的初始种子节点集,使得初始种子节点集的信息传播范围可以覆盖目标用户群体中预期数量的用户。考虑社交网络中节点传播能力的不同,本文提出了受限传播模型（LD-IC）,证明了在该模型下NLC-TU问题是NP-hard问题,并且NLC-TU问题的信息传播函数在LD-IC模型下具有单调性和子模性。本文提出贪心算法来解决这个问题并且分析了贪心算法的精度保证。然而贪心算法耗时长,难以应用于大型社交网络。考虑到在LD-IC模型下节点的局部影响力可以近似表示全局影响力,面向目标节点的局部影响力启发式算法（TU-LIH）被提出。在四个真实社交网络上的实验证明了我们提出的算法高效且具有可拓展性。随后,考虑现实网络中信息传播的复杂性,本文在NLC-TU问题的基础上针对竞争环境下面向目标用户的最小节点问题（CLC-TU）展开研究。假设网络中的用户可以接收并且传播多种信息但是最后只会被其中一种信息影响,本文提出了竞争受限传播模型（LD-CIC）,证明CIC-TU问题在LD-CIC模型下是NP-hard问题,并且该问题的信息传播函数在LD-CIC模型下具有单调性和子模性。本文提出了改进的竞争贪心算法和面向目标用户的竞争影响力算法（TU-CIH）来解决CIC-TU问题,并且通过在不同的数据集上的实验,验证了本文提出的算法的可行性和高效性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
•   1.1 研究背景和意义
•   1.2 研究内容
•   1.3 论文的主要内容与章节安排
• 第二章 国内外相关研究
•   2.1 引言
•   2.2 相关理论
•     2.2.1 在线社交网络
•     2.2.2 传播模型
•     2.2.3 相关算法
•     2.2.4 目标用户
•   2.3 单一传播环境下最小节点问题的研究
•   2.4 竞争环境下最小节点问题的研究
•   2.5 本章小结
• 第三章 单一传播环境下面向目标用户的最小节点问题
•   3.1 问题描述
•     3.1.1 用户画像
•     3.1.2 受限传播模型（LD-IC）
•     3.1.3 NLC-TU问题
•   3.2 受限传播模型下的函数性质
•     3.2.1 NP-hard
•     3.2.2 子模性
•     3.2.3 单调性
•   3.3 算法设计
•     3.3.1 Greedy算法
•     3.3.2 针对目标节点的局部影响力算法
•   3.4 实验验证
•     3.4.1 实验数据
•     3.4.2 实验参数
•     3.4.3 比较算法
•     3.4.4 实验结果
•   3.5 本章小结
• 第四章 竞争环境下面向目标用户的最小节点问题
•   4.1 问题描述
•     4.1.1 受限竞争传播模型（LD-CIC）
•     4.1.2 CLC-TU问题
•   4.2 受限竞争传播模型下函数性质
•     4.2.1 NP-hard
•     4.2.2 单调性
•     4.2.3 子模性
•   4.3 算法设计
•     4.3.1 Greedy算法
•     4.3.2 面向目标节点的竞争影响力算法
•   4.4 实验验证
•     4.4.1 实验数据
•     4.4.2 实验参数
•     4.4.3 比较算法
•     4.4.4 实验结果
•   4.5 本章小结
• 第五章 结束语
•   5.1 主要工作与创新点
•   5.2 后续研究工作
• 参考文献
• 致谢
• 攻读硕士学位期间已发表或录用的论文

文章来源

类型: 硕士论文

作者: 陈梦仪

导师: 潘理

关键词: 最小节点问题,用户画像,在线社交网络,贪心算法

来源: 上海交通大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 上海交通大学

分类号: TP301.6;O157.5

DOI: 10.27307/d.cnki.gsjtu.2019.001561

总页数: 69

文件大小: 3022K

下载量: 7