Yaron Singer
Skip Abstract Section
Abstract
In this monograph we survey the adaptive seeding methodology for influence maximization. Influence maximization is the challenge of spreading information effectively through influential users in a social network. In many applications, one is restricted to select influencers from a set of users who engaged with the topic being promoted, and due to the structure of social networks, these users often rank low in terms of their influence potential. An alternative approach one can consider is an adaptive method which selects users in a manner which targets their influential neighbors. The advantage of such an approach is that it leverages the friendship paradox in social networks: while users are often not influential themselves, they know someone who is.
Adaptive seeding is a two-stage stochastic optimization framework, designed to leverage the friendship paradox to seed high influential nodes. This framework encompasses a rich set of algorithmic challenges at the intersection of stochastic optimization and submodular optimization. We discuss this method here, along with algorithmic approaches, the friendship paradox in random graph models, and experiments on adaptive seeding.
- Abraham, I., Chechik, S., Kempe, D., and Slivkins, A. 2013. Low-distortion inference of latent similarities from a multiplex social network. In SODA. 1853--1872. Google Scholar
Digital Library
- Ageev, A. A. and Sviridenko, M. 2004. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 8, 3.Google ScholarCross Ref
- Aiello, W., Chung, F., and Lu, L. 2000. A random graph model for power law graphs. In Symposium on Theory of Computing (STOC). Google ScholarDigital Library
- Badanidiyuru, A., Papadimitriou, C. H., Rubinstein, A., Seeman, L., and Singer, Y. 2016. Locally adaptive optimization: Adaptive seeding for monotone submodular functions. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016. 414--429. Google ScholarDigital Library
- Bakshy, E., Hofman, J. M., Mason, W. A., and Watts, D. J. 2011. Everyone's an influencer: quantifying influence on twitter. In WSDM. Google ScholarDigital Library
- Barabasi, A. L. and Albert, R. 1999. Emergence of scaling in random networks. Science 286, 509--512.Google ScholarCross Ref
- Bollobás, B. 1980. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin..Google Scholar
- Borgs, C., Brautbar, M., Chayes, J., and Lucier, B. 2012. Influence maximization in social networks: Towards an optimal algorithmic solution. arXiv preprint arXiv: 1212.0884.Google Scholar
- Calinescu, G., Chekuri, C., Pál, M., and Vondrák, J. 2011. Maximizing a submodular set function subject to a matroid constraint. SIAM J. Commuting 40, 6. Google ScholarDigital Library
- Chen, N. 2008. On the approximability of influence in social networks. In SODA. Google ScholarDigital Library
- Domingos, P. and Richardson, M. 2001. Mining the network value of customers. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD). 57--66. Google ScholarDigital Library
- Du, N., Song, L., Gomez-Rodriguez, M., and Zha, H. 2013. Scalable influence estimation in continuous-time diffusion networks. In NIPS '13: Advances in Neural Information Processing Systems. Google ScholarDigital Library
- Dughmi, S., Roughgarden, T., and Yan, Q. 2011. From convex optimization to randomized mechanisms: toward optimal combinatorial auctions. In STOC. 149--158. Google ScholarDigital Library
- Even-Dar, E. and Shapira, A. 2011. A note on maximizing the spread of influence in social networks. Information Processing Letters 111, 4, 184--187. Google ScholarDigital Library
- Feige, U. 1998. A threshold of ln n for approximating set cover. Journal of the ACM 45, 4, 634--652. Google ScholarDigital Library
- Feld, S. 1991. Why your friends have more friends than you do. American Journal of Sociology.Google Scholar
- Gomez-Rodriguez, M., Leskovec, J., and Krause, A. 2010. Inferring networks of diffusion and influence. In KDD. Google ScholarDigital Library
- Gomez-Rodriguez, M., Leskovec, J., and Schölkopf, B. 2013. Modeling information propagation with survival theory. In ICML.Google Scholar
- Granovetter, M. 1978. Threshold models of collective behavior. The American Journal of Sociology 83, 6, 1420--1443.Google ScholarCross Ref
- Granovetter, M. 1983. The strength of weak ties: A network theory revisited. Sociological Theory 1.Google Scholar
- Hodas, N. O., Kooti, F., and Lerman, K. 2013. Friendship paradox redux: Your friends are more interesting than you. CoRR abs/1304.3480.Google Scholar
- Holley, R. A. and Liggett, T. M. 1975. Ergodic Theorems for Weakly Interacting Infinite Systems and the Voter Model. The Annals of Probability 3, 4, 643--663.Google ScholarCross Ref
- Horel, T. and Singer, Y. 2015. Scalable methods for adaptively seeding a social network. In Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy, May 18-22, 2015. 441--451. Google ScholarDigital Library
- Kempe, D., Kleinberg, J., and Tardos, E. 2003. Maximizing the spread of influence through a social network. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD). Google ScholarDigital Library
- Kleinberg, J. 2000. The small-world phenomenon: An algorithmic perspective. In Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing. STOC '00. ACM, New York, NY, USA, 163--170. Google ScholarDigital Library
- Lattanzi, S. and Singer, Y. 2015. The friendship paradox in power law networks.Google Scholar
- Leskovec, J., Adamic, L. A., and Huberman, B. A. 2006. The dynamics of viral marketing. In ACM Conference on Electronic Commerce. Google ScholarDigital Library
- Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., vanBriesen, J. M., and Glance, N. S. 2007. Cost-effective outbreak detection in networks. In KDD. Google ScholarDigital Library
- Leskovec, J. and Sosič, R. 2014. SNAP: A general purpose network analysis and graph mining library in C++. http://snap.stanford.edu/snap.Google Scholar
- Mathioudakis, M., Bonchi, F., Castillo, C., Gionis, A., and Ukkonen, A. 2011. Sparsification of influence networks. In KDD. Google ScholarDigital Library
- Mitzenmacher, M. 2004. A brief history of generative models for power law and lognormal distributions. Internet mathematics 1 (2).Google Scholar
- Mossel, E. and Roch, S. 2007. On the submodularity of influence in social networks. In STOC. Google ScholarDigital Library
- Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. 1978. An analysis of approximations for maximizing submodular set functions ii. Math. Programming Study 8.Google Scholar
- Newman, M. 2003. The structure and function of complex networks. SIAM review 45, 2, 167--256.Google Scholar
- Richardson, M. and Domingos, P. 2002. Mining knowledge-sharing sites for viral marketing. In KDD. 61--70. Google ScholarDigital Library
- Rubinstein, A., Seeman, L., and Singer, Y. 2015. Approximability of adaptive seeding under knapsack constraints. In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, Portland, OR, USA, June 15-19, 2015. 797--814. Google ScholarDigital Library
- Santos, F. and Lenaerts, J. P. T. 2006. Evolutionary dynamics of social dilemmas in structured heterogeneous populations. PNAS.Google Scholar
- Schelling, T. C. 1978. Micromotives and Macrobehavior. Norton.Google Scholar
- Seeman, L. and Singer, Y. 2013. Adaptive seeding in social networks. In IEEE Symposium on Foundations of Computer Science (FOCS). Google ScholarDigital Library
- Singer, Y. 2012. How to win friends and influence people, truthfully: influence maximization mechanisms for social networks. In WSDM. 733--742. Google ScholarDigital Library
- Ugander, J., Karrer, B., Backstrom, L., and Marlow, C. 2011. The anatomy of the facebook social graph. CoRR abs/1111.4503.Google Scholar
- Viger, F. and Latapy, M. 2005. Efficient and simple generation of random simple connected graphs with prescribed degree sequence. In Proceedings of the 11th Annual International Conference on Computing and Combinatorics. COCOON'05. Springer-Verlag, Berlin, Heidelberg, 440--449.Google Scholar
- Vondrák, J., Chekuri, C., and Zenklusen, R. 2011. Submodular function maximization via the multilinear relaxation and contention resolution schemes. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing. STOC '11. ACM, New York, NY, USA, 783--792. Google ScholarDigital Library
- Watts, D. and Strogatz, S. 1998. Collective dynamics of 'small-world' networks. Nature 393.Google Scholar
- Yang, J. and Counts, S. 2010. Predicting the speed, scale, and range of information diffusion in twitter. In ICWSM.Google Scholar
Index Terms
- Influence maximization through adaptive seeding
Recommendations
Adaptive Seeding in Social Networks
FOCS '13: Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer ScienceThe algorithmic challenge of maximizing information diffusion through word-of-mouth processes in social networks has been heavily studied in the past decade. While there has been immense progress and an impressive arsenal of techniques has been ...
Influence Maximization in Online Social Networks
WSDM '18: Proceedings of the Eleventh ACM International Conference on Web Search and Data MiningStarting with the earliest studies showing that the spread of new trends, information, and innovations is closely related to the social influence exerted on people by their social networks, the research on social influence theory took off, providing ...
Influence Maximization Revisited
Databases Theory and ApplicationsAbstractInfluence Maximization (IM) has been extensively studied, which is to select a set of k seed users from a social network to maximize the expected number of influenced users in the social network. There are many approaches proposed under a cascade ...
Comments