Diffusion in Social Networks with Competing Products
6982, chapter 20, page 212--223. Springer Berlin Heidelberg, Berlin, Heidelberg, (Apr 16, 2013)DOI: 10.1007/978-3-642-24829-0\_20
Abstract
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. 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 determining whether a final network exists in which
all nodes adopted some product is NP-complete. In turn, the problems of
determining whether a given node adopts some (respectively, a given) product in
some (respectively, all) network(s) are either co-NP complete or can be solved
in polynomial time.
Further, 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
\$Ømega(n)\$, in contrast to the maximum spread, which is efficiently
computable. Finally, we clarify that some of the above problems can be solved
in polynomial time when there are only two products.