Network Science: theory and applications

Lecturer:

Márton KARSAImarton.karsai@ens-lyon.fr
Office: ENS Lyon, IXXI, site Monod, M7.1H24
Tel: +33 426 233 805
Web: perso.ens-lyon.fr/marton.karsai

Tutorials:

Lorenza Pacini – lorenza.pacini@ens-lyon.fr

Description:

The course provides an introduction to complex network theory by walking through the established methods and the most recent techniques of modelling and analysing structured complex systems. During the course we will define the general properties, measures and models of complex networks, and the most recent developments in the field considering the dynamics on and of networks, human mobility, network embedding methods or unsupervised learning methods to characterise the mezoscopic structure of large graphs.
The course concentrate on the related theories, algorithms, models and measures of large-scale real world networks, especially focusing on network algorithms and network data analysis techniques. Tutorial is given in parallel to the course where the implementations of related models and algorithms will be carried out and tested.
The course is mandatory for students in the Modeling Complex Systems M2 program, while students from other master programs are also welcome.

Prerequisites: Background in graph theory, statistical data analysis, and algorithms is required.

Evaluation: Attendants will complete course work during the tutorial and will need to pass a written exam in the end of the course.

When: September 2019 – January 2020

Subjects:

Class 1: Introduction to network science
Complex systems as complex networks
Types and representation of complex networks
Characteristic measures of complex networks

Class 2: Advanced network characteristics
Graph spectral properties
Connectivity based and geometric centrality measures
Similarity measures

Class 3: Percolation phenomena – Random Graphs
Percolation phenomena and its models
The network percolation problem
Introduction to random graphs – the Erdös-Rényi model

Class 4: Null models for network analysis
The configuration model
Stochastic block models
Generating functions and their applications
Galton-Wattson process for networks

Class 5: Small-World networks, Watts-Strogatz model
Six degrees of separation and the small-world phenomena
The Watts-Strogatz model
Decentralised navigability in small-world networks

Class 6: Scale-free networks, Barabási-Albert model
Scale-free property and scale-free networks
Robustness of SF networks
The Barabási-Albert model

Class 7: Unsupervised characterisation of mezoscopic structure
Motifs in static networks
Modularity based methods
Methods based on higher order representations
Methods based in information compression
Network benchmarks

Class 8: Dynamics on networks
Simple spreading processes
Homogeneous mixing for spreading in unstructured population
Degree-decomposition methods for spreading on structured populations
Immunisation strategies
Complex contagion processes

Class 9: Dynamics of networks
Time-scale of network evolution
Representation of dynamic networks
Higher-order correlations in time-varying networks
Randomised reference models
Generative models of time-varying networks

Class 10: Mobility and spatial networks
Representation, characters and models of spatially embedded networks
Observation and predictability methods of human mobility
Levy-flights in human mobility
The gravity and radiation laws

Class 11: Network embedding methods
Introduction to graph-based machine learning methods
Random walk-based methods
Graph convolutional methods
Un- and semi-supervised methods

Class 12: Methods of network data analysis
analysis of heterogeneous data
sampling methods of networks
visualisation of networks

References:

M.E.J. Newman, Networks, an Introduction (Oxford University Press)
D. Easley, J. Kleinberg, Networks, Crowds, and Markets (Cambridge University Press)