社交活动网络中的影响力最大化方法研究

摘要

随着社交网络的流行，找到一组最具影响力的用户（或节点）以便触发最大的影响范围是很有意义的。例如，公司可以通过提供免费样品/折扣给这些影响力最大的用户，从而借助“口碑”效应来触发更大范围的宣传和购买，最终使该产品在网络中得以大规模普及。这类任务通常被建模为影响力最大化问题，并在过去十多年得到了广泛的研究。但是，考虑到社交网络中的用户可以参加各种各样的在线活动，例如，给产品做评价，加入讨论组等，因此影响力通过在线活动传播的情况变得更加有研究意义。
　　本文主要研究将用户活动考虑在内的影响力最大化问题。包含用户活动的社交网络可以被称为社交活动网络，本文首先将传统的影响力传播模型扩展至其中，从而引出社交活动网络中的影响力最大化问题。基于随机游走理论，本文定义了影响力中心性指标来近似节点集合的影响力，并提出了基于蒙特卡洛的近似算法，实现了对影响力中心性的快速计算。根据子模函数的性质，本文进一步提出了贪心算法和若干优化技术，实现了对影响力最大化问题的快速求解。最后我们利用实际的社交评分数据验证了算法的有效性、效率和通用性。可以看到本文所提出的算法在运行速度上明显优于当前已有的最优算法，且在不同的影响力传播模型与异构网络中都有很好的效果。

目录

声明

摘要

插图索引

第一章 绪论

1．1 研究背景

1．1．1 影响力传播研究的应用

1．1．2 影响力传播模型

1．1．3 传播模型参数学习

1．1．4 影响力最大化

1．2 本文主要研究工作和贡献

1．3 本文组织结构

第二章 影响力最大化和随机游走相关研究

2．1 基于网络拓扑的中心性指标

2．1．1 度中心性

2．1．2 接近中心性

2．1．3 中介中心性

2．1．4 PageRank中心性

2．2 影响力最大化算法

2．2．1 贪心算法

2．2．2 启发式算法

2．2．3 反向蒙特卡洛算法

2．3 随机游走

2．3．1 随机游走的应用

2．3．2 超图上的随机游走

2．4 本文的研究意义

2．5 本章小结

第三章 社交活动网络中的影响力最大化

3．1 问题描述

3．1．1 社交活动网络模型

3．1．2 社交活动网络中的影响力最大化问题定义

3．2 考虑用户活动的影响力最大化方法

3．2．1 考虑用户活动的随机游走

3．2．2 影响力中心性

3．2．3 中心性计算

3．2．4 中心性最大化

3．3 本章小结

第四章 实验

4．1 数据集

4．2 考虑用户活动对影响力最大化的提升

4．3 算法的运行效率及准确性

4．4 模型通用性

4．4．1 线性阈值模型

4．4．2 多种用户和活动类型

4．5 模型可扩展性

4．6 本章小结

5．1 总结

5．2 展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果