Publikation:

Extending the Usability of Multidimensional Scaling for Graph Drawing

Lade...
Vorschaubild

Dateien

klimenta_212991.pdf
klimenta_212991.pdfGröße: 32.23 MBDownloads: 428

Datum

2012

Autor:innen

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

DOI (zitierfähiger Link)
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Dissertation
Publikationsstatus
Published

Erschienen in

Zusammenfassung

Multidimensionale Skalierung (MDS) ist eine Familie von Methoden zur Visualisierung von Ähnlichkeitsdaten als Abstände im niedrigdimensionalen Raum. Die graphische Repräsentation von Objekten ermöglicht das Verständnis der zu Grunde liegenden strukturellen Eigenschaften, sowohl lokal als auch im globalen Zusammenhang. Durch die Wiedergabe von Objektähnlichkeiten als Abstände zwischen den diese Objekte repräsentierenden Punkten in einer graphischen Darstellung werden die bestehenden Beziehungen effizient dargestellt. In Bereichen, welche auf dem Konzept der Nachbarschaftsanalyse aufbauen, wie zum Beispiel der Visualisierung von Verkehrssystemen, der Molek ulstruktur in der Chemie oder einer Teilmenge von Computerverbindungen aus dem Internet, wurde so die Visualisierung von Objekt-Beziehungen mit Hilfe von MDS-Methoden erfolgreich verwendet. Die wachsende Größe und Komplexität der zu Grunde liegenden Struktur verstärkt die Bedeutung ihrer visuellen Repräsentation. Ziel des Graphenzeichnens ist die geometrische Repräsentation einer Menge von Objekten und deren Beziehungen. Dafür sollten Objekte mit geringen graphentheoretischen Abständen in der Regel auch geometrisch nah und Objekte mit grösseren graphentheoretischen Abständen geometrisch weiter von einander entfernt gezeichnet werden. Das Ziel ist eine geometrische Repräsentation, welche zuverlässig die lokalen und die globalen Zusammenhänge von Graphobjekten widerspiegelt. Da dies auch das Ziel von MDS ist, kann das Graphenzeichnen sehr von Methoden dieser Familie profitieren. Andererseits gibt es wichtige Kriterien, welche den Nutzen von MDS im Graphenzeichnen steuern: die zu Grunde liegende Zeit- und Raumkomplexität der Methode und vom Anwendungsbereich abhängige ästhetische Kriterien. Ersteres impliziert die Notwendigkeit von effizienten und effektiven Graphenzeichenmethoden, welche auch für grösseren Datensätze geeignet sind. Letzteres dagegen ist die Anforderung, welche durch die erzeugte Repräsentation erfüllt werden soll. Ziel dieser Arbeit ist es, den Nutzen von MDS Verfahren für das Graphenzeichnen zu erweitern. Die präsentierten Erweiterungen haben zum Ziel, die Skalierbarkeit und die Flexibilität der Verwendung von MDS zu verfeinern und zu verbessern. Durch die Nutzung der der MDS zu Grunde liegenden Zielfunktionen konnten elegante und praktische Lösungen erzielt werden. Neben der Möglichkeit, grössere Datensätze zu bearbeiten, wurde auch die Flexibilität der MDS-Methoden verbessert, so dass spezifische Nebenbedingungen erfüllen werden können. Der erste Teil dieser Arbeit betrachtet ein spektrales MDS-Verfahren, die klassische Skalierung (CMDS) und deren jüngst vorgeschlagene Ann aherungen. Die pr asentierten Verbesserungen betreffen nicht nur die Qualität der Näherung, sondern auch die Effizienz des Verfahrens. Die Nutzbarkeit von CMDS für das Zeichnen von Graphen wird au erdem erweitert, indem man Modifikationen der Eingabe berücksichtigen und Freiheitsgrade des CMDS anpassen kann, sowie eine niedrigdimensionale Abbildung einer hochdimensionalen CMDS-Lösung. Ein weiterer, verbreiteter MDS-Ansatz, die Distanz Skalierung, wird im zweiten Teil der Arbeit betrachtet. Es werden Aspekte zur Minimierung der zu Grunde liegenden Zielfunktion untersucht und effiziente Verbesserungen vorgeschlagen. Die Verbesserungen betreffen sowohl die Beschleunigung der Konvergenz der genutzten iterativen Minimierung als auch die tatsächliche Komplexität der Iteration. Die vorgeschlagenen Verfahren erlauben es so, viel grössere Datensätze zu verarbeiten. Der letzte Teil der Arbeit betrachtet eine spezi sche Anpassung von MDS-Modellen. Die Anpassungen für die visuelle Betonung einer ausgew ahlten Region eines Graphen, sowohl für die Klassische Skalierung als auch für die Distanz Skalierung werden bereitgestellt. Um das visuelle Durcheinander allgemeiner Layouts zu reduzieren, wird eine Anpassung der Distanz Skalierung präsentiert.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690KLIMENTA, Mirza, 2012. Extending the Usability of Multidimensional Scaling for Graph Drawing [Dissertation]. Konstanz: University of Konstanz
BibTex
@phdthesis{Klimenta2012Exten-21299,
  year={2012},
  title={Extending the Usability of Multidimensional Scaling for Graph Drawing},
  author={Klimenta, Mirza},
  address={Konstanz},
  school={Universität Konstanz}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/21299">
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/21299/2/klimenta_212991.pdf"/>
    <dc:contributor>Klimenta, Mirza</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:issued>2012</dcterms:issued>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2013-01-31T12:31:23Z</dcterms:available>
    <dcterms:abstract xml:lang="deu">Multidimensionale Skalierung (MDS) ist eine Familie von Methoden zur Visualisierung von Ähnlichkeitsdaten als Abstände im niedrigdimensionalen Raum. Die graphische Repräsentation von Objekten ermöglicht das Verständnis der zu Grunde liegenden strukturellen Eigenschaften, sowohl lokal als auch im globalen Zusammenhang. Durch die Wiedergabe von Objektähnlichkeiten als Abstände zwischen den diese Objekte repräsentierenden Punkten in einer graphischen Darstellung werden die bestehenden Beziehungen effizient dargestellt. In Bereichen, welche auf dem Konzept der Nachbarschaftsanalyse aufbauen, wie zum Beispiel der Visualisierung von Verkehrssystemen, der Molek ulstruktur in der Chemie oder einer Teilmenge von Computerverbindungen aus dem Internet, wurde so die Visualisierung von Objekt-Beziehungen mit Hilfe von MDS-Methoden erfolgreich verwendet. Die wachsende Größe und Komplexität der zu Grunde liegenden Struktur verstärkt die Bedeutung ihrer visuellen Repräsentation.   Ziel des Graphenzeichnens ist die geometrische Repräsentation einer Menge von Objekten und deren Beziehungen. Dafür sollten Objekte mit geringen graphentheoretischen Abständen in der Regel auch geometrisch nah und Objekte mit grösseren graphentheoretischen Abständen geometrisch weiter von einander entfernt gezeichnet werden. Das Ziel ist eine geometrische Repräsentation, welche zuverlässig die lokalen und die globalen Zusammenhänge von Graphobjekten widerspiegelt. Da dies auch das Ziel von MDS ist, kann das Graphenzeichnen sehr von Methoden dieser Familie profitieren. Andererseits gibt es wichtige Kriterien, welche den Nutzen von MDS im Graphenzeichnen steuern: die zu Grunde liegende Zeit- und Raumkomplexität der Methode und vom Anwendungsbereich abhängige ästhetische Kriterien. Ersteres impliziert die Notwendigkeit von effizienten und effektiven Graphenzeichenmethoden, welche auch für grösseren Datensätze geeignet sind. Letzteres dagegen ist die Anforderung, welche durch die erzeugte Repräsentation erfüllt werden soll.  Ziel dieser Arbeit ist es, den Nutzen von MDS Verfahren für das Graphenzeichnen zu erweitern. Die  präsentierten Erweiterungen haben zum Ziel, die Skalierbarkeit und die Flexibilität der Verwendung von MDS zu verfeinern und zu verbessern. Durch die Nutzung der der MDS zu Grunde liegenden Zielfunktionen konnten elegante und praktische Lösungen erzielt werden. Neben der Möglichkeit, grössere Datensätze zu bearbeiten, wurde auch die Flexibilität der MDS-Methoden verbessert, so dass spezifische Nebenbedingungen erfüllen werden können.   Der erste Teil dieser Arbeit betrachtet ein spektrales MDS-Verfahren, die klassische Skalierung (CMDS) und deren jüngst vorgeschlagene Ann aherungen. Die pr asentierten Verbesserungen betreffen nicht nur die Qualität der Näherung, sondern auch die Effizienz des Verfahrens. Die Nutzbarkeit von CMDS für das Zeichnen von Graphen wird au erdem erweitert, indem man Modifikationen der Eingabe berücksichtigen und Freiheitsgrade des CMDS anpassen kann, sowie eine niedrigdimensionale Abbildung einer hochdimensionalen CMDS-Lösung.   Ein weiterer, verbreiteter MDS-Ansatz, die Distanz Skalierung, wird im zweiten Teil der Arbeit betrachtet. Es werden Aspekte zur Minimierung der zu Grunde liegenden Zielfunktion untersucht und effiziente Verbesserungen vorgeschlagen. Die Verbesserungen betreffen sowohl die Beschleunigung der Konvergenz der genutzten iterativen Minimierung als auch die tatsächliche Komplexität der Iteration. Die vorgeschlagenen Verfahren erlauben es so, viel grössere Datensätze zu verarbeiten.   Der letzte Teil der Arbeit betrachtet eine spezi sche Anpassung von MDS-Modellen. Die Anpassungen für die visuelle Betonung einer ausgew ahlten Region eines Graphen, sowohl für die Klassische Skalierung als auch für die Distanz Skalierung werden bereitgestellt. Um das visuelle Durcheinander allgemeiner Layouts zu reduzieren, wird eine Anpassung der Distanz Skalierung präsentiert.</dcterms:abstract>
    <dc:rights>terms-of-use</dc:rights>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:title>Extending the Usability of Multidimensional Scaling for Graph Drawing</dcterms:title>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/21299/2/klimenta_212991.pdf"/>
    <dc:creator>Klimenta, Mirza</dc:creator>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/21299"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:language>deu</dc:language>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2013-01-31T12:31:23Z</dc:date>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

December 17, 2012
Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen