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

Graph Mining (24h, 3 ECTS, period 2)

Course director: Mauro Sozio

Teachers for 2020-2021

Mauro Sozio (MC1 Telecom Paris, IP Paris, LTCI) sozio at telecom dash paristech dot fr
Laurent Viennot (DR INRIA, IRIF, Paris Diderot) 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 main objective of the course is to present the models and algorithms for discovering structures in large graphs, while covering the main theoretical and practical aspects of graph mining. In particular, algorithms with theoretical guarantees as well as algorithms that are proven to work well in practice will be discussed. We will cover 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 and community detection (Louvain algorithm, clustering algorithms on the metric space)
  • graph decompositions (k-core, modular, local decompositions)
  • diffusion and influence maximization
  • ranking (PageRank, HITS)
  • Diameter computation: heuristics and lower bounds.
  • Distance distribution computation: sampling and sketch techniques.
  • Distance based centrality measures: betweenness and closeness.
  • Temporal graphs: definitions, problems, algorithms, and complexity.

Content and schedule

Exercises and Research Questions

Please find below a list of exercises for the final exam. The same or very similar exercises will be asked at the exam. A few more exercises will be added shortly.

Exercises on the on the 1st part and on the 2nd part of the course

Default Projects:

You can choose one project among the following ones. The deadline is 24/11 for both of them. Doing a project is not required to pass the course, however, in case no project is completed the maximum note is capped at 16.

Project on 3-Hopsets (Update 14/11: after requests, Rust and Go are also supported) Project on Community Search

News and Announcements

  • 14/09 The course on graph mining starts tomorrow!
  • 21/10 The two projects have been posted on the website
  • 23/10 Some typos have been fixed on the slides and on the text of the project (Mauro's part)
  • 02/11 The remaining classes will be online due to the lockdown in France. In case you would like to attend the course and you don't have the link, please contact Mauro Sozio.
  • 16/11 Some exercises have been posted, a few more will be added shortly.
  • 30/11 The exam will take place on 01/12 between 9-11am. It will take place remotely, using the same link we usually use for the course. In case you didn't receive the link, please contact one of the instructors of the course.
  • 06/01 The final notes have been posted on the MPRI website.

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.

The final exam contributes to 80% of the maximum grade, while a practical project contributes to 20% of the maximum grade. The project is not required to pass the course. It 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