Maximizing the Spread of Influence through a Social Network

by David Kempe, Jon Kleinberg, and Éva Tardos

Theory of Computing, Volume 11(4), pp. 105-147, 2015

Bibliography with links to cited articles

[1]   Nima Ahmadi Pour Anari, Shayan Ehsani, Mohammad Ghodsi, Nima Haghpanah, Nicole Immorlica, Hamid Mahini, and Vahab S. Mirrokni: Equilibrium pricing with positive externalities. Theor. Comput. Sci., 476:1–15, 2013. Preliminary version in WINE’10. [doi:10.1016/j.tcs.2013.01.014]

[2]   Hessameddin Akhlaghpour, Mohammad Ghodsi, Nima Haghpanah, Hamid Mahini, Vahab S. Mirrokni, and Afshin Nikzad: Optimal iterative pricing over social networks. In Proc. 6th Workshop on Internet and Network Economics (WINE’10), pp. 415–423, 2010. [doi:10.1007/978-3-642-17572-5_34]

[3]   Réka Albert, Hawoong Jeong, and Albert-László Barabási: Error and attack tolerance of complex networks. Nature, 406(406):378–382, 2000. [doi:10.1038/35019019]

[4]   Noga Alon, Michal Feldman, Ariel D. Procaccia, and Moshe Tennenholtz: A note on competitive diffusion through social networks. Inform. Process. Lett., 110(4):221–225, 2010. [doi:10.1016/j.ipl.2009.12.009]

[5]   David Arthur, Rajeev Motwani, Aneesh Sharma, and Ying Xu: Pricing strategies for viral marketing on social networks. In Proc. 5th Workshop on Internet and Network Economics (WINE’09), pp. 101–112, 2009. [doi:10.1007/978-3-642-10841-9_11, arXiv:0902.3485]

[6]   Chalee Asavathiratham: The Influence Model: A Tractable Representation for the Dynamics of Networked Markov Chains. Ph. D. thesis, Massachusetts Institute of Technology, 2001. Available at MIT DSPACE, Subsequent paper available at IEEE Control Systems.

[7]   Chalee Asavathiratham, Sandip Roy, Bernard C. Lesieutre, and George C. Verghese: The influence model. IEEE Comp. Soc. Press, 21(6):52–64, 2001. [doi:10.1109/37.969135]

[8]   Frank M. Bass: A new product growth model for consumer durables. Management Science, 15(5):215–227, 1969. [doi:10.1287/mnsc.1040.0264]

[9]   Eli Berger: Dynamic monopolies of constant size. J. Combin. Theory Ser. B, 83(2):191–200, 2001. [doi:10.1006/jctb.2001.2045]

[10]   Shishir Bharathi, David Kempe, and Mahyar Salek: Competitive influence maximization in social networks. In Proc. 3rd Workshop on Internet and Network Economics (WINE’07), pp. 306–311, 2007. [doi:10.1007/978-3-540-77105-0_31]

[11]   Lawrence E. Blume: The statistical mechanics of strategic interaction. Games and Economic Behavior, 5(3):387–424, 1993. [doi:10.1006/game.1993.1023]

[12]   Christian Borgs, Michael Brautbar, Jennifer Chayes, and Brendan Lucier: Maximizing social influence in nearly optimal time. In Proc. 25th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’14), pp. 946–957, 2014. [doi:10.1137/1.9781611973402.70]

[13]   Allan Borodin, Yuval Filmus, and Joel Oren: Threshold models for competitive influence in social networks. In Proc. 6th Workshop on Internet and Network Economics (WINE’10), pp. 539–550, 2010. [doi:10.1007/978-3-642-17572-5_48]

[14]   Jacqueline J. Brown and Peter H. Reinegen: Social ties and word-of-mouth referral behavior. Journal of Consumer Research, 14(3):350–362, 1987. [doi:10.1086/209118]

[15]   Ceren Budak, Divyakant Agrawal, and Amr El Abbadi: Limiting the spread of misinformation in social networks. In 20th Internat. World Wide Web Conf. (WWW’11), pp. 665–674, 2011. [doi:10.1145/1963405.1963499]

[16]   Tim Carnes, Chandrashekar Nagarajan, Stefan M. Wild, and Anke van Zuylen: Maximizing influence in a competitive social network: A follower’s perspective. In Proc. Internat. Conf. on Electronic Commerce (ICEC), pp. 351–360, 2007. [doi:10.1145/1282100.1282167]

[17]   Ning Chen: On the approximability of influence in social networks. SIAM J. Discr. Math., 23(3):1400–1415, 2009. Conference version in SODA’08. [doi:10.1137/08073617X]

[18]   Wei Chen, Alex Collins, Rachel Cummings, Te Ke, Zhenming Liu, David Rincon, Xiaorui Sun, Yajun Wang, Wei Wei, and Yifei Yuan: Influence maximization in social networks when negative opinions may emerge and propagate. In Proc. 11th SIAM Internat. Conf. on Data Mining (SDM’11), pp. 379–390, 2011. [doi:10.1137/1.9781611972818.33]

[19]   Wei Chen, Laks V.S. Lakshmanan, and Carlos Castillo: Information and Influence Propagation in Social Networks. Synthesis Lectures on Data Management. Morgan & Claypool, 2013. [doi:10.2200/S00527ED1V01Y201308DTM037]

[20]   Wei Chen, Yajun Wang, and Siyu Yang: Efficient influence maximization in social networks. In Proc. 15th Internat. Conf. on Knowledge Discovery and Data Mining (KDD’09), pp. 199–208, 2009. [doi:10.1145/1557019.1557047]

[21]   Wei Chen, Yifei Yuan, and Li Zhang: Scalable influence maximization in social networks under the linear threshold model. In Proc. 10th Internat. Conf. on Data Mining (ICDM’12), pp. 88–97, 2010. [doi:10.1109/ICDM.2010.118]

[22]   Peter Clifford and Aidan Sudbury: A model for spatial conflict. Biometrika, 60(3):581–588, 1973. [doi:10.1093/biomet/60.3.581]

[23]   James S. Coleman, Herbert Menzel, and Elihu Katz: Medical Innovations: A Diffusion Study. Bobbs Merrill, 1966.

[24]   Gérard Cornuéjols, Marshall L. Fisher, and George L. Nemhauser: Location of bank accounts to optimize float. Management Science, 23(8):789–810, 1977. [doi:10.1287/mnsc.23.8.789]

[25]    Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, David L. Malec, S. Raghavan, Anshul Sawant, and Morteza Zadimoghadam: How to influence people with partial incentives. In 23rd Internat. World Wide Web Conf. (WWW’14), pp. 937–948, 2014. [doi:10.1145/2566486.2568039, arXiv:1401.7970]

[26]   Pedro Domingos and Matthew Richardson: Mining the network value of customers. In Proc. 7th Internat. Conf. on Knowledge Discovery and Data Mining (KDD’01), pp. 57–66, 2001. [doi:10.1007/978-3-540-77105-0_27]

[27]   Pradeep Dubey, Rahul Garg, and Bernard de Meyer: Competing for customers in a social network: The quasi-linear case. In Proc. 2nd Workshop on Internet and Network Economics (WINE’06), pp. 162–173, 2006. [doi:10.1007/11944874_16]

[28]   Richard Durrett: Lecture Notes on Particle Systems and Percolation. Wadsworth Publishing, 1988.

[29]   Glenn Ellison: Learning, local interaction, and coordination. Econometrica, 61(5):1047–1071, 1993. [doi:10.2307/2951493]

[30]   Eyal Even-Dar and Asaf Shapira: A note on maximizing the spread of influence in social networks. Inform. Process. Lett., 111(4):184–187, 2011. Preliminary version in WINE’11. [doi:10.1016/j.ipl.2010.11.015]

[31]   Uriel Feige: A threshold of lnn for approximating set cover. J. ACM, 45(4):634–652, 1998. Preliminary version in STOC’96. [doi:10.1145/285055.285059]

[32]   Jacob Goldenberg, Barak Libai, and Eitan Muller: Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters, 12(3):211–223, 2001. [doi:10.1023/A:1011122126881]

[33]   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, 2001.

[34]   Manuel Gomez-Rodriguez, David Balduzzi, and Bernhard Schölkopf: Uncovering the temporal dynamics of diffusion networks. In Proc. 28th Int. Conf. on Machine Learning (ICML’11), pp. 561–568, 2011. [arXiv:1105.0697]

[35]   Manuel Gomez-Rodriguez, Jure Leskovec, and Andrease Krause: Inferring networks of diffusion and influence. ACM Transactions on Knowledge Discovery from Data (TKDD), 5(4):21, 2012. Preliminary version in KDD’10. [doi:10.1145/2086737.2086741]

[36]   Manuel Gomez-Rodriguez and Bernhard Schölkopf: Submodular inference of diffusion networks from multiple trees. In Proc. 29th Int. Conf. on Machine Learning (ICML’12), 2012. Available at ICML. [arXiv:1205.1671]

[37]   Amit Goyal, Francesco Bonchi, and Laks V. S. Lakshmanan: Learning influence probabilities in social networks. In Proc. 3rd ACM Internat. Conf. on Web Search and Data Mining (WSDM’10), pp. 241–250, 2010. [doi:10.1145/1718487.1718518]

[38]   Amit Goyal, Wei Lu, and Laks V. S. Lakshmanan: CELF++: Optimizing the greedy algorithm for influence maximization in social networks. In 20th Internat. World Wide Web Conf. (WWW’11), pp. 47–48, 2011. [doi:10.1145/1963192.1963217]

[39]   Amit Goyal, Wei Lu, and Laks V. S. Lakshmanan: SIMPATH: An efficient algorithm for influence maximization under the linear threshold model. In Proc. 11th Internat. Conf. on Data Mining (ICDM’11), pp. 211–220, 2011. [doi:10.1109/ICDM.2011.132]

[40]   Sanjeev Goyal, Hoda Heidari, and Michael Kearns: Competitive contagion in networks. Games and Economic Behavior, 2014 (online). Preliminary version in STOC’12. [doi:10.1016/j.geb.2014.09.002]

[41]   Mark Granovetter: Threshold models of collective behavior. American Journal of Sociology, 83(6):1420–1443, 1978. [doi:10.1086/226707]

[42]   Dilek Günneç: Integrating Social Network Effects in Product Design and Diffusion. Ph. D. thesis, University of Maryland, 2012. Available at DRUM.

[43]   Nima Haghpanah, Nicole Immorlica, Vahab S. Mirrokni, and Kamesh Munagala: Optimal auctions with positive network externalities. ACM Trans. Economics and Comput., 1(2):13, 2013. Conference version in EC’11. [doi:10.1145/2465769.2465778]

[44]   Venky Harinarayan, Anand Rajaraman, and Jeffrey D. Ullman: Implementing data cubes efficiently. In Proc. 16th ACM SIGMOD Internat. Conf. on Managment of Data, pp. 205–216, 1996. [doi:10.1145/233269.233333]

[45]   Jason D. Hartline, Vahab S. Mirrokni, and Mukund Sundararajan: Optimal marketing strategies over social networks. In 17th Internat. World Wide Web Conf. (WWW’08), pp. 189–198, 2008. [doi:10.1145/1367497.1367524]

[46]   Xinran He and David Kempe: Price of anarchy for the n-player competitive cascade game with submodular activation functions. In Proc. 9th Workshop on Internet and Network Economics (WINE’13), pp. 232–248, 2013. [doi:10.1007/978-3-642-45046-4_20]

[47]   Xinran He, Guojie Song, Wei Chen, and Qingye Jiang: Influence blocking maximization in social networks under the competitive linear threshold model. In Proc. 12th SIAM Internat. Conf. on Data Mining (SDM’12), pp. 463–474, 2012. [doi:10.1137/1.9781611972825.40, arXiv:1110.4723]

[48]   Richard A. Holley and Thomas M. Liggett: Ergodic theorems for weakly interacting infinite systems and the voter model. Annals of Probability, 3(4):643–663, 1975. Available at Project Euclid.

[49]   Qingye Jiang, Guojie Song, Gao Cong, Yu Wang, Wenjun Si, and Kunqing Xie: Simulated annealing based influence maximization in social networks. In Proc. 26th AAAI Conf. on Artificial Intelligence, 2011. Available at AAAI.

[50]   Kyomin Jung, Wooram Heo, and Wei Chen: IRIE: Scalable and robust influence maximization in social networks. In Proc. 12th Internat. Conf. on Data Mining (ICDM’12), pp. 918–923, 2012. [doi:10.1109/ICDM.2012.79]

[51]   David Kempe, Jon Kleinberg, and Éva Tardos: Maximizing the spread of influence in a social network. In Proc. 9th Internat. Conf. on Knowledge Discovery and Data Mining (KDD’03), pp. 137–146, 2003. [doi:10.1145/956750.956769]

[52]   David Kempe, Jon Kleinberg, and Éva Tardos: Influential nodes in a diffusion model for social networks. In Proc. 32th Internat. Colloq. on Automata, Languages and Programming (ICALP’05), pp. 1127–1138, 2005. [doi:10.1007/11523468_91]

[53]   Masahiro Kimura and Kazumi Saito: Tractable models for information diffusion in social networks. In Proc. 10th European Conf. on Principles and Practice of Knowledge Discovery in Databases (PKDD’06), pp. 259–271, 2006. [doi:10.1007/11871637_27]

[54]   Andreas Krause and Daniel Golovin: Submodular function maximization. In Lucas Bordeaux, Youssef Hamadi, and Pushmeet Kohli, editors, Tractability: Practical Approaches to Hard Problems, pp. 71–104. Cambridge University Press, 2014.

[55]   Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie S. Glance: Cost-effective outbreak detection in networks. In Proc. 13th Internat. Conf. on Knowledge Discovery and Data Mining (KDD’07), pp. 420–429, 2007. [doi:10.1145/1281192.1281239]

[56]   Thomas M. Liggett: Interacting Particle Systems. Springer, 1985.

[57]   Michael Macy: Chains of cooperation: Threshold effects in collective action. American Sociological Review, 56(6):730–747, 1991. [doi:10.2307/2096252]

[58]   Michael Macy and Robert Willer: From factors to actors: Computational sociology and agent-based modeling. Annual Review of Sociology, 28:143–166, 2002. [doi:10.1146/annurev.soc.28.110601.141117]

[59]   Vijay Mahajan, Eitan Muller, and Frank M. Bass: New product diffusion models in marketing: A review and directions for research. Journal of Marketing, 54(1):1–26, 1990.

[60]   Colin McDiarmid: Concentration. In Michel Habib, Colin McDiarmid, Jorge Ramirez-Alfonsin, and Bruce Reed, editors, Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 195–247. Springer, 1998. [doi:10.1007/978-3-662-12788-9_6]

[61]   Stephen Morris: Contagion. Review of Economic Studies, 67(1):57–78, 2000. [doi:10.1111/1467-937X.00121]

[62]   Elchanan Mossel and Sebastien Roch: Submodularity of influence in social networks: From local to global. SIAM J. Comput., 39(6):2176–2188, 2010. Preliminary version in STOC’07. [doi:10.1137/080714452]

[63]   Seth A. Myers and Jure Leskovec: On the convexity of latent social network inference. In Proc. 22nd Advances in Neural Information Processing Systems Conf. (NIPS’10), pp. 1741–1749, 2010. Available at ML Repository. [arXiv:1010.5504]

[64]   George L. Nemhauser and Laurence A. Wolsey: Integer and Combinatorial Optimization. Wiley, 1988.

[65]   George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher: An analysis of the approximations for maximizing submodular set functions—I. Mathematical Programming, 14(1):265–294, 1978. [doi:10.1007/BF01588971]

[66]   Mark E. J. Newman: The structure of scientific collaboration networks. Proc. Natl. Acad. Sci. USA, 98(2):404–409, 2001. [doi:10.1073/pnas.98.2.404]

[67]   David Peleg: Local majorities, coalitions and monopolies in graphs: a review. Theoret. Comput. Sci., 282(2):231–257, 2002. Preliminary version in SIROCCO’96. [doi:10.1016/S0304-3975(01)00055-X]

[68]   Matthew Richardson and Pedro Domingos: Mining knowledge-sharing sites for viral marketing. In Proc. 8th Internat. Conf. on Knowledge Discovery and Data Mining (KDD’02), pp. 61–70, 2002. [doi:10.1145/775047.775057]

[69]   Everett Rogers: Diffusion of Innovations. Free Press, 4th edition, 1995.

[70]   Eldar Sadikov, Montserrat Medina, Jure Leskovec, and Hector Garcia-Molina: Correcting for missing data in information cascades. In Proc. 4th ACM Internat. Conf. on Web Search and Data Mining (WSDM’11), pp. 55–64, 2011. [doi:10.1145/1935826.1935844]

[71]   Kazumi Saito, Masahiro Kimura, Kouzou Ohara, and Hiroshi Motoda: Selecting information diffusion models over social networks for behavioral analysis. In Proc. European Conf. on Machine Learning and Knowledge Discovery in Databases: Part III (ECML/PKDD’10), volume 6323 of LNCS, pp. 180–195. Springer, 2010. [doi:10.1007/978-3-642-15939-8_12]

[72]   Kazumi Saito, Ryohei Nakano, and Masahiro Kimura: Prediction of information diffusion probabilities for independent cascade model. In Proc. 12th Internat. Conf. on Knowledge-Based and Intelligent Information & Engineering Systems (KES’08), volume 5179 of LNCS, pp. 67–75. Springer, 2008. [doi:10.1007/978-3-540-85567-5_9]

[73]   Mahyar Salek, Shahin Shayandeh, and David Kempe: You share, I share: Network effects and economic incentives in P2P file-sharing systems. In Proc. 6th Workshop on Internet and Network Economics (WINE’10), pp. 354–365, 2010. [doi:10.1007/978-3-642-17572-5_29, arXiv:1107.5559]

[74]   Thomas Schelling: Micromotives and Macrobehavior. Norton, 1978.

[75]   Lior Seeman and Yaron Singer: Adaptive seeding in social networks. In Proc. 54th FOCS, pp. 459–468. IEEE Comp. Soc. Press, 2013. [doi:10.1109/FOCS.2013.56]

[76]   Yaron Singer: How to win friends and influence people, truthfully: Influence maximization mechanisms for social networks. In Proc. 5th ACM Internat. Conf. on Web Search and Data Mining (WSDM’12), pp. 733–742, 2012. [doi:10.1145/2124295.2124381]

[77]   Jason Tsai, Thanh H. Nguyen, and Milind Tambe: Security games for controlling contagion. In Proc. 27th AAAI Conf. on Artificial Intelligence (AAAI’12), pp. 1464–1470, 2012. Available at AAAI.

[78]   Vasileios Tzoumas, Christos Amanatidis, and Evangelos Markakis: A game-theoretic analysis of a competitive diffusion process over social networks. In Proc. 8th Workshop on Internet and Network Economics (WINE’12), pp. 1–14, 2012. [doi:10.1007/978-3-642-35311-6_1]

[79]   Thomas W. Valente: Network Models of the Diffusion of Innovations. Hampton Press, 1995. Available at Springer.

[80]   Adrian Vetta: Nash equlibria in competitive societies with applications to facility location, traffic routing and auctions. In Proc. 43rd FOCS, pp. 416–425. IEEE Comp. Soc. Press, 2002. [doi:10.1109/SFCS.2002.1181966]

[81]   Chi Wang, Wei Chen, and Yajun Wang: Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery Journal, 25(3):545–576, 2012. Preliminary version in KDD’10. [doi:10.1007/s10618-012-0262-1]

[82]   Yu Wang, Gao Cong, Guojie Song, and Kunqing Xie: Community-based greedy algorithm for mining top-k influential nodes in mobile social networks. In Proc. 16th Internat. Conf. on Knowledge Discovery and Data Mining (KDD’10), pp. 1039–1048, 2010. [doi:10.1145/1835804.1835935]

[83]   Stanley S. Wasserman and Katherine Faust: Social Network Analysis. Cambridge University Press, 1994.

[84]   Duncan J. Watts: A simple model of global cascades in random networks. Proc. Natl. Acad. Sci. USA, 99(9):5766–5771, 2002. [doi:10.1073/pnas.082090499]

[85]   H. Peyton Young: Individual Strategy and Social Structure: An Evolutionary Theory of Institutions. Princeton University Press, 1998.

[86]   H. Peyton Young: The diffusion of innovations in social networks. Technical Report 02-14-018, Santa Fe Institute Working Paper, 2002. Available at IDEAS.