$\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{\mathbf{E}}\DeclareMathOperator{\deg}{deg}\newcommand{\N}{\mathbb{N}}$

COMP 4900/5900 Graph Analytics

This is the course webpage for the Winter 2026 offering of COMP4900/5900: Graph Analytics.

This course focuses on extracting information from large graphs that occur in applications as well as developing synthetic/artificial models of these graphs for testing and validation purposes.

Office Hours

I will have office hours on Tuesdays 13:00-14:30 in 5177HP.

Grading Scheme

There will be three assignments, each worth 25% of your final grade and one end-of-term exam, also worth 25% of your final grade.

The assignments will include a mix of closely-related theoretical/conceptual work and programming work.

The end-of-term exam will take place during the last class.

Students taking the graduate version of this course (COMP5900) will have additional/more advanced questions on their assignments and on their exam.

Important Dates

Assignments will be due on the last weeks of January, Febuary, and March. The end-of-term exam will take place in class on April 7th.

Background

You should be familiar with the material covered in COMP2804: Discrete Structures II, mainly counting and discrete probability. Some knowledge of algorithm design and efficiency like the material in COMP3804: Algorithm Design is helpful, but not strictly necessary. I won't assume anything beyond the material covered in COMP2402: Data Structures and even most of that is not directly relevant.

Textbooks

The main source of material taught in this course will be the textbook by Kamiński, Prałat, and Théberge. The other texts may be used for some selected topics. To keep things inexpensive, I will be using free online versions of all texts (links below).

One nice aspect of the primary textbook is that the authors have provided videos and Jupyter notebooks covering (the practical aspects of) the main chapters.

• Bogumił Kamiński, Paweł Prałat, and François Théberge, Mining complex networks. Second edition, CRC Press, 2026. [pdf]

• David Easley and Jon Kleinberg, Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press, 2010. [pdf]

• Charu C. Aggarwal and Haixun Wang (editors), Managing and Mining Graph Data. Springer, 2016 [pdf]

• Albert-László Barabási, Network Science. Cambridge University Press, 2016. [online]

Topics

The following is a rough outline of the topics we will cover in the order we will cover them. It will evolve as we progress through the course.

Here is the directory containing code and data that we discuss in class.

1. Introduction (notes from lectures 1 and 2) (code from lecture 2 (or 3))

   • Mathematical background
   • Graph theory basics (Ch. 1)
   • Working with igraph in Python

2. Random graph models

3. Centrality measures

4. Degree correlations

5. Community detection

6. Graph embeddings

7. Hypergraphs

8. Selected topics