Research Of Link Prediction Based On Multi-dimensional Check-in Information On LBSN

With the rapid development of mobile Internet,the Location-based service is increasing.More and more people share the geographical images,video,text and so on through the online social network,forming the Location-based social network(LBSN).Data mining for social networks is also known as link mining.In this paper,the friendship prediction on LBSN we studied is an important branch of link mining and it has become a hot spot in present research field.It provides a new direction for the research of link prediction which based on mining the large number of check-in information in LBSN.However,the check-in information is sparse and the analysis dimension about it is single.As a result,it is more and more difficult to improve the performance of link prediction effectively.In order to solve these problems,this paper excavates the user similarity features contained in the check-in information from four dimensions respectively such as user,location,time and semantic feature of location,and then uses the supervised learning strategy to synthesize these four features for link prediction.The simulation results in real network dataset show that the proposed method in this paper improves the performance of link prediction significantly.The work of the dissertation is partly supported by the National Natural Science Foundation of China(No.61172072,61271308),Beijing Natural Science Foundation(No.4112045),and Research Fund for the Doctoral Program of Higher Education of China(No.20100009110002).The main work and contributions of this paper are summarized as follows:(1)Analyze the distribution characteristics of check-in behavior based on the LBSN dataset from three dimensions such as user,location and time respectively.The analysis shows that the check-in distribution is sparse,which makes it difficult to make full use of the check-in information.(2)In view of the problem that the check-in location is sparse,the hierarchical clustering algorithm is used to cluster the check-in location to a region.Then we introduce the concept of generalized location and the generalized co-location network,based on them the number of isolated user node in the network is greatly reduced and we can retain much more users and check-in information about them in the network.Aiming at the problem that the check-in behavior in time dimension is sparse,the similarity feature of the check-in behavior of a user at different times is used to calculate the similarity of two users.Thus,we can make full use of check-in time information.(3)The UTP model is proposed to mine the user similarity features based on the spatial-temporal dimension.Then two user similarity features are proposed that one takes into account both the user and the location and the other one takes into account into the check-in time.The validation in the real network dataset shows that the two features proposed in this paper can effectively distinguish between friends and non-friends.(4)From the view of the semantic dimension of location,this paper explores the user similarity features based on check-in POI information,we use the LDA to model the users’ check-in POI list and it is called the model of location-topic,based on which we get the user similarity feature that takes into account the check-in POI information.The validation in the real network dataset shows that this feature can effectively distinguish between friends and non-friends.(5)A supervised machine learning algorithm is used to integrate the network structure information,the spatial-temporal information and the semantic information of location in LBSN into a multi-dimensional similarity feature vector for link prediction.Experimental results in real network dataset show that the performance of LBSN link prediction is significantly improved by using the multi-dimensional similarity feature vector compared with the traditional link prediction algorithm.