Remove node and reconnect edges in a very large graph

I asked a similar question before and tried to apply the code towards a large network with 6119 nodes and 7260 edges. The large network makes the code very inefficient.

The original question is: I have some nodes in an undirected graph that acts as a sort of 'temporary connector' node. I'd like to remove these nodes and update the edges in the graph so that all of the neighbors ponit to the next neighbors. Example: I have a graph 1 - 2 - 3. I'd like to remove node 2 and end up with the graph 1 - 3.

My end goal is to get an adjacency matrix of the graph after these 'temporary connector' node are removed. I want to know, whether the remaining nodes are incident to each other or not.

I am trying to figure out another way to conduct the work so that the computation can be quicker. Right now, I was able to remove 2000 nodes after running the code for 30+ hours. And the time for reming each node takes longer and longer. I think the problem being the number of neighbors explores when I remove nodes and reconnect edges.

My code is:

G1 = G;

for n = 1:length(node_need_to_be_remove)
    neig = neighbors(G1,n);
    for i=1:length(neig)
        for j=i+1:length(neig)
            G1=addedge(G1, neig(i), neig(j));
        end
    end 
    G1 = rmnode(G1,string(exclusion(n)));   % remove the node also remover the edges to the node
    %%%% Remove duplicated edges
    G1 = simplify(G1);
end

I know this question may be too specific, but I appreciate any suggestions. Thanks.

Answer 1

[BhaTTa]

@IrisL, since you have an undirected graph the adjacency Matrix will have dimension of V*V, where row goes from 1 to V and column goes from 1 to V.

For any particluar cell in Matrix lets say (i,j) in a graph G:

1. G(i,j) = 1, represents there is an edge between the Vertex i and Vertex j.

2. G(i,j) = 0, represents there is no edge between the Vertex i and Vertex j.

To remove edge between any arbitrary Vertex say A and B, we have to set G(A,B) = 0 and G(B,A) = 0.

Hope it helps.

Answer 2

[Christine Tobler]

It is usually best to first compute all the edges / nodes to act on, and then modify the graph in one step with all of them:

G1 = G;
s = [];
t = [];
for n = 1:length(node_need_to_be_remove)
    neig = neighbors(G1,n);
    for i=1:length(neig)
        tnew = neig(i+1:end);
        snew = repmat(neig(i), 1, length(tnew))
        s = [s; snew];
        t = [t; tnew];
    end 
end

% Add new edges
G1 = addedge(G1, s, t);

% Remove unused nodes
G1 = rmnode(G1, string(exclusion(node_need_to_be_remove))); 

% Remove duplicated edges
G1 = simplify(G1);

This should reduce the runtime, since we're not modifying G1 so many times, which tends to be expensive.

Of course, if the nodes to be removed have many neighbors, there can be a large number of new edges added, which would make G1 much larger at the end than in the beginning.