Complex Networks (2019)

Introduction
This is the page of the Complex Networks course, part of the Science of Complex Systems Option of the M2 at ENS de Lyon.
The class will cover: 1)Fundamentals of Network Science, e.g., Classic random models, centralities, small-world phenomenon, etc. 2)Focus classes on advances topics, e.g., dynamic networks, community detection, machine learning on graphs 3)An introduction to cutting-edge research topics, such as Graph embedding and Graph Convolutional Neural Networks (GCN).

Objectives
This class is thought to provide a broad overview of current topics in network science. It is grouded in research, with short presentations by researchers in the field introducing their research questions, and a cession for collective reading and commenting of recent scientific articles. The objective of the course is to lead the students to a point where they are able to gain a general understanding of most articles currently published in the field.

Overview of the course
The course is composed of 24h of lectures, and 6 hours of tutorial (TP).

Lectures will take place every Thursday at 10:15 a.m in amphi H. (Exceptionnaly the first lecture (September 12) will start at 10:45).
The content of the class this year is new, but based in part on the course of the previous lecturer, Marton Karsai, in part on a previous lecture by myself, and in part on new contents.

Tutorials

Tutorials will take place on thursday mornings, before the lectures (8:00-10:00 a.m), the following days: October 17, November 21, November 28. You can find below the description of each session. Note that you can do them at your own pace, but:
  • The first two ones are useful to give you a concrete notion of what dealing with networks can mean, and constitute an introduction to the manipulation of networks through code
  • The last one requires you to send us files that we will grade, so don't forget not to spend too much time on the others.
  1. Tutorial 1: networks from scratch. PDF - graph.py
  2. Tutorial 2: networkx library and random models. PDF
  3. Tutorial 3: Project. PDF Examples of projects: files

Lectures

Below is an overview of the class, and slides of presentations.
  1. Introduction, Describing Networks: PDF, notebook
  2. Centralities and Similarities: PDF, Eigenvector Centrality notebook
  3. Random Graph Models I: ER, Configuration, WS PDF, friendship paradox notebook
  4. Guest Speakers: Complex Networks seen by researchers Luisa Di Paola - Lorenza Pacini - Esteban Bautista
  5. Random Graph Models II: Scale Free, Barabasi, Forest Fire, etc. PDF
  6. Communities and Community Detection PDF
  7. Dynamic Networks PDF
  8. Complexifying Complex Networks (Multilayer, higher Order, Spatial, etc.) PDF
  9. Machine Learning on graphs (Link Prediction, Node classification, etc.) PDF
  10. Graph Embedding and Graph Convolutional Networks PDF notebook
  11. Spreading Processes PDF
  12. Last class: article reading and commenting. Note: the last two classes are on the same day

Exams

There will be two grades given in this class:
  • One grade for the tutorials' project, representing 40% of the mark. The project should be sent to Rémy Cazabet (remy.cazabet AT univ-lyon1.fr) before UPDATE: Friday December 20, 23:59.
  • One grade for the final exam, representing 60% of the mark. The exam will take place on December 19 at 8:15 a.m. (3 hours)
The final exam will consist in writing an analysis of short (e.g., 10 pages) scientific articles taken from the network science literature. More precisely, several questions will be asked about particular aspects of the article. Examples of questions could be:
  • Explain in your own terms the interpretation of a definition/equation
  • Comment about a proposed definition (a centrality, a community detection algorithm...) by doing a parallel with related definitions/methods we have discussed during the class
  • Propose a variant, an improvement of a method introduced in the paper, based on what we have seen during the class
  • Write a critical evaluation about some aspect of the article, weaknesses and/or strengths you could identify compared to the state of the art (introduced in the class).
All written documents will be allowed. You can train yourself to read such short articles by looking at those recently published in the latest complex networks conference, for instance (all articles can be downloaded free of charge): https://www.complexnetworks.org .
As this was requested by some students, I provide last years exams for reference. Note however that the teacher was different, the content of the class was different, and the nature of the exam was different. EXAM, default version --- EXAM, Cognitive Science students version.