Phorgy Phynance

Network Theory and Discrete Calculus – Graph Divergence and Graph Laplacian

with one comment

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:

\begin{aligned} d\mathbf{e}^i = \sum_{i,j} \left( \sum_{\epsilon\in[j,i]}\mathbf{e}_\epsilon^{j,i} - \sum_{\epsilon\in[i,j]} \mathbf{e}_\epsilon^{i,j}\right).\end{aligned}

Applied to a general discrete 0-form, this becomes

\begin{aligned} d\phi = \sum_{i,j} {\left(\phi_j-\phi_i\right) \sum_{\epsilon\in[i,j]} \mathbf{e}_\epsilon^{i,j}} .\end{aligned}

To re-simplify the notation while maintaining the advantages of the new generalized notation, we can define

\begin{aligned} \mathbf{e}^{i,j} = \sum_{\epsilon\in[i,j]} \mathbf{e}_\epsilon^{i,j} \end{aligned}

and we’re back to

\begin{aligned} d\mathbf{e}^i = \sum_{i,j} \left(\mathbf{e}^{j,i} - \mathbf{e}^{i,j}\right)\end{aligned} and \begin{aligned} d\phi = \sum_{i,j} \left(\phi_j-\phi_i\right) \mathbf{e}^{i,j} \end{aligned}

as before. Furthermore, we have

\partial\mathbf{e}^{i,j} = N_{i,j} \left(\mathbf{e}^j - \mathbf{e}^i\right),

where N_{i,j} is the number of directed edges from node i to node j.

Trace and Inner Products

Given a discrete 0-form \phi, we define its trace via

\begin{aligned} tr_0(\phi) = \sum_i \phi_i. \end{aligned}

Similarly, given a discrete 1-form \alpha, its trace is given by

\begin{aligned} tr_1(\alpha) = \sum_{i,j} {\sum_{\epsilon\in[i,j]} \alpha^\epsilon_{i,j}} .\end{aligned}

With the trace, we can define the inner product of discrete 0-forms via

\langle \phi,\psi\rangle_0 = tr_0(\phi\psi)

and the inner product of discrete 1-forms via

\langle \alpha,\beta\rangle_1 = tr_1(\alpha\circ\beta),

where \alpha\circ\beta is the edge product.

Graph Divergence

The graph divergence was introduced here as a boundary operator, but the relation to divergence was mentioned here.

With the inner products defined above, a simple calculation shows

\langle \partial\alpha,\phi\rangle_0 = \langle \alpha, d\phi\rangle_1

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 d and \partial for discrete forms.

Graph Laplacian

The graph Laplacian of a discrete 0-form \phi is given by

\begin{aligned} \partial d\phi = -\sum_{i,j} \left(\phi_j - \phi_i\right) \left(N_{i,j} + N_{j,i}\right) \mathbf{e}^i. \end{aligned}

More generally, we could define a graph Laplace-Beltrami operator

d\partial + \partial d.

Graph Dirac Operator

The graph Dirac operator is essentially the “square root” of the graph Laplace-Beltrami operator. Since d^2 = 0 and \partial^2 = 0, we have

d\partial + \partial d = (d+\partial)^2

so the/a graph Dirac operator is given by

d + \partial.

About these ads

Written by Eric

December 4, 2011 at 1:26 pm

One Response

Subscribe to comments with RSS.

  1. […] was defined in a previous post. […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: