Research On Community Detection And Location Recommendation Algorithms In Location-based Social Networks

As a popular social media,Location-based social networks(LBSNs)have witnessed greatly development,and attracted millions of mobile users to share their locations and location-related contents.With the increasing use of LBSNs,an efficient personalized recommendation service is required to recommend appropriate point of interests(POIs)to users.Traditional collaborative filtering(CF)based recommendation algorithms need go through all users in LBSN to recommend locations to the target user.Due to the fact that many users are irrelevant to the target user,these approaches perform poorly in accuracy and scalability.In view of the above issues,this thesis deeply investigates the location recommendation algorithms in LBSN,and the main research contributions are given as follows:(1)This thesis comprehensively mines and analyzes the Foursquare check-in data,preprocesses the raw data to filter sparse data to extract the effective datasets which is used in our following experiments,and characterizes the features of these location check-in data.In particular we observe the influence of the social contact among users on the location recommendation and the consistency between the social contact strength and the times of common check-in location.Meanwhile,it is found that geographical factors have a significant influence on the location recommendation and the check-in probability of location can be characterized as power-law distribution by the distance between the location and the user's place of residence.These findings establish the foundation for a sound and effective location recommendation model.(2)We propopose an efficient location recommendation method based on discrete particle swarm optimization(DPSO)and collaborative filtering(CF),ELR-DC.This scheme efficiently detects communities with close internal ties and then conducts location recommendation in each community.Specifically,a similarity network among users is firstly constructed based on their check-in activities,which explicitly takes into account users' similarities of interest and active regions.Then,an improved merging DPSO algorithm(IMDPSO)is proposed to detect communities through utilizing the formed similarity network.Then,in each community,CF algorithm is applied to recommend Top-N locations to each user.Finally,we conduct a comprehensive performance evaluation on a large-scale datasets collected from Foursquare.Experimental results show that the proposed scheme have the superiority of the precision and efficiency over the existed CF algorithms.(3)In order to overcome the shortcomings of ELR-DC in detecting the communites' efficiency and modularity and to use the influence of geographical factors on the location recommendation and further improve the recommendation effect,an efficient location recommendation method based on Louvain algorithm and multi-source information fusion,ELR-LM is proposed.Firstly,Louvain algorithm is utilized to detect communities,and experimental results show that ELR-LM advantages over ELR-DC in terms of modularity and efficiency of community detection.Then,in each community,check-ins(check-ins are used to predict the ratings of locations through CF algorithm),geographical influence(the power law distribution model obtained by Foursquare analysis is used to predict the ratings of locations)and popularity factor of location(i.e.,the check-in times of locations are used to predict the ratings of locations)weight combination to predict the ratings of locations.Finally,this scheme recommends Top-N locations to each user.Experimental results show that the proposed scheme advantages over ELR-DC in terms of precision,reccall and efficiency.