时间敏感的社交网络影响力传播算法研究

发布时间：2022-05-08 13:36

　　随着移动互联网的飞速发展,在线社交网络已经成为了营销活动最有效的运营平台,进而催生出了“病毒营销”这一商业推广模式。“病毒营销”所面临的最大挑战便是如何从全体用户集合中选出k个用户组成“种子集合”去传播影响,从而使得最终被影响到的用户的期望数目最大化。上述问题就是经典的影响力传播最大化问题。基于上述背景,本文首先为社交网络中的影响力传播问题引入新的考量因素,一是差异化的用户耗费与收益,二是包含传播延迟和时限约束的时间限制,在时间敏感的传播模型下,构建了时间敏感的社交网络反馈收益计算问题。该问题的目的是在新的时间敏感影响力传播模型下,给定任意的结点集合S去传播影响,快速高效的计算最终所有激活结点的反馈收益和。本文证明了该问题在两种影响力传播模型下均是#P难的,并设计新的采样策略对最终的反馈收益函数进行快速高效的估计。随后对采样策略的等价性与近似性进行了理论分析,证明了采样策略的优异性质。其次,本文形式化地构建了时间敏感的社交网络反馈收益最大化问题。该问题的目的是在时限约束T和预算约束B下,寻找到最具性价比的用户集合去最大化地影响目标用户,从而使得最终所有受影响的用户的反馈收益和最大化。本... 

【文章页数】：95 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第1章 绪论
    1.1 社交网络影响力传播概述
    1.2 背景知识介绍
        1.2.1 基本概念
        1.2.2 研究现状
        1.2.3 研究趋势及研究难点
    1.3 本文的主要工作
        1.3.1 主要贡献与研究意义
        1.3.2 研究方法
    1.4 本文的组织结构
第2章 社交网络影响力传播相关研究
    2.1 影响力传播模型
        2.1.1 独立级联模型
        2.1.2 线性阈值模型
        2.1.3 引入相遇事件的影响力传播模型
    2.2 影响力传播最大化算法
        2.2.1 贪心算法及其改进
        2.2.2 启发式算法
        2.2.3 基于采样的近似算法
    2.3 团队组建问题与算法
        2.3.1 交流耗费最小化的团队组建算法
        2.3.2 影响力传播最大化的团队组建算法
    2.4 本章小结
第3章 时间敏感的社交网络反馈收益采样估计算法
    3.1 问题定义及计算复杂度
    3.2 影响力传播模型性质分析
    3.3 社交网络反馈收益采样估计算法
        3.3.1 采样算法框架设计
        3.3.2 IC-M模型下的采样算法
        3.3.3 LT-M模型下的采样算法
    3.4 采样算法性能分析
        3.4.1 等价性分析
        3.4.2 近似性分析
    3.5 本章小结
第4章 时间敏感的社交网络反馈收益最大化算法
    4.1 问题定义及计算复杂度
    4.2 社交网络反馈收益最大化算法
    4.3 反馈收益最大化算法近似度分析
    4.4 实验
        4.4.1 数据集描述
        4.4.2 实验参数设定
        4.4.3 性能评估准则
        4.4.4 实验结果分析
    4.5 本章小结
第5章 基于时间敏感社交网络影响力传播的事件组织者挖掘
    5.1 问题定义及计算复杂度
    5.2 朴素贪心算法
    5.3 双向算法
        5.3.1 反馈收益估计策略
        5.3.2 双向算法
    5.4 实验
        5.4.1 数据集描述
        5.4.2 实验参数设定
        5.4.3 性能评估准则
        5.4.4 实验结果分析
    5.5 本章小结
第6章 总结与展望
    6.1 论文总结
    6.2 研究展望
参考文献
致谢
在读期间发表的学术论文与取得的研究成果



本文编号：3651756