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

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?

[Steven Lord]

So you somehow want to represent edges in the subgraph that go to nodes that are not present in the subgraph?

Can you show a small concrete example of a graph and its subgraph and the graph Laplacian for the subgraph that you're hoping to generate?

[L'O.G.]

@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?

Answer 1

[Steven Lord]

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