Krzysztof R. Apt, Evangelos Markakis
posted by Matúš Medo
(3 May 2012)
(70 views, 79 downloads, 0 comments )
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
$\Omega(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.
The Econophysics Forum
welcomes your comments