Topic outline

  • General

    MS-E1052 Combinatorial Network Analysis


    • Period II: 1 November-9 December 2021
    • Lecturer: Vanni Noferini, M307, vanni dot noferini at aalto dot fi
    • Head assistant: Ryan Wood, M309, ryan dot wood at aalto dot fi
    • Registration at Susi
    • 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. Exception: since Monday 6.12 is holiday, that lecture is moved to Tuesday 7.12 (same time and same room).


    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% each of the final grade. 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

    Important: note that, as it often happens in graph theory, notations, terminology, and definitions 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, you must specify if your notation, terminology, or definitions are different than in the lecture notes.

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