MATLAB Answers

Graph Laplacian and adjacency matrix

14 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!

Translated by