I would like to apply a majority rule cellular automata to graphs. Specifically, I would like to take a graph as input, and then define two functions, InitialColoring[graph] and MajorityRule[graph]. Suppose the set of colors is some given finite list.
InitialColoring[graph] uses some rule (such as randomly assigning colors to each vertex). MajorityRule[graph] this "updates" the coloring for a given graph by getting the neighbors of each vertex, checking which color has the majority, and then coloring the majority color. For simplicity, let's assume the set of colors only has two colors, and if there is a tie, the vertex keeps its current color.
My thoughts: Make a loop ranging over vertices, get neighbors, get colors, count colors, apply. I am very new to Mathematica so I am not sure how to implement this. Any suggestions on this approach or a better method to accomplish the same goal?
Also note: I want to apply cellular automata to graphs (specifically CayleyGraphs), not just the integer lattice so the built-in CellularAutomata function doesn't seem to help much.
Suppose we have the graph shown in the upper left corner in the figure below.
We want to apply the rule that a vertex's color is determined by the color of the majority of its neighbors (if there is a tie, it keeps its color). Below shows an example of the progression of this automata. This outlines what I want: 1) enter a graph with an initial coloring 2) apply a rule (shown through progression of arrows) that outputs a new graph (or perhaps two functions, one that outputs the graph data, and one that outputs the color data... then these are combined in some way... I'm not sure which would be easier/more efficient to implement).
I am lost as to how to implement this, although the algorithm is pretty easy. In fact, focusing to the case where we only have two colors and the majority rule would suffice.
EDIT 2: Further Details Updating should be synchronous, i.e., when we go from one time to the next, it should look like we updated every vertex all at once. Otherwise, we could get unwanted colorings due to intermediate updates in sequential updating. For example, in the example above, if we colored the top vertex first, and then proceeded, the rightmost vertex would stay blue the next generation instead of changing to red.
Also, when checking for the vertex's color, the vertex itself should only be considered in the event of a tie, i.e., it is not considered one of its neighbors unless there is a loop (we don't assume graphs are implicitly reflexive).