Asymptotics for preferential attachment random graphs via Stein’s method

Preferential attachment random graphs evolve in time by sequentially adding vertices and edges randomly so that connections to vertices having high degree are favored. There has been an explosion of research on these models since Barabasi and Albert popularized them in 1999 to explain the so-called power law behavior observed in real networks such as the graph of the Internet where Web pages correspond to vertices and hyperlinks between them correspond to edges. In this talk we will show how to derive rates of convergence for the distribution of the degree of a fixed vertex to its distributional limit using a new variation of Stein’s method that relies on finding couplings to motivate distributional transformations for which limit distributions are fixed points. Surprisingly little is known about these limit distributions despite the large literature on such graphs.