ABSTRACT
In recent years, social networking platforms have developed into extraordinary channels for spreading and consuming information. Along with the rise of such infrastructure, there is continuous progress on techniques for spreading information effectively through influential users. 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, they often know someone who is. Despite the various complexities in such optimization problems, we show that scalable adaptive seeding is achievable. In particular, we develop algorithms for linear influence models with provable approximation guarantees that can be gracefully parallelized. To show the effectiveness of our methods we collected data from various verticals social network users follow. For each vertical, we collected data on the users who responded to a certain post as well as their neighbors, and applied our methods on this data. Our experiments show that adaptive seeding is scalable, and importantly, that it obtains dramatic improvements over standard approaches of information dissemination.
- https://projects.coin-or.org/Clp.Google Scholar
- A. A. Ageev and M. Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Comb. Optim., 8(3):307--328, 2004.Google ScholarCross Ref
- E. Bakshy, J. M. Hofman, W. A. Mason, and D. J. Watts. Everyone's an influencer: quantifying influence on twitter. In WSDM, 2011. Google ScholarDigital Library
- C. Borgs, M. Brautbar, J. Chayes, and B. Lucier. Maximizing social influence in nearly optimal time. In SODA, volume 14. SIAM, 2014. Google ScholarDigital Library
- N. Chen. On the approximability of influence in social networks. In SODA, pages 1029--1037, 2008. Google ScholarDigital Library
- J. Cheng, L. Adamic, P. A. Dow, J. M. Kleinberg, and J. Leskovec. Can cascades be predicted? WWW '14, pages 925--936, New York, NY, USA, 2014. ACM. Google ScholarDigital Library
- P. Domingos and M. Richardson. Mining the network value of customers. In KDD, pages 57--66, 2001. Google ScholarDigital Library
- E. Even-Dar and A. Shapira. A note on maximizing the spread of influence in social networks. In WINE, pages 281--286, 2007. Google ScholarDigital Library
- S. L. Feld. Why your friends have more friends than you do. American Journal of Sociology, pages 1464--1477, 1991.Google ScholarCross Ref
- S. Goel, D. J. Watts, and D. G. Goldstein. The structure of online diffusion networks. In EC '12, Valencia, Spain, June 4-8, 2012, pages 623--638, 2012. Google ScholarDigital Library
- D. Golovin and A. Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42(1):427--486, 2011. Google ScholarDigital Library
- R. A. Holley and T. M. Liggett. Ergodic theorems for weakly interacting infinite systems and the voter model. The annals of probability, pages 643--663, 1975.Google Scholar
- T. Horel and Y. Singer. Scalable methods for adaptively seeding a social network. CoRR, abs/1503.01438, 2015. Google ScholarDigital Library
- D. Kempe, J. M. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In KDD, pages 137--146, 2003. Google ScholarDigital Library
- D. Kempe, J. M. Kleinberg, and E. Tardos. Influential nodes in a diffusion model for social networks. In ICALP, pages 1127--1138, 2005. Google ScholarDigital Library
- A. J. Kleywegt, A. Shapiro, and T. Homem-de Mello. The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2):479--502, 2002. Google ScholarDigital Library
- R. Kumar, B. Moseley, S. Vassilvitskii, and A. Vattani. Fast greedy algorithms in mapreduce and streaming. In G. E. Blelloch and B. Vocking, editors, SPAA 2013, pages 1--10. ACM, 2013. Google ScholarDigital Library
- S. Lattanzi and Y. Singer. The power of random neighbors in social networks. WSDM, 2015. Google ScholarDigital Library
- J. Leskovec, D. Chakrabarti, J. M. Kleinberg, and C. Faloutsos. Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication. In PKDD 2005, volume 3721 of Lecture Notes in Computer Science, pages 133--145. Springer, 2005. Google ScholarDigital Library
- J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. M. VanBriesen, and N. S. Glance. Cost-effective outbreak detection in networks. In KDD, pages 420--429, 2007. Google ScholarDigital Library
- J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.Google Scholar
- M. Mathioudakis, F. Bonchi, C. Castillo, A. Gionis, and A. Ukkonen. Sparsification of influence networks. In KDD, 2011. Google ScholarDigital Library
- E. Mossel and S. Roch. On the submodularity of influence in social networks. In STOC, pages 128--134, 2007. Google ScholarDigital Library
- G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions|i. Mathematical Programming, 14(1):265--294, 1978.Google ScholarDigital Library
- M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In KDD, pages 61--70, 2002. Google ScholarDigital Library
- M. Richardson and P. Domingos. Mining knowledge-sharing sites for viral marketing. In KDD, pages 61--70. ACM, 2002. Google ScholarDigital Library
- L. Seeman and Y. Singer. Adaptive seeding in social networks. In FOCS, 2013. Google ScholarDigital Library
- J. Vondrak, C. Chekuri, and R. Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. In STOC, pages 783--792. ACM, 2011. Google ScholarDigital Library
- J. Yang and S. Counts. Predicting the speed, scale, and range of information diffusion in twitter. In ICWSM, 2010.Google ScholarCross Ref
- T. R. Zaman, R. Herbrich, J. V. Gael, and D. Stern. Predicting information spreading in twitter, 2010.Google Scholar
Index Terms
- Scalable Methods for Adaptively Seeding a Social Network
Recommendations
Scalable Methods for Adaptively Seeding a Social Network
WWW '15 Companion: Proceedings of the 24th International Conference on World Wide WebIn many applications of influence maximization, 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 ...
A Bio-Inspired Defensive Rumor Confinement Strategy in Online Social Networks
Online social networks (OSNs) are used to connect people and propagate information around the globe. Along with information propagation, rumors also penetrate across the OSNs in a massive order. Controlling the rumor propagation is utmost important to ...
Social media analytics: tracking, modeling and predicting the flow of information through networks
WWW '11: Proceedings of the 20th international conference companion on World wide webOnline social media represent a fundamental shift of how information is being produced, transferred and consumed. User generated content in the form of blog posts, comments, and tweets establishes a connection between the producers and the consumers of ...
Comments