## Theory and Applications of the Laplacian

2007
##### Open Access-VerÃ¶ffentlichung
Open Access Green
##### Titel in einer weiteren Sprache
Theorie und Anwendungen der Laplace-Matrix und des Laplace-Operators
Dissertation
Published
##### Zusammenfassung

Like the adjacency, incidence matrix and other matrices associated with graphs, the Laplacian matrix enables a fruitful interplay between graph theory and linear algebra, where graph-theoretic properties of a graph are reflected by algebraic properties of one of its matrices.
Part 1, Chapters 1 and 2, considers well-known applications of the Laplacian matrix and compares the discrete and the continuous case, where in the latter case the Laplacian operator plays the role of the Laplacian matrix. Here we focus on two partial differential equations: wave and potential equation. Many properties and concepts like, e.g., the Dirichlet problem, meanvalue property, maximum principle, fundamental solutions, Perron's method, Dirichlet's principle, spectra, etc., exist both in the discrete and continuous case. Part 1 introduces the theoretical foundations for the applications of the second Part.
Part 2, Chapters 3 to 6, presents four new applications involving the Laplacian matrix:
The first application is from the area of network analysis. Two common measures for vertices of a graph are called closeness and betweenness for which exist two variants current-flow closeness and current-flow betweenness that consider the graph as an electrical network. By means of concepts from Part 1 these can be computed faster and can be well approximated.
Another application is (dynamic) graph drawing. Minimizing the sum of squared edge lengths corresponds to minimizing the energy of the graph. This is often used as a quality criterion for graph drawings. Its minimization can be done by a spectral decomposition of the Laplacian matrix. For dynamic graphs it is reasonable to use corresponding eigenvectors of linearly interpolated matrices. These can be computed efficiently and in particular for the random graph model small worlds their dynamics can be proven to be sufficiently smooth.
A third application is geographic routing in wireless networks. In a network of, say, small mini computers (vertices) with geographic positions in the plane, messages between arbitrary vertices should be sent. By means of the Laplacian matrix we can compute virtual positions. On these positions a simple set of routing rules guarantees message delivery and generates very short routes in practice.
Finally, the Laplacian matrix has an application in coloring graphs or data that basically corresponds to a graph. Anyhow, we do not consider the usual combinatorial optimization problem, but instead focus on the two objectives that adjacent vertices should be colored as different as possible, and the used colors can be distinguished well. This translates to a graph drawing problem into a color space with the unusual objective that edges should be as long as possible, while non-adjacent vertices should not be too close to each other.
Chapter 7 concludes with a brief summary, how concepts of the theory Part 1 entered the application Part 2.

##### Zusammenfassung in einer weiteren Sprache

Ebenso wie Adjazenz- und Inzidenzmatrix, die sich zu einem gegebenem Graphen definieren lassen, ermÃ¶glicht die Laplace-Matrix ein fruchtbares Zusammenspiel zwischen Graphentheorie und linearer Algebra. Viele Eigenschaften des Graphen spiegeln sich in algebraischen Eigenschaften der Matrizen wider.
In Teil 1 der Arbeit, Kapitel 1 und 2, betrachten wir bekannte Anwendungen der Laplace-Matrix und vergleichen zwischen diskretem und kontinuierlichem Fall, wobei in letzterem der Laplace-Operator die Rolle der Laplace-Matrix einnimmt. Hier stehen die beiden partiellen Differentialgleichungen Wellen- und Potenzialgleichung im Mittelpunkt. Viele bekannte Prinzipien aus der Potenzialtheorie lassen sich im diskreten und im kontinuierlichen Fall anwenden, wie etwa das Dirichlet-Problem, Mittelwerteigenschaft, Maximumprinzip, GrundlÃ¶sungen, Methode von Perron, Dirichletsche Prinzip, Spektra, etc. Teil 1 liefert damit die theoretischen Grundlagen fÃ¼r die Anwendungen des zweiten Teils.
In Teil 2, Kapitel 3 bis 6, betrachten wir vier neue Anwendungen, welche die Laplace-Matrix verwenden:
Die erste Anwendung stammt aus dem Bereich der Netzwerkanalyse. Zwei bekannte MaÃŸe fÃ¼r Knoten eines Graphen sind closeness und betweenness. Zu diesen lassen sich Varianten current-flow closeness und current-flow betweenness definieren, die den Graphen als ein elektrisches Netzwerk auffassen. Mit Hilfe von Prinzipien aus Teil 1 lassen sich diese Varianten schneller berechnen und gut approximieren.
Eine weitere Anwendung ist das (dynamische) Zeichnen von Graphen. Die Minimierung der Summe der quadrierten KantenlÃ¤ngen entspricht dem Minimieren der Energie des Graphen. Dies wird oft als ein QualitÃ¤tskriterium zum Zeichnen von Graphen verwendet. Die Minimierung kann durch Berechnen von Eigenvektoren der Laplace-Matrix gelÃ¶st werden. FÃ¼r dynamische Graphen ist es sinnvoll, die entsprechenden Eigenvektoren von linear interpolierten Matrizen zu verwenden. Diese kÃ¶nnen effizient berechnet werden und Ã¤ndern sich speziell fÃ¼r das Graphenmodell small worlds Ã¼ber die Zeit hinreichend glatt.
Eine dritte Anwendung ist geographic routing in drahtlosen Netzwerken. Hier sollen in einem Netzwerk von z.B. Minicomputern (Knoten) mit geographischen Positionen in der Ebene Nachrichten zwischen beliebigen Knoten verschickt werden. Mit Hilfe der Laplace-Matrix lassen sich (iterativ und verteilt) virtuelle Positionen berechnen, auf denen sich dann sehr einfache Regeln zum Weiterleiten von Nachrichten angeben lassen, die garantieren, dass Nachrichten ihr Ziel erreichen und in der Praxis sehr kurze Wege liefern.
Zuletzt lÃ¤sst sich die Laplace-Matrix auch dazu verwenden, um Graphen zu fÃ¤rben bzw. Strukturen, aus denen sich leicht ein Graph ableiten lÃ¤sst. Wir betrachten hier jedoch nicht das bekannte kombinatorische Optimierungsproblem, sondern konzentrieren uns auf die beiden Forderungen, benachbarte Knoten so unterschiedlich wie mÃ¶glich zu fÃ¤rben und paarweise gut unterscheidbare Farben zu verwenden. Dieses Problem lÃ¤sst sich als Graphenzeichnen-Problem in einen Farbraum auffassen. Im Vergleich zu sonst Ã¼blichen QualitÃ¤tskriterien verlangen die beiden Forderungen hier aber, dass Kanten mÃ¶glichst lang sind, und dass alle Knoten paarweise einen gewissen Mindestabstand von einander haben.
Kapitel 7 schlieÃŸt mit einer kurzen Zusammenfassung ab, wie die beiden Teile der Arbeit, Theorie und Anwendungen, miteinander verknÃ¼pft sind.

004 Informatik
##### SchlagwÃ¶rter
Graph algorithms, potential theory, Dirichlet problem, social networks, wireless networks, graph drawing
##### Zitieren
ISO 690FLEISCHER, Daniel, 2007. Theory and Applications of the Laplacian [Dissertation]. Konstanz: University of Konstanz
BibTex
@phdthesis{Fleischer2007Theor-5507,
year={2007},
title={Theory and Applications of the Laplacian},
author={Fleischer, Daniel},
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#" >
<dc:contributor>Fleischer, Daniel</dc:contributor>
<dcterms:issued>2007</dcterms:issued>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:creator>Fleischer, Daniel</dc:creator>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:title>Theory and Applications of the Laplacian</dcterms:title>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:56:05Z</dc:date>
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5507/1/Fleischer_Diss.pdf"/>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5507/1/Fleischer_Diss.pdf"/>
<dcterms:alternative>Theorie und Anwendungen der Laplace-Matrix und des Laplace-Operators</dcterms:alternative>
<dc:language>eng</dc:language>
<bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5507"/>
<dc:rights>terms-of-use</dc:rights>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T15:56:05Z</dcterms:available>
<dcterms:abstract xml:lang="eng">Like the adjacency, incidence matrix and other matrices associated with graphs, the Laplacian matrix enables a fruitful interplay between graph theory and linear algebra, where graph-theoretic properties of a graph are reflected by algebraic properties of one of its matrices.&lt;br /&gt;Part 1, Chapters 1 and 2, considers well-known applications of the Laplacian matrix and compares the discrete and the continuous case, where in the latter case the Laplacian operator plays the role of the Laplacian matrix. Here we focus on two partial differential equations: wave and potential equation. Many properties and concepts like, e.g., the Dirichlet problem, meanvalue property, maximum principle, fundamental solutions, Perron's method, Dirichlet's principle, spectra, etc., exist both in the discrete and continuous case. Part 1 introduces the theoretical foundations for the applications of the second Part.&lt;br /&gt;Part 2, Chapters 3 to 6, presents four new applications involving the Laplacian matrix:&lt;br /&gt;The first application is from the area of network analysis. Two common measures for vertices of a graph are called closeness and betweenness for which exist two variants current-flow closeness and current-flow betweenness that consider the graph as an electrical network. By means of concepts from Part 1 these can be computed faster and can be well approximated.&lt;br /&gt;Another application is (dynamic) graph drawing. Minimizing the sum of squared edge lengths corresponds to minimizing the energy of the graph. This is often used as a quality criterion for graph drawings. Its minimization can be done by a spectral decomposition of the Laplacian matrix. For dynamic graphs it is reasonable to use corresponding eigenvectors of linearly interpolated matrices. These can be computed efficiently and in particular for the random graph model small worlds their dynamics can be proven to be sufficiently smooth.&lt;br /&gt;A third application is geographic routing in wireless networks. In a network of, say, small mini computers (vertices) with geographic positions in the plane, messages between arbitrary vertices should be sent. By means of the Laplacian matrix we can compute virtual positions. On these positions a simple set of routing rules guarantees message delivery and generates very short routes in practice.&lt;br /&gt;Finally, the Laplacian matrix has an application in coloring graphs or data that basically corresponds to a graph. Anyhow, we do not consider the usual combinatorial optimization problem, but instead focus on the two objectives that adjacent vertices should be colored as different as possible, and the used colors can be distinguished well. This translates to a graph drawing problem into a color space with the unusual objective that edges should be as long as possible, while non-adjacent vertices should not be too close to each other.&lt;br /&gt;Chapter 7 concludes with a brief summary, how concepts of the theory Part 1 entered the application Part 2.</dcterms:abstract>
<dc:format>application/pdf</dc:format>
</rdf:Description>
</rdf:RDF>
##### PrÃ¼fungsdatum der Dissertation
November 23, 2007