
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, we also resolve the complexity of the problems of determining whether a given node adopts some (respectively, a given) product in some (respectively, all) network(s). 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 Ω(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.
Social and Information Networks (cs.SI), FOS: Computer and information sciences, Physics - Physics and Society, Analysis of algorithms and problem complexity, FOS: Physical sciences, Computer Science - Social and Information Networks, Physics and Society (physics.soc-ph), 004, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Social networks; opinion dynamics
Social and Information Networks (cs.SI), FOS: Computer and information sciences, Physics - Physics and Society, Analysis of algorithms and problem complexity, FOS: Physical sciences, Computer Science - Social and Information Networks, Physics and Society (physics.soc-ph), 004, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Social networks; opinion dynamics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 8 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
