Graph Laplacian and adjacency matrix

Hi,

Does anyone know an afficient way to compute sparse adjacency matrix and Graph Laclcian directly from a data matrix ?

I saw there are function called 'adjacency' and 'laplacian which get graph object and return the adjacency/graph laplacian matrix but i wonder if there are functions which calcute it directly over a data matrix?

That means i have large data matrix Nxd (where N is the number of data point , let assue 50,000 and d is a sample dimention , assume d=100)

I would like that the adjacency matrix will return NXN sparse matrix W which contain a measure of distance (euclidian/RBF or someting like that) between the data points (not all of them necesserly. lets assume that only to the 50 nearest neigbours so we get a sparse matrix).

and the laplacian is L=D-W where D is diagonal matrix contains W cloums' sum.

I tried to implement it by myself but i found it very inefficient so i wondered if there id something built-in in Matlab ?

Thanks alot

[AMA]

Hi, I have the same problem

did you solve it ?

kind Regards

Answer 1

[Bruno Luong]

Not sure what data format you have, but for graph

% TMW example
s = [1 2 2 3 3 3 4 5 5 5 8 8 9];
t = [2 3 4 1 4 5 5 3 6 7 9 10 10];
G = graph(s,t);

A = G.adjacency;
D = diag(sum(A)); % degree matrix
L = D - A; % laplacian matrix
disp(L)

   (1,1)        2
   (2,1)       -1
   (3,1)       -1
   (1,2)       -1
   (2,2)        3
   (3,2)       -1
   (4,2)       -1
   (1,3)       -1
   (2,3)       -1
   (3,3)        4
   (4,3)       -1
   (5,3)       -1
   (2,4)       -1
   (3,4)       -1
   (4,4)        3
   (5,4)       -1
   (3,5)       -1
   (4,5)       -1
   (5,5)        4
   (6,5)       -1
   (7,5)       -1
   (5,6)       -1
   (6,6)        1
   (5,7)       -1
   (7,7)        1
   (8,8)        2
   (9,8)       -1
  (10,8)       -1
   (8,9)       -1
   (9,9)        2
  (10,9)       -1
   (8,10)      -1
   (9,10)      -1
  (10,10)       2

Answer 2

[Christine Tobler]

Take a look at pdist in the Statistics and Machine Learning toolbox. If you apply this to your matrix, and then call squareform on the result, it should give you the W matrix you're looking for. There's a choice of different distance measures to choose from in pdist.