Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
How to go Viral: Cheaply and Quickly
verfasst von : Ferdinando Cicalese, Gennaro Cordasco, Luisa Gargano, M. Milanič, Joseph G. Peters, Ugo Vaccaro
Erschienen in: Fun with Algorithms
Verlag: Springer International Publishing
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
Given a social network represented by a graph
G
, we consider the problem of finding a bounded cardinality set of nodes
S
with the property that the influence spreading from
S
in
G
is as large as possible. The dynamics that govern the spread of influence is the following: initially only elements in
S
are influenced; subsequently at each round, the set of influenced elements is augmented by all nodes in the network that have a sufficiently large number of already influenced neighbors. While it is known that the general problem is hard to solve — even in the approximate sense — we present exact polynomial time algorithms for trees, paths, cycles, and complete graphs.