How to make nodes' removal from a graph as a function of time?

Question

Waseem AL Aqqad 2021-1-14

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/716973-how-to-make-nodes-removal-from-a-graph-as-a-function-of-time

评论： Waseem AL Aqqad 2021-2-5

Hello,

I'm simulating failures of nodes in an interdependent system (two graphs, g and h) and their adjacency matrices are A and B. Some nodes in graph g (layer A) will get attacked randomly, and then this failure will get propagated to graph h (layer B) through the interlinks between the two graphs.

I'm trying to simulate failure or nodes removal based on time, that is,

at: t=1, remove first node in A.

t=2, remove the second node in A

t=3, failure propagates to B and first node in B get removed and so on.

Your help would be highly appreciated.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Waseem AL Aqqad 2021-1-14

It would be fine If you can show me how this works for a single layer. I can then apply it to multi-layers or graphs.

请先登录，再进行评论。

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

Answer 1

Christine Tobler 2021-1-15

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/716973-how-to-make-nodes-removal-from-a-graph-as-a-function-of-time#answer_598370

You may want to look at the graph and digraph classes: Graph and Network Algorithms and their method rmnode specifically.

6 个评论
显示 4更早的评论隐藏 4更早的评论

Waseem AL Aqqad 2021-2-1

在 MATLAB Online 中打开

Hi Christine,

Thanks for referring me to this documentation. It took me two weeks to digest it but it is worth it.

So, my algorithm works as the following steps:

Initially, a number of nodes will get removed randomly from the first graph.
Checking if any of the remaining nodes doesn't belong to the largest component after the initial node removal or if it is isolated. If any node satisfies these two conditions, it will fail (get removed).
All nodes in the second graph that are connected to the isolated nodes from the first graph will fail (will be removed). Since they depend on each other (Interdependent Systems/graphs).

G= WattsStrogatz(8,2,.2);
F= WattsStrogatz(8,2,.2);
E=G.Edges{:,:};
[M, ~]=mode(E(:));
G=minspantree(G,'Root',M);
Ef=F.Edges{:,:};
[M, ~]=mode(Ef(:));
F=minspantree(F,'Root',M);
Hf=Cascading_Failure(G,F,2);
function Hf=Cascading_Failure(G,F,rmv) % G,F are the first and second Graphs respectively. 
%rmv is the number of nodes to be removed initially
N=numnodes(G);
p=plot(G);
x=p.XData;
y=p.YData;
z=zeros(1,N);
GF=graph([G.Edges{:,:}(:,1),F.Edges{:,:}(:,1)+N],[G.Edges{:,:}(:,2),F.Edges{:,:}(:,2)+N]);
%Calculate the degree of both graphs
 Da= degree(G);    %First Graph 	
 Db= degree(F);    %Second Graph 	
                 % Interlinks structure                      
%Monotonic i.e. the node with highest degree in first graph is connected with
%the node of the highest degree in second graph
[~, inda] = sort(Da, 'descend');
[~, indb] = sort(Db, 'descend');
% Add the edges of both graphs (Networks A and B) to one larger graph, and then use addedge to connect them 
GF=addedge(GF,inda,indb+N);
plot(GF,'XData',[x, x],'YData',[y, y], 'ZData',[z, z-3]);
% Random Failure starts
attack=zeros(1,rmv);
attack(1,:)=randsample(N,rmv);
Gf=GF;
for ii=1:length(attack)
    eid = outedges(GF,attack(ii));
    GF=rmedge(GF,eid);
end
figure;
plot(GF,'XData',[x, x],'YData',[y, y],'ZData',[z, z-3])
G_Prime=subgraph(GF,(1:N));
[bin,binsize]=conncomp(G_Prime);
comp=length(binsize);
m=mode(bin);
o=find(bin==m); % members of largest component in first graph
        for j=1:N  % check on the neighbors if they'll get isolated
            for jj=N+1:N+N
                if ~ismember(j,o) && isempty(neighbors(G_Prime,j)) && (ismember (horzcat(j,jj),  horzcat(inda, indb+N),'rows') || ismember (horzcat(jj,j),  horzcat(inda, indb+N),'rows')) % propagation to layer B
                    eid_j = outedges(GF,j);
                    GF=rmedge(GF,eid_j);                
%                     figure; plot(GF,'XData',[x, x],'YData',[y, y],'ZData',[z, z-3])
                    eid = outedges(GF,jj);
                    GF=rmedge(GF,eid);
                    G_Prime=subgraph(GF,(1:N));
                    
                end 
            end
        end
        figure; plot(GF,'XData',[x, x],'YData',[y, y],'ZData',[z, z-3])
        
        F_prime = subgraph(GF,findnode(GF,N+1:N+N));
        lh=N+1:N+N;
        lh=arrayfun(@num2str,lh,'un',0);
        F_prime.Nodes.Name=lh';
        [bin,binsize]=conncomp(F_prime);
        compF=length(binsize);
        m=mode(bin);
        oF = F_prime.Nodes.Name(bin==m); % members of largest component in second graph
        
                for l=N+1:N+N
                    for ll=1:N                
                        if ~ismember(cellstr(num2str(l)),oF) && isempty(neighbors(F_prime,cellstr(num2str(l)))) && (ismember (horzcat(l,ll),  horzcat(inda, indb+N),'rows') || ismember (horzcat(ll,l),  horzcat(inda, indb+N),'rows'))
                            eid_l = outedges(GF,l);
                            GF=rmedge(GF,eid_l);
%                             figure; plot(GF,'XData',[x, x],'YData',[y, y],'ZData',[z, z-3])
                            eid = outedges(GF,ll);
                            GF=rmedge(GF,eid);
                            F_prime = subgraph(GF,findnode(GF,N+1:N+N));
                            lh=N+1:N+N;
                            lh=arrayfun(@num2str,lh,'un',0);
                            F_prime.Nodes.Name=lh';
                        end
                    end
                end
                
        figure; plot(GF,'XData',[x, x],'YData',[y, y],'ZData',[z, z-3])
       
Hf=GF;   
end

Waseem AL Aqqad 2021-2-2

编辑：Waseem AL Aqqad 2021-2-2

Thanks, Christine!

No, G and F will not be changing. But this could be another nice idea.

I wrote another function "Self_Healing" to try to recover as many as possible of those failed nodes. I want to call my "Self_Healing" function at a time instant right after the failure of the first nodes.

So, at t=1 Cascading_Failure starts by removing two nodes, at t=2 Self_Healing will start trying to recover the two removed nodes while at the same time instant the Cascading_Failure will be removing the next nodes, and so on.

Another question please, based on my Cascading_Failure function how can I simulate the time needed for each node to get failed? As I believe, in real world applications, one node might take 30 sec to get removed and another one might take several minutes.

Thanks again!

Waseem AL Aqqad 2021-2-5