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.