Geometric and spectral analysis on weighted digraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911780896243712 |
|---|---|
| author | Lledó, Fernando Sevillano, Ignacio |
| author_facet | Lledó, Fernando Sevillano, Ignacio |
| contents | In this article we give a geometrical description of the (in general non-selfadjoint) in/out Laplacian $\mathcal{L}^{+/-} = (d^{+/-})^* d$ and adjacency matrix on digraphs with arbitrary weights, where $(d^{+/-})^*$ is the adjoint of the evaluation map $d^{+/-}$ on the terminal/initial vertex of each arc and $d = d^+ + d^-$ denotes the discrete gradient. We prove that the multiplicity of the zero eigenvalue of $\mathcal{L}^{+/-} = (d^{+/-})^* d$ coincides with the number of sources/sinks of the digraph. We also show that for an acyclic digraph with combinatorial weights the spectrum is contained in the set of non-zero integers. The geometrical perspective allows to interpret the set of circulations $\mathcal{C}$ of a weighted digraph as coclosed forms on the arcs, i.e. as the kernel of the discrete divergence $d^*$. Moreover, $\mathcal{C}$ is perpendicular to the set of discrete gradients of functions on the vertices. We also give formulas to compute the capacity of a cut and the value of a flow in terms of $\mathcal{L}^-$ and $d$. We illustrate the results with many concrete examples. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_16773 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Geometric and spectral analysis on weighted digraphs Lledó, Fernando Sevillano, Ignacio Combinatorics Functional Analysis 05C20, 05C50, 05C10, 05C21, 47B39 In this article we give a geometrical description of the (in general non-selfadjoint) in/out Laplacian $\mathcal{L}^{+/-} = (d^{+/-})^* d$ and adjacency matrix on digraphs with arbitrary weights, where $(d^{+/-})^*$ is the adjoint of the evaluation map $d^{+/-}$ on the terminal/initial vertex of each arc and $d = d^+ + d^-$ denotes the discrete gradient. We prove that the multiplicity of the zero eigenvalue of $\mathcal{L}^{+/-} = (d^{+/-})^* d$ coincides with the number of sources/sinks of the digraph. We also show that for an acyclic digraph with combinatorial weights the spectrum is contained in the set of non-zero integers. The geometrical perspective allows to interpret the set of circulations $\mathcal{C}$ of a weighted digraph as coclosed forms on the arcs, i.e. as the kernel of the discrete divergence $d^*$. Moreover, $\mathcal{C}$ is perpendicular to the set of discrete gradients of functions on the vertices. We also give formulas to compute the capacity of a cut and the value of a flow in terms of $\mathcal{L}^-$ and $d$. We illustrate the results with many concrete examples. |
| title | Geometric and spectral analysis on weighted digraphs |
| topic | Combinatorics Functional Analysis 05C20, 05C50, 05C10, 05C21, 47B39 |
| url | https://arxiv.org/abs/2305.16773 |