## How to find the Laplacian of a Graph with multiple edges

Asked by Deepa Maheshvare

### Deepa Maheshvare (view profile)

on 3 Dec 2018
Latest activity Commented on by Deepa Maheshvare

### Deepa Maheshvare (view profile)

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);
plot(Graph)
D = degree(Graph)
L = full(laplacian(Graph))

### Release

R2018b ### Walter Roberson (view profile)

Answer by Walter Roberson

### Walter Roberson (view profile)

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 .

Deepa Maheshvare

### Deepa Maheshvare (view profile)

on 4 Dec 2018
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.
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);
plot(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
Walter Roberson

### Walter Roberson (view profile)

on 4 Dec 2018
Are we assuming no self-loops ?
Deepa Maheshvare

on 4 Dec 2018
Yes.