Efficient Location-Aware Influence Maximization

Although influence maximization, which selects a set of users in a social network to maximize the expected number of users influenced by the selected users (called influence spread), has been extensively studied, existing works neglected the fact that the location information can play an important role in influence maximization. Many real-world applica-tions such as location-aware word-of-mouth marketing have location-aware requirement. In this paper we study the location-aware influence maximization problem. One big challenge in location-aware influence maximization is to de-velop an efficient scheme that offers wide influence spread. To address this challenge, we propose two greedy algorithms with 1 − 1/e approximation ratio. To meet the instant-speed requirement, we propose two efficient algorithms with ǫ · (1 − 1/e) approximation ratio for any ǫ ∈ (0, 1]. Exper-imental results on real datasets show our method achieves high performance while keeping large influence spread and significantly outperforms state-of-the-art algorithms