Spreading messages
Journal
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Journal Volume
5092 LNCS
Pages
587-599
Date Issued
2008
Author(s)
Chang, C.-L.
Abstract
We model a network in which messages spread by a simple directed graph G = (V,E) [8] and a function α: V →ℕ 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 all individuals by convincing a subset S ⊆ V of individuals at the beginning and then let the message spread. We study minimum-sized sets S needed to convince all individuals at the end. In particular, our results include a lower bound on the size of a minimum S and the NP-completeness of computing a minimum S. Our lower bound utilizes a technique in [9]. Finally, we analyze the special case where each individual is convinced of a message when more than half of its in-neighbors are convinced. © 2008 Springer-Verlag Berlin Heidelberg.
Type
conference paper