Remove node and reconnect edges in a very large graph

6 次查看（过去 30 天）
IrisL
IrisL 2022-7-22
回答： Christine Tobler 2024-9-4
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.

请先登录，再回答此问题。

回答（2 个）

BhaTTa
BhaTTa 2024-9-4
编辑：BhaTTa 2024-9-4
@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.
Christine Tobler
Christine Tobler 2024-9-4
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.

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

产品


版本

R2020b

Community Treasure Hunt

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

Start Hunting!

Translated by