Johann Bernoulli Colloquium

Title: Diffusion in Social Networks with Competing Products
Speaker: Prof.dr. Krzysztof R. Apt
CWI and University of Amsterdam

Abstract:

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.