Sum if multiple conditions satisfied across different arrays

Hello everyone!

Would love some help to create an optimal solution to this problem.

Considering that I have the adjacency matrix describing a network:

      adj =     [0  1  1  1
                 1  0  0  1
                 1  0  0  1
                 1  1  1  0];

and a binary matrix:

array = randi([0 1],4,10)

where the columns are each node in the network, and the rows are the state of the network at each time step. To clarify, if node 1 is '1' at time step 2, it would be represented as:

array(2,1) = 1

How would I create a vector counting the number of times between time steps that these two conditions are satisfied:

• 1. Node i is: 0 at time t and 1 at time t+1
• 2. Node i is: not neighbors with any nodes that have the value of 1 at time t

So far, through the wonderful help of the MATLAB community, the list of neighbors for each node may be extracted as follows:

adj=            [0  1  1  1
                 1  0  0  1
                 1  0  0  1
                 1  1  1  0];
  [i,j]=find(adj);
  neighbour_list = accumarray(i,j,[size(adj,1), 1],@(x) {sort(x).'});

And the first condition may be found as follows:

condition1_satisfied_count = sum( diff(array,1,1)==-1  ,2)

I just have no clue how to test for both of these conditions and count them. The solution needs to be inherently fast and efficient since this code will be run >100,000 times.

Really appreciate it :)

Cheers, Abhishek

[Jos (10584)]

Just to show you a faster way to get the neighbours:

nb_list = arrayfun(@(r) find(adj(r,:)), 1:size(adj,1),'un',0) ;
% nb_list{k} holds the neighbours of node k

[Abhishek Varghese]

Thanks heaps! Is there any way we can apply that to the solution below? Currently we are still sweeping through the entire adjacency matrix which may be computationally expensive, right?

[Jos (10584)]

Perhaps, but it might also depend on the number of nodes and the number of neighbours. cond2 then becomes:

cond2 = @(i,t) all(S(nb_list{i},t)==0) ; 
% true when the neighbours of i are not active at time t

A first checks shows the same results :D You should check timings though.

[Abhishek Varghese]

eek haha it's slower by 1.5 secs, with 16 nodes, running 1000 simulations 10 times.. Almost non-intuitive, but I think it may become more useful in larger network groups. Thanks!

Answer 1

[Jos (10584)]

% data
S = randi([0 1],4,10) % state matrix
adj = [0 1 1 1 ; 1 0 0 1 ; 1 0 0 1 ; 1 1 1 0]  % adjacency matrix (symmetric)

% functions that represent the conditions
cond1 = @(i,t) S(i,t)==0 && S(i,t+1) ;     % true if node i is 0 at t, and 1 at t+1
cond2 = @(i,t) all(adj(i, S(:,t)==1)==0) ; % true if all nodes 1 are not neighbours of node i

Ni = size(adj,1) ;     % number of nodes
Nt = size(S,2) - 1 ;   % number of times to check (-1!)

% engine
[ii, tt] = ndgrid(1:Ni, 1:Nt) ; 
R = arrayfun(@(i,t) cond1(i,t) && cond2(i,t) , ii, tt)

[Jos (10584)]

And you can sum them using sum(R(:)), of course :D

[Abhishek Varghese]

G'day Jos, thanks so much!

I made a significant mistake, in that the state matrix should be 4 columns, and 10 rows: so I should have written randi([0 1], 10,4). So sorry about that.

Apart from the indexing of the i and t, what else would I be changing?

[Jos (10584)]

Indeed, the indices into S swap places. And the calculation of Nt should take the number of rows, not columns.

[Jos (10584)]

Also note that adj(x,x) should be 0 for all x

[Abhishek Varghese]

Yes, of course. A node can't be a neighbour of itself :)

Corrected code: Is this right?

% functions that represent the conditions
cond1 = @(t,i) S(t,i)==0 && S(t+1,i) ;     % true if node i is 0 at t, and 1 at t+1
cond2 = @(t,i) all(adj(i, S(t,:)==1)==0) ; % true if all nodes 1 are not neighbours of node i
Ni = size(adj,1) ;     % number of nodes
Nt = size(S,1) - 1 ;   % number of times to check (-1!)
% engine
[tt, ii] = ndgrid(1:Nt, 1:Ni) ; 
R = arrayfun(@(t,i) cond1(t,i) && cond2(t,i) , tt, ii)

[Jos (10584)]

I think so, just test!

btw you only needed to switch S(x,y) into S(y,x); apparently you switched a lot more :D (but that should be no problem)