Document Open Access Logo

Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization

Authors Grant Schoenebeck , Biaoshuai Tao , Fang-Yi Yu

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2019.39.pdf
  • Filesize: 0.65 MB
  • 20 pages

Document Identifiers

Author Details

Grant Schoenebeck
  • University of Michigan, Ann Arbor, USA
Biaoshuai Tao
  • University of Michigan, Ann Arbor, USA
Fang-Yi Yu
  • University of Michigan, Ann Arbor, USA

Funding

  • Schoenebeck, Grant: National Science Foundation AitF #1535912 and CAREER #1452915
  • Tao, Biaoshuai: National Science Foundation CAREER #1452915
  • Yu, Fang-Yi: National Science Foundation AitF #1535912

Cite As Get BibTex

Grant Schoenebeck, Biaoshuai Tao, and Fang-Yi Yu. Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.39

Abstract

We study the r-complex contagion influence maximization problem. In the influence maximization problem, one chooses a fixed number of initial seeds in a social network to maximize the spread of their influence. In the r-complex contagion model, each uninfected vertex in the network becomes infected if it has at least r infected neighbors.
In this paper, we focus on a random graph model named the stochastic hierarchical blockmodel, which is a special case of the well-studied stochastic blockmodel. When the graph is not exceptionally sparse, in particular, when each edge appears with probability omega (n^{-(1+1/r)}), under certain mild assumptions, we prove that the optimal seeding strategy is to put all the seeds in a single community. This matches the intuition that in a nonsubmodular cascade model placing seeds near each other creates synergy. However, it sharply contrasts with the intuition for submodular cascade models (e.g., the independent cascade model and the linear threshold model) in which nearby seeds tend to erode each others' effects.
Finally, we show that this observation yields a polynomial time dynamic programming algorithm which outputs optimal seeds if each edge appears with a probability either in omega (n^{-(1+1/r)}) or in o (n^{-2}).

Subject Classification

ACM Subject Classification
  • Theory of computation → Social networks
  • Mathematics of computing → Random graphs
Keywords
  • Nonsubmodular Influence Maximization
  • Bootstrap Percolation
  • Stochastic Blockmodel

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rico Angell and Grant Schoenebeck. Don't be greedy: leveraging community structure to find high quality seed sets for influence maximization. In International Conference on Web and Internet Economics, pages 16-29. Springer, 2017. Google Scholar
  2. Lars Backstrom, Daniel P. Huttenlocher, Jon M. Kleinberg, and Xiangyang Lan. Group formation in large social networks: membership, growth, and evolution. In ACM SIGKDD, 2006. Google Scholar
  3. Eric Balkanski, Nicole Immorlica, and Yaron Singer. The Importance of Communities for Learning to Influence. In Advances in Neural Information Processing Systems, pages 5862-5871, 2017. Google Scholar
  4. Frank M Bass. A new product growth for model consumer durables. Management science, 15(5):215-227, 1969. Google Scholar
  5. Dimitri P Bertsekas and John N Tsitsiklis. Introduction to probability, volume 1. Athena Scientific Belmont, MA, 2002. Google Scholar
  6. Jacqueline Johnson Brown and Peter H Reingen. Social ties and word-of-mouth referral behavior. Journal of Consumer research, 14(3):350-362, 1987. Google Scholar
  7. Damon Centola and Michael Macy. Complex contagions and the weakness of long ties. American journal of Sociology, 113(3):702-734, 2007. Google Scholar
  8. John Chalupa, Paul L Leath, and Gary R Reich. Bootstrap percolation on a Bethe lattice. Journal of Physics C: Solid State Physics, 12(1):L31, 1979. Google Scholar
  9. Wei Chen, Tian Lin, Zihan Tan, Mingfei Zhao, and Xuren Zhou. Robust influence maximization. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 795-804. ACM, 2016. Google Scholar
  10. Wei Chen, Yajun Wang, and Siyu Yang. Efficient influence maximization in social networks. In ACM SIGKDD, pages 199-208. ACM, 2009. Google Scholar
  11. Wei Chen, Yifei Yuan, and Li Zhang. Scalable influence maximization in social networks under the linear threshold model. In Data Mining (ICDM), 2010 IEEE 10th International Conference on, pages 88-97. IEEE, 2010. Google Scholar
  12. Aaron Clauset, Cristopher Moore, and Mark EJ Newman. Hierarchical structure and the prediction of missing links in networks. Nature, 453(7191):98, 2008. Google Scholar
  13. Edith Cohen, Daniel Delling, Thomas Pajor, and Renato F Werneck. Sketch-based influence maximization and computation: Scaling up with guarantees. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pages 629-638. ACM, 2014. Google Scholar
  14. James Samuel Coleman, Elihu Katz, and Herbert Menzel. Medical innovation: A diffusion study. Bobbs-Merrill Co, 1966. Google Scholar
  15. Paul DiMaggio. Structural analysis of organizational fields: A blockmodel approach. Research in organizational behavior, 1986. Google Scholar
  16. John W Essam. Percolation theory. Reports on Progress in Physics, 43(7):833, 1980. Google Scholar
  17. Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):7821-7826, 2002. Google Scholar
  18. Jacob Goldenberg, Barak Libai, and Eitan Muller. Using complex systems analysis to advance marketing theory development: Modeling heterogeneity effects on new product growth through stochastic cellular automata. Academy of Marketing Science Review, 9(3):1-18, 2001. Google Scholar
  19. Mark Granovetter. Threshold Models of Collective Behavior. American Journal of Sociology, 83(6):1420-1443, 1978. URL: http://www.journals.uchicago.edu/doi/abs/10.1086/226707.
  20. Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983. Google Scholar
  21. Svante Janson, Tomasz Łuczak, Tatyana Turova, and Thomas Vallier. Bootstrap percolation on the random graph G_N, P. The Annals of Applied Probability, 22(5):1989-2047, 2012. Google Scholar
  22. David Kempe, Jon Kleinberg, and Éva 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, pages 137-146. ACM, 2003. Google Scholar
  23. David Kempe, Jon Kleinberg, and Éva Tardos. Influential nodes in a diffusion model for social networks. In International Colloquium on Automata, Languages, and Programming, pages 1127-1138. Springer, 2005. Google Scholar
  24. Jure Leskovec, Lada A. Adamic, and Bernardo A. Huberman. The dynamics of viral marketing. In EC, pages 228-237, 2006. URL: https://doi.org/10.1145/1134707.1134732.
  25. Qiang Li, Wei Chen, Xiaoming Sun, and Jialin Zhang. Influence Maximization with ε-Almost Submodular Threshold Functions. In NIPS, pages 3804-3814, 2017. Google Scholar
  26. Brendan Lucier, Joel Oren, and Yaron Singer. Influence at Scale: Distributed Computation of Complex Contagion in Networks. In ACM SIGKDD, pages 735-744. ACM, 2015. Google Scholar
  27. John S MacDonald and Leatrice D MacDonald. Chain migration ethnic neighborhood formation and social networks. The Milbank Memorial Fund Quarterly, 42(1):82-97, 1964. Google Scholar
  28. Vijay Mahajan, Eitan Muller, and Frank M Bass. New product diffusion models in marketing: A review and directions for research. In Diffusion of technologies and social behavior, pages 125-177. Springer, 1991. Google Scholar
  29. Elchanan Mossel and Sébastien Roch. Submodularity of Influence in Social Networks: From Local to Global. SIAM J. Comput., 39(6):2176-2188, 2010. URL: https://doi.org/10.1137/080714452.
  30. Elizabeth Levy Paluck, Hana Shepherd, and Peter M Aronow. Changing climates of conflict: A social network experiment in 56 schools. Proceedings of the National Academy of Sciences, 113(3):566-571, 2016. Google Scholar
  31. Daniel M Romero, Brendan Meeder, and Jon Kleinberg. Differences in the Mechanics of Information Diffusion Across Topics : Idioms , Political Hashtags , and Complex Contagion on Twitter. In WWW, pages 695-704. ACM, 2011. URL: http://dl.acm.org/citation.cfm?id=1963503.
  32. Grant Schoenebeck and Biaoshuai Tao. Beyond Worst-Case (In)approximability of Nonsubmodular Influence Maximization. In International Conference on Web and Internet Economics, pages 368-382. Springer, 2017. Google Scholar
  33. Grant Schoenebeck and Biaoshuai Tao. Beyond worst-case (in) approximability of nonsubmodular influence maximization. ACM Transactions on Computation Theory (TOCT), 11(3):12, 2019. Google Scholar
  34. Grant Schoenebeck and Biaoshuai Tao. Influence Maximization on Undirected Graphs: Towards Closing the (1-1/e) Gap. In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019., pages 423-453, 2019. URL: https://doi.org/10.1145/3328526.3329650.
  35. Gordon Tullock. Toward a theory of the rent-seeking society, chapter Efficient rent seeking,(pp. 112), 1980. Google Scholar
  36. Harrison C White, Scott A Boorman, and Ronald L Breiger. Social structure from multiple networks. I. Blockmodels of roles and positions. American journal of sociology, 81(4):730-780, 1976. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact