MATLAB Answers

Graph Laplacian and adjacency matrix

13 views (last 30 days)
Orr Streicher
Orr Streicher on 5 May 2021
Answered: Christine Tobler on 11 Jun 2021
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
  1 Comment
AMA
AMA on 11 Jun 2021
Hi, I have the same problem
did you solve it ?
kind Regards

Sign in to comment.

Answers (2)

Bruno Luong
Bruno Luong on 11 Jun 2021
Edited: Bruno Luong on 11 Jun 2021
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

Christine Tobler
Christine Tobler on 11 Jun 2021
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.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!