Course director: Mauro Sozio

Mauro Sozio (MC1 Telecom Paristech, LTCI) sozio at telecom dot paristech dot fr
Laurent Viennot (DR INRIA, IRIF, Paris Diderot)

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)
• community and event detection (Louvain algorithm, event detection via densest subgraph computation, impossibility theorem for clustering)
• graph decompositions (k-core, modular, local decompositions)
• diffusion and influence maximization
• ranking (PageRank, HITS)
• Mining road networks (pre-computation for shortest path queries, distance labeling and highway dimension, radius and diameter heuristics)
• Graph decomposition methods and algorithms. Survey of exact algorithms for modular decomposition and some other polynomial graph decompositions and approximation methods for NP-hard decompositions such as treewidth or treelength.

1. 05/12:Introduction to the CourseCommunity DetectionPageRank
2. 12/12 Commmunity Detection with Seed NodesFinding Densest SubgraphsProject and Internship
3. 19/12:Minimal Densest Subgraphs (paper)
4. 16/01:Notes on Finding Densest Subgraphs via Convex OptExperiments
5. 23/01:Influence Maximization Streaming Graph MiningPaper on streaming submodular optimization
6. 30/01: Generative Models Fully Dynamic k-cener clusteringMiscellanous Topics
7. 06/02:Shortest Paths Computation
8. 13/02:
9. 27/02: Final Exam (start 13.45 end 15.45) in room 1004 (same of our classes)

A list of exercises follows. Similar or the very same exercises might be asked at the exam. Exercises

The text of the project can be found here Text of the Project

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: Dataset (read the readme file which contains some information about the file format and other valuable info)

The deadline for the project is February 15th 2019.

16/12 A list of exercises has been posted

14/12 the text of the project has been posted

12/12 all the slides so far have been posted

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)

6/8 of classes will be in English, the rest English or French.

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.

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

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
• 2.29.1 Graph algorithms
• 2.26.2 Web data management (especially for the part about MapReduce)