Network Theory and Discrete Calculus – Graph Divergence and Graph Laplacian
This post is part of a series
Another Note on Notation
In a previous post, I introduced a slightly generalized notation in order to deal with directed graphs with multiple directed edges between any two nodes, e.g. parallel elements in electrical networks. However, the revised notation now makes some simpler calculations look more cumbersome. This is an example of what my adviser called the conservation of frustration. For example, the coboundary is now given by:
Applied to a general discrete 0-form, this becomes
To re-simplify the notation while maintaining the advantages of the new generalized notation, we can define
and we’re back to
as before. Furthermore, we have
where is the number of directed edges from node to node .
Trace and Inner Products
Given a discrete 0-form , we define its trace via
Similarly, given a discrete 1-form , its trace is given by
With the trace, we can define the inner product of discrete 0-forms via
and the inner product of discrete 1-forms via
where is the edge product.
With the inner products defined above, a simple calculation shows
so the graph divergence is the adjoint of the coboundary.
In relating discrete calculus to algebraic topology, typically, in algebraic topology you would have a coboundary operator for cochains and a boundary operator for chains. With discrete calculus, we have both and for discrete forms.
The graph Laplacian of a discrete 0-form is given by
More generally, we could define a graph Laplace-Beltrami operator
Graph Dirac Operator
The graph Dirac operator is essentially the “square root” of the graph Laplace-Beltrami operator. Since and , we have
so the/a graph Dirac operator is given by