کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428605 | 686835 | 2011 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Triggering cascades on undirected connected graphs Triggering cascades on undirected connected graphs](/preview/png/428605.png)
Consider the following cascading process on an undirected connected graph G(V,E)G(V,E). A set S of vertices, called the seeds, are active initially. Thereafter, an inactive vertex is activated when at least a ρ fraction of its neighbors is active, where ρ∈(0,1]ρ∈(0,1]. The cascading process proceeds asynchronously until no more vertices can be activated. This paper proves the existence of at most (22+3)⌈ρ|V|⌉ seeds that can activate all vertices at the end.
► We consider threshold-based cascades on connected graphs.
► A degree-d vertex is activated when it has at least ρd active neighbors.
► We find bounds on the minimum number of seeds activating all vertices eventually.
► We use techniques of Ackerman et al. [Theoret. Comput. Sci. 411 (44–46) (2010) 4017–4022].
Journal: Information Processing Letters - Volume 111, Issue 19, 15 October 2011, Pages 973–978