Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models

ABSTRACT

The steady growth of graph data from social networks has resulted in wide-spread research in finding solutions to the influence maximization problem. In this paper, we propose a holistic solution to the influence maximization (IM) problem. (1) We introduce an opinion-cum-interaction (OI) model that closely mirrors the real-world scenarios. Under the OI model, we introduce a novel problem of Maximizing the Effective Opinion (MEO) of influenced users. We prove that the MEO problem is NP-hard and cannot be approximated within a constant ratio unless P=NP. (2) We propose a heuristic algorithm OSIM to efficiently solve the MEO problem. To better explain the OSIM heuristic, we first introduce EaSyIM - the opinion-oblivious version of OSIM, a scalable algorithm capable of running within practical compute times on commodity hardware. In addition to serving as a fundamental building block for OSIM, EaSyIM is capable of addressing the scalability aspect - memory consumption and running time, of the IM problem as well. Empirically, our algorithms are capable of maintaining the deviation in the spread always within 5% of the best known methods in the literature. In addition, our experiments show that both OSIM and EaSyIM are effective, efficient, scalable and significantly enhance the ability to analyze real datasets.

References

1. http://an.kaist.ac.kr/traces/WWW2010.html.
2. http://lamda.nju.edu.cn/zhangt/dm2012/Project4.html.
3. arXiv. http://www.arxiv.org.
4. Empath: Sentiment, Topic, and Demographic Analysis. https://www.parc.com/services/focus-area/bigdata/.
5. Natural Language Sentiment Analysis API. http://text-processing.com/demo/sentiment/.
6. SNAP Datasets. https://snap.stanford.edu/data/.
7. The Boost Graph Library. http://www.boost.org.
8. Ç. Aslay, N. Barbieri, F. Bonchi, and R. A. Baeza-Yates. Online topic-aware influence maximization queries. In EDBT, pages 295--306, 2014.
9. C. Aslay, W. Lu, F. Bonchi, A. Goyal, and L. V. S. Lakshmanan. Viral marketing meets social advertising: Ad allocation with minimum regret. PVLDB, 8:814--825, 2015.
10. L. Backstrom, D. Huttenlocher, J. Kleinberg, and X. Lan. Group formation in large social networks: Membership, growth, and evolution. In KDD, pages 44--54, 2006.
11. N. Barbieri, F. Bonchi, and G. Manco. Topic-aware social influence propagation models. In ICDM, pages 81--90, 2012.
12. N. Barbieri, F. Bonchi, and G. Manco. Cascade-based community detection. In WSDM, pages 33--42, 2013.
13. C. Borgs, M. Brautbar, J. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. In SODA, pages 946--957, 2014.
14. V. Chaoji, S. Ranu, R. Rastogi, and R. Bhatt. Recommendations to boost content spread in social networks. In WWW, pages 529--538, 2012.
15. S. Chen, J. Fan, G. Li, J. Feng, K.-l. Tan, and J. Tang. Online topic-aware influence maximization. PVLDB, 8:666--677, 2015.
16. W. Chen, A. Collins, R. Cummings, T. Ke, Z. Liu, D. Rincon, X. Sun, Y. Wang, W. Wei, and Y. Yuan. Influence Maximization in Social Networks When Negative Opinions May Emerge and Propagate. In SDM, 2011.
17. 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.
18. W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In KDD, pages 199--208, 2009.
19. W. Chen, Y. Yuan, and L. Zhang. Scalable influence maximization in social networks under the linear threshold model. In ICDM, pages 88--97, 2010.
20. Y. Chen, E. K. Garcia, M. R. Gupta, A. Rahimi, and L. Cazzanti. Similarity-based classification: Concepts and algorithms. Journal of Machine Learning Res, 10:747--776, 2009.
21. S. Cheng, H. Shen, J. Huang, W. Chen, and X. Cheng. Imrank: influence maximization via finding self-consistent ranking. In SIGIR, pages 475--484, 2014.
22. S. Cheng, H. Shen, J. Huang, G. Zhang, and X. Cheng. Staticgreedy: solving the scalability-accuracy dilemma in influence maximization. In CIKM, pages 509--518, 2013.
23. E. Cohen, D. Delling, T. Pajor, and R. F. Werneck. Sketch-based influence maximization and computation: Scaling up with guarantees. In CIKM, pages 629--638, 2014.
24. T. N. Dinh, H. Zhang, D. T. Nguyen, and M. T. Thai. Cost-effective viral marketing for time-critical campaigns in large-scale social networks. IEEE/ACM Trans. Netw., 22:2001--2011, 2014.
25. S. Eubank, H. Guclu, V. S. Anil Kumar, M. V. Marathe, A. Srinivasan, Z. Toroczkai, and N. Wang. Modelling disease outbreaks in realistic urban social networks. Nature, 429(6988):180--184, 2004.
26. S. Galhotra, A. Arora, S. Virinchi, and S. Roy. Asim: A scalable algorithm for influence maximization under the independent cascade model. In WWW (Companion Volume), 2015.
27. H. Gao, J. Mahmud, J. Chen, J. Nichols, and M. X. Zhou. Modeling user attitude toward controversial topics in online social media. In ICWSM, 2014.
28. A. Goyal, W. Lu, and L. V. Lakshmanan. Celf+: Optimizing the greedy algorithm for influence maximization in social networks. In WWW (Companion Volume), pages 47--48, 2011.
29. A. Goyal, W. Lu, and L. V. Lakshmanan. Simpath: An efficient algorithm for influence maximization under the linear threshold model. In ICDM, pages 211--220, 2011.
30. X. He, G. Song, W. Chen, and Q. Jiang. Influence blocking maximization in social networks under the competitive linear threshold model. In SDM, pages 463--474, 2012.
31. K. Jung, W. Heo, and W. Chen. Irie: Scalable and robust influence maximization in social networks. In ICDM, pages 918--923, 2012.
32. D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In KDD, pages 137--146, 2003.
33. 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.
34. J. Leskovec, J. Kleinberg, and C. Faloutsos. Graphs over time: Densification laws, shrinking diameters and possible explanations. In KDD, pages 177--187, 2005.
35. J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In KDD, pages 420--429, 2007.
36. H. Li, S. S. Bhowmick, J. Cui, Y. Gao, and J. Ma. Getreal: Towards realistic selection of influence maximization strategies in competitive networks. In SIGMOD, pages 1525--1537, 2015.
37. Y. Li, W. Chen, Y. Wang, and Z.-L. Zhang. Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships. In WSDM, pages 657--666, 2013.
38. K. W. Lim and W. Buntine. Twitter opinion topic model: Extracting product opinions from tweets by leveraging hashtags and sentiment lexicon. In CIKM, pages 1319--1328, 2014.
39. W. Lu, F. Bonchi, A. Goyal, and L. V. S. Lakshmanan. The bang for the buck: fair competitive viral marketing from the host perspective. In KDD, pages 928--936, 2013.
40. Y. Mehmood, N. Barbieri, F. Bonchi, and A. Ukkonen. CSI: com-munity-level social influence analysis. In ECML/PKDD, pages 48--63, 2013.
41. G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of approximations for maximizing submodular set functionsi. Mathematical Programming, 14(1):265--294, 1978.
42. N. Ohsaka, T. Akiba, Y. Yoshida, and K. Kawarabayashi. Fast and accurate influence maximization on large networks with pruned monte-carlo simulations. In AAAI, pages 138--144, 2014.
43. A. Pak and P. Paroubek. Twitter as a corpus for sentiment analysis and opinion mining. In LREC, 2010.
44. M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In KDD, pages 61--70, 2002.
45. Y. Tang, Y. Shi, and X. Xiao. Influence maximization in near-linear time: A martingale approach. In SIGMOD, pages 1539--1554, 2015.
46. Y. Tang, X. Xiao, and Y. Shi. Influence maximization: Near-optimal time complexity meets practical efficiency. In SIGMOD, pages 75--86, 2014.
47. L. G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8:410--421, 1979.
48. H. Zhang, T. N. Dinh, and M. T. Thai. Maximizing the spread of positive influence in online social networks. In ICDCS, pages 317--326, 2013.
49. X. W. Zhao, Y. Guo, Y. He, H. Jiang, Y. Wu, and X. Li. We know what you want to buy: A demographic-based system for product recommendation on microblogs. In KDD, pages 1935--1944, 2014.
50. X. Zhu and Z. Ghahramani. Learning from labeled and unlabeled data with label propagation.

Index Terms

• Information systems

  • Information systems applications

    • Data mining

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms