How to find the Laplacian of a Graph with multiple edges

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))

Answer 1

[Walter Roberson]

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]

Yes, but isn't the laplacian computed from Adjacency and degree?

Adjacency and degree commands work for multigraph in 2018b

[Walter Roberson]

According to Wikipedia

"Every row sum and column sum of L is zero. Indeed, in the sum, the degree of the vertex is summed with a "−1" for each neighbor."

However this cannot hold if there are self loops or multiple edges . The off diagonals are -1 if a node is adjacent rather than reflecting the number of times it is adjacent . With self loops there is no adjacency to subtract off the degree to get the row and column sum to 0.

[Deepa Maheshvare]

Thanks a lot for the clarification. Can the Laplacian be computed from the incidence matrix of multigaph?

L = I*I'

' = transpose

[Walter Roberson]

I am not convinced it is defined for multigraph .

[Deepa Maheshvare]

I = incidence(Graph) works for multigraph in version 2018b

[Walter Roberson]

however the question is whether laplacian is meaningful for multigraph .

[Deepa Maheshvare]

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

[Walter Roberson]

Are we assuming no self-loops ?

[Deepa Maheshvare]

Yes.