Accession Number ADA578231
Title Fast and Deterministic Computation of Fixation Probability in Evolutionary Graphs.
Publication Date Nov 2012
Media Count 11p
Personal Author P. Roos P. Shakarian
Abstract In evolutionary graph theory biologists study the problem of determining the probability that a small number of mutants overtake a population that is structured on a weighted, possibly directed graph. Currently Monte Carlo simulations are used for estimating such fixation probabilities on directed graphs, since no good analytical methods exist. In this paper, we introduce a novel deterministic algorithm for computing fixation probabilities for strongly connected directed, weighted evolutionary graphs under the case of neutral drift, which we show to be a lower bound for the case where the mutant is more fit than the rest of the population (previously, this was only observed from simulation). We also show that, in neutral drift, fixation probability is additive under the weighted, directed case. We implement our algorithm and show experimentally that it consistently outperforms Monte Carlo simulations by several orders of magnitude, which can allow researchers to study fixation probability on much larger graphs.
Keywords Algorithms
Graphs
Modelling of evolution
Monte carlo method
Network diffusion
Network science
Probability
Stochastic models
Stochastic processes
Theorems


 
Source Agency Non Paid ADAS
NTIS Subject Category 72B - Algebra, Analysis, Geometry, & Mathematical Logic
72F - Statistical Analysis
Corporate Author Military Academy, West Point, NY. Network Science Center (NSC).
Document Type Technical report
Title Note Conference paper.
NTIS Issue Number 1321
Contract Number W911NF-08-1-0144

Science and Technology Highlights

See a sampling of the latest scientific, technical and engineering information from NTIS in the NTIS Technical Reports Newsletter

Acrobat Reader Mobile    Acrobat Reader