Techniken zum Verringern der Überschätzung der approximierten Graph Editier Distanz

Zur Förderung der Kommunikation zwischen den Jugendlichen

In vielen Anwendungen ist die Berechnung der Unähnlichkeit zwischen Objekten eine grundlegende Auf-gabe. Im Gegensatz zu vektoriellen Objektdarstellungen, wo das euklidische Distanzmodell als Norm der Unähnlichkeitsmessung dient, gibt es für Graphen kein Standard-Distanzkonzept. Eine der flexibelsten Methoden für die Berechnung der Unähnlichkeit von Graphen basiert auf der Editier Distanz von Graphen. Dennoch ist die Zeitkomplexität der Berechnung der Editier Distanz von Graphen bekanntermassen exponentiell was die Anzahl Knoten der beteiligten Graphen betrifft. Daher können die Zeit- und die Speicherkomplexität auch für eher kleine Graphen gewaltig sein.

Ziele

Der Projektverantwortliche im vorliegenden Projekt entwickelte ein gängiges approximatives Graph Editier Distanz Verfahren. Das vorgeschlagene algorithmische Vorgehen erlaubt es, Graph-Distanzen we-sentlich schneller als mit herkömmlichen Methoden zu berechnen. Es wurde empirisch überprüft, dass dieses Framework sich kleinen Abständen mit einer hohen Genauigkeit annähert, während relativ grosse Entfernungen oft überschätzt werden. Das Hauptziel des vorliegenden Projektes ist, diese Überschätzung deutlich zu reduzieren.

Praxis

Aufgrund ihrer Fähigkeit, die Eigenschaften von Entitäten und binäre Beziehungen zur gleichen Zeit darstellen, haben die Graphen weit verbreitete Anwendungen in Wissenschaft und Technik gefunden.

Theorie

Die erste Forschungsrichtung betrachtet die Integration von strukturellen und topologischen Deskriptoren im Vergleichsprozess. Die zweite Forschungsrichtung verfolgt die Idee der übereinstimmenden Teilgraphen anstelle von einzelnen Knoten zur Vermeidung unnötiger Kantenoperationen in der abgeleiteten Editier Distanzberechnung. Schliesslich wird die optimale Abstimmung der Teilgraphen berechnet, was zu einer umfassenden Knotenabbildung führt, worauf dann der approximative Editier Distanzwert abgeleitet werden kann.

Projektpartner und Sponsor(en)

Hasler Stiftung

Kontakt

laden

Social Media des Instituts für Wirtschaftsinformatik

No social media links available.