Generating the laplacian for a sub-graph that still reflects the connectivity of the overall graph

3 views (last 30 days)
Generating a sub-graph I think by convention breaks all edges between the sub-graph and the rest of the graph. Is it possible to include the edges with the rest of the graph in the resulting laplacian? In other words, the sub-graph will still consist of the subset of nodes that you want. How do you do this?
  2 Comments
L'O.G.
L'O.G. on 1 Nov 2022
Edited: L'O.G. on 1 Nov 2022
@Steven Lord Yes, that's correct -- to represent those edges in the laplacian. Since my graphs are large, I'll try to give a very simple example: this would be like if I construct a sub-graph of the 6-node graph in the first figure just consisting of node 4 and 6. What I want is to preserve the degree of the overall graph (the diagonal of the laplacian) in the sub-graph. So here, the diagonal would be 1 and 3 (rather than 1 and 1) in the case of the two nodes in the sub-graph that I mentioned. How would you do that in a general way based on the original graph?

Sign in to comment.

Accepted Answer

Steven Lord
Steven Lord on 1 Nov 2022
Your comment refers to "the first figure" but no figures are attached to this post nor are there any linked documents including figures. But what I think you want to do is just to take a submatrix portion of the Laplacian of the whole graph.
rng default
A = sprand(10, 10, 0.2);
A = (A+A')/2;
G = graph(A, string(1:10), 'omitselfloops');
plot(G)
So if we took the subgraph that consists of nodes 1, 2, 8, 9, and 10:
nodes = [1 2 8 9 10];
S = subgraph(G, nodes);
figure
plot(S)
Would you want what's in the variable named expected below instead of the variable Lsub? [Note I've intentionally converted the Laplacians to full from sparse to make them a little easier to read.] If not then for this particular pair of graphs G and S, what would you expect to receive?
Lfull = full(laplacian(G))
Lfull = 10×10
4 0 0 0 -1 0 0 -1 -1 -1 0 3 0 0 0 0 0 -1 -1 -1 0 0 2 0 0 0 0 -1 0 -1 0 0 0 2 0 -1 0 0 0 -1 -1 0 0 0 2 0 -1 0 0 0 0 0 0 -1 0 1 0 0 0 0 0 0 0 0 -1 0 3 0 -1 -1 -1 -1 -1 0 0 0 0 4 0 -1 -1 -1 0 0 0 0 -1 0 3 0 -1 -1 -1 -1 0 0 -1 -1 0 6
Lsub = full(laplacian(S))
Lsub = 5×5
3 0 -1 -1 -1 0 3 -1 -1 -1 -1 -1 3 0 -1 -1 -1 0 2 0 -1 -1 -1 0 3
expected = Lfull(nodes, nodes)
expected = 5×5
4 0 -1 -1 -1 0 3 -1 -1 -1 -1 -1 4 0 -1 -1 -1 0 3 0 -1 -1 -1 0 6

More Answers (0)

Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

Products


Release

R2021b

Community Treasure Hunt

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

Start Hunting!

Translated by