- Diffusion in social networks with competing products
- Algorithmic game theory: 4th International Symposium, SAGT 2011
- Book/source title
- Algorithmic Game Theory
- Book/source subtitle
- 4th International Symposium, SAGT 2011, Amalfi, Italy, October 17-19 2011: proceedings
- Pages (from-to)
- Heidelberg: Springer
- ISBN (electronic)
- Lecture Notes in Computer Science: 0302-9743
- Volume (Serie)
- Document type
- Conference contribution
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
We introduce a new threshold model of social networks, in which the nodes influenced by their neighbours can adopt one out of several alternatives. We characterize the graphs for which adoption of a product by the whole network is possible (respectively necessary) and the ones for which a unique outcome is guaranteed. These characterizations directly yield polynomial time algorithms that allow us to determine whether a given social network satisfies one of the above properties.
We also study algorithmic questions for networks without unique outcomes. We show that the problem of computing the minimum possible spread of a product is NP-hard to approximate with an approximation ratio better than Ω(n), in contrast to the maximum spread, which is efficiently computable. We then move on to questions regarding the behavior of a node with respect to adopting some (resp. a given) product. We show that the problem of determining whether a given node has to adopt some (resp. a given) product in all final networks is co-NP-complete.
- go to publisher's site
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.