This class will be a seminar class which interweaves two points of view: structure of random graphs and statistical inference on graphs. On one had, we will explore different models of random graphs and the structure they produce. Topics in this direction will include, Erdos-Renyi graphs, small world networks, phase transitions and processes such as epidemics on random graphs. The second aspect will explore inference and computational aspects of graphical models focusing on Gauss-Markov random graphs. Topics will cover graphical models and multivariate Gaussians, factor graphs, decomposable graphical models, Wishart distributions, loopy belief propagation, variational approximate inference, diffusion graphs, elements of spectral graph theory, and geometric perspectives including multiscale graphical models. This class is necessarily work in progress, the exact topics covered will be influenced by the participants (as well as the instructors).