MS-E1052 - Combinatorial Network Analysis D, Lecture, 23.10.2023-30.11.2023

Topic outline

• Select topic General

  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 

  
  

  • Select activity Announcements

    

    Announcements Forum
  • Select activity Introductory slides

    

    Introductory slides File PDF
  • Select activity Slides on Perron-Frobenius Theorem

    

    Slides on Perron-Frobenius Theorem File PDF
  • Select activity Slides for last lecture

    

    Slides for last lecture File PDF
  • Select activity Lecture notes, week 1

    

    Lecture notes, week 1 File PDF
  • Select activity Lecture notes, week 2

    

    Lecture notes, week 2 File PDF
  • Select activity Lecture notes, week 3

    

    Lecture notes, week 3 File PDF
  • Select activity Lecture notes, week 4

    

    Lecture notes, week 4 File PDF
  • Select activity Lecture notes, weeks 5 and 6

    

    Lecture notes, weeks 5 and 6 File PDF
  • Select activity Exercise session solutions, week 2

    Show more Show less

    Not available unless any of: You are a(n) Student ...

    Not available unless any of:

    • You are a(n) Student
    • You are a(n) Teacher
    • You are a(n) Non-editing teacher

    

    Exercise session solutions, week 2 File PDF
  • Select activity Homework 1

    Show more Show less

    Not available unless any of: You are a(n) Student ...

    Not available unless any of:

    • You are a(n) Student
    • You are a(n) Teacher
    • You are a(n) Non-editing teacher

    

    Homework 1 Assignment
  • Select activity Exercise session questions, week 3

    Show more Show less

    Not available unless any of: You are a(n) Teacher ...

    Not available unless any of:

    • You are a(n) Teacher
    • You are a(n) Student
    • You are a(n) Non-editing teacher

    

    Exercise session questions, week 3 File PDF
  • Select activity Exercise session solutions, week 3

    Show more Show less

    Not available unless any of: You are a(n) Student ...

    Not available unless any of:

    • You are a(n) Student
    • You are a(n) Teacher
    • You are a(n) Non-editing teacher

    

    Exercise session solutions, week 3 File PDF
  • Select activity List of possible projects

    

    List of possible projects File PDF
  • Select activity Homework 2

    Show more Show less

    Not available unless any of: You are a(n) Teacher ...

    Not available unless any of:

    • You are a(n) Teacher
    • You are a(n) Student
    • You are a(n) Non-editing teacher

    

    Homework 2 Assignment
  • Select activity Exercise session questions, week 5

    Show more Show less

    Not available unless any of: You are a(n) Student ...

    Not available unless any of:

    • You are a(n) Student
    • You are a(n) Teacher
    • You are a(n) Non-editing teacher

    

    Exercise session questions, week 5 File PDF