199.016 Algorithms for Graph Analysis AbgesagtDiese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_21",{id:"j_id_21",showEffect:"fade",hideEffect:"fade",target:"isAllSteop"});});Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.\$(function(){PrimeFaces.cw("Tooltip","widget_j_id_23",{id:"j_id_23",showEffect:"fade",hideEffect:"fade",target:"isAnySteop"});}); 2023W

2023W, VU, 2.0h, 3.0EC

Merkmale

• Semesterwochenstunden: 2.0
• ECTS: 3.0
• Typ: VU Vorlesung mit Übung
• Format der Abhaltung: Präsenz

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage...

**************************************************

Information will be added as soon as possible.

**************************************************

Inhalt der Lehrveranstaltung

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)

Methoden

Further information will be added as soon as possible.

Prüfungsimmanent

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.

Leistungsnachweis

Further information will be added as soon as possible.

LVA-Anmeldung

Von Bis Abmeldung bis
06.10.2023 00:00 30.10.2023 23:59

Curricula

StudienkennzahlVerbindlichkeitSemesterAnm.Bed.Info
PhD TU Wien Informatics Doctoral School Pflichtfach

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Weitere Informationen

• Anwesenheitspflicht!

Englisch