# Diffusion in Social Networks with Competing Products

29^{th} November 2011, 16:00, ALT

Prof. Krzysztof Apt

CWI and University of Amsterdam

NL

## 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.