Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Competitive Influence Maximization in Social Networks
verfasst von : Shishir Bharathi, David Kempe, Mahyar Salek
Erschienen in: Internet and Network Economics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Social networks often serve as a medium for the diffusion of ideas or innovations. An individual’s decision whether to adopt a product or innovation will be highly dependent on the choices made by the individual’s peers or neighbors in the social network. In this work, we study the game of innovation diffusion with multiple competing innovations such as when multiple companies market competing products using viral marketing. Our first contribution is a natural and mathematically tractable model for the diffusion of multiple innovations in a network. We give a (1 − 1/
e
) approximation algorithm for computing the best response to an opponent’s strategy, and prove that the “price of competition” of this game is at most 2. We also discuss “first mover” strategies which try to maximize the expected diffusion against perfect competition. Finally, we give an FPTAS for the problem of maximizing the influence of a single player when the underlying graph is a tree.