normalized Laplacian

[andferrari]

The type NormalizedLaplacian is defined but not the function to compute the normalized Laplacian from the graph.

Did I miss something?

[sbromberger]

@andferrari sorry for the delayed response.

ping @jpfairbanks

[jpfairbanks]

So the way the NormalizedLaplacian type works is that it uses multiple dispatch to evaluate matrix vector products with the Normalized Laplacian matrix L = NormalizedLaplacian(g); x = ones(nv(g)); y = L*x multiplies x by the normalized laplacian of g without ever explicitly forming the laplacian matrix. This memory bandwidth because you don't need to store the matrix in memory (since you already have the edges in memory). I think you should be able to sparse(L) to get L in the form of a SparseMatrixCSC data structure in case you need to do something with it other than compute L*x

[andferrari]

Thank you for your detailed answer.

However, I am not able to reproduce your example. L = NormalizedLaplacian(SimpleGraph(10))
gives me ERROR: MethodError: no method matching NormalizedAdjacency(::SimpleGraph{Int64})

[sbromberger]

ping @jpfairbanks :)

[jpfairbanks]

You should be able to do NormalizedLaplacian(NormalizedAdjacency(g)) or something like that. I can take a look later

[stale]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[jpfairbanks]

So you have to chain the constructors. Like the following:

g = Graph(10,30)
A = CombinatorialAdjacency(adjacency_matrix(g).+ 0.0)
 = NormalizedAdjacency(A)
L̂ = NormalizedLaplacian(Â)

We could add additional constructors like NormalizedLaplacian(A::SimpleGraph) = NormalizedLaplacian(NormalizedAdjacency(A .+ 0.0))

[andferrari]

many thanks!

I was missing the .+ 0.0...

It would indeed be a good idea. Do you mean ?

NormalizedLaplacian(g::SimpleGraph) = NormalizedLaplacian(NormalizedAdjacency(CombinatorialAdjacency(adjacency_matrix(g).+ 0.0)))

or

NormalizedLaplacian(A::SparseMatrix) = NormalizedLaplacian(NormalizedAdjacency(CombinatorialAdjacency(A.+ 0.0)))

[sbromberger]

Hey all, I'm going to close this out. If either / both of you want to work on a PR to implement the additional constructors, please have at it :)