Random graphs with arbitrary degree distributions and their applications -art. no. 026118

Recent work on the structure of social networks and the internet has focuse d attention on graphs with distributions of vertex degree that are signific antly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of rand om graphs with arbitrary degree distributions. In addition to simple undire cted, unipartite graphs, we examine the properties of directed and bipartit e graphs. Among other results, we derive exact expressions for the position of the phase transition at which a giant component first forms, the mean c omponent size, the size of the giant component if there is one, the mean nu mber of vertices a certain distance away from a randomly chosen vertex, and the average vertex-vertex distance within a graph. We apply our theory to some real-world graphs, including the worldwide web and collaboration graph s of scientists and Fortune 1000 company directors. We demonstrate that in some cases random graphs with appropriate distributions of vertex degree pr edict with surprising accuracy the behavior of the real world, while in oth ers there is a measurable discrepancy between theory and reality, perhaps i ndicating the presence of additional social structure in the network that i s not captured by the random graph.