Stable sets of threshold-based cascades on the Erdos-R?nyi random graphs
Journal
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Journal Volume
7056 LNCS
Pages
96-105
Date Issued
2011
Author(s)
Chang, C.-L.
Abstract
Consider the following reversible cascade on the Erdos-Rényi random graph G(n,p). In round zero, a set of vertices, called the seeds, are active. For a given ρ ∈ (0,1 ], a non-isolated vertex is activated (resp., deactivated) in round t ∈ ℤ+ if the fraction f of its neighboring vertices that were active in round t - 1 satisfies f ≥ ρ (resp., f < ρ). An irreversible cascade is defined similarly except that active vertices cannot be deactivated. A set of vertices, S, is said to be stable if no vertex will ever change its state, from active to inactive or vice versa, once the set of active vertices equals S. For both the reversible and the irreversible cascades, we show that for any constant ε > 0, all p ∈ [(1 + ε) (ln (e/ρ))/n,1] and with probability 1 - n -Ω(1), every stable set of G(n,p) has size O(⌈ρ n⌉) or n - O(⌈ρ⌉). © 2011 Springer-Verlag.
Type
conference paper