Search code examples
matlabgraph-theoryadjacency-matrix

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

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!?

Solution

  • 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')

    graph