Spreading messages

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 Erdő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.