Abstract: We study how the outcome of evolutionary dynamics on
graphs depends on a randomness on the graph structure. We gradually
change the underlying graph from completely regular (e.g. a square lattice) to completely random. We find that the fixation probability increases as the randomness increases; nevertheless, the increase is
not significant and thus the fixation probability could be estimated by the known formulas for underlying regular graphs.