Topic outline

  • General

    MS-E1052 Combinatorial Network Analysis


    • Period II: 23 October-30 November 2023
    • Lecturer: Vanni Noferini, M307, vanni dot noferini at aalto dot fi
    • Head assistant: Ryan Wood, M309, ryan dot wood at aalto dot fi
    • Registration in Sisu
    • Content: review of basic graph theory, spectral theory for adjacency matrix and graph Laplacian, centrality measures, deformed graph Laplacian, spectral clustering.
    • Lectures and exercise sessions: Mondays 14:15-16:00 in M234 (M3), Thursdays 14:15-16:00 in Y313.
    • Lecture notes will be uploaded in MyCourses. For pedagogical reasons, this will normally happen each week after the lectures.
    • Material for exercises and homework will also appear in MyCourses.


    How to pass the course

    The assessment for this course is via homework + final project. There will be two homework sheets, whose mark is worth 20% of the final grade each. The final project's mark is worth 60% of the final grade. More details on the homework and the project will be given during the course.

    Tentative Schedule

    • Week 1. Introduction. Review of basic graph theory.
    • Week 2. Algebraic graph theory: spectral theory for the adjacency matrix and the graph Laplacian.
    • Week 3. Introduction to walk-based centrality measures. Katz centrality.
    • Week 4. Non-backtracking walks. Deformed graph Laplacian and its spectrum.
    • Week 5. Non-backtracking centrality measures and deformed graph Laplacian. Introduction to clustering.
    • Week 6. Spectral techniques for clustering.

    Recommended books and articles for further reading

    As it often happens in graph theory, notations, terminology, and definitions in the recommended books may slightly differ from the lecture notes. For the homework, it will be tacitly agreed that notations, terminology, and definitions are as in the lecture notes; in the project, it is OK if you wish to adopt notation, terminology, or definitions that are different than in the lecture notes, but in this case you must specify it for clarity.

    • U. Brandes, T. Erlebach (editors), Network analysis -- Methodological foundations, Springer
    • E. Estrada, P. Knight, A first course in network theory, Oxford University Press