Hauptinhalt überspringenNavigation überspringenFooter überspringen
Logo der Fachhochschule Nordwestschweiz
Studium
Weiterbildung
Forschung und Dienstleistungen
Internationales
Die FHNW
De
Standorte und KontaktBibliothek FHNWKarriere an der FHNWMedien

      Logo der Fachhochschule Nordwestschweiz
      • Studium
      • Weiterbildung
      • Forschung und Dienstleistungen
      • Internationales
      • Die FHNW
      De
      Standorte und KontaktBibliothek FHNWKarriere an der FHNWMedien
      Hochs...
      Hochschule für Wirt...
      Institut für Wirtschaf...
      Systems Eng...
      Techniken zum Verringern der Überschätzung der approximierten Graph Edit...

      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.

      Hochschule für Wirtschaft FHNW

      Institut für Wirtschaftsinformatik
      hsw_iwi_systemsengineering_teaserhsw_iwi_systemsengineering_projekt

      Angebot

      • Studium
      • Weiterbildung
      • Forschung & Dienstleistungen

      Über die FHNW

      • Hochschulen
      • Organisation
      • Leitung
      • Facts and Figures

      Hinweise

      • Datenschutz
      • Accessibility
      • Impressum

      Support & Intranet

      • IT Support
      • Login Inside-FHNW

      Member of: