Fragmentation of Random Trees

Abstract

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 phi_s of trees of size s. The size density has power-law tail phi_s ~ 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.

9 pages, 5 figures

References in corpus (21)

• Emergence of scaling in random networks
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Connectivity of Growing Random Networks
• Organization of Growing Random Networks
• Co-evolution of strategy and structure in complex networks with dynamical linking
• Emergence of a small world from local interactions: Modeling acquaintance networks
• Transition from damage to fragmentation in collision of solids
• Exact solutions for models of evolving networks with addition and deletion of nodes
• Largest Lyapunov Exponent for Many Particle Systems at Low Densities
• Scaling, Multiscaling, and Nontrivial Exponents in Inelastic Collision Processes
• Traveling Waves, Front Selection, and Exact Nontrivial Exponents in a Random Fragmentation Problem
• Extremal properties of random trees
• Percolation theory applied to measures of fragmentation in social networks
• Addition-Deletion Networks
• Cutting down trees with a Markov chainsaw
• Evolving networks through deletion and duplication
• Fragmentation with a Steady Source
• Topological phase transition in a network model with preferential attachment and node removal
• Scale free networks by preferential depletion
• Minimal Fragmentation of Regular Polygonal Plates
• Minimal fragmentation problem

Cited by in corpus (4)

• Random Recursive Trees and the Elephant Random Walk
• Fragmentation of fractal random structures
• Stochastic resetting in a networked multiparticle system with correlated transitions
• Morphology-dependent random binary fragmentation of in silico fractal-like agglomerates