A fast approximation for influence maximization in large social networks

ABSTRACT

This paper deals with a novel research work about a new efficient approximation algorithm for influence maximization, which was introduced to maximize the benefit of viral marketing. For efficiency, we devise two ways of exploiting the 2-hop influence spread which is the influence spread on nodes within 2-hops away from nodes in a seed set. Firstly, we propose a new greedy method for the influence maximization problem using the 2-hop influence spread. Secondly, to speed up the new greedy method, we devise an effective way of removing unnecessary nodes for influence maximization based on optimal seed's local influence heuristics. In our experiments, we evaluate our method with real-life datasets, and compare it with recent existing methods. From experimental results, the proposed method is at least an order of magnitude faster than the existing methods in all cases while achieving similar accuracy.

References

1. M. Cha, A. Mislove, and K. P. Gummadi. A measurement-driven analysis of information propagation in the flickr social network. In Proceedings of the 18th international conference on World wide web, WWW '09, pages 721--730, 2009.
2. W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '10, 2010.
3. W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '09, 2009.
4. P. Domingos and M. Richardson. Mining the network value of customers. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '01, 2001.
5. A. Goyal, W. Lu, and L. V. Lakshmanan. Celf+: optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th international conference companion on World wide web, WWW '11, 2011.
6. Q. Jiang, G. Song, C. Gao, Y. Wang, W. Si, and K. Xie. Simulated annealing based influence maximization in social networks. In AAAI Conference on Artificial Intelligence, 2011.
7. K. Jung, W. Heo, and W. Chen. Irie: Scalable and robust influence maximization in social networks. In Data Mining (ICDM), 2012 IEEE 12th International Conference on, pages 918--923, 2012.
8. D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '03, 2003.
9. J. Kim, S.-K. Kim, and H. Yu. Scalable and parallelizable processing of influence maximization for large-scale social networks? In Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pages 266--277, April 2013.
10. H. Kwak, C. Lee, H. Park, and S. Moon. What is twitter, a social network or a news media? In Proceedings of the 19th international conference on World wide web, WWW '10, pages 591--600, 2010.
11. J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '07, 2007.
12. E. Sun, I. Rosenn, C. Marlow, and T. Lento. Gesundheit! modeling contagion through facebook news feed. Proc. ICWSM, 9, 2009.
13. Y. Wang, G. Cong, G. Song, and K. Xie. Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD '10, 2010.

Index Terms

• Information systems

  • Information systems applications

    • Data mining