LBSN中基于链路预测的位置推荐算法研究

发布时间：2018-03-12 17:19

本文选题：基于位置的社会网络　切入点：位置推荐　出处：《北京交通大学》2017年硕士论文　论文类型：学位论文

【摘要】：随着移动互联网的快速发展和移动终端设备的普及,位置服务(Location Based Service,简称LBS)与传统社会网络逐渐融合,形成了基于位置的社会化网络(Location-Based Social Network,简称 LBSN)。LBSN 通过用户的地理位置信息,将线上虚拟社会网络与线下实体世界联系在一起,使得用户能更方便的分享和获取感兴趣的信息,越来越受到用户的青睐。LBSN下的位置推荐不仅能帮助用户发现其感兴趣的新位置,而且还能帮助商家进行品牌推广及精准营销,从而带来巨大的经济效益,具有极大的研究价值,已经成为了学术界和工业界研究的热点。虽然大量的线上和线下用户数据的积累为研究LBSN下的位置推荐提供了良好的数据基础,但是由于LBSN中的数据具有规模大、多维度、稀疏性高的特点,使得现有的位置推荐算法在算法实时性、推荐准确度等方面仍有较大提升空间。针对上述存在的问题,本文融合了 LBSN中的社交关系、时间、空间等多维信息,利用复杂网络链路预测技术来进行位置推荐,完成的工作及研究成果如下:(1)从社交关系、时间、空间三个方面对LBSN下的用户签到数据进行深入分析,挖掘出了用户签到行为的一般模式。结合LBSN数据的特征,构建了一个包含用户、位置两类节点,包含用户-用户、用户-位置、位置-位置三类边的复杂图模型。同时融合时空等多维信息,提出了对图模型中三类边的权值度量方法;(2)提出了基于图消息传播的二度好友选取算法GraphSF(Graph Second Friends),能够过滤图模型中用于计算的用户节点数量。在此基础上,提出了随机游走的链路预测算法WPPR(Weighted PersonalizedPageRank),用复杂网络的链路预测技术完成位置推荐。该算法考虑了边权值的影响,并加入了重启机制,使得其具有较好的推荐准确性和运行效率;(3)基于Spark平台下的并行图计算框架GraphX对本文提出的算法进行了并行化实现,有效的提高了算法的可扩展性和实时性能。最后在真实的Spark集群环境下与其他几类位置推荐算法进行对比实验,结果表明本文提出的算法不仅在准确率和召回率指标上表现良好,而且算法效率更高,扩展性更强;(4)以本文提出的链路预测位置推荐算法作为推荐引擎,结合Google Map API及web开发相关技术,实现了一个LBSN下的位置推荐原型系统。
[Abstract]:With the rapid development of mobile Internet and the popularity of mobile terminal devices, location Based Service (LBSs) and traditional social networks are gradually merged, and a location-based social network based Social network is formed, which is referred to as LBSN).LBSN through the geographic location information of users. Connecting online virtual social networks with offline physical worlds allows users to more easily share and access information of interest. The location recommendation under. LBSN is becoming more and more popular among users. It can not only help users find the new location that they are interested in, but also help merchants to promote brand and accurate marketing, which brings great economic benefits and has great research value. Although the accumulation of a large amount of online and offline user data provides a good data base for the research of location recommendation under LBSN, because of the large scale and multi-dimension of the data in LBSN, Because of its high sparsity, the existing location recommendation algorithms still have a great improvement in real-time algorithm, recommendation accuracy and so on. In view of the above problems, this paper combines the social relationship, time and time in LBSN. Space and other multidimensional information, the use of complex network link prediction technology to recommend the location, the completed work and research results are as follows: 1) from the social relations, time, space three aspects of the user sign in LBSN data in-depth analysis, This paper excavates the general pattern of user check-in behavior, combines the characteristics of LBSN data, and constructs two kinds of nodes including user, location, user-user, user-location, and so on. A complex graph model with three edges of position and position. At the same time, it fuses the multidimensional information, such as space-time and so on. In this paper, a method to measure the weights of three kinds of edges in graph model is presented. (2) the second degree friend selection algorithm GraphSF(Graph Second friends based on graph message propagation is proposed, which can filter the number of user nodes used in the graph model to calculate the number of user nodes. A random walk link prediction algorithm, WPPR(Weighted Personalized Page rank, is proposed, which uses the link prediction technique of complex networks to complete the location recommendation. The algorithm takes into account the influence of boundary weights and adds a restart mechanism. It has good recommendation accuracy and running efficiency. Based on the parallel graph computing framework GraphX under Spark platform, the algorithm proposed in this paper has been parallelized. The extensibility and real-time performance of the algorithm are improved effectively. Finally, the algorithm is compared with other location recommendation algorithms in the real Spark cluster environment. The results show that the proposed algorithm not only performs well in accuracy and recall index, but also has higher efficiency and expansibility. Combined with Google Map API and web development technology, a location recommendation prototype system based on LBSN is implemented.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP391.3

【参考文献】