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

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-29-2 [2019/02/25 07:31]
sozio [Content and schedule]
cours:c-2-29-2 [2020/02/22 10:38] (current)
crescenzi [News and Announcements]
Line 5: Line 5:
  
  
-==== Teachers for 2018-2019 ====+==== Teachers for 2019-2020 ====
  
-Mauro Sozio (MC1 Telecom Paristech, LTCI) sozio at telecom dot paristech dot fr\\ +Pierluigi Crescenzi (Prof. Paris Diderot) pierluigi dot crescenzi at irif dot fr \\ 
-Laurent Viennot (DR INRIA, IRIF, Paris Diderot) \\+Mauro Sozio (MC1 Telecom Paris, IP Paris, LTCI) sozio at telecom dot paristech dot fr\\ 
 +Laurent Viennot (DR INRIA, IRIF, Paris Diderot) laurent dot viennot at inria dot fr \\
  
 ==== Scientific and pedagogical content ==== ==== Scientific and pedagogical content ====
Line 16: Line 17:
   *finding cliques and dense subgraphs (sequential, parallel/distributed, dynamic algorithms)   *finding cliques and dense subgraphs (sequential, parallel/distributed, dynamic algorithms)
   *graph generation models (Erdös-Rényi, preferential attachment, small world phenomenon)   *graph generation models (Erdös-Rényi, preferential attachment, small world phenomenon)
-  *community and event detection (Louvain algorithm, event detection via densest subgraph computation, impossibility theorem for clustering)+  *graph clustering and community detection (Louvain algorithm, clustering algorithms on the metric space)
   *graph decompositions (k-core, modular, local decompositions)   *graph decompositions (k-core, modular, local decompositions)
   *diffusion and influence maximization   *diffusion and influence maximization
   *ranking (PageRank, HITS)   *ranking (PageRank, HITS)
-  *Mining road networks (pre-computation for shortest path queries, distance labeling and highway dimension, radius and diameter heuristics) +  *Diameter computation: heuristics and lower bounds. 
-  *Graph decomposition methods and algorithmsSurvey of exact algorithms for modular decomposition and some other polynomial graph decompositions and approximation methods for NP-hard decompositions such as treewidth or treelength+  *Distance distribution computation: sampling and sketch techniques. 
 +  *Distance based centrality measures: betweenness and closeness. 
 +  *Temporal graphs: definitions, problems, algorithmsand complexity.
  
 ==== Content and schedule ==== ==== Content and schedule ====
-  - **05/12**:[[https://sites.google.com/site/maurosozio/L1a-IntroGraphMiningMPRI.pdf?attredirects=0&d=1|Introduction to the Course]][[https://sites.google.com/site/maurosozio/communityMPRI.pdf?attredirects=0&d=1|Community Detection]][[https://sites.google.com/site/maurosozio/PageRankMPRI.pdf?attredirects=0&d=1|PageRank]] +  - **19/12**: [[https://sites.google.com/site/maurosozio/L1a-IntroGraphMiningMPRI.pdf?attredirects=0&d=1|Intro]] [[https://sites.google.com/site/maurosozio/communityDetMPRI.pdf?attredirects=0&d=1|Community Detection]] [[https://sites.google.com/site/maurosozio/PageRankMPRI.pdf?attredirects=0&d=1|Pagerank]] [[https://sites.google.com/site/maurosozio/communitySeedMPRI.pdf?attredirects=0&d=1|Community Detection with seed nodes]] 
-  - **12/12** [[https://sites.google.com/site/maurosozio/communitySeedMPRI.pdf?attredirects=0&d=1|Commmunity Detection with Seed Nodes]][[https://sites.google.com/site/maurosozio/DensestMPRI.pdf?attredirects=0&d=1|Finding Densest Subgraphs]][[https://sites.google.com/site/maurosozio/ProjectIntMPRI.pdf?attredirects=0&d=1|Project and Internship]] +  - **09/01**: [[https://sites.google.com/site/maurosozio/DensestMPRI19.pdf?attredirects=0&d=1|Finding Densest Subgraphs]][[https://sites.google.com/site/maurosozio/wsdm2015.pdf?attredirects=0&d=1|Minimal Densest Subgraphs and more on LP formulation]] 
-  - **19/12**:[[https://sites.google.com/site/maurosozio/wsdm2015.pdf?attredirects=0&d=1|Minimal Densest Subgraphs (paper)]] +  - **16/01**: [[https://sites.google.com/site/maurosozio/denseCPMPRI.pdf?attredirects=0&d=1|Densest Subgraphs via Convex Programming (Notes)]] [[https://sites.google.com/site/maurosozio/densityFriendly.pdf?attredirects=0&d=1|Densest Subgraphs via Convex Programming (Slides)]] 
-  - **16/01**:[[https://sites.google.com/site/maurosozio/denseCPMPRI.pdf?attredirects=0&d=1|Notes on Finding Densest Subgraphs via Convex Opt]][[https://sites.google.com/site/maurosozio/densityFriendlyMPRI19.pdf?attredirects=0&d=1|Experiments]] +  - **23/01**: [[https://sites.google.com/site/maurosozio/infmaxMPRI.pdf?attredirects=0&d=1|Influence Maximization]] [[https://sites.google.com/site/maurosozio/streamingSubmodularMPRI.pdf?attredirects=0&d=1|Streaming Algorithms (slides)]] [[https://sites.google.com/site/maurosozio/badanidiyuru14streaming.pdf?attredirects=0&d=1|Streaming Submodular Optimization (paper)]] [[https://sites.google.com/site/maurosozio/dynclust.pdf?attredirects=0&d=1|Fully Dynamic k-center clustering]] 
-  - **23/01**:[[https://sites.google.com/site/maurosozio/infmaxMPRI.pdf?attredirects=0&d=1|Influence Maximization]] [[https://sites.google.com/site/maurosozio/streamingSubmodularMPRI.pdf?attredirects=0&d=1|Streaming Graph Mining]][[https://sites.google.com/site/maurosozio/badanidiyuru14streaming.pdf?attredirects=0&d=1|Paper on streaming submodular optimization]] +  - **30/01**: [[https://slides.com/piluc/gm-1/fullscreen?token=FoVCTAuw|Diameter computation]] 
-  - **30/01**: [[https://sites.google.com/site/maurosozio/generativeModels.pdf?attredirects=0&d=1|Generative Models]] [[https://sites.google.com/site/maurosozio/dynclust.pdf?attredirects=0&d=1|Fully Dynamic k-cener clustering]][[https://sites.google.com/site/maurosozio/misc.pdf?attredirects=0&d=1|Miscellanous Topics]] +  - **06/02**: [[https://slides.com/piluc/gm2/fullscreen?token=_08rG4v5|Distance distributions: sampling and sketches]] 
-  - **06/02**:[[https://sites.google.com/site/maurosozio/fast_shortest_paths.pdf?attredirects=0&d=1|Shortest Paths Computation]] +  - **13/02**: [[https://slides.com/piluc/gm3/fullscreen?token=eosV6tAN|Centrality measures: betweenness and closeness]] 
-  - **13/02**: +  - **20/02**: [[https://slides.com/piluc/gm4/fullscreen?token=2T9G9sUR|Temporal graphs]] 
-  - **27/02**: Final Exam (start 13.45 end 15.45) in room 1004 (same of our classes) +  - **27/02**: Exam
 ==== Exercises and Research Questions ==== ==== Exercises and Research Questions ====
 A list of exercises follows. Similar or the very same exercises might be asked at the exam. A list of exercises follows. Similar or the very same exercises might be asked at the exam.
-[[https://sites.google.com/site/maurosozio/ExercisesMPRI18.pdf?attredirects=0&d=1|Exercises]] 
-==== Default Project: Streaming k-Center Clustering with Outliers ==== 
  
-The text of the project can be found here [[https://sites.google.com/site/maurosozio/TextProjectMPRI19.pdf?attredirects=0&d=1|Text of the Project]]+[[https://sites.google.com/site/maurosozio/ExercisesMPRI19.pdf?attredirects=0&d=1|Exercises]] and [[https://www.pilucrescenzi.it/gm/exercises_02.pdf|Exercises]]
  
  
-The dataset we are going to use consists of a collection of 1M tweets where only the timestamp and the geographic location have been retained: [[https://partage.mines-telecom.fr/index.php/s/W2iP72sRfwp2AkI/download|Dataset]] (read the readme file which contains some information about the file format and other valuable info) +==== Default Project==== 
-  +[[https://sites.google.com/site/maurosozio/ProjectMPRI2020.zip?attredirects=0&d=1|Text of the Project]]
-The deadline for the project is February 15th 2019.+
 ==== News and Announcements ==== ==== News and Announcements ====
-16/12 A list of exercises has been posted +  * 04/12 The lecture on 05/12 is cancelled due to the strike on public transportation. The course will start on 19/12. 
- +  * 18/12 The lecture on 19/12 is confirmed. 
-14/12 the text of the project has been posted +  * 07/01 The text of the (default) project has been posted on the website.  
- +  * 14/01 A list of exercises has been posted on the website.   
-12/12 all the slides so far have been posted +  * 22/02 A second list of exercises has been posted on the website.
- +
-23/01 all the slides so far have been posted +
- +
-07/02 all the slides so far have been posted +
- +
-07/02 added 2 exercises (on fastest shortest path computation) +
- +
- +
 ==== Teaching language ==== ==== Teaching language ====
  
-6/8 of classes will be in English, the rest English or French.+The course will be in English.
  
 ==== Evaluation ==== ==== Evaluation ====
Line 68: Line 58:
 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.  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 an optional practical project which might give additionally up to 20% of the maximum grade. The final exam contributes to 80% of the maximum grade. The project is optional, in the sense that it 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. +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. Students are not allowed to bring any notes at the final exam.
 
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