MATLAB: Finding the number of unique successors of each node from a matrix

Question

I'm new to the MATLAB software and am currently trying to learn it without being formally taught and have a pretty simple question.

I have an adjacency matrix that corresponds to a digraph and want to see what nodes are connected by a walk to other nodes in the network. So, given an adjacency matrix with n nodes:

D = [0,1,1,0,0,0,0;
     0,0,0,1,1,0,0;
     0,0,0,0,1,0,0;
     0,0,0,0,0,1,0;
     0,0,0,0,0,1,0;
     0,0,0,0,0,0,1;
     0,0,0,0,0,0,0]

I want to find the number of unique successors for each node. I am currently using a code to do this, but it is very clunky; every time I change the matrix I need to change the code. It is as follows:

D1 = logical(D^1 + D^2 + D^3 + D^4 + D^5 + D^6 + D^7);

D1(logical(eye(size(D1)))) = 0;

B = sum(transpose(D1));

Is there any way to tidy up the code and just make a more general one!?

Answer 1

Here is a straightforward way:

N = length(D);
DD = zeros(N);
for i=1:N
    DD = DD + D^i;
end
DD = logical(DD);
DD(1:N+1:end) = false;
B = sum(DD,2);

Perhaps a link to explain the meaning of the powers of the adjacency matrix.

---

You can use the following code to visualize the resulting graph (note that the plot doesn't distinguish directed/undirected edges):

% circular layout
t = linspace(0,2*pi,N+1)'; t(end) = [];
xy = [cos(t) sin(t)];

% plot graph and label nodes
subplot(121), gplot(DD, xy, '-*')
text(xy(:,1), xy(:,2), num2str((1:N)'), 'BackgroundColor',[.4 .9 .5], ...
    'VerticalAlign','bottom', 'HorizontalAlign','right')
axis square off

% adjacency matrix
subplot(122), spy(DD)
set(gca, 'XTick',1:N, 'YTick',1:N)
ylabel('from'), xlabel('to')

Answer 2

You can change D^1 + D^2 + D^3 + D^4 + D^5 + D^6 + D^7 with D*(D^size(D,1)-eye(size(D)))/(D-eye(size(D))) and use .*~eye(size(D)) to get rid of the diagonal and end up with

B=sum(logical(D*(D^size(D,1)-eye(size(D)))/(D-eye(size(D)))).*~eye(size(D)), 2)';

However, I personally prefer your code. It is easier to understand what it is doing.

Answer 3

You can change

D1 = logical(D^1 + D^2 + D^3 + D^4 + D^5 + D^6 + D^7);

to

aux = (arrayfun(@(x) D^x, 1:length(D), 'UniformOutput',false));
D1 = any(cat(3,aux{:}),3);

which is valid for all sizes of D.