Applications of Algebraic Graph Theory
Teacher
Gabriele Oliva
Abstract
Roughly speaking, Algebraic Graph Theory is the art of applying algebraic methods in order to solve problems about graphs.
This course aims at presenting some of the major applications of Algebraic Graph Theory, with particular reference to Laplacian matrices and Random Walks.
As a first step, the course will provide a brief introduction regarding the key concepts in the algebraic (i.e., eigenvalues, eigenvectors, eigenspaces, etc.) and graph-theoretical (i.e., nodes, edges, paths, loops, etc.) domains, along with the major notions that relate algebra and graphs (i.e., adjacency and incidence matrices, Laplacian matrices, algebraic connectivity, etc.).
Then, the course will present selected applications:
• Distributed Control: the course will present the key approaches to let a set of distributed agents reach an agreement without a central coordination. Specifically, the course will introduce to distributed averaging approaches such as consensus and gossip, and will discuss their application to coordination tasks such as flocking, data fusion and connectivity estimation.
• Laplacian Graph Drawing and Clustering: this module will present applications of the Laplacian matrix such as the embedding of a graph in the Euclidean space and the detection of communities based on the degree of interconnection among individuals.
• Random Walks: this unit will present random walks, a convenient framework to model the random exploration of a graph. Such a formalism is often used to explain phenomena such as the motion of foraging beasts or the diffusion of an epidemic. In particular, the course will focus on characterizing the main properties of random walks from the algebraic side and will present some of the major applications in different domains, ranging from economy to biology and mobile robotics.
• Metropolis-Hastings Techniques: the last module reviews the Metropolis-Hastings approaches, that aim at biasing a random walk in order to achieve arbitrary probability distributions. The course will present such techniques as a convenient way to sample from probability distributions that are not easily described in a closed form. Moreover, the course will inspect the connection between these approaches and the Analytic Hierarchy Process, a popular decision making framework.
Program
1. Brief introduction to Algebraic Graph Theory
2. Distributed Control
3. Laplacian Graph Drawing and Clustering
4. Random Walks
5. Metropolis-Hastings Techniques
Primary Material
Primary source material will be readings in the form of research papers and material provided by the instructor.
