This looks good and could use some tests.

I see you have modified what @bjedwards to use NumPy eigensolvers instead of the power method.
That is probably a good move for small graphs but for larger graphs we'll want sparse matrix representations. I think that is where we were headed with that code. Ben do you recall what our plans were?

The bigger picture is that we will want to provide sparse matrix versions for all of the functions in networkx/linalg - but that is a bigger project and should be a new issue.

I tried to keep Ben's code as intact as possible.

Another option is to use the power method implemented in the Pagerank algorithm. Or may be we can have a parameter that determine what algorithm (power method, eig, eigs) we use to compute the Perron vector.

Let's put your version in (with some tests) and then open another issue to create a sparse matrix version.

I think the plan was to provide a power method version, a numpy version, and a sparse matrix version, then import based on what is available.

I think part of the consensus was if you are doing spectral graph theory, you like have numpy or scipy installed. So we could potentially make these modules require numpy and not provide a power method version.

Moreover, I don't think numpy is as big of a dependency hassle as it used to be, so I actually wouldn't be opposed to just making it a requirement for networkx, but that is a horse of a different color.

On Sun, Jul 22, 2012 at 4:06 PM, Ben Edwards
reply@reply.github.com
wrote:

I think the plan was to provide a power method version, a numpy version, and a sparse matrix version, then import based on what is available.

I think part of the consensus was if you are doing spectral graph theory, you like have numpy or scipy installed. So we could potentially make these modules require numpy and not provide a power method version.

Moreover, I don't think numpy is as big of a dependency hassle as it used to be, so I actually wouldn't be opposed to just making it a requirement for networkx, but that is a horse of a different color.

I don't mind part of networkx depending on numpy and scipy (as it does
now). For the spectral graph theory part of networkx it is required.
One thing we might consider doing is not importing the linear algebra
tools automatically, i.e. require from networkx import linalg (or
whatever name). That could make the dependency handling simpler.

One idea that occurred to me is to make all of the linalg functions
return scipy sparse matrices and then just call .todense() to get a
full matrix. What are the performance implications of that?

Anyway - I don't want to get too far off track. I think with some
tests and docs Alejandro's pull request is good.

@hagberg I added some tests for the directed laplacian.

Test results for commit 96c0bd1 merged into master
Platform: linux2

• python2.6: OK
• python2.7: OK
• python3.2: Failed, log at https://gist.github.com/3285149

Not available for testing:

@jtorrents I removed the print statement that caused the python 3.2 failure. (See 92709b4. The print shouldn't be there in the first place).

Test results for commit 92709b4 merged into master
Platform: linux2

• python2.6: OK
• python2.7: OK
• python3.2: OK

Alejandro,

Thanks for the quick response. I'm adapting an IPython script for testing
NetworkX pull requests, while testing yours noticed the error and wanted to
test that the gist part works. It's very neat and will be very useful.

I'm preparing a pull request with the adapted script.

2012/8/7 Alejandro Weinstein notifications@github.com

@jtorrents https://github.com/jtorrents I removed the print statement
that caused the python 3.2 failure in 92709b492709b4(the
print shouldn't be there in the first place).

—
Reply to this email directly or view it on GitHubhttps://github.com//pull/741#issuecomment-7557509.

NetworkX: Test results for pull request #741 (aweinstein 'directed_laplacian' branch)
✳️ This pull request can be merged cleanly (commit ede03b2 into NetworkX master ef11bff)
Platform: linux2

• python2.6: ✳️ OK (SKIP=59) Ran 1532 tests (libraries not available: pyyaml, pydot, numpy, matplotlib, ogr, yaml, scipy, pyparsing, pygraphviz)
• python2.7: ✳️ OK (SKIP=None) Ran 1723 tests
• python3.2: ✳️ OK (SKIP=6) Ran 1702 tests (libraries not available: ogr, pygraphviz, pydot)
• python3.3: ✳️ OK (SKIP=37) Ran 1596 tests (libraries not available: pyyaml, pydot, numpy, matplotlib, ogr, yaml, scipy, pyparsing, pygraphviz)

I can't seem to figure out how to merge this correctly (which is likely my inexperience with git). @aweinstein can you look at it? I'd like to include this code for the networkx-1.8 release.

@hagberg I can help, but I don't know exactly how.

Is it enough if I figure it out how to merge this into my master branch?

I think if you can rebase your changes on the latest master then it would work.

@hagberg I did the rebase and fixed some conflicts. Please let me know if this fixed the problem.

Looks good, thanks! I'll review it and do the merge if it all is OK.

NetworkX: Test results for pull request #741 (aweinstein 'directed_laplacian' branch)
✳️ This pull request can be merged cleanly (commit 4f6b5ae into NetworkX master fd11407)
Platform: linux2

• python2.6: ✳️ OK (SKIP=60) Ran 1533 tests (libraries not available: pyyaml, pydot, numpy, matplotlib, ogr, yaml, scipy, pyparsing, pygraphviz)
• python2.7: ✳️ OK (SKIP=None) Ran 1724 tests
• python3.2: ✳️ OK (SKIP=6) Ran 1703 tests (libraries not available: ogr, pygraphviz, pydot)
• python3.3: ✳️ OK (SKIP=37) Ran 1597 tests (libraries not available: pyyaml, pydot, numpy, matplotlib, ogr, yaml, scipy, pyparsing, pygraphviz)

I added some updates in #811 to address some formatting and naming issues.

Question:

Shouldn't the directed_laplacian_matrix function be a normalized_directed_laplacian_matrix function?
This function uses the normalized formula
L = I - (\Phi^{1/2} P \Phi^{-1/2} + \Phi^{-1/2} P^T \Phi^{1/2} ) / 2

For a directed_laplacian_matrix the combinatorial (non normalized) formula should be used
L = \Phi - (\Phi P + P^T \Phi) / 2

What do you people think about this modification? I am also new to Github, so sorry if there is another way to have you notice this.

Hi @antoniopugliese, thanks for contributing. Can you please create a new issue containing your question so that we can track its resolution separately from this pull request? (Feel free to reference this pull request when you create the issue.)

@antoniopugliese @jfinkels We used the definition given in the paper

Fan Chung (2005). Laplacians and the Cheeger inequality for directed graphs. Annals of Combinatorics, 9(1), 2005 (available here http://www.math.ucsd.edu/~fan/wp/dichee.pdf).

This paper just call it "Laplacian". I would call a function returning L = \Phi - (\Phi P + P^T \Phi) / 2 directed_combinatorial_laplacian_matrix.

@aweinstein @jfinkels
The paper just calls it "Laplacian", but as you can see the formula has a "L" in math cursive, which is used for the normalized Laplacian. Also, in the documentation of the function is reported that the function returns a normalized matrix.

I like the directed_combinatorial_laplacian_matrix name. I used this name in the issue I just created.