Beyond Worst-case (In)approximability of Nonsubmodular Influence Maximization

Abstract

We consider the problem of maximizing the spread of influence in a social network by choosing a fixed number of initial seeds, formally referred to as the influence maximization problem. It admits a (1−1/e)-factor approximation algorithm if the influence function is submodular. Otherwise, in the worst case, the problem is NP-hard to approximate to within a factor of N^1−ε. This article studies whether this worst-case hardness result can be circumvented by making assumptions about either the underlying network topology or the cascade model. All our assumptions are motivated by many real-life social network cascades.

First, we present strong inapproximability results for a very restricted class of networks called the (stochastic) hierarchical blockmodel, a special case of the well-studied (stochastic) blockmodel in which relationships between blocks admit a tree structure. We also provide a dynamic-programming-based polynomial time algorithm, which optimally computes a directed variant of the influence maximization problem on hierarchical blockmodel networks. Our algorithm indicates that the inapproximability result is due to the bidirectionality of influence between agent-blocks.

Second, we present strong inapproximability results for a class of influence functions that are “almost” submodular, called 2-quasi-submodular. Our inapproximability results hold even for any 2-quasi-submodular f fixed in advance. This result also indicates that the “threshold” between submodularity and nonsubmodularity is sharp, regarding the approximability of influence maximization.

References

1. Rico Angell and Grant Schoenebeck. 2017. Don,t be greedy: Leveraging community structure to find high quality seed sets for influence maximization. In Proceedings of the WINE. Springer, 16--29.
2. W. B. Arthur. 1989. Competing technologies, increasing returns, and lock-in by historical events. Econ. J. 99, 394 (1989), pp. 116--131. Retrieved from http://www.jstor.org/stable/2234208c.
3. Lars Backstrom, Daniel P. Huttenlocher, Jon M. Kleinberg, and Xiangyang Lan. 2006. Group formation in large social networks: Membership, growth, and evolution. In Proceedings of the ACM SIGKDD.
4. Abhijit Banerjee, Arun G Chandrasekhar, Esther Duflo, and Matthew O Jackson. 2013. The diffusion of microfinance. Science 341, 6144 (2013).
5. F. M. Bass. 1969. A new product growth for model consumer durables. Manage. Sci. 15, 5 (1969), 215--227.
6. Shishir Bharathi, David Kempe, and Mahyar Salek. 2007. In Proceedings of the WINE. Springer, Berlin, 306--311.
7. Christian Borgs, Michael Brautbar, Jennifer T. Chayes, and Brendan Lucier. 2012. Influence maximization in social networks: Towards an optimal algorithmic solution. arXiv preprint arXiv:1212.0884 (2012).
8. J. J. Brown and P. H. Reingen. 1987. Social ties and word-of-mouth referral behavior. J. Consumer Res. 14 (1987), 350--362.
9. D. Centola. 2010. The spread of behavior in an online social network experiment. Science 329, 5996 (2010), 1194--1197.
10. Ning Chen. 2009. On the approximability of influence in social networks. SIAM J. Discrete Math. 23, 3 (2009), 1400--1415.
11. Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, and Xuren Zhou. 2016. Robust influence maximization. In Proceedings of the ACM SIGKDD. ACM, 795--804.
12. Wei Chen, Yajun Wang, and Siyu Yang. 2009. Efficient influence maximization in social networks. In Proceedings of the ACM SIGKDD. ACM, 199--208.
13. Wei Chen, Yifei Yuan, and Li Zhang. 2010. Scalable influence maximization in social networks under the linear threshold model. In Proceedings of the ICDM. IEEE, 88--97.
14. Aaron Clauset, Cristopher Moore, and Mark EJ Newman. 2008. Hierarchical structure and the prediction of missing links in networks. Nature 453, 7191 (2008), 98--101.
15. J. Coleman, E. Katz, and H. Menzel. 1957. The diffusion of an innovation among physicians. Sociometry 20 (1957), 253--270.
16. T. G. Conley and C. R. Udry. 2010. Learning about a new technology: Pineapple in Ghana. Amer. Econ. Rev. 100, 1 (2010), 35--69.
17. Paul DiMaggio. 1986. Structural analysis of organizational fields: A blockmodel approach. Res. Organiz. Behav. 8 (1986), 335--370.
18. P. Domingos and M. Richardson. 2001. Mining the network value of customers. In Proceedings of the ACM SIGKDD.
19. J. Goldenberg, B. Libai, and E. Muller. 2001. Using complex systems analysis to advance marketing theory development: Modeling heterogeneity effects on new product growth through stochastic cellular automata. Acad. Market. Sci. Rev. 9, 3 (2001), 1--18.
20. Sanjeev Goyal and Michael Kearns. 2012. Competitive contagion in networks. In Proceedings of the STOC. 759--774.
21. Mark Granovetter. 1978. Threshold models of collective behavior. Amer. J. Sociol. 83, 6 (1978), 1420--1443.
22. Xinran He and David Kempe. 2016. Robust influence maximization. In Proceedings of the ACM SIGKDD.
23. Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. 1983. Stochastic blockmodels: First steps. Soc. Netw. 5, 2 (1983), 109--137.
24. Matthew O. Jackson. 2008. Social and Economic Networks. Princeton University Press.
25. David Kempe, Jon M. Kleinberg, and Éva Tardos. 2003. Maximizing the spread of influence through a social network. In Proceedings of the ACM SIGKDD. 137--146.
26. David Kempe, Jon M. Kleinberg, and Éva Tardos. 2005. Influential nodes in a diffusion model for social networks. In Proceedings of the ICALP. 1127--1138.
27. K. Lerman and R. Ghosh. 2010. Information contagion: An empirical study of the spread of news on Digg and Twitter social networks. In Proceedings of the ICWSM. 90--97.
28. Jure Leskovec, Lada A. Adamic, and Bernardo A. Huberman. 2006. The dynamics of viral marketing. In Proceedings of the EC. 228--237.
29. Qiang Li, Wei Chen, Xiaoming Sun, and Jialin Zhang. 2017. Influence maximization with ϵ-almost submodular threshold functions. In Proceedings of the NIPS. 3804--3814.
30. Brendan Lucier, Joel Oren, and Yaron Singer. 2015. Influence at scale: Distributed computation of complex contagion in networks. In Proceedings of the ACM SIGKDD. ACM, 735--744.
31. Vince Lyzinski, Minh Tang, Avanti Athreya, Youngser Park, and Carey E. Priebe. 2017. Community detection and classification in hierarchical stochastic blockmodels. IEEE Transactions on Network Science and Engineering 4, 1 (2017), 13--26.
32. V. Mahajan, E. Muller, and F. M. Bass. 1990. New product diffusion models in marketing: A review and directions for research. J. Market. 54 (1990), 1--26.
33. S. Morris. 2000. Contagion. Rev. Econ. Studies 67, 1 (2000), 57--78.
34. Elchanan Mossel and Sébastien Roch. 2010. Submodularity of influence in social networks: From local to global. SIAM J. Comput. 39, 6 (2010), 2176--2188.
35. George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. 1978. An analysis of approximations for maximizing submodular set functions. Math. Program. 14, 1 (1978), 265--294.
36. M. Richardson and P. Domingos. 2002. Mining knowledge-sharing sites for viral marketing. In Proceedings of the ACM SIGKDD. 61--70.
37. Daniel M. Romero, Brendan Meeder, and Jon Kleinberg. 2011. Differences in the mechanics of information diffusion across topics: Idioms, political hashtags, and complex contagion on Twitter. In Proceedings of the WWW. ACM, 695--704. Retrieved from http://dl.acm.org/citation.cfm?id=1963503.
38. Lior Seeman and Yaron Singer. 2013. Adaptive seeding in social networks. In Proceedings of the FOCS. IEEE, 459--468.
39. Yaron Singer and Thibaut Horel. 2016. Maximization of approximately submodular functions. In Proceedings of the NIPS.
40. D. J. Watts. 2002. A simple model of global cascades on random networks. Proc. Natl. Acad. Sci. U.S.A. 99, 9 (2002), 5766--5771. Retrieved from arXiv:http://www.pnas.org/content/99/9/5766.full.pdf+html.
41. Harrison C. White, Scott A. Boorman, and Ronald L. Breiger. 1976. Social structure from multiple networks. I. Blockmodels of roles and positions. Amer. J. Sociol. 81, 4 (1976), 730--780. Retrieved from http://www.jstor.org/stable/2777596.

Index Terms

• Networks

  • Network algorithms

    • Network economics

• Theory of computation

  • Computational complexity and cryptography