A novel approach for location promotion on location-based social networks

摘要

Maximizing the spread of influence was recently studied in several models of social networks. For location-based social networks, it also plays an important role, so a further research about this field is necessary. In this study, based on users' movement histories and their friendships, we first design the Predicting Mobility in the Near Future (PMNF) model to capture human mobility. Human mobility is inferred from the model by taking into account the following three features: (1) the regular movement of users, (2) the movement of friends of users, (3) hot regions, the most attractive places for all users. Second, from the result of predicting movements of users at each location, we determine influence of each user on friends with the condition that friends are predicted to come to the location. Third, the Influence Maximization (IM) algorithms are proposed to find a set of k influential users who can make the maximum influence on their friends according to either the number of influenced users (IM num) or the total of probability of moving the considered location of influenced users (IM score). The model and algorithms are evaluated on three large datasets collected by from 40,000 to over 60,000 users for each dataset over a period of two years in the real world at over 500,000 checked-in points as well as 400,000 to nearly 2,000,000 friendships also considered. The points are clustered into locations by density-based clustering algorithms such as OPTICS and GRID. As a result, our algorithms give an order of magnitude better performance than baseline approaches like choosing influential users based on the number of check-ins of users and selecting influential users by the number of friends of users. From the result of experiments, we are able to apply to some areas like advertisement to get the most efficient with the minimum costs. We show that our framework reliably determines the most influential users with high accuracy.