Complex Networks - 2020/2021

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 covers: 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, collective reading and commenting of recent scientific articles, and experimental applications of key concepts. 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).


Previous Versions

The page of last year's course can be found there: 2019/2020. Before that, the instructor was Marton Karsai and its course can be found there.

E-learning setting

Due to the COVID situation, I'll do my best to allow students to follow classes online. Because I'm not an ENS de Lyon staff member, I cannot use some official tools, so here are the settings I propose (I'm open to any improvement, we are all experimenting here)
  • All classes will be streamed online at the following address : https://univ-lyon1.webex.com/meet/remy.cazabet, using Webex, which should work with any operating system and most browsers.
  • Classes will be recorded, and slides and recordings will be available a few hours after each class, on this page
  • A discord channel. You can register using this link : https://discord.gg/ZXg4yGP. This can be more convenient than e-mails for discussions which are not strictly personal (questions about the class, about exams, etc.).

Program, classes and content

Below is an overview of the courses and practicals. As the classes are done, I'll add my presentation slides, recordings, some notebooks, etc. All videos are availble on a Youtube Channel for simplicity.
This organization can be subject to changes !.

Day Time Room Type Topic Resources
Tuesday 09/15 10h15-12h15 F Lecture Introduction, Describing Networks CheatSheet Intro - CheatSheet Matrix - Video - Slides
Thursday 09/17 10h15-12h15 F Lecture CentralitiesCheatSheet - Slides - Experiments Video
Thursday 09/24 08h-9h30H TD - Practicals Python / Gephi / Network structurePractical 1
Thursday 10/01 08h-10hH Lecture Random Graph Models I: ER, ConfigurationCheatSheet - Slides - Experiments
Thursday 10/08 08h-10hH Lecture Random Graph Models II: WS, Scale Free, Barabasi-Albert.CheatSheet Scale-Free - Slides - ExperimentsVideo
Thursday 10/15
Tuesday 10/13
08h-10h
10:15-12:15
HF Lecture Communities and Community DetectionCheatSheet - Slides - Experiments - Video
Thursday 10/22 08h-10hH TD - Practicals Project / Python TD - project
Thursday 11/05 10h15-12h15? Lecture Visualization - AssortativityVideo1 - Video2 - CheatSheet - Experiments - Slides1 - Slides2
Thursday 11/12 10h15-12h15F Lecture Dynamic NetworksVideo - CheatSheet - Experiments - Slides
Thursday 11/19 10h15-12h15F Lecture Spreading ProcessesVideo - CheatSheet - Experiments - Slides
Thursday 11/26 10h15-12h15F Lecture Spatial NetworksVideo - CheatSheet - Experiments - Slides - Misc. Networks video
Thursday 12/03 10h15-12h15F Lecture Machine Learning on graphs (Link Prediction, Node classification, etc.)Video - CheatSheet - Experiments - Slides
Tuesday 12/08 10h15-12h15F TD - Practicals Project / Python
Thursday 12/10 10h15-12h15F Lecture Graph EmbeddingVideo - CheatSheet - Experiments - Slides
Thursday 12/17 10h15-12h15F Lecture Last class: article reading and commenting.Bonus: CheatSheet GCN


Networks


Small network StarWars(.graphml)
Small network Game Of Thrones(.csv)
Medium network Airports(.edges)
Airports with location and country(.graphml)

Dataset collections
There are many network dataset repositories available on the web, here is for instance a collection of collection of networks: network-datasets
A recent addition to this list is Netzschleuder repository, which has the advantage of allowing to load a graph directly from its name. Here is a minimal working example, to load the openflights dataset:

from io import BytesIO
from zipfile import ZipFile
from urllib.request import urlopen
address="https://networks.skewed.de/net/openflights/files/openflights.csv.zip"
resp=urlopen(address)
zipfile = ZipFile(BytesIO(resp.read()))
strf=zipfile.read("edges.csv").decode().split("\n")
g= nx.parse_edgelist(strf,delimiter=",",data=False)

Tools

For tutorials and the experimental part of lectures, you need to use some softwares, detailed below.

Gephi

Gephi is a software for basic graph manipulation and visualization. Although you can't do much in term of graph analysis, it is really convenient to explore and visualize graphs of small to medium size ( < 1000 nodes).
It can be donwloaded there : Gephi.
Gephi requires Java, and suffer from a few bugs on windows (but there is no better alternative). Here are solutions to common problems:

Python

Most of the experiments are done in python. If you're not familiar with this language, there are numerous tutorials on the web. A good one for instance is from w3schools. If you want to be all set-up for experiments, here is a list of packages we will use. Note that some of them are only available with pip, and not anaconda. If you're using anaconda, you can neverthless use them, using the pip command (pip install package_name).
  • networkx. Generic network analysis
  • notebook. Jupyter notebook
  • cdlib. Community detection
  • tnetwork. Temporal networks
  • scikit-learn. Machine learning/Data mining
  • seaborn. ploting library

Exams

Important dates:
The final date to send the project is Sunday, December 20 at 23:59.
The written exam will take place on Thursday, January 7, from 10:15 to 12:15.


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).
  • One grade for the final exam, representing 60% of the mark.
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 : https://www.complexnetworks.org .
Last year exam can be found there: Subject - Article.