After successful completion of the course, students are able to...
***************************************************
Information will be added as soon as possible.
***************************************************
Description:
We focus on algorithms and data structures for analyzing graphs.
The first part is devoted to graph similarity. Graph similarity is the basis for many graph and network analyzing tasks. Applications are, e.g., learning tasks in drug design, social network analysis, brain network analysis, and geodesy. We will discuss similarity concepts for graphs that are relevant for analysis tasks on graph data sets. These include graph isomorphism based approaches such as maximum common subgraph as well as Weisfeiler-Leman and graph edit distance.
The second chapter deals with efficient algorithms and data structures for computing centrality indices. These are based on shortest paths and have increasing applications in social network analysis, e.g., when we are interested in finding the most influential persons in a network or finding superspreaders of some disease. In particular, we start with an introduction to several centrality indices before we look closer into an efficient algorithm for computing the betweenness centrality. Fibonacci heaps and their amortized analysis follow. We end this section with modern state- of-the-art speed-up techniques for shortest path problems.
The final chapter will focus on algorithms for big data. These incluse external memory algorithms and data structures as well as parallel algorithms and data streaming algorithms.
ECTS breakdown:
Lectures - in the class (16h)
Discussion of exercises - in the class (3.5h)
Oral exam (if applicable) - in the class (0.5h)
Solving exercises - at home (30h)
Further reading - at home (25h)
-----------------------
Total (75h)
Content of the course:
I) Graph similarity (5 lectures)
II) Centrality indices and temporal graphs (3 lectures)
III) Big data algorithms (2 lectures)
The lecturer of this course will be Petra Mutzel / University of Bonn (D).
This is a guest professor course of the TU Wien Informatics Doctoral School. It is targeted to Doctoral Students of the Faculty of Informatics, but, subject to availability of free seats, open to all PhD students and interested Master students.
