Exponential families of random graphs

Sourav Chatterjee
University of California, Berkeley (UC Berkeley)

Consider a statistical model of a random graph, where the Hamiltonian is a linear combination of the vertex degrees, and the coefficients in the linear combination are unknown parameters. Thus, there is one unknown parameter for each vertex. In the first part of the talk, I will show that there is a fast and easy algorithm for computing accurate estimates of all of these parameters from a single observed realization of the graph. This is joint work with Joe Blitzstein and Persi Diaconiss.

In the second part, I will consider the following toy problem as a precursor to more complex questions: What happens if the Hamiltonian is a linear combination of the number of edges and the number of triangles? Is it still possible to evaluate the normalizing constant?
I will present a new technique that gives an analytical solution to this problem in a `sufficiently high temperature' regime. As a byproduct , this gives an explicit formula for large deviations rate function for the number of triangles in Erdos-Renyi graphs in certain regimes.

Audio (MP3 File, Podcast Ready)

Back to Workshop III: Random and Dynamic Graphs and Networks