社交网络中基于位置的影响最大化问题分析与算法设计

摘要

影响最大化问题一直是社会网络研究中广受关注的热点问题，而在在线社交网站成为重要产品营销平台的网络时代，影响最大化问题的意义愈显突出。影响最大化问题源自于病毒式营销，可以描述为如何确定一定数量的初始用户，通过他们的口碑宣传，使得最终整个社会网络中接受产品或思想的用户数量达到最大。近年来，O2O商业模式开始崭露头角，O2O指对线下的服务进行线上的交易，它连接了线上的营销和线下的消费，正成为电子商务的一大发展趋势。然而在O2O环境下，由于用户线下消费环节的存在，传统的单一线上影响传播模型已经不能精准地描述用户接受产品的过程，而现有在线社交网站上的影响最大化问题的研究视角也都专注于线上的人际网络，O2O模式线上线下相结合的特征，要求我们将营销过程的线下环节和位置特征作为重要的内容纳入影响最大化问题之中。
　　本文针对O2O商业模式下的产品推广，以基于位置的社交网站LBSN为平台，进行基于位置的影响最大化问题研究，考虑到用户地理特征，在同时涉及到线上线下的口碑营销中，实现对初始种子用户的定位，以达到产品推广的效益最大。本文选择著名LBSN网站Foursquare作为数据源，获取其用户社交网络数据和用户历史签到数据，作为真实的数据基础。
　　本文首先对现有的影响传播模型进行改进，引入线下环节，提出了二阶段影响传播模型，可以很好地描述O2O环境下用户接受产品的过程;其次针对O2O模式下产品推广的位置因素，对基于位置的影响最大化这一新的问题进行了定义和描述;然后基于用户的历史位置访问信息，分析了用户移动行为的特征，提出了线下概率的计算方法，可以体现用户消费行为的位置偏好，用于传播模型和影响最大化问题之中;在此之上，本文结合二阶段影响传播模型的特征，综合考虑影响力传播的能力和广度，定义了启发式参数用以描述用户的影响力大小，基于此提出并实现了基于位置的影响最大化算法TPH算法，并通过不同设置下的分组实验验证了算法总体上具有较高的优势，其后针对TPH算法在特殊情况下的表现，分析用户被影响的难易程度，设计并实现了MR算法对其进行补充，并通过实验说明了算法的有效性。
　　本文设计和实现了Foursquare统一数据抓取系统，获取了用户社交网络数据和用户历史签到数据，并根据基于位置的影响最大化算法，采用真实数据作为输入，设计和实现了影响最大化原型系统。

目录

声明

摘要

第一章 绪论

1．1 研究背景

1．2 研究现状

1．3 研究目标与内容

1．4 本文的组织结构

第二章 相关理论工作

2．1 社会网络

2．2 影响传播模型

2．2．1 线性阈值模型

2．2．2 独立级联模型

2．2．3 其他传播模型

2．3 影响最大化问题

2．4 常见影响最大化算法

2．4．1 贪婪算法

2．4．2 CELF算法

2．4．3 度中心算法

2．4．4 度折扣算法

2．4．5 PageRank算法

2．5 LBSN

2．5．1 LBSN简介

2．5．2 基于位置的异构网络模型

2．5．3 LBSN相关研究

2．6 本章小结

第三章 LBSN真实数据获取与处理

3．1 数据源选择与介绍

3．2 数据获取

3．3 数据内容形式

3．4 数据处理

3．4．1 纽约签到处理

3．4．2 纽约用户处理

3．4．3 消费签到处理

3．4．4 数据集整理

3．5 数据分析

3．6 本章小结

第四章 基于位置的影响最大化问题

4．1 二阶段影响传播模型

4．1．1 建模基础

4．1．2 影响传播模型描述

4．2 基于位置的影响最大化问题

4．3 线下概率

4．3．1 用户移动模式分析

4．3．2 线下概率计算

4．4 本章小结

第五章 基于位置的影响最大化算法

5．1 TPH算法

5．1．1 算法思路

5．1．2 算法描述

5．2 TPH实验

5．2．1 实验目标与评价标准

5．2．2 实验设计

5．2．3 实验结果与分析

5．2．4 实验总结

5．3 MR算法

5．3．1 算法思路

5．3．2 算法描述

5．4 MR实验

5．5 本章小结

第六章 系统设计和实现

6．1 Foursquare数据抓取系统

6．1．1 系统设计与功能

6．1．2 系统实现

6．2 基于位置的影响最大化原型系统

6．2．1 系统设计与功能

6．2．2 系统实现

6．3 本章小结

第七章 总结与展望

7．1 工作总结

7．2 研究展望

参考文献

致谢

硕士期间发表的论文