A widely studied process of influence diffusion in social networks posits that the dynamics of influence diffusion evolves as follows: Given a graph G = (V,E), representing the network, initially only the members of a given S are influenced; subsequently, at each round, the set of influenced nodes is augmented by all the nodes in the network that have a sufficiently large number of already influenced neighbors. The general problem is to find a small initial set of nodes that influences the whole network. In this paper we extend the previously described basic model in the following ways: firstly, we assume that there are non negative values c(v) associated to each node v in V , measuring how much it costs to initially influence node v, and the algorithmic problem is to find a set of nodes of minimum total cost that influences the whole network; successively, we study the consequences of giving incentives to member of the networks, and we quantify how this affects (i.e., reduces) the total costs of starting an influence diffusion process that influence the whole network. For the two above problems we provide both hardness results and algorithms.We also experimentally validate our algorithms via extensive simulations on real life networks.

Optimizing Spread of Influence in Social Networks via Partial Incentives

GARGANO, Luisa;RESCIGNO, Adele Anna;VACCARO, Ugo
2015

Abstract

A widely studied process of influence diffusion in social networks posits that the dynamics of influence diffusion evolves as follows: Given a graph G = (V,E), representing the network, initially only the members of a given S are influenced; subsequently, at each round, the set of influenced nodes is augmented by all the nodes in the network that have a sufficiently large number of already influenced neighbors. The general problem is to find a small initial set of nodes that influences the whole network. In this paper we extend the previously described basic model in the following ways: firstly, we assume that there are non negative values c(v) associated to each node v in V , measuring how much it costs to initially influence node v, and the algorithmic problem is to find a set of nodes of minimum total cost that influences the whole network; successively, we study the consequences of giving incentives to member of the networks, and we quantify how this affects (i.e., reduces) the total costs of starting an influence diffusion process that influence the whole network. For the two above problems we provide both hardness results and algorithms.We also experimentally validate our algorithms via extensive simulations on real life networks.
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/4651589
 Attenzione

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

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