Exact numerical calculation of fixation probability and time on graphs

Exact numerical calculation of fixation probability and time on graphs
Laura Hindersin, Marius Möller, Arne Traulsen, Benedikt Bauer

The Moran process on graphs is an interesting model to study the spread of a new mutant in a spatially structured population. Exact analytical solutions for the fixation probability and time have been found for only a few classes of graphs so far. Simulations are time-expensive and many realizations are necessary, as the variance of the fixation times is high. We present an algorithm that numerically computes these quantities by an approach based on the transition matrix. The advantage over simulations is that the calculation has to be executed only once. Building the transition matrix is automated by our algorithm. This enables a fast and interactive study of different graph structures and their effect on fixation probability and time. We provide a fast implementation in C with this note. Our code is very flexible, as it can handle two different update mechanisms (Birth-death or death-Birth), as well as directed or undirected graphs.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s