Efficient location-aware influence maximization

ABSTRACT

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 applications 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 develop 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]. Experimental results on real datasets show our method achieves high performance while keeping large influence spread and significantly outperforms state-of-the-art algorithms.

References

1. S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Computer Networks, 30(1-7):107--117, 1998.
2. W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In KDD, pages 1029--1038, 2010.
3. W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In KDD, pages 199--208, 2009.
4. W. Chen, Y. Yuan, and L. Zhang. Scalable influence maximization in social networks under the linear threshold model. In ICDM, pages 88--97, 2010.
5. Y.-C. Chen, W.-C. Peng, and S.-Y. Lee. Efficient algorithms for influence maximization in social networks. Knowl. Inf. Syst., 33(3):577--601, 2012.
6. P. Domingos and M. Richardson. Mining the network value of customers. In KDD, pages 57--66, 2001.
7. R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. In PODS, 2001.
8. A. Goyal, F. Bonchi, and L. V. S. Lakshmanan. A data-based approach to social influence maximization. PVLDB, 5(1):73--84, 2011.
9. K. Jung, W. Heo, and W. Chen. Irie: Scalable and robust influence maximization in social networks. In ICDM, pages 918--923, 2012.
10. D. Kempe, J. M. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In KDD, pages 137--146, 2003.
11. J. Kim, S.-K. Kim, and H. Yu. Scalable and parallelizable processing of influence maximization for large-scale social networks? In ICDE, pages 266--277, 2013.
12. M. Kimura and K. Saito. Tractable models for information diffusion in social networks. In PKDD, pages 259--271, 2006.
13. J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. M. VanBriesen, and N. S. Glance. Cost-effective outbreak detection in networks. In KDD, pages 420--429, 2007.
14. G. Li, J. Hu, K. lee Tan, and J. Feng. Effective location identification from microblogs. In ICDE, 2014.
15. G. Li, Y. Wang, T. Wang, and J. Feng. Location-aware publish/subscribe. In KDD, pages 802--810, 2013.
16. R. Li, S. Wang, H. Deng, R. Wang, and K. C.-C. Chang. Towards social user profiling: unified and discriminative influence model for inferring home locations. In KDD, pages 1023--1031, 2012.
17. I. R. Misner and V. Devine. The world's best known marketing secret: Building your business with word-of-mouth marketing. In Bard Press; 2nd Edition edition, 1999.
18. J. Nail, C. Charron, and S. Baxter. The consumer advertising backlash. In Forrester Research:, 2004.
19. M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In KDD, pages 61--70, 2002.
20. C. Zhang, L. Shou, K. Chen, G. Chen, and Y. Bei. Evaluatin ggeo-social influence in location-based social networks. In CIKM, pages 1442--1451, 2012

Index Terms

• Human-centered computing

  • Visualization

    • Visualization application domains

      • Geographic visualization

• Information systems

  • Information systems applications

    • Spatial-temporal systems