Triggering cascades on strongly connected directed graphs
Journal
International Symposium on Parallel Architectures, Algorithms and Programming
Pages
95-99
Date Issued
2012
Author(s)
Chang, C.-L.
Abstract
Consider the following process of activation on a directed graph G(V,E). In round zero, a set of vertices, called the seeds, are active. Thereafter, a vertex is activated in a round if at least a ρ ∈ (0,1] fraction of its in-neighbors are active in the previous round. Once a vertex is activated, it remains active. Assuming the strong connectivity of G, this paper proves the existence of O([ρ|V|]) seeds that will activate all vertices after a finite number of rounds.
Type
conference paper