Bounding the sizes of dynamic monopolies and convergent sets for threshold-based cascades
Journal
Theoretical Computer Science
Journal Volume
468
Pages
37-49
Date Issued
2013
Author(s)
Chang, C.-L.
Abstract
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 Erdos-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. © 2012 Elsevier B.V. All rights reserved.
Type
journal article