MATLAB Answers

0

How to find the Laplacian of a Graph with multiple edges

Asked by Deepa Maheshvare on 3 Dec 2018
Latest activity Commented on by Deepa Maheshvare on 4 Dec 2018
I'm using MATLAB online version 2018b. I'd like to ask for help in using the laplacian function in graph.
The adjacency(A) and degree(D) commands(doesn't work for multi graphs(multiple edges between two nodes) in version 2016b) work for the graph with multi edges. But, laplacian(Graph) isn't working.Is it a bug? Because, from what I understand, L=A-D. I get the following error,
Error using graph/laplacian (line 22)
Graph has multiple edges.
Code:
Input = [1,2;2,3;3,4;4,5;4,5;5,6;5,7];
tail = Input(:,1);
head = Input(:,2);
Graph = graph(tail,head)
plot(Graph)
A = full(adjacency(Graph))
D = degree(Graph)
L = full(laplacian(Graph))

  0 Comments

Sign in to comment.

Products


Release

R2018b

1 Answer

Answer by Walter Roberson
on 3 Dec 2018

no the documentation for laplacian says that the input cannot be a multigraph or contain self loops so there is no bug in the routine .

  9 Comments

I interpret Laplacian as the discretized form of the second derivate.
I think the way the vertex-adjacency matrix(A) is defined for a multi graph is different from how it is defined for a simple graph.
In a vertex x vertex adjacency matrix, the entry mij is the multiplicity of edge i-j.
Ref:link
When A is defined as above, the laplacian that results from L= D-A is symmetric,
positive semi-definite, has row sum and column sum equal to 0.Also, I*I'(transpose of incidence) = L.
In short, L = D-A = I*I';
The above can be tested from the below example of multigraph
Input = [1,2;2,3;3,4;4,5;4,5;5,6;5,7];
tail = Input(:,1);
head = Input(:,2);
Graph = graph(tail,head)
plot(Graph)
A = full(adjacency(Graph))
D = degree(Graph)
I = full(incidence(Graph))
%% Defining vertex-adjacency matrix mij is multiplicity of edges
Adj = [0 1 0 0 0 0 0;1 0 1 0 0 0 0;0 1 0 1 0 0 0;0 0 1 0 2 0 0; 0 0 0 2 0 1 1;
0 0 0 0 1 0 0;0 0 0 0 1 0 0]
Degree = diag(D)
Lap = Degree - Adj ;
RowSum = sum(Lap) % is zero
ColSum = sum(Lap') % is zero
Lap2 = I*I'
isequal(Lap,Lap2)
issymmetric(Lap)% is symmetric
eig(Lap) % is positive semi-definite
Looking forward to hear your feedbacks
Are we assuming no self-loops ?

Sign in to comment.