UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Vertex degrees in preferential attachment random graphs

Mathematical Physics & Probability

Speaker: Nathan Ross, UC Berkeley
Location: 1147 MSB
Start time: Wed, Oct 10 2012, 4:10PM

Preferential attachment random graphs evolve in time by sequentially adding vertices and edges in a random way so that connections to vertices having high degree are favored. Particular versions of these models were used by Barabasi and Albert in 1999 to explain the so-called power law behavior observed in the degree distribution of some real world networks, for example the graph derived from the world wide web by considering webpages as vertices and hyperlinks between them as edges. In this talk we discuss recent results for some of these models which provide rates of convergence for both the distribution of the degree of a fixed vertex (properly scaled) to its distributional limit and the distribution of the degree of a randomly chosen vertex to an appropriate power law. We obtain these rates through new variations of Stein's method which rely on showing appropriate limiting distributions are the unique fixed points of certain distributional transformations. This point of view also provides new descriptions and properties of some of these limiting distributions. Joint work with Erol Pekoz and Adrian Roellin.