CR15 - Complex Networks


Master 2 course organised by

    ENS Lyon Computer Science Department

    IXXI - Rhone Alpes Complex System Institute

 

The course provides an introduction to complex network theory by walking through the established methods and the most recent techniques of modeling and analyzing structured complex systems. During the course we will define the general properties and measures of complex networks, fundamental network models (ER networks, SW networks, BA networks), structural phase-transitions, node and link centrality measures, network modularity and community detection methods, temporal, multiplex and spatial networks, and network construction practical analysis.

The course consists of two parts. The first part is concentrating on the related theories, algorithms, models and measures of networks, while the second part gives an introduction to the different types, representations, and applications of complex networks.

Tutorial is given in parallel to the course where the related analytic calculations and network implementations will be discussed. Tutorial is not mandatory for students out of the Modeling Complex Systems M2 program.

The course is mandatory for students in the Modeling Complex Systems M2 program and included in the course offer for M2 Computer Science students at ENS Lyon. Students from other master programs are also welcome.

Prerequisites: Background in graph theory, statistical analysis, and computer algorithms is an advantage but is not mandatory, as the course intends to be accessible for students coming from different disciplines

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 2017 - January 2017

Subjects:

Introduction and general network characteristics (MK)

        - Complex systems as complex networks

        - Representation of complex networks

        - Characteristic measures of complex networks

Betweenness centrality and algorithm (EF)

        - The Brandes Algorithm

Erdös-Rényi random networks (EF)

        - Definitions and statistical properties

        - Structural phase transition

Configuration model networks (EF)

        - Definitions and statistical properties

        - Stochastic block models

Small-world networks (EF)

        - Definitions and statistical properties

        - Navigability in small-world networks (Kleinberg algorithm)

Scale-free networks, Barabási-Albert model (MK)

        - Scale-free property and observations

        - Vulnerability and robustness

        - The BA model

        - Alternative models of scale-free networks

Motifs and communities (MK)

        - Motifs in static networks

        - Communities - basics

        - Modularity based methods: Girvan Newman algorithm, Louvain algorithm

        - Overlapping communities: Link-communities, Clique percolation

        - The Infomap method

        - Network benchmarks

Temporal networks (MK)

        - Time-scales and representation

        - Micro- and macroscopic measures of temporal networks

        - Correlations in temporal networks

        - Random reference models of temporal networks

        - Generative models of temporal networks

Spatial networks (MK)

        - Definition, representation, and characterization

        - Simple models of spatial networks

        - Human mobility - the gravity law - the radiation law

Multilayer and multiplex networks (MK)

        - Definition and representation

        - Characterization and general measures

        - Interdependent networks

        - Cascading failures in interdependent networks

From data to networks 1 (MK)

        - Network construction from data

        - Statistical analysis and fitting methods

        - Sampling and biases

        - Visualization and applications

From data to networks 2 (EF)

        - signal processing on graph

        - semi-supervised learning




Books:

  1. M.E.J. Newman, Networks, an Introduction (Oxford University Press)

  2. D. Easley, J. Kleinberg, Networks, Crowds, and Markets (Cambridge University Press)

Reviews:

  1. M.E.J. Newman, The structure and function of complex networks, SIAM Review 45, 167-256 (2003).

  2. R. Albert, A-L. Barabási, Statistical Mechanics of Complex Networks, Rev. Mod. Phys. 74, 47-97 (2002)

 

24 hours lecture + 6 hours tutorial (4 ECTS)


Lecturers:

  1. Márton KARSAI - marton.karsai@ens-lyon.fr

          Office: ENS Lyon, IXXI, site Monod, N222

          Tel: +33 426 233 805

          Web: perso.ens-lyon.fr/marton.karsai


  1. Eric FLEURY - eric.fleury@ens-lyon.fr

           Office: ENS Lyon, IXXI, site Monod, N232


Tutorials:

  1. Samuel UNICOMB - samuel.unicomb@ens-lyon.fr