Course director: Mauro Sozio

Pierluigi Crescenzi (Prof. Paris Diderot) pierluigi dot crescenzi at irif dot fr
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

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.

1. 19/12: Intro Community Detection Pagerank Community Detection with seed nodes
2. 09/01: Finding Densest SubgraphsMinimal Densest Subgraphs and more on LP formulation
3. 16/01: Densest Subgraphs via Convex Programming (Notes) Densest Subgraphs via Convex Programming (Slides)
4. 23/01: Influence Maximization Streaming Algorithms (slides) Streaming Submodular Optimization (paper) Fully Dynamic k-center clustering
5. 30/01: Diameter computation
6. 06/02: Distance distributions: sampling and sketches
7. 13/02: Centrality measures: betweenness and closeness
8. 20/02: Temporal graphs
9. 27/02: Exam

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

Exercises and Exercises

Text of the Project

• 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.
• 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.
• 22/02 A second list of exercises has been posted on the website.

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.

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.

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)