We will show how physical metaphors can help us understand the structure of a graph. The graphs arising in different disciplines can have very different characteristics: social networks, protein-protein interactions networks, road networks, and scientific meshes are all graphs. But, they can look very different from each other. This diversity makes it difficult to understand arbitrary graphs.
We will explore an approach to understanding graphs that has been unreasonably successful: imagining that a graph represents a phyisical object. For example, we may pretend that the edges of a graph are springs, rubber bands, or resistors. Linear algebraic techniques for understanding these physical systems naturally lead to the development of spectral and algebraic graph theory. We will survey some of the fundamental ideas from these fields.
Daniel Alan Spielman received his B.A. in Mathematics and Computer Science from Yale in 1992, and his Ph.D in Applied Mathematics from M.I.T. in 1995. He spent a year as a NSF Mathematical Sciences Postdoc in the Computer Science Department at U.C. Berkeley, and then taught in the Applied Mathematics Department at M.I.T. until 2005. Since 2006, he has been a Professor at Yale University. He is presently the Henry Ford II Professor of Computer Science, Mathematics, and Applied Mathematics.
He has received many awards, including the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Paper Award, the 2008 Godel Prize, the 2009 Fulkerson Prize, the 2010 Nevanlinna Prize, an inaugural Simons Investigator Award, and a MacArthur Fellowship. He is a Fellow of the Association for Computing Machinery and a member of the Connecticut Academy of Science and Engineering. His main research interests include the design and analysis of algorithms, graph theory, machine learning, error-correcting codes and combinatorial scientific computing.