Spreading messages
Journal
Theoretical Computer Science
Journal Volume
410
Journal Issue
27-29
Pages
2714-2724
Date Issued
2009
Author(s)
Chang, Ching-Lueh
Abstract
We model a network in which messages spread by a simple directed graph G = (V, E) and a function α : V → N mapping each v ∈ V to a positive integer less than or equal to the indegree of v. The graph G represents the individuals in the network and the communication channels between them. An individual v ∈ V will be convinced of a message when at least α (v) of its in-neighbors are convinced. Suppose we are to convince a message to the individuals by first convincing a subset of individuals, called the seeds, and then let the message spread. We study the minimum number min-seed (G, α) of seeds needed to convince all individuals at the end. In particular, we prove a lower bound on min-seed (G, α) and the NP-completeness of computing min-seed (G, α). We also analyze the special case, called the strict-majority scenario, where each individual is convinced of a message when more than half of its in-neighbors are convinced. For the strict-majority scenario, we prove three results. First, we show that with high probability over the Erdo{double acute}s-Rényi random graphs G (n, p), Ω (min {n, 1 / p}) seeds are needed to convince all individuals at the end. Second, if G = (V, E) is undirected, then a set of s uniformly random samples from V convinces no more than an expected s (2 | E | + 2 | V |) | V | individuals at the end. Third, in a digraph G = (V, E) with a positive minimum indegree, one can find in polynomial (in | V |) time a set of at most (23/27)| V | seeds convincing all individuals. © 2009 Elsevier B.V. All rights reserved.
Type
journal article