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

2 vues (au cours des 30 derniers jours)
L'O.G. le 1 Nov 2022
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 commentairesAfficher AucuneMasquer Aucune
Steven Lord le 1 Nov 2022
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. le 1 Nov 2022
Modifié(e) : L'O.G. le 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?

Connectez-vous pour commenter.

### Réponse acceptée

Steven Lord le 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
##### 0 commentairesAfficher -2 commentaires plus anciensMasquer -2 commentaires plus anciens

Connectez-vous pour commenter.

### Catégories

En savoir plus sur Graph and Network Algorithms dans Help Center et File Exchange

R2021b

### Community Treasure Hunt

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

Start Hunting!

Translated by