Charakteristiken und Beziehungen zwischen Methoden für den Vergleich relationaler Strukturen

Die Entwicklung von Methoden zur Analyse von Graphen ist ein multidisziplinäres Problem, da die zu Grunde liegenden Fragestellungen über viele wissenschaftliche Disziplinen verteilt sind. Speziell nach dem ersten Hype, um globale Eigenschaften von komplexen Netzwerken zu bestimmen, ist die Einsicht gereift, verstärkt quantitative Methoden, z.B. Graphähnlichkeitsmaße oder andere Graphmaße zu untersuchen. Der Schwerpunkt dieses Projekts liegt auf der Untersuchung von mathematischen Eigenschaften von Methoden zur Bestimmung der strukturellen Ähnlichkeit von Graphen, die im Allgemeinen als Graphmatching-Methoden bezeichnet werden. Frühe Beiträge fokussieren sich auf Ansätze zur Bestimmung der Graphähnlichkeit basierend auf Isomorphie- und Untergraphisomorphiebeziehungen. Die resultierenden Graphähnlichkeitsmaße besitzen aber meistens ungünstige Zeitkomplexität, da Isomorphie- und Untergraphisomorphie schwierige Probleme darstellen. Folglich sind auch andere Ansätze zur Bestimmung der Ähnlichkeit von Graphen, insbesondere fehlertolerante Methoden, untersucht worden. Zwar sind einige der genannten Methoden über viele wissenschaftliche Disziplinen hinweg angewendet und diskutiert worden, aber eine tiefgehende mathematische Analyse solcher Methoden ist bisher nicht erfolgt. Dieses Forschungsprojekt verfolgt daher das folgende Ziel: Es werden mathematische Eigenschaften von Methoden zum Vergleich relationaler Strukturen untersucht, da das Feld einen Mangel an tiefer gehenden Resultaten aufweist. Dies bezieht sich zum Beispiel auf die Erforschung von mathematischen Beziehungen zwischen solchen Methoden. Weiter wird die strukturelle Interpretation solcher Methoden untersucht.

Ziel diesesForschungsprojektes war es,mathematische Eigenschaftenvon Graphvergleichsmethoden zu untersuchen. Unsere Ergebnisse umfassen die Entwicklung neuer Techniken zur Ähnlichkeit von Graphen sowie die Untersuchung ihrer mathematischen Beziehungen. Dies umfasst beispielsweise Ungleichungen zwischen den Graphabstandsmaße darstellen, und die Diskussion ihrer strukturellen Interpretation. Die Entwicklung von Methoden zur Bestimmung der Ähnlichkeit/Distanz von Graphen ist ein multidisziplinäres Problem, da die zugrunde liegenden Forschungsprobleme auf verschiedene wissenschaftliche Disziplinen verteilt sind. Insbesondere nach dem Hype um die Untersuchung globaler Eigenschaften komplexer Netzwerke hat sich herausgestellt, dass quantitative Methoden zur Untersuchung von Graphen, wie z.B. die Ähnlichkeit von Graphen von entscheidender Bedeutung sind. In diesem Projekt haben wir Methoden untersucht, um die strukturelle Ähnlichkeit/Distanz von Graphen zu messen, die allgemein als Graph Matching-Methoden bezeichnet werden. Außerdem haben wir die mathematischen Eigenschaften solcher Methoden eingehend untersucht. Weiter haben wir topologische Graphmaße und deren Eignung zur Definition von Ähnlichkeit/Distanz-Maße untersucht. In Anbetracht der Tatsache, dass sich frühe Beiträge mit der Erforschung isomorphie- basierter Ähnlichkeit/Distanz-Maße befassten, wurde hier der Schwerpunkt auf Methoden ohne Berechnung der Graphisomorphie gelegt. Daher wurden auch andere Ansätze entwickelt und untersucht, welche quasi fehlertolerante Methoden darstellen. Alle diese Techniken wurden auf in mehreren Disziplinen angewendet und wir führten eine Analyse von mathematischen Eigenschaften ausgewählter Graphvergleichsmethoden durch. 1