Geometric and spectral analysis on weighted digraphs

In this article we give a geometrical description of the (in general non-selfadjoint) in/out Laplacian 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 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 C of a weighted digraph as coclosed forms on the arcs, i.e. as the kernel of the discrete divergence d∗. Moreover, C is perpendicular to the set of discrete gradients of functions on the vertices. We also give formulas to compute the capacity

directed graphs; spectral graph theory; discrete laplacian; sinks and sources; circulations and flows; value and capacity

Geometric and spectral analysis on weighted digraphs Articles