| Popis: |
The main subject of this thesis is the effective resistance — a measure of distance between the nodes of a graph which reflects how close or well- connected two nodes are, taking into account all paths between them and their interconnections. The effective resistance has many other properties, however, and the contribution of this thesis is twofold. First, we provide a self-contained and unified exposition of some important but not well-known results on the effective resistance: the Fiedler–Bapat identity between Laplacian and resistance matrices and the graph–simplex correspondence. Second, we introduce and study two new applications of the effective resistance: a distance-based measure of variance for distributions on the nodes of a graph, and two resistance-based graph invariants p and σ2 which we interpret in the context of discrete curvature. These contributions are unified in their geometric perspective on the effective resistance — ranging from the celebrated concept of resistance distance, to the lesser-known but far-reaching relation to simplex geometry and finally, a newly discovered relation to discrete curvature. While the focus lies on developing the mathematical theory of effective resistances in a unified matrix-theoretic language, we also discuss many examples and some applications. In particular, the proposed measures of variance and covariance are readily applicable in practice to study functional data (signals, distributions, etc.) defined on graphs. We hope that the exposition in this thesis will enable and stimulate further research on this fascinating subject and in particular on the theory of the resistance-based graph invariants p and σ2, the full depths of which still remain to be explored. |
