Asked by Deepa Maheshvare
on 3 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))

Answer by Walter Roberson
on 3 Dec 2018

Deepa Maheshvare
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.

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
on 4 Dec 2018

Are we assuming no self-loops ?

Deepa Maheshvare
on 4 Dec 2018

Yes.

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.