2020/03/31 by Gábor Timár, G. Timár, Rui A. da Costa +5 · 30 citations
Agricultural and Biological Sciences · Environmental Science · Mathematics · Physics and Astronomy · #Artificial intelligence #Binary tree #Class (philosophy) #Combinatorics #Complex Network Analysis Techniques #Computer science #Ecology and Vegetation Dynamics Studies #Inference #K-ary tree #Logarithm #Mathematical analysis #Mathematics #Plant and animal studies #Root (linguistics) #Tree (set theory) #Tree structure #nlin.AO #physics.data-an #physics.soc-ph
paper · pdf · doi:10.1103/physreve.102.032304
published in Physical review. E 102(3), 032304 (American Physical Society) · 17 pages, 10 figures
arxiv created 2020/07/24 · openalex publication_date 2020/09/10 · arxiv updated 2020/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The structure of an evolving network contains information about its past. Extracting this information efficiently, however, is, in general, a difficult challenge. We formulate a fast and efficient method to estimate the most likely history of growing trees, based on exact results on root finding. We show that our linear-time algorithm produces the exact stepwise most probable history in a broad class of tree growth models. Our formulation is able to treat very large trees and therefore allows us to make reliable numerical observations regarding the possibility of root inference and history reconstruction in growing trees. We obtain the general formula 〈lnN〉≅NlnN-cN for the size dependence of the mean logarithmic number of possible histories of a given tree, a quantity that largely determines the reconstructability of tree histories. We also reveal an uncertainty principle: a relationship between the inferability of the root and that of the complete history, indicating that there is a tradeoff between the two tasks; the root and the complete history cannot both be inferred with high accuracy at the same time.