The Laplacian matrices of graphs are used to solve problems in many fields, including Machine Learning, Computer Vision, Optimization, Computational Science, and of course Network Analysis. We will explain what these matrices are and why they arise in so many applications.

We then introduce ideas that allow us to solve systems of linear equations in Laplacian matrices in nearly linear time, emphasizing the utility of graph sparsification — the approximation of a graph by a sparser one. As an application, we explain how Laplacian system solvers can be used to quickly solve network optimization problems.