Leadership statistics in random structuresE. Ben-Naim1 and P. L. Krapivsky2
1 Theoretical Division and Center for Nonlinear Studies Los Alamos National Laboratory - Los Alamos, NM, 87545 USA
2 Center for Polymer Studies and Department of Physics Boston University - Boston, MA, 02215 USA
(Received 31 July 2003; accepted in final form 18 November 2003)
The largest component ("the leader") in evolving random structures often exhibits universal statistical properties. This phenomenon is demonstrated analytically for two ubiquitous structures: random trees and random graphs. In both cases, lead changes are rare as the average number of lead changes increases quadratically with logarithm of the system size. As a function of time, the number of lead changes is self-similar. Additionally, the probability that no lead change ever occurs decays exponentially with the average number of lead changes.
02.50.-r - Probability theory, stochastic processes, and statistics.
05.40.-a - Fluctuation phenomena, random processes, noise, and Brownian motion.
89.75.Hc - Networks and genealogical trees.
© EDP Sciences 2004