Lecturer:

**Márton KARSAI** – marton.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)