is there a reason that Laplacian matrices aren't defined for DiGraphs?

[sbromberger]

This one's for @jpfairbanks :)

[jpfairbanks]

Well they aren't defined in the software because no one has a need for it yet. There is a definition in http://www.math.ucsd.edu/~fan/wp/dichee.pdf that has usefully properties so if there were some methods that needed the laplacian we could write it.

[sbromberger]

Ah, so the Laplacian for digraphs is not the same formula as the one for undirected? (Sorry - spectral theory is not anywhere close to my area of expertise.)

[jpfairbanks]

Yeah the formula is different. The formula given in the Fan Chung reference above uses the matrix adjoint. The definition provided in section 4 captures the notion that if x is a vector indexed by vertices r = x'Lx/x'x is the "variance" of x with respect to the graph. So they define L for directed graphs in the way they choose to in order for that to make sense. They go from adjacency to random walk matrix to laplacian.

Definitions are chosen by coming up with a few candidates that seem to have interesting properties and then proving some theorems about them. If one candidate turns out "better" than the others then a consensus will form and we call that candidate "the definition" instead of "a good definition."

Does anyone need laplacians for directed graphs? What are they trying to do?

[sbromberger]

Does anyone need laplacians for directed graphs? What are they trying to do?

Not yet - I was trying to find a spectral graph solution to calculate periodicity and I came across the wikipedia article:

Given a simple graph G with n vertices, its Laplacian matrix L_{n \times n} is defined as:[1] L = D - A, where D is the degree matrix and A is the adjacency matrix of the graph. In the case of directed graphs, either the indegree or outdegree might be used, depending on the application.

and was wondering why we restricted Laplacians to undirected graphs in our package.

[sbromberger]

@jpfairbanks does it make sense that there are two (presumably incompatible) definitions for Laplacian matrices on directed graphs? If so, which do you want to use?

[jpfairbanks]

So it makes sense to support both in and out degree. How do you feel about using a symbol argument to the constructor to decide :in or :out?

I think any more advance thing such as a normalization or random walk matrix the user will know enough to construct it themself from the Adjacency matrix. If any "advanced" versions become demanded it can be supported by extending the symbols accepted by the constructor.

[sbromberger]

I'd prefer to have a kwarg default in=true or something.... but could be convinced of anything.

[jpfairbanks]

The benefit of a switch is that you can extend it with different normalization later

:in :out :leftstochastic :rightstochastic

You can still set the default as :in

[sbromberger]

Makes sense!

[sbromberger]

@jpfairbanks could you please check out the laplacian branch and make sure it's right? (If it is, could you write some meaningful tests?) Thank you.

(ETA: see #81)

[sbromberger]

OK - I merged all_neighbors. This should be what we need for DiGraphs.

[sbromberger]

Closed via #89.