Community-based influence maximization in location-based social network

Influence maximization, as one of the major problems in Location-based Social Networks (LBSN), aims to determine a subset of influential users to maximize the influence spread through the “word-of-mouth” effect. Although many recent studies have focused on the influence maximization problem in LBSN, a majority part of the concern is shed on the influence spread in the whole network, with an underestimation in the importance of the community structure. In this paper, we propose a Community-based Influence Maximization model to study the influence maximization problem in LBSN, with consideration of both community structure and users’ spatio-temporal behavior. Two community-based algorithms are developed to maximize the influence spread, which encompass two components: 1) detecting communities in LBSN based on users’ mobility; and 2) selecting the most influential individuals based on communities. In the first phase, we calculate the similarity between users according to their historical check-in data and design a Weighted Distance algorithm to detect communities based on the similarity. In the second phase, we select candidates based on local network structure and propose two different methods to calculate the precise influence spread of each candidate based on communities. The extensive experiments over real datasets demonstrate the efficiency and effectiveness of the proposed algorithms.