社交网络影响力最大化模型与计算方法研究

摘要

随着社交网络的快速发展与广泛应用，社交网络平台如Facebook，Wechat，Weibo带来了巨额的网络流量和用户数据，带动了社会化营销的研究工作。在社会化营销领域，影响力最大化是其一个重点研究方向。传统的研究关注于设计和优化社交网络中节点影响力的信息扩散模型，并改进相应算法来量化模型中节点的影响力值，这对社交网络研究起到了积极的推动作用。然而，企业利用社交网络进行产品营销时，通常面临多种现实因素的影响，如何解决多因素影响具有重要的研究价值。
　　本文以影响力最大化为主要思路来寻找种子用户进行产品信息传播，同时也考虑用户的兴趣偏好，即种子用户所能影响到的目标用户对该产品是感兴趣的;并且企业要控制营销成本，获得较大的边际收益。基于此，本文考虑信息扩散规模，用户兴趣偏好和企业预算等因素，将影响力最大化模型作为多目标优化问题，提出多目标影响最大化(MOIM)模型。为了解决影响力最大化的NP-hard难题，本文利用蒙特卡洛抽样来计算高影响力用户。接着提出一种基于分解策略的多目标进化算法(MOEA/D)的种子选择算法来组合优化种子，求解MOIM模型。
　　我们利用真实社交网络数据来验证模型与方法的性能。由于影响力计算过程比较耗时，时间复杂度较高，我们使用分布式框架MapReduce将该过程并行化来加速运算。实验表明，提出的模型可以生成适当的种子集并能够满足信息传播的不同目的。灵敏度分析证明，我们的模型在不同实际条件下具有鲁棒性。

目录

声明

致谢

摘要

第一章 绪论

1．1 研究背景与研究意义

1．2 国内外研究现状

1．2．1 影响力最大化

1．2．2 多目标优化算法

1．3 本文主要研究内容与贡献

1．4 本文组织结构

第二章 社交网络与多目标优化相关理论

2．1 社交网络及其特点

2．2 社交网络影响力的度量

2．2．1 基于中心性度量

2．2．2 PageRank

2．3 社交网络影响力传播模型

2．3．1 传染病模型

2．3．2 独立级联模型(ICM)

2．3．3 线性阈值模型(LTM)

2．4．1 影响力最大化问题

2．4．2 影响力最大化求解算法

2．5 多目标优化方法

2．5．1 多目标问题的定义

2．5．2 多目标优化模型

第三章 影响力最大化模型与求解算法

3．1 引例

3．2 影响力模型构建

3．2．1 信息扩散影响目标

3．2．2 用户兴趣偏好目标

3．2．3 企业预算目标

3．3 基于蒙特卡洛抽样的节点影响力计算

3．4．1 算法框架

3．4．2 种子节点选择算法

3．4．3 遗传算子

3．5 本章小结

第四章 并行化计算与实验分析

4．1 并行化计算的需求

4．2 基于Hadoop的计算框架

4．3 算法并行化设计

4．4 实验与分析

4．4．1 并行化实验

4．4．2 一般性实验结果

4．4．3 实验对比

4．4．4 敏感性分析

4．4．5 实验结论

第五章 总结与展望

5．1 总结

5．2 展望

参考文献

攻读硕士学位期间的学术活动及成果情况