摘 要

随着互联网技术的高速发展，基于位置的社交网络（LBSN）迅速普及并且受到了广泛关注。兴趣点和好友推荐服务是LBSN网络中重要的两种推荐服务，同时给用户和提供服务的商户提供了便利。推荐服务含有的巨大研究意义和商业价值使得其迅速成为了一个研究热点。然而受LBSN网络数据量巨大、数据稀疏程度高、异质性高等因素影响，LBSN网络下进行好友推荐和兴趣点推荐的表现效果往往不够好。

网络嵌入技术是一种学习网络特征的无监督学习方法，其中心思想是将网络中的每个节点转换为低维度的潜在表示，该方法能够有效克服网络稀疏性带来的问题。鉴于网络嵌入方法在网络链路预测方面具有良好的表现效果，本文基于网络嵌入方法设计了好友和兴趣点推荐系统。通过综合分析考虑用户社交，签到时间、地点、类别等语义信息，本文将社交关系和签到记录建模为一个超图网络，对该超图网络进行网络嵌入学习。在学习过程中，我们首先改进传统的随机游走方案共同采样社交关系和签到记录，然后根据LBSN网络特性，定义了两种相似度来设计目标函数，通过优化目标函数来得到每个节点的低维向量表示，最后根据用户及位置的相似程度进行推荐。

我们选取了在LBSN典型应用平台Foursquare搜集的真实签到数据集上开展实验并进行分析，将本文提出的推荐模型和一些经典推荐算法通过准确率和召回率两个衡量指标对比实验。结果表明了本文设计的推荐系统模型在地点和好友推荐方面的有效性。

关键词：基于位置的社交网络；个性化推荐；网络嵌入；链路预测

Abstract

As network techniques are developing, location-based social network (LBSN) has been extensively used and drawn lots of attentions. Recommendation service for friends and point-of-interests is an important service in location-based social network, which provides convenience to both users and service provider. Owing to great research significance and commercial value in recommendation service, it has quickly become a research focus. However, due to the large amount of LBSN network data, the high degree of data sparsity and heterogeneity, the performance of friends recommendation and point-of-interests recommendation in LBSN are not satisfying.

Network embedding technology learns features in an unsupervised way. The main method is to embed all nodes of the network into a low-dimensional latent space. This way can resultfully alleviates the problems caused by network sparsity. Owing to its good performance in link prediction task by network embedding, we design a system for friends and point-of-interests recommendation based on network embedding in this paper. After the comprehensive analysis of semantic information such as user’s social contact, check-in time, location and category. we jointly model the social relationships and check-in records as a hypergraph network and conduct network embedding for the hypergraph. In the process of network embedding, we first improve the traditional random walk scheme to jointly sample social relationships and check-in records, and then define two kinds of similarities to design the objective function considering LBSN properties. The objective function is optimized to obtain the low-dimensional vectors and finally we can recommend friends and locations to each user according to their similarities.

We select the real check-in datasets collected on Foursquare, a typical application platform of LBSN, for analysis and experiment. Then we compare the model in this paper with several typical recommendation algorithms by measuring accuracy and recall. According to the results, our recommendation system in this paper is effective in both friends and point-of-interests recommendation tasks.

Keywords: location-based social network；personalized recommendations；network embedding；link prediction

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1研究背景及意义 1

1.1.1研究背景 1

1.1.2研究意义 2

1.2 国内外研究现状 2

1.2.1 基于位置的社交网络发展及研究现状 2

1.2.2 网络嵌入技术的发展与研究现状 5

1.3 研究内容与本文结构 7

1.3.1 研究内容 7

1.3.2 本文组织结构 7

1.4 本章小结 8

第2章 基于网络嵌入的推荐技术研究 9

2.1 基于随机游走的链路预测算法 9

2.1.1 基于短随机游走模型的链路预测算法 9

2.1.2 基于元路径的链路预测算法 10

2.2 网络嵌入技术 10

2.2.1 网络嵌入算法 10

2.2.2负采样算法 11

2.2.3梯度下降技术 11

2.3 相似性度量 13

2.3.1余弦相似度 13

2.3.2 Jaccard相似度 14

2.4本章小结 14

第3章 基于超图的LBSN网络模型构建 15

3.1 LBSN数据分析 15

3.1.1社交网络统计分析 16

3.1.2用户移动性统计分析 17

3.2 社交和用户移动性的相互关系 18

3.2.1原有社交对建立新的好友关系的影响 18

3.2.1用户移动性对社交的影响 19

3.2.2社交对移动性的影响 22

3.3本章小结 23

第4章 基于超图嵌入的推荐系统设计 24

4.1推荐流程框图 24

4.2 改进随机游走采样 24

4.3 基于超图嵌入保存网络结构特征 26

4.3.1 相似度定义 26

4.3.2 最佳拟合线 27

4.3.3 学习网络特征 27

4.3.4 优化过程 28

4.4好友推荐和兴趣点推荐 29

4.4.1好友推荐 29

4.4.2兴趣点推荐 30

4.5本章小结 30

第5章 实验及结果分析 31

5.1 实验设置 31

5.1.1数据集 31

5.1.2实验环境 32

5.1.3对比算法 32

5.1.4评价指标 33

5.2推荐系统表现效果 33

5.2.1好友推荐 33

5.2.2兴趣点推荐 35

5.3参数调节 36

5.3.1社交和移动性平衡参数的影响 36

5.3.2嵌入维数d的影响 37

第6章 总结与展望 38

6.1总结 38

6.2展望 38

参考文献 40

致 谢 43

第1章 绪论

1.1研究背景及意义

1.1.1研究背景

在移动设备、互联网、全球定位等信息化技术广泛普及的时代，人们生活中的衣食住行都因互联网的加入而发生了变化。因其突破了时空限制，消除了信息壁垒，网络社交得到了蓬勃发展。据中国产业信息网发布的《2020-2026年中国社交网络行业市场深度调研及投资战略分析报告》^[1]显示，2016年全球移动社交网络用户数为18.8亿人，占全部网络用户规模的80.20%。截止至2020年，全球已超过25.3亿人经常访问社交网络，且数据仍然处于不断增长的态势。社交网络占据了互联网很大一部分份额，在线社交已经成为人们生活中必不可少的一部分。

图1-1 2014-2020年全球移动社交网络行业用户规模走势预测

社交网络跨越了时空限制，极大的促进了信息的传播。正是由于目前种类繁多的社交应用软件、网站等，网络上产生了海量数据，其中地理位置数据与社交网络的相互融合，使得基于位置的社交网络（Location-based Social Network，LBSN）有机会发展起来。得益于4G、5G、移动网络和智能手机等技术的成熟，人们想要精确的获取自己的位置信息已经变得及其容易，用户可以随时随地通过手机上的各类应用软件在社交平台上分享当前个人地理位置，这一分享过程被称为签到，签到的地点被称为兴趣点。当前国内主流的LBSN应用平台有：微信、QQ等，国外有Foursquare、Gowalla等。这些软件给用户提供了基于位置的服务，用户可以在分享个人生活的同时发布实际地理位置。部分LBSN社交网站已经吸引了上亿的用户，有极大的市场规模和商业价值，并由此产生了大量的签到记录。