Document Open Access Logo

Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network

Authors Gianlorenzo D'Angelo, Lorenzo Severini, Yllka Velaj

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.75.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Gianlorenzo D'Angelo
Lorenzo Severini
Yllka Velaj

Cite As Get BibTex

Gianlorenzo D'Angelo, Lorenzo Severini, and Yllka Velaj. Selecting Nodes and Buying Links to Maximize the Information Diffusion in a Network. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 75:1-75:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.75

Abstract

The Independent Cascade Model (ICM) is a widely studied model that aims to capture the dynamics of the information diffusion in social networks and in general complex networks. In this model, we can distinguish between active nodes which spread the information and inactive ones. The process starts from a set of initially active nodes called seeds. Recursively, currently active nodes can activate their neighbours according to a probability distribution on the set of edges. After a certain number of these recursive cycles, a large number of nodes might become active. The process terminates when no further node gets activated.
Starting from the work of Domingos and Richardson [Domingos et al. 2001], several studies have been conducted with the aim of shaping a given diffusion process so as to maximize the number of activated nodes at the end of the process. One of the most studied problems has been formalized by Kempe et al. and consists in finding a set of initial seeds that maximizes the expected number of active nodes under a budget constraint [Kempe et al. 2003].
In this paper we study a generalization of the problem of Kempe et al. in which we are allowed to spend part of the budget to create new edges incident to the seeds. That is, the budget can be spent to buy seeds or edges according to a cost function. The problem does not admin a PTAS, unless P=NP. We propose two approximation algorithms: the former one gives an approximation ratio that depends on the edge costs and increases when these costs are high; the latter algorithm gives a constant approximation guarantee which is greater than that of the first algorithm when the edge costs can be small.

Subject Classification

Keywords
  • Approximation algorithms
  • information diffusion
  • complex networks
  • independent cascade model
  • network augmentation

Metrics

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

References

  1. C. Asavathiratham, S. Roy, B. Lesieutre, and G. Verghese. The influence model. IEEE Control Systems, 21(6):52-64, 2001. Google Scholar
  2. Eytan Bakshy, Jake M. Hofman, Winter A. Mason, and Duncan J. Watts. Everyone’s an influencer: Quantifying influence on twitter. In Proc. of the 4th ACM International Conference on Web Search and Data Mining, WSDM11, pages 65-74. ACM, 2011. Google Scholar
  3. Frank M Bass. A new product growth for model consumer durables. Management science, 15(5):215-227, 1969. Google Scholar
  4. Wei Chen, Chi Wang, and Yajun Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proc. of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD10, 2010. Google Scholar
  5. James S. Coleman, Elihu Katz, and Herbert Menzel. Medical innovation: A diffusion study. The Bobbs-Merrill Company, 1966. Google Scholar
  6. Pierluigi Crescenzi, Gianlorenzo D'Angelo, Lorenzo Severini, and Yllka Velaj. Greedily improving our own closeness centrality in a network. ACM Trans. Knowl. Discov. Data, 11(1):9:1-9:32, 2016. Google Scholar
  7. Gianlorenzo D'Angelo, Lorenzo Severini, and Yllka Velaj. Influence maximization in the independent cascade model. In Proceedings of the 17th Italian Conference on Theoretical Computer Science, Lecce, Italy, September 7-9, 2016., pages 269-274, 2016. Google Scholar
  8. Gianlorenzo D'Angelo, Lorenzo Severini, and Yllka Velaj. Recommending links through influence maximization. arXiv preprint, 2017. URL: http://arxiv.org/abs/1706.04368.
  9. Gianlorenzo D'Angelo, Lorenzo Severini, and Yllka Velaj. Selecting nodes and buying links to maximize the information diffusion in a network. arXiv preprint, 2017. URL: https://arxiv.org/abs/1706.06466.
  10. Pedro Domingos and Matt Richardson. Mining the network value of customers. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD01, pages 57-66. ACM, 2001. Google Scholar
  11. 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. Google Scholar
  12. 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(9):1, 2001. Google Scholar
  13. Mark Granovetter. Threshold models of collective behavior. American journal of sociology, 83(6):1420-1443, 1978. Google Scholar
  14. David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD03, pages 137-146. ACM, 2003. Google Scholar
  15. David Kempe, Jon M. Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. Theory of Computing, 11:105-147, 2015. Google Scholar
  16. Elias Boutros Khalil, Bistra Dilkina, and Le Song. Scalable diffusion-aware optimization of network topology. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD14, pages 1226-1235. ACM, 2014. Google Scholar
  17. Samir Khuller, Anna Moss, and Joseph Naor. The budgeted maximum coverage problem. Inf. Process. Lett., 70(1):39-45, 1999. Google Scholar
  18. Masahiro Kimura, Kazumi Saito, and Hiroshi Motoda. Solving the contamination minimization problem on networks for the linear threshold model. In Proc. of the 10th Pacific Rim International Conference on Artificial Intelligence, PRICA08, pages 977-984. Springer Berlin Heidelberg, 2008. Google Scholar
  19. Masahiro Kimura, Kazumi Saito, and Hiroshi Motoda. Blocking links to minimize contamination spread in a social network. ACM Trans. Knowl. Discov. Data, 3(2):9:1-9:23, 2009. Google Scholar
  20. Chris J Kuhlman, Gaurav Tuli, Samarth Swarup, Madhav V Marathe, and SS Ravi. Blocking simple and complex contagion by edge removal. In IEEE International Conference on Data Mining, ICDM13. IEEE, 2013. Google Scholar
  21. Vijay Mahajan, Eitan Müller, and Frank M Bass. New product diffusion models in marketing: A review and directions for research. Journal of Marketing, 54:1-26, 1990. Google Scholar
  22. Lauren Meyers. Contact network epidemiology: Bond percolation applied to infectious disease prediction and control. Bulletin of the American Mathematical Society, 44(1):63-86, 2007. Google Scholar
  23. M. E. J. Newman. Spread of epidemic disease on networks. Phys. Rev. E, 66:016128, Jul 2002. Google Scholar
  24. H. Nguyen and R. Zheng. On budgeted influence maximization in social networks. IEEE Journal on Selected Areas in Communications, 31(6):1084-1094, June 2013. URL: http://dx.doi.org/10.1109/JSAC.2013.130610.
  25. Manos Papagelis. Refining social graph connectivity via shortcut edge addition. ACM Trans. Knowl. Discov. Data, 10(2):12, 2015. Google Scholar
  26. Matthew Richardson and Pedro Domingos. Mining knowledge-sharing sites for viral marketing. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD02, pages 61-70. ACM, 2002. Google Scholar
  27. E. Rogers. Diffusion of innovations. Free Press, 1995. Google Scholar
  28. Thomas C Schelling. Micromotives and macrobehavior. Norton &Company, 2006. Google Scholar
  29. Daniel Sheldon, Bistra N. Dilkina, Adam N. Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad, Carla P. Gomes, David B. Shmoys, William Allen, Ole Amundsen, and William Vaughan. Maximizing the spread of cascades using network design. CoRR, abs/1203.3514, 2012. URL: http://arxiv.org/abs/1203.3514.
  30. T. Valente. Network models of the diffusion of innovations. Hampton Press, 1995. Google Scholar
  31. Xiaojian Wu, Daniel Sheldon, and Shlomo Zilberstein. Efficient algorithms to optimize diffusion processes under the independent cascade model. In NIPS Workshop on Networks in the Social and Information Sciences, Montreal, Quebec, Canada, 2015. Google Scholar
  32. Y. Zhang, A. Adiga, A. Vullikanti, and B. A. Prakash. Controlling propagation at group scale on networks. In IEEE International Conference on Data Mining, ICDM15, pages 619-628, 2015. 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