Given a population with internal structures determining possible interactions between population members, what can be said about the spread of innovation? In genetics, this is a question of the spread of a favorable mutation within a genetically homogeneous population. In a model society, it is the question of rumors, beliefs, or innovation 1,2,3,4,5. This paper sketches a simple iterative model of populations with structure represented in terms of edge weighted graphs. Use of such graphs has become a powerful tool in evolutionary dynamics e.g. 6. The model presented here employs a Markov process on a state space isomorphic to the vertex set of the N-hypercube. In analogy to genetics, spread of innovation is first modeled as a biased birth-death process in which the innovation provides a fitness r as compared to the fitness of 1 assigned to non-innovative individuals. Following on this, a probabilistic model is developed that, in the simplest cases, corresponds to an elementary probabilistic cellular automata.