Asymptotic Results for Configuration Model Random Graphs with Arbitrary Degree Distributions (2010)

Luke Fostvedt, Dan Nordman, Alyson Wilson

Abstract: We consider a model for generating a random graph using the configuration model. In the configuration model, each node draws a degree independently from a marginal degreed distribution and endpoints pair randomly. We establish non-trivial bounds on the expected sizes of “buckets ” for large graphs. We define nodes i and j in a graph as neighbors if they share an edge, and we define the “bucket ” associated with node i as the set of nodes that are its neighbors and have degree greater than node i. We formalize this argument by providing an analysis for the expected number of items and pairs in a “bucket ” for arbitrarily specified degree distributions, which include power laws.

Paper: Technical Report