Table of Contents
Theory of practical graph algorithms (24h, 3 ECTS, period 2)Course director: Mauro Sozio Teachers for 20222023
Mauro Sozio (Professor, Telecom Paris, Institut Polytechnique de Paris, LTCI) sozio at telecom dash paris dot fr Scientific and pedagogical contentGraphs provide a powerful abstraction for representing a wide variety of realworld 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 realworld 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:
Content and (tentative) schedule
Some material from previous occurrences of the course (content or topics might change every year): Finding Densest Subgraphs Finding Minimal Densest Subgraphs Listing kcliques 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 QuestionsTo be posted. Project/Reading MaterialStudent 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 24 additional points on the final mark (exact number of additional points will be communicated in the first lecture). News and AnnouncementsTeaching languageThe course will be in English. EvaluationDuring 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 24 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. PrerequisitesGood knowledge of algorithms and complexity theory. Good knowledge of Java, C++ or Python are preferable but not necessary. Related BooksAlgorithm 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
