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

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.

[Waseem AL Aqqad]

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]

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

[Waseem AL Aqqad]

I could not find what I am looking for. But thanks for your reply and support. As for removing nodes, I prefer to place zeroes in the adjacency matrix instead of using rmnode since I want to preserve the no. of nodes for visualization purposes. But I don’t know how to let the cascading failure of nodes happens at different time instances.

Thanks again.

[Waseem AL Aqqad]

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:

1. Initially, a number of nodes will get removed randomly from the first graph.
2. 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).
3. 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]

But now how can I add timeSteps to my code. I'd appreciate any idea please

[Christine Tobler]

I'm not sure what it means to add timesteps here. Would both G and F be changing? Could you just call Cascading_Failure after each change to G and F?

[Waseem AL Aqqad]

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]

Hi Christine, I don’t mean to bother you but I was wondering if you have had a chance to look at my problem yet? Your help is greatly appreciated.