Title
Vertex Degrees in Preferential Attachment Random Graphs
Speaker
Nathan Ross, University of California, Berkeley
Abstract
Note: This seminar is primarily hosted by the Mathematics Department.
Random graph models have recently been used to understand the structure and dynamics of real world networks, for example the "web of human sexual contacts" and the power grid. One family of such models is called preferential attachment random graphs which evolve in time by sequentially adding vertices and edges in a random way so that connections to vertices having high degree are favored. These models were popularized by Barabasi and Albert in 1999 to explain the so-called power law behavior observed in degree distributions of some real world networks such as 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 preferential attachment graphs 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. Our results are derived by identifying the distributional limits as unique fixed points of appropriate distributional transformations and then showing that these transformations have a small effect on the respective distributions of interest. This method of proof is useful for obtaining distributional limit and approximation results in other applications and it automatically yields various descriptions and properties of the limiting distributions under consideration. Joint work with Erol Pekoz and Adrian Roellin.
