Extending the Usability of Multidimensional Scaling for Graph Drawing

Lade...
Vorschaubild
Dateien
klimenta_212991.pdf
klimenta_212991.pdfGröße: 32.23 MBDownloads: 411
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
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
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
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