Bounding the sizes of dynamic monopolies and convergent sets for threshold-based cascades

• Published in: Theoretical computer science 2013-01, Vol.468, p.37-49
• Main Authors: Chang, Ching-Lueh, Lyuu, Yuh-Dauh
• Format: Article
• Language: English
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2012.11.016

Consider the following reversible cascade on a simple directed graph G=(V,E). In round zero, a set of vertices, called the seeds, are active. In round k∈Z+, a vertex v∈V is activated (deactivated) if at least (resp., fewer than) ϕ(v) of its in-neighbors are active in round k−1, where ϕ:V→N. An irreversible cascade is defined similarly except that active vertices cannot be deactivated. Two specific candidates for the threshold function ϕ are ϕmaj(v)strict≡⌈(deg−(v)+1)/2⌉ and ϕρ(v)≡⌈ρ⋅deg−(v)⌉, where deg−(v) denotes the indegree of v∈V and ρ∈(0,1]. An irreversible dynamic monopoly is a set of seeds that leads all vertices to activation after finitely many rounds of the irreversible cascade with ϕ=ϕmajstrict. A set of vertices, S, is said to be convergent if no vertex will ever change its state, from active to inactive or vice versa, once the set of active vertices equals S. This paper shows that an irreversible dynamic monopoly of size at most ⌈|V|/2⌉ can be found in polynomial (in |V|) time if G is strongly connected. Furthermore, we show that for any constant ϵ>0, all ρ∈(0,1], ϕ=ϕρ, p∈[(1+ϵ)(ln(e/ρ))/n,1] and with probability 1−n−Ω(1), every convergent set of the Erdős–Rényi random graph G(n,p) has size O(⌈ρn⌉) or n−O(⌈ρn⌉). Our result on convergent sets holds for both the reversible and irreversible cascades.