BLG 549E - Graph Theory and Algorithms

Course Objectives

This courses aims to teach students the fundamental of the field of graph theory while branching into hot topics such as "deep learning on graphs" and "data analysis". Students will gain theoretical and practical experience through exercises and projects. This course will address different questions such as:

1. What is a graph?
2. How to formalize a problem using graphs and graph-based algorithms?
3. How to solve real-world problems using graphs?

Course Description

The following is a *preliminary syllabus* of the course —which will be refined:

1. Introduction to graph theory (week 1)
1.1. Motivation and broad introduction: The sample is a graph, a node in a graph is a sample! Ways of using graphs. We can look at graphs in different ways, use them in diverse manners.
1.2. Graphs representation (nodes, edges, types of graphs, directionality, sparsity, adjacency matrix)
1.3 Types of graphs including decorated or annotated graphs (where nodes take attributes)

Murphy, A.C. et al. Explicitly linking regional activation and function connectivity:
community structure of weighted networks with continuous annotation. Preprint
at https://arxiv.org/abs/1611.07962 (2016).

1.4. Introduction to graph topology (degree, centrality, neighbourhood) ==> What is the difference between a graph encoded in an adjacency matrix and an image?


2. Graph topology: tools and measures (week 2)
2.1. Centrality, Hubs, Cliques
2.2 Component, cores, and clubs
2.3 Clustering, Degeneracy, and Small Worlds [subgraphs and motifs, modularity] (week 3)

3. Basic graph-based algorithms: start with the fundamentals and go deeper with “deep learning”
3.1 Paths (path length), diffusion, and Navigation (shortest path); Chinese Postman problem, travelling salesman problem; Dijkstra’s Method (week 4)
3.2 Hamiltonian cycle and Eulerian tour
3.3 Diffusion on graphs (information, false news on FB/Twitter), transition matrix (SNF) (week); network morphospace (Bullmore)
3.4 Graph matching algorithms (week 6)


4. Graph transformation techniques
4.1 Graph factorisation techniques with and without learning (factors, arboricity, domination, independence) (week 8)
4.2 Graph Filtering techniques (week 9)
4.3 Graph spectral analysis, spectral embedding(week 10)
4.4 Graph dim reduction techniques and embedding (week 11)
4.5 Graph convolution networks (GCNs) (week 12)