Name
Abstract | ||
|---|---|---|
We study a combinatorial model of the spread of influence in networks that generalizes existing schemata recently proposed in the literature. In our model agents change behaviors/opinions on the basis of information collected from their neighbors in a time interval of bounded size whereas agents are assumed to have unbounded memory in previously studied scenarios. In our mathematical framework, one is given a network G = (V,E), an integer value t(v) for each node v ∈ V, and a time window size λ. The goal is to determine a small set of nodes (target set) that influences the whole graph. The spread of influence proceeds in rounds as follows: initially all nodes in the target set are influenced; subsequently, in each round, any uninfluenced node v becomes influenced if the number of its neighbors that have been influenced in the previous λ rounds is greater than or equal to t(v). We prove that the problem of finding a minimum cardinality target set that influences the whole network G is hard to approximate within a polylogarithmic factor. On the positive side, we design exact polynomial time algorithms for paths, rings, trees, and complete graphs. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.tcs.2015.02.015 | Theoretical Computer Science |
Keywords | DocType | Volume |
Target set selection,Influence diffusion | Journal | 584 |
Issue | ISSN | Citations |
C | 0304-3975 | 9 |
PageRank | References | Authors |
0.51 | 26 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luisa Gargano | 1 | 725 | 71.91 |
| Pavol Hell | 2 | 2638 | 288.75 |
| Joseph G. Peters | 3 | 347 | 38.88 |
| Ugo Vaccaro | 4 | 980 | 87.28 |