Social networks with competing products

DOI10.3233/FI-2014-970MaRDI QIDQ5408617zbMATH OpenOpenAlexFDO

Authors Krzysztof R. Apt, Evangelos Markakis

Publication date 11 April 2014

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.5636

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Social networks; opinion dynamics (91D30)

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

Recommendations

• Diffusion in social networks with competing products
• On the approximability of influence in social networks
• scientific article; zbMATH DE number 7356860
• Social network games
• A new model for product adoption over social networks

Cited in

(20)

• Local information in influence networks
• Competitive contagion in networks
• Election control through social influence with unknown preferences
• Election control through social influence with voters' uncertainty
• Competitive and collaborative influence in social networks
• On the non-progressive spread of influence through social networks
• Influence maximization in switching-selection threshold models
• Diffusion in social networks with competing products
• Competitive diffusion on weighted graphs
• On non-progressive spread of influence through social networks
• A dynamics for advertising on networks
• Competing for customers in a social network
• A new model for product adoption over social networks
• A bilevel programming approach for spread of influence in competitive environment
• scientific article; zbMATH DE number 7356860 (Why is no real title available?)
• On the effectiveness of social proof recommendations in markets with multiple products
• Marketing impact on diffusion in social networks
• Paradoxes in social networks with multiple products
• Social network games
• Competitive contagion in networks

This page was built for publication: Social networks with competing products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5408617)