2014/09/24 by Z. Kalay, Z Kalay, E. Ben-Naim +1
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Exponent #Fragmentation (computing) #Limit (mathematics) #Node (physics) #Random tree #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #Tree (set theory) #Tree structure #cond-mat.stat-mech #math.CO #math.PR
paper · pdf · doi:10.1088/1751-8113/48/4/045001
published as J. Phys. A 48, 045001 (2015) · 9 pages, 5 figures
arxiv created 2014/09/24 · openalex publication_date 2014/12/24 · arxiv updated 2014/12/25 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
We study fragmentation of a random recursive tree into a forest by repeated removal of nodes. The initial tree consists of N nodes and it is generated by sequential addition of nodes with each new node attaching to a randomly-selected existing node. As nodes are removed from the tree, one at a time, the tree dissolves into an ensemble of separate trees, namely, a forest. We study statistical properties of trees and nodes in this heterogeneous forest, and find that the fraction of remaining nodes m characterizes the system in the limit N --> infty. We obtain analytically the size density phis of trees of size s. The size density has power-law tail phis ~ s^(-alpha) with exponent alpha=1+1/m. Therefore, the tail becomes steeper as further nodes are removed, and the fragmentation process is unusual in that exponent alpha increases continuously with time. We also extend our analysis to the case where nodes are added as well as removed, and obtain the asymptotic size density for growing trees.