Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Graphs are everywhere. For example, people spend a lot of time on traversing the hyperlink-edges of the web graph. Other examples of graphs are social networks, public transportation maps, molecules, financial transactions, fishing nets, family trees, and the graph that you get by connecting any two natural numbers that have the same digit sum. A graph can be represented by its adjacency matrix W, but there exist several alternative graph matrices. Many structural properties of a graph such as the absence of cycles, number of spanning trees or random walk hitting times, reflect in these graph matrices as all kinds of algebraic properties. This fundamental relation allows to study graph properties by applying all the machinery from linear algebra to matrices. Spectral graph theory focuses particularly on the eigenvalues and eigenvectors of graph matrices. In this field of research, the graph Laplacian matrix L = D − W is particularly well-known, but there are numerous variants such as the normalized Laplacian, the signless Laplacian and the Diplacian. Most variants are defined by a "syntactically tiny" modification of L, for example D + W instead of D − W. Nevertheless, such modifications can drastically affect the information that is encoded in the eigenvalues and eigenvectors. This can finally lead to new relations to graph properties. This thesis studies novel and existing variants of Laplacian matrices. The f-adjusted Laplacian is introduced and proven to be a specific diagonal modification of the normalized Laplacian matrix. In the context of random geometric neighborhood graphs, this matrix can be understood as a specific distortion that is applied to the underlying probability density. This intuition allows for new approaches to various applications in machine learning, for example to image segmentation in case of non-uniformly sampled pixel positions. This thesis further studies the repeated application of the normalization step that underlies the normalized Laplacian. It contributes a novel convergence ...