Combinatorial Algorithms for Graph Sparsification

Lade...
Vorschaubild
Dateien
Ortmann_2-q0c9utyejf0y0.pdf
Ortmann_2-q0c9utyejf0y0.pdfGröße: 50.95 MBDownloads: 267
Datum
2017
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
Zusammenfassung in einer weiteren Sprache

Eine Vielzahl der gegenwärtig gesammelten Daten kann durch Graphen modelliert werden. Ein Graph in seiner einfachsten Form besteht aus einer Menge von Entitäten, auch Knoten genannt, und einer Menge von ungerichteten Beziehungen zwischen diesen, Kanten genannt. Prominente Beispiele für Daten, die mit Graphen modelliert werden können, sind soziale Netzwerke und andere soziale Medien, wie beispielsweise Facebook, Google+, Twitter oder ResearchGate. Das Anwendungsgebiet von Graphen ist jedoch nicht auf die Modellierung von sozialen Netzwerken begrenzt; sie können überall da eingesetzt werden, wo Beziehungen zwischen Objekten untersucht werden. Ebenso vielfältig wie das Anwendungsgebiet von Graphen ist auch die Menge an Werkzeuge für deren Analyse. Da das Sammeln von massiven Datensätzen in Zeiten des Internets vergleichbar einfach geworden ist, stößt eine Vielzahl dieser Analysetechniken an die Grenzen ihrer Anwendbarkeit. Gleichzeitig ist die Analyse eben jener massiven Datensätze von unschätzbarem Wert für Wirtschaft, Politik, Gesundheitswesen, Sicherheit, Sport, und Wissenschaft, um nur einige Beispiele zu nennen. Eine Lösung, um die Analyse dieser Daten zu ermöglichen, besteht darin, die Komplexität des Graphens zu reduzieren, indem man diesen ausdünnt.

Das Ziel der Ausdünnung von Graphen ist eine schlankere Darstellung des Originals, indem man die Anzahl von Knoten bzw. Kanten vermindert, wobei man gleichzeitig einige seiner Eigenschaften aufrecht erhält oder zumindest approximiert. Zwar führt die Ausdünnung zu einem Informationsverlust, jedoch sind nicht alle Knoten bzw. Kanten gleichermaßen wichtig für die durchzuführende Analyse. Insofern der Ausdünnungsprozess jene Knoten und Kanten verschont, welche unentbehrlich für die anschließende Analyse sind, kann diese für große Graphen durchgeführt werden und potentiell zu den gleichen Ergebnissen, oder zumindest einer Approximation dieser, führen.

Die vorliegende Arbeit beschäftigt sich mit drei unterschiedlichen Ausdünnungsverfahren und deren effizienten Berechnung, das Hauptaugenmerk liegt dabei auf dem “Quadrilateral Simmelian Backbone”.

Die Berechnung des Quadrilateral Simmelian Backbone besteht aus zwei Teilproblemen, nämlich der Aufzählung aller vollständigen Teilgraphen mit drei Knoten, sogenannten Dreiecken, und dem Zählen, wie oft eine Kante in einem speziellen nicht induzierten Viereck, das heißt einem Teilgraphen mit vier Knoten, vorkommt.

In Kapitel 3 beschäftigen wir uns mit effzienten kombinatorischen Algorithmen zum Aufzählen von Dreiecken und zeigen, dass die meisten Dreiecksaufzählungsverfahren aus der Literatur Instanziierungen eines einzigen generischen Verfahren sind. Basierend auf dieser Abstraktion zeigen wir, dass nahezu alle dieser Algorithmen eine Laufzeit von O(a(G)m) haben, wobei a(G) die Arborizität des Graphen bezeichnet und m die Anzahl seiner Kanten ist. Diese Laufzeit wurde bisher nur für den Algorithmus von Chiba and Nishizeki (1985) bewiesen. Weiterhin zeigen wir hier, dass unsere verbesserte Implementation dieses Algorithmus in der Praxis der schnellste ist.

Das effiziente Aufzählen von Dreiecken ist nicht nur relevant für den Quadrilateral Simmelian Backbone, sondern auch für die Berechnung eines anderen Ausdünnungsverfahren, dem “Irreducible Spine” (Pfaltz, 2013). In Kapitel 4 präsentieren wir einen dynamische Algorithmus zur Bestimmung des Irreducible Spine in O(a(G)m) Zeit und beweisen seine Eindeutigkeit bis auf Isomorphie. Die Konstruktion des Irreducible Spines basiert darauf, dominierte Knoten aus dem Graphen sukzessive zu entfernen. Da die verwendete Definition von Dominanz nur eine von vielen möglichen Instanziierungen des Dominanzkonzepts von Brandes (2016) und daher austauschbar ist, präsentieren wir zusätzlich weitere Algorithmen zur Berechnung anderer Arten von Dominanz.

In Kapitel 5 widmen wir uns wieder der effizienten Berechnung des Quadrilateral Simmelian Backbone. Obgleich für dessen Berechnung nur die Anzahl eines bestimmten Subgraphs mit vier Knoten wichtig ist, führen wir hier einen ganzheitlichen Ansatz zur Berechnung der Häufigkeiten aller induzierten und nicht-induzierten Subgraphen mit vier Knoten ein. Genauer gesagt präsentieren wir einen Algorithmus mit Komplexität in O(a(G)2m), der diese Häufigkeiten für jeden Knoten und jede Kante berechnet mitsamt einer Unterscheidung der Automorphismusklassen in diesen Teilgraphen. Weitherhin zeigen wir in diesem Kapitel am Beispiel des “Triaden Zensus”, wie man unserer Ansatz auf gerichtete Graphen erweitern kann.

Ausgehend von den Ergebnissen von Kapitel 3 und 5, führen wir in Kapitel 6 den Algorithmus zur effizienten Berechnung des Quadrilateral Simmelian Backbone mit einer Laufzeit in O(m(a(G) + log m)) ein. In einer umfangreichen experimentellen Studie zeigen wir, dass der Quadrilateral Simmelian Backbone besonders gut geeignet ist, um die Gruppenstruktur eines Graphens herauszuarbeiten und bessere Ergebnisse liefert als verwandte Ansätze.

Die Ergebnisse der Evaluation in Kapitel 6 zeigen, dass die Qualität des Quadrilateral Simmelian Backbone stark von der Anzahl der ausgedünnten Kanten abhängt. Daher zeigen wir in Kapitel 7, wie man diese Anzahl automatisch in O(m(a(G) + log m)) Zeit bestimmen kann und veranschaulichen die Effektivität unseres Verfahrens anhand von Experimenten.

Abschließend präsentieren in Kapitel 8 ein weiteres Ausdünnungsverfahren. Wie wir durch Experimente zeigen, ermöglicht diese Methode der “Stressminimierung”, ein energiebasiertes Graphenzeichenverfahren, in einem Bruchteil der Zeit annähernd die selben Zeichnungen zu erzeugen wie wenn es den Originalgraphen als Eingabe erhalten hätte. Weiterhin zeigt unsere Evaluation, dass dieses Ausdünnungsverfahren bessere Ergebnisse bei vergleichbarer Laufzeit liefert als alternative Herangehensweisen, um Zeichnungen mit geringem Stress zu erzeugen.

Fachgebiet (DDC)
004 Informatik
Schlagwörter
graph theory, efficient graph algorithms, graph sparsification, triangle listing, dominance, orbit-aware quad census, quadrilateral simmelian backbone, sparse stress minimization
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690ORTMANN, Mark, 2017. Combinatorial Algorithms for Graph Sparsification [Dissertation]. Konstanz: University of Konstanz
BibTex
@phdthesis{Ortmann2017Combi-44287,
  year={2017},
  title={Combinatorial Algorithms for Graph Sparsification},
  author={Ortmann, Mark},
  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/44287">
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/44287/3/Ortmann_2-q0c9utyejf0y0.pdf"/>
    <dcterms:issued>2017</dcterms:issued>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-12-12T11:53:51Z</dcterms:available>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-12-12T11:53:51Z</dc:date>
    <dc:contributor>Ortmann, Mark</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:title>Combinatorial Algorithms for Graph Sparsification</dcterms:title>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Ortmann, Mark</dc:creator>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44287"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:language>eng</dc:language>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/44287/3/Ortmann_2-q0c9utyejf0y0.pdf"/>
  </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
October 23, 2017
Hochschulschriftenvermerk
Konstanz, Univ., Diss., 2017
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen