School Seminars and Colloquia

Vertices of high degree in the preferential attachment tree

Discrete Structures and Algorithms (Seminar)

by Graham Brightwell


Institution: London School of Economics, UK
Date: Tue 15th November 2011
Time: 11:00 AM
Location: Russell Love Theatre, Richard Berry Building

Abstract: The preferential attachment tree is the most basic model of evolving web graphs and social networks. 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.

This is joint work with Malwina Luczak.