A widely studied model of influence diffusion in social networks represents the network as a graph G=(V,E), with an integer influence threshold t(v) for each node, and the diffusion process as follows: Initially the members of a chosen set S⊆V are influenced and, during each subsequent round, the set of influenced nodes is augmented by including every new 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 amount of the incentive required to ensure that the information diffusion process terminates within a given number of rounds λ. The problem is hard to approximate in general networks. We present optimal polynomial-time algorithms for paths, cycles, trees, and complete networks for any λ. For the special case λ=1, we present a polynomial-time algorithm with a logarithmic approximation guarantee for any network.

Fast and frugal targeting with incentives

Gargano L.;Rescigno A. A.;Vaccaro U.
2020

Abstract

A widely studied model of influence diffusion in social networks represents the network as a graph G=(V,E), with an integer influence threshold t(v) for each node, and the diffusion process as follows: Initially the members of a chosen set S⊆V are influenced and, during each subsequent round, the set of influenced nodes is augmented by including every new 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 amount of the incentive required to ensure that the information diffusion process terminates within a given number of rounds λ. The problem is hard to approximate in general networks. We present optimal polynomial-time algorithms for paths, cycles, trees, and complete networks for any λ. For the special case λ=1, we present a polynomial-time algorithm with a logarithmic approximation guarantee for any network.
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: http://hdl.handle.net/11386/4734987
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact