Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Theory of practical graph algorithms (24h, 3 ECTS, period 2)

Course director: Mauro Sozio

Teachers for 2022-2023

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

Scientific and pedagogical content

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

Content and (tentative) schedule

  1. 7.12.22 no class (canceled due to health issues of the professor)
  2. 14.12.22 no class (canceled due to health issues of the professor)
  3. 01.03.23 Exam 2h (Mauro's part) 12:45-14:45 room 1004 (same of the course)
  4. 08.03.23 Exam 2h (Laurent's part)

All classes take place between 12:45 and 15:45 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 Fast shortest path computation and planarity Practical distance labeling and skeleton dimension Temporal graphs, a hierarchy of models Diameter computation and hardness in P

Exercises and Research Questions

Project/Reading Material

Student have the possibility of doing a project, which typically consists of implementing a graph algorithm or a data analysis task. Alternatively, students could read a scientific paper and present it. Either one is optional, while it gives up to 2-3 additional points on the final mark.

Short description and organization

Text of the optional practical project (Deadline February 28th)

News and Announcements

  • 14/05 The notes have been published on the MPRI website. Students who did not pass the exam may contact Laurent or Mauro to schedule an oral exam.
  • 27/01 All material for the first part of the course has been posted on the website.
  • 19/01 The text of the optional project has been posted on the website. A list of exercises for the final exam has also been posted.
  • 12/01 About minimal densest subgraph: I am pretty convinced that the algorithm that some of you proposed in the class works, it is simpler and deterministic, so it is interesting. Bravo to those who came up with this!!! (I am going to ask your names next week for some extra points). I will teach that algorithm in future occurrences of this course. The lemma about the small number of eps-bad nodes still contains some interesting info, an interesting question is whether this or some other facts can be used to speed up the algo even further. Keep up the good work!
  • 13/12 Schedule has changed, no class on 06/12 or 13/12. The course will start on 04/01
  • 06/12 The class on 07/12 is canceled due to health issues of the professor

Teaching language

The course will be in English.

Evaluation

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.

Prerequisites

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

Related Books

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.

Related courses

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA