Latency-bounded Target Set Selection in Signed Networks
| Autor: | Giovanna Varricchio, Miriam Di Ianni |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
social networks
Theoretical computer science lcsh:T55.4-60.8 Diffusion of information 0102 computer and information sciences 02 engineering and technology 01 natural sciences lcsh:QA75.5-76.95 Theoretical Computer Science Viral marketing 0202 electrical engineering electronic engineering information engineering lcsh:Industrial engineering. Management engineering Latency (engineering) network analysis approximation Numerical Analysis business.industry diffusion processes Settore INF/01 Computational Mathematics Computational Theory and Mathematics Diffusion process 010201 computation theory & mathematics Bounded function New product development 020201 artificial intelligence & image processing lcsh:Electronic computers. Computer science business Network analysis |
| Zdroj: | Algorithms Volume 13 Issue 2 Algorithms, Vol 13, Iss 2, p 32 (2020) |
| ISSN: | 1999-4893 |
| DOI: | 10.3390/a13020032 |
| Popis: | 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 &ldquo target&rdquo (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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
| Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |