Influence Spread in Location-Based Social Network: An Efficient Algorithm of Epidemic Controlling

ABSTRACT

Much work has already been studied on the interrelation between the epidemic spreading and awareness spreading to prevent infections in a social network. By selecting seed users to spread awareness, we can control epidemic spreading. However, selecting seed users with the maximum influential users may not be the best solution in location-based social networks. Therefore, it is challenging to determine users to spread the information (the awareness of prevention) in these networks. The minimized epidemic infection (MEI) problem aims to find a seed set with k seed users such that the infection users can be minimized. In this article, we propose a piecewise function to measure the probability of each user being infected, which considers the distance and time. Then, we propose an algorithm called location-infected-greedy (LIG) to solve the MEI problem by finding the seed nodes that consider the probability of infection, time of check-in, location information, and influence of users. In the meantime, LIG can obtain an upper bound of the data-dependent approximate ratio, and it runs in O(kn(2)), where n is the total number of nodes and k is the number of seed nodes. Finally, extensive contrast experiments on real-world location-based social networks show that our algorithm is efficient and effective.