The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Vertices of high degree in the preferential attachment tree

Luczak, M (London School of Economics)
Wednesday 02 March 2011, 14:00-15:00

Seminar Room 1, Newton Institute


The preferential attachment tree is the most basic model of evolving web graphs. At each stage of the process, a new vertex is added and joined to one of the existing vertices, with each vertex chosen with probability proportional to its current degree. In probability theory, this is also known as a Yule process. Much is known about this model, including the fact that the numbers of vertices of each small degree follow a ``power law''. Here we study in detail the degree sequence of the preferential attachment tree, looking at the vertices of large degrees as well as the numbers of vertices of each fixed degree. Our method is based on bounding martingale deviations, using exponential supermartingales. This is joint work with Graham Brightwell.


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧