We consider a population of interconnected individuals that, with respect to a piece information, at each time instant can be subdivided into three (time-dependent) categories: agnostic, influenced, and evangelists.A dynamical process of information diffusion evolves among the individuals of the population according to the following rules.Initially, all individuals are agnostic.Then, a set of people is chosen from the outside and convinced to start evangelizing, i.e., to start spreading the information.When a number of evangelists, greater than a given threshold, communicate with an node v, the node v becomes influenced, whereas, as soon as the individual v is contacted by a sufficiently much larger number of evangelists, it is itself converted into an evangelist and consequently it starts spreading the information.The question is: How to choose a bounded cardinality initial set of evangelists so as to maximize the final number of influenced individuals? We prove that the problem is hard to solve, even in an approximate sense, and we present exact polynomial time algorithms for trees and complete graphs.For general graphs, we derive exact algorithms parameterized with respect to neighborhood diversity.We also study the problem when the objective is to select a minimum number of evangelists able of influencing the whole network.

Evangelism in social networks

GARGANO, Luisa;RESCIGNO, Adele Anna;VACCARO, Ugo
2016-01-01

Abstract

We consider a population of interconnected individuals that, with respect to a piece information, at each time instant can be subdivided into three (time-dependent) categories: agnostic, influenced, and evangelists.A dynamical process of information diffusion evolves among the individuals of the population according to the following rules.Initially, all individuals are agnostic.Then, a set of people is chosen from the outside and convinced to start evangelizing, i.e., to start spreading the information.When a number of evangelists, greater than a given threshold, communicate with an node v, the node v becomes influenced, whereas, as soon as the individual v is contacted by a sufficiently much larger number of evangelists, it is itself converted into an evangelist and consequently it starts spreading the information.The question is: How to choose a bounded cardinality initial set of evangelists so as to maximize the final number of influenced individuals? We prove that the problem is hard to solve, even in an approximate sense, and we present exact polynomial time algorithms for trees and complete graphs.For general graphs, we derive exact algorithms parameterized with respect to neighborhood diversity.We also study the problem when the objective is to select a minimum number of evangelists able of influencing the whole network.
2016
9783319445427
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/11386/4673188
 Attenzione

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

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