2013/02/28 by S. Nowak, Stefan Nowak, Joachim Krug +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Continuum percolation theory #Distance #Path (computing) #Percolation (cognitive psychology) #Percolation threshold #Random graph #Random tree #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #Vertex (graph theory) #cond-mat.stat-mech #math.PR #q-bio.PE
paper · pdf · doi:10.1209/0295-5075/101/66004
published as EPL 101 (2013) 66004 · 6 pages, 4 figures
openalex publication_date 2013/03/01 · arxiv created 2013/04/03 · arxiv updated 2013/04/04 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
Accessibility percolation is a new type of percolation problem inspired by evolutionary biology. To each vertex of a graph a random number is assigned and a path through the graph is called accessible if all numbers along the path are in ascending order. For the case when the random variables are independent and identically distributed, we derive an asymptotically exact expression for the probability that there is at least one accessible path from the root to the leaves in an n -tree. This probability tends to 1 (0) if the branching number is increased with the height of the tree faster (slower) than linearly. When the random variables are biased such that the mean value increases linearly with the distance from the root, a percolation threshold emerges at a finite value of the bias.