It is well-documented that social networks play a considerable role in information spreading. The dynamic processes governing the diffusion of information have been studied in many fields, including epidemiology, sociology, economics, and computer science. A widely studied problem in the area of viral marketing is the target set selection: in order to market a new product, hoping it will be adopted by a large fraction of individuals in the network, which set of individuals should we “target” (for instance, by offering them free samples of the product)? In this paper, we introduce a diffusion model in which some of the neighbors of a node have a negative influence on that node, namely, they induce the node to reject the feature that is supposed to be spread. We study the target set selection problem within this model, first proving a strong inapproximability result holding also when the diffusion process is required to reach all the nodes in a couple of rounds. Then, we consider a set of restrictions under which the problem is approximable to some extent.

DI IANNI, M., Varricchio, G. (2020). Latency-bounded target set selection in signed networks. ALGORITHMS, 13(2) [10.3390/a13020032].

Latency-bounded target set selection in signed networks

Miriam Di Ianni;
2020

Abstract

It is well-documented that social networks play a considerable role in information spreading. The dynamic processes governing the diffusion of information have been studied in many fields, including epidemiology, sociology, economics, and computer science. A widely studied problem in the area of viral marketing is the target set selection: in order to market a new product, hoping it will be adopted by a large fraction of individuals in the network, which set of individuals should we “target” (for instance, by offering them free samples of the product)? In this paper, we introduce a diffusion model in which some of the neighbors of a node have a negative influence on that node, namely, they induce the node to reject the feature that is supposed to be spread. We study the target set selection problem within this model, first proving a strong inapproximability result holding also when the diffusion process is required to reach all the nodes in a couple of rounds. Then, we consider a set of restrictions under which the problem is approximable to some extent.
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01
English
social networks; network analysis; diffusion processes; approximation
mdpi.com/1999-4893/13/2/32#
DI IANNI, M., Varricchio, G. (2020). Latency-bounded target set selection in signed networks. ALGORITHMS, 13(2) [10.3390/a13020032].
DI IANNI, M; Varricchio, G
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
algorithms-13-00032-v2.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: Non specificato
Dimensione 417.12 kB
Formato Adobe PDF
417.12 kB Adobe PDF Visualizza/Apri

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/2108/263529
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact