Development of a Graph Matching Toolkit

Entwicklung einer benutzerfreundlichen Software für Graph Matching

Graphen sind die mächtigsten und flexibelsten Datenstrukturen, die in der Informatik Anwendung finden. Während der quantitative Vergleich von Vektoren oder Zeichenketten trivial ist, ist der Vergleich von Graphen, respektive die Distanzberechnung zwischen Graphen (bekannt als "Graph Matching"), ein schwieriges Problem. Tatsächlich existieren zur exakten Lösung des Graph-Matching-Problems nur exponentielle Algorithmen. Der Verantwortliche dieses Projektes hat in der Vergangenheit mehrere approximative Verfahren für das Graph-Matching-Problem entwickelt. Obschon die Algorithmen zur Graph-Distanz- Berechnung zur Verfügung stehen, besteht kein benutzerfreundliches Framework, das die Anwendung dieser Verfahren für eine breitere Öffentlichkeit ermöglicht.

Ziele

Das primäre Ziel dieses Projektes ist es, basierend auf den bestehenden Algorithmen eine benutzer-freundliche Software für flexibles Graph Matching zu entwickeln.

Praxis

Aufgrund der Tatsache, dass Graphen Attribute und Beziehungen gleichzeitig darstellen können, besitzen Graphen vielfältige Anwendungen in der Wissenschaft und Industrie. In der Bio- und Chemoinformatik werden Graphen als Datenstruktur zum Beispiel in der Web-Content-Analyse und im Data Mining, in der Bildanalyse und Bildklassifikation oder in der Netzwerkanalyse verwendet.

Theorie

Distanzberechnungen zwischen zwei Objekten in den oben genannten Anwendungsgebieten sind ein häufiges Problem. Im Gegensatz zu Vektorräumen, in denen die Euklidische Distanz als "Gold-Standard" verwendet wird, existiert für Graphen kein Standardmodell zur Distanzberechnung. Die Editierdistanz von Graphen ist eine der flexibelsten und mächtigsten Werkzeuge zur Graphdistanzberechnung. Allerdings weist die Berechnung der Editierdistanz von Graphen eine exponentielle Laufzeit auf, was deren Anwendung massiv einschränkt. Die in diesem Projekt verwendeten Algorithmen zur Approximation der Editierdistanz basieren auf Zuordnungsproblemen, für deren Lösung verschiedene sehr schnelle Verfahren existieren (z.B. der Algorithmus von Kuhn-Munkres oder das Verfahren von Edmonds-Karp).

Projektpartner und Sponsor(en)

Hasler Stiftung

Social Media des Instituts für Wirtschaftsinformatik

No social media links available.