ST2: Mathematical Modeling of Propagation Phenomena

Propagation on Graphs

Course Overview

General Info:

  • CentraleSupélec
  • Dates: December '18 - January '19

Instructor: Fragkiskos Malliaros (John Cagnol, Sarah Lemler and Véronique Letort also participate at the thematic sequence ST2)
Email: fragkiskos.me [at] gmail.com
Office hours: Right after class (or send me an email and we will find a good time to meet)

TA: Abdulkadir Çelikkanat
Email: abdcelikkanat [at] gmail.com

Piazza: piazza.com/centralesupelec/winter2019/st2/home


Which people should we immunize, to prevent an epidemic (e.g., Ebola) as fast as possible? Which users should we target to in order to achieve an effective promotion campaign for our product? How do opinions or rumors get formed and propagate in social media (e.g., Twitter)? The modeling of propagation in various contexts (populations, materials, computer networks, social networks) has seen great progress in its formalization in recent decades. The goal of this class is to familiarize students with the classic techniques that will allow them to reproduce, predict and anticipate the effects of a virus or information propagation in real-life situations. Two main approaches will be considered in this course: propagation in a homogeneous population, leading to continuous modeling; propagation in a structured population with an underlying graph layer. In the latter case, the properties of the propagation phenomenon depend on the graph structure.





Schedule and Lectures

The slides for each lecture will be posted on piazza just before the start of the class.

Date Topic Material
1December 10 Introduction to propagation modeling and graph analysis Lecture 1
2December 12 Centrality criteria and link analysis algorithms Lecture 2
3December 17 Models of information propagation on graphs Lecture 3
4December 19 Identification of influential spreaders on graphs Lecture 4
5January 7 Influence maximization in social networks Lecture 5



[December 10] Lecture 1: Introduction to propagation modeling and graph analysis

Introduction to propagation modeling and graph analysis. Administrivia and course structure. Presentation of basic concepts in graph theory, linear algebra and spectral graph theory that will be used throughout the course. Basic network properties: degree distribution, clustering coefficient and shortest path length.

Reading: Additional:

[December 12] Lecture 2: Centrality criteria and link analysis algorithms

Centrality criteria in graphs (degree, closeness, betweenness, eigenvector, Katz). Core decomposition on graphs. Link analysis ranking algorithms (HITS and PageRank).

Reading: Additional:

[December 17] Lecture 3: Models of information propagation on graphs

Cascading behavior on graphs. Models of virus and information propagation.

Reading: Additional:

[December 19] Lecture 4: Identification of influential spreaders on graphs

Core decomposition and algorithms. Applications in dense subgraph detection, community detection, identification of influential spreaders.

Reading:
Additional:

[January 7] Lecture 5: Influence maximization

Influence maximization in social networks. The Greedy algorithm. Outbreak detection in networks.

Reading:
Additional:


Course Structure

Learning objectives

Introduce students to the field of graph analysis for propagation modeling by:
  • Covering a wide range of topics, methodologies and applications related to information spreading over networks.
  • Giving the students the opportunity to obtain hands-on experience on dealing with graph data analysis for propagation phenomena.
We expect that by the end of the course, the students will have a thorough understanding of various data analysis tasks related to graphs and information spreading, and will be able to formulate and solve problems that involve propagation phenomena on networks.


Prerequisites

There is no official prerequisite for this course. However, the students are expected to:

  • Have basic knowledge of graph theory and linear algebra.
  • Be familiar with at least one programming language (e.g., Python or any language of their preference).
In the first lecture, we will review basic concepts in graph theory and linear algebra.


Reading material

Most of the material of the course is based on the books shown below. Some of the topics covered in the course are also based on research articles.




Resources

Software tools

  • NetworkX: Python software package for graph analytics
  • igraph: collection of software packages for graph theory and network analysis (Python, C++ and R)
  • SNAP: high performance system for the analysis of large network (C++ and Python)
  • seaborn: statistical data visualization based on matplotlib
  • scikit-learn: Machine Learning library in Python
  • pandas: Python data analysis library
  • Gephi: graph visualization and exploration software