Leadership Statistics in Random Structures
E. Ben-Naim and P.L. Krapivsky
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.
source,
ps,
pdf