Research On Two-stage Location Promotion Algorithm Combining With User Interests

Location Based Social Network(LBSN)provides businesses with a good advertising platform due to the rapid propagation of information.Location promotion algorithms can help businesses find the seed users,so as to help businesses get the maximum advertising revenue with the least cost by the influence of these users.Location promotion can be seen as the influence maximization in LBSN.In which,two key issues need to be addressed:how to extract valuable information from a large amount of network data to measure the propagation probability between users accurately;how to design an efficient and accurate algorithm to select seed users.For the first key issue,existing researches lack the exploration of multiple factors such as the interaction between users,which reduces the accuracy of information propagation probability and thus affects the accuracy of seed selection.For the second key issue,existing researches mainly use heuristic algorithm or greedy algorithm.Compared with the heuristic algorithm,greedy algorithm can make the seed users achieve greater influence scope,but its time complexity is correspondingly higher,which is not suitable for large-scale networks.Therefore,how to accurately measure the probability of information propagation among users in LBSN network and how to design efficient and accurate seed selection algorithm needs further study.In order to improve the accuracy of propagation probability,in this paper,multi-dimensional information such as user's check-in information,social relationship information and location information in LBSN is used to measure the propagation probability between users.Based on above factors,a Multi-Feature Independent Cascade Model(MFICM)is proposed to improve the accuracy of information propagation probabilities among users,thus improve the accuracy of measure the propagation scope of users.Considering the special attributes of seed users,such as high access probabilities and high propagation desires,a Two-stage Location Promotion algorithm combining with User Interest(TLPUI)is proposed in this paper,in which the seed selection process is divided into two stages.In the first stage,some users in the LBSN network are pruned in advance,and the candidate seed users are screened out to narrow the selection range.In the second stage,greedy algorithm and MFICM propagation model are used to select the final seed users,thus the time complexity of seed selection algorithm is reduced and the accuracy is increasedthrough two-stage seed selection.LBSN-yelp dataset that provides abundant semantic information is used for experimental verification.MFICM propagation model is first evaluated using three criteria:spread scope,accuracy and coverage.Experimental results show that MFICM,which combines with user interest,similarity between users and propagation influence,can get larger spread scope and more accurate measure of user's spread scope.Then,the proposed location promotion algorithm is evaluated from four aspects:spread scope,accuracy,coverage and time complexity.The experimental results show that although TLPUI achieves slightly lower spread scope and coverage than the NewGreedy greedy algorithm,it greatly reduces the time complexity of the seed selection process and improves the accuracy of seeds selection efficiently.