Skip Menu |

This queue is for tickets about the Graph CPAN distribution.

Report information
The Basics
Id: 9482
Status: resolved
Priority: 0/
Queue: Graph
People
Owner: Nobody in particular
Requestors: mre2007 [...] cs.columbia.edu
Cc:
AdminCc:
Bug Information
Severity: Wishlist
Broken in: (no value)
Fixed in: (no value)

History Show all quoted text
  Thu Jan 06 16:49:51 2005 Guest - Ticket created
Subject: Laplacian Matrices
It would be nice to compute Laplacian matrices and Normalized Laplacian Matrices. I have a crude way of doing this now, by using PDL so that I can calculate the eigenvalue spectra using the PDL SVD operation.
  Wed Jan 12 12:14:46 2005 JHI [...] cpan.org - Correspondence added
Laplacian matrices would probably be best implemented as objects that return the elements by computing them in runtime instead of really constructing the matrices because of the V**2 effect.
  Sat Jan 15 10:44:04 2005 Guest - Correspondence added
From: mre2007 [...] cs.columbia.edu
[JHI - Wed Jan 12 12:14:46 2005]: Show quoted text
> Laplacian matrices would probably be best implemented as objects that > return the > elements by computing them in runtime instead of really constructing > the matrices > because of the V**2 effect. > > >
Since I'm interested in the Laplacian spectrum of a graph, I need to use the matrix as a whole, and returning individual elements of the matrix would be of no use to my application. The normal definition of the Laplacian of a graph is something like what is stated here: http://mathworld.wolfram.com/LaplacianMatrix.html However, another equivalent definition can be defined in terms of the Adjacency matrix. The Laplacian and adjacency matrices can be related as follows. Let D be a n x n diagonal matrix such that D_vv = \sum_w A_vw. We can compute L(G) as L = D - A and the normalized Laplacian as L = D^{1/2} x L x D^{1/2}. Thus the normalized Laplacian represents a rescaling by the number of edges per vertex. Do you think you could perform this calculation based on the Graph::Adjacency implementation? If this isn't clear, please let me know and I can give more information. I just snipped a section from my paper where I relate the Laplacian to the Adjacency matrix. Thanks, -Marc
  Sat Jan 15 11:11:30 2005 jhi [...] iki.fi - Correspondence added
Date: Sat, 15 Jan 2005 18:01:32 +0200
From: Jarkko Hietaniemi <jhi [...] iki.fi>
To: bug-Graph [...] rt.cpan.org
Subject: Re: [cpan #9482] Laplacian Matrices
RT-Send-Cc:
Show quoted text
> > Since I'm interested in the Laplacian spectrum of a graph, I need to use > the matrix as a whole, and returning individual elements of the matrix > would be of no use to my application. The normal definition of the > Laplacian of a graph is something like what is stated here: > > http://mathworld.wolfram.com/LaplacianMatrix.html
Yes, but I remain very doubtful about whether my rather complex (read: slow *and* big) implementation of Graphs is any good for the linear algebra approach like the Laplacian. PDL sounds like a much better match. Show quoted text
> However, another equivalent definition can be defined in terms of the > Adjacency matrix. > > The Laplacian and adjacency matrices can be related as follows. Let D be > a n x n diagonal matrix such that D_vv = \sum_w A_vw. We can compute > L(G) as L = D - A and the normalized Laplacian as > L = D^{1/2} x L x D^{1/2}. Thus the normalized Laplacian represents a > rescaling by the number of edges per vertex. > > Do you think you could perform this calculation based on the > Graph::Adjacency implementation? If this isn't clear, please let me know > and I can give more information. I just snipped a section from my paper > where I relate the Laplacian to the Adjacency matrix. > > Thanks, > -Marc
-- Jarkko Hietaniemi <jhi@iki.fi> http://www.iki.fi/jhi/ "There is this special biologist word we use for 'stable'. It is 'dead'." -- Jack Cohen
  Sat Jan 15 11:57:19 2005 Guest - Correspondence added
From: mre2007 [...] cs.columbia.edu
[jhi@iki.fi - Sat Jan 15 11:11:30 2005]: Show quoted text
> > > > Since I'm interested in the Laplacian spectrum of a graph, I need to use > > the matrix as a whole, and returning individual elements of the matrix > > would be of no use to my application. The normal definition of the > > Laplacian of a graph is something like what is stated here: > > > > http://mathworld.wolfram.com/LaplacianMatrix.html
> > Yes, but I remain very doubtful about whether my rather complex > (read: slow *and* big) implementation of Graphs is any good for > the linear algebra approach like the Laplacian. PDL sounds like > a much better match. >
Oh, I see what you're getting at. I'm using PDL right now, so I'll try to update my code to the newest version of Graph and go from there. Thanks for everything! -Marc
  Sun Jan 16 07:00:47 2005 JHI [...] cpan.org - Status changed from 'new' to 'resolved'
  Sun Jan 23 03:49:11 2005 jhi [...] iki.fi - Correspondence added
Date: Sun, 23 Jan 2005 10:38:18 +0200
From: Jarkko Hietaniemi <jhi [...] iki.fi>
To: bug-Graph [...] rt.cpan.org
Subject: Re: [cpan #9482] Laplacian Matrices
RT-Send-Cc:
Show quoted text
>>Do you think you could perform this calculation based on the >>Graph::Adjacency implementation? If this isn't clear, please let me know >>and I can give more information. I just snipped a section from my paper >>where I relate the Laplacian to the Adjacency matrix.
If you still think you want to try doing Laplacians with Graph (which I still think will not be computationally efficient), you might want to try whether the Graph::BitMatrix::get_row() in Graph 0.55 is of any help. Show quoted text
>>Thanks, >>-Marc
> >
-- Jarkko Hietaniemi <jhi@iki.fi> http://www.iki.fi/jhi/ "There is this special biologist word we use for 'stable'. It is 'dead'." -- Jack Cohen
  Sun Jan 23 03:49:12 2005 The RT System itself - Status changed from 'resolved' to 'open'
  Sun Jan 23 03:53:55 2005 JHI [...] cpan.org - Status changed from 'open' to 'resolved'