Course director: Mauro Sozio

Mauro Sozio (Professor, Telecom Paris, Institut Polytechnique de Paris, LTCI) sozio at telecom dash paris dot fr
Laurent Viennot (Research Director, INRIA) laurent dot viennot at inria dot fr

Graphs provide a powerful abstraction for representing a wide variety of real-world information, such as social networks, knowledge and information networks, biological networks, etc. The course will focus on the theoretical aspects of graph algorithms that work “well” in practice. We will see how theory can lead to a better understanding of the structure of the problem at hand, which, in turn, can lead to more effective or more efficient algorithms. We will also see how real-world problems can inspire interesting theoretical problems. As a result, theory and practice can be much more intertwined than we tend to believe.

We will cover (tentatively) the following main topics:

• finding cliques and dense subgraphs (sequential, parallel/distributed, dynamic algorithms)
• graph generation models (Erdös-Rényi, preferential attachment, small world phenomenon)
• graph clustering (k-center)
• graph decompositions (k-core)
• diffusion and influence maximization
• efficient representation of distances in a graph
• temporal graphs: when edges appear at certain points in time
• computing the diameter of a graph

1. 12/12/24 no class
2. 19/12/24 no class
3. 09/01/25 Intro to the course Greedy and Exact algo for Densest Subgraph Streaming Densest Subgraph
4. 16/01/25 Minimal Densest Subgraph (Lemma 4.1-4.2) Densest Subgraph via Convex Programming
5. 23/01 Fully Dynamic k-center clustering Listing k-cliques
6. 30/01 influence Max Streaming Submodular Paper Streaming Submodular Community detection
7. 06/02 Diameter computation and fine-grained complexity
8. 13/02 Fast shortest path computation and planarity
9. 20/02 Two-hop distance labelings
10. 27/02 Graph neural networks Exercise for next week , Temporal graphs
11. 06/03 Exam Mauro's part
12. 13/03 Exam Laurent's part

All classes take place between 12:45 and 15:45 on Thursdays in room 1004. The time for the exams will be communicated later on.

Some material from previous occurrences of the course (content or topics might change every year):

Finding Densest Subgraphs Finding Minimal Densest Subgraphs Listing k-cliques Influence Maximization Generative Models for Social Networks

09/12 The course will start in January (on 09/01/25)
17/04 The final marks are available on the MPRI website. Students who would like to do a make-up exam (rattrapage) should contact us by the end of April. 

The course will be in English.

During the course a few exercises related to the content of the course will be given. A subset of those exercises (or similar ones) will be asked during the final exam. Material presented during the lectures might also be asked at the final exam.

There is also the possibility of doing either a project or read a scientific article and present it. This is optional, while it gives up to 2-4 additional points on the final mark. The project typically consists of implementing efficiently a graph algorithm or a data analysis task. Students should preferably use C++, Java, or Python, however, any programming language can be used.

Students are not allowed to bring any notes at the final exam.

Some exercises for the Final Exam

Some more exercises

Good knowledge of algorithms and complexity theory. Good knowledge of Java, C++ or Python are preferable but not necessary.

Algorithm Design par J. Kleinberg et E. Tardos, Addison Welsey 2005.

D. Easley, J. Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, 2010.

• 2.11.1 Advanced algorithms
• 2.24.1 Optimization
• 2.18.1 Distributed algorithms for the networks