Statistical Inference on Random Graphs

The study of random graphs is a field that emerged in the second half of the 20th century. Most of the work in this area is combinatorial in nature: a random model is assumed and used for computing various asymptotic properties on the graph. The work contained in this book takes a reverse approach. Our questions are: given a large graph realization, what can we learn about it? How can we hypothesize an underlying model? How can we test the graph for the hypothesis? The first half of the book is a survey of some well-known and less well-known methods, and apply some of them on various "scale-free" graphs, including the famous Albert-Barabási graph model. Then we proceed beyond the scale-free realm to examine the problem of generation uniformly distributed graphs with a given expected degree sequence. We hope every reader will find something to enjoy in and/or learn from the book.