Graph Laplacian and adjacency matrix

10 次查看（过去 30 天）
Orr Streicher
Orr Streicher 2021-5-5
回答： Christine Tobler 2021-6-11
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

请先登录，再回答此问题。

回答（2 个）

Bruno Luong
Bruno Luong 2021-6-11
编辑：Bruno Luong 2021-6-11
Ran in:
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 2021-6-11
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.

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by