Geometric and spectral analysis on weighted digraphs
Articles
Overview
published in
publication date
- February 2024
start page
- 252
end page
- 280
volume
- 687
Digital Object Identifier (DOI)
full text
International Standard Serial Number (ISSN)
- 0024-3795
Electronic International Standard Serial Number (EISSN)
- 1873-1856
abstract
- In this article we give a geometrical description of the (in general non-selfadjoint) in/out Laplacian L+/-=(d+/-)*dand 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 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 Cof a weighted digraph as coclosed forms on the arcs, i.e. as the kernel of the discrete divergence d*. Moreover, Cis perpendicular to the set of discrete gradients of functions on the vertices. We also give formulas to compute the capacity to compute the capacity of a cut and the value of a flow in terms of L and d. We illustrate the results with many concrete examples.
Classification
subjects
- Mathematics
keywords
- directed graphs; spectral graph theory; discrete laplacian; sinks and sources; circulations and flows; value and capacity