A widely studied model of influence diffusion in social networks represents the network as a graph G = (V, E) with an influence threshold t(v) for each node. Initially the members of an initial set S ⊆ V are influenced. During each subsequent round, the set of influenced nodes is augmented by including every node v that has at least t(v) previously influenced neighbours. The general problem is to find a small initial set that influences the whole network. In this paper we extend this model by using incentives to reduce the thresholds of some nodes. The goal is to minimize the total of the incentives required to ensure that the process completes within a given number of rounds. The problem is hard to approximate in general networks. We present polynomial-time algorithms for paths, trees, and complete networks.

Time-bounded influence diffusion with incentives

Cordasco, Gennaro
;
2018

Abstract

A widely studied model of influence diffusion in social networks represents the network as a graph G = (V, E) with an influence threshold t(v) for each node. Initially the members of an initial set S ⊆ V are influenced. During each subsequent round, the set of influenced nodes is augmented by including every node v that has at least t(v) previously influenced neighbours. The general problem is to find a small initial set that influences the whole network. In this paper we extend this model by using incentives to reduce the thresholds of some nodes. The goal is to minimize the total of the incentives required to ensure that the process completes within a given number of rounds. The problem is hard to approximate in general networks. We present polynomial-time algorithms for paths, trees, and complete networks.
2018
9783030013240
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11591/403163
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact