Diffusion in Social Networks with Competing Products
Krzysztof R. Apt
CWI and University of Amsterdam


Social networks have become a huge interdisciplinary research area with important links to sociology, economics, epidemiology, computer science, and mathematics. 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 social networks for which adoption of a product by the whole network is possible (respectively necessary) and the ones for which a unique outcome is guaranteed. We also study algorithmic questions concerning these networks. In particular we consider the problem of computing the minimum (resp. maximum) possible spread of a product and the problem of determining whether a given node has to adopt some (resp. a given) product in all final networks. Some of these problems are efficiently computable, while others are co-NP complete, or NP-hard to approximate with an approximation ratio better than Omega(n).
This is a joint work with Evangelos Markakis.

back to the list of talks