Preferential attachment, vertex arrival times, and probabilistic symmetries in random graphs
13th October 2017, 3:30 pm – 4:30 pm
Main Maths Building, SM3
Preferential attachment (PA) models of network formation are based on a simple, interpretable mechanism (namely, size-biased reinforcement) from which non-trivial properties emerge. In particular, power law degree distributions have generated a great deal of interest. We show that the power law exponent in PA models depends on two quantities: an offset to the size-biased sampling distribution, and the rate at which new vertices arrive. By conditioning on the arrival times of new vertices, we give a representation theorem reminiscent of residual allocation, or ``stick-breaking''. The representation is used to analyze the asymptotic degree properties of the random graphs, and to characterize their local weak limit. Finally, I will briefly discuss this representation in the context of other probabilistic symmetries found in the network modeling literature.
Collaborators: Christian Borgs and Jennifer Chayes (Microsoft Research), and Peter Orbanz (Columbia University).