Adjacency matrix of a network to Distance matrix (Two -Hop)

I have the following code for generating an adjacency matrix for a network. How do I go about creating a distance matrix (Probably a two hop matrix) from this output.

    function  adj = AdjMatrixLattice4( N, M )
    % Size of adjacency matrix
    MN = M*N;
    adj = zeros(MN,MN);

      for i=1:N
        for j=1:N
            A = M*(i-1)+j;          %Node # for (i,j) node
            if(j<N)                
                B = M*(i-1)+j+1;    %Node # for node to the right
                C = M*(i-1)+j+2;
                D = M*(i-1)+j+2;
                adj(A,B) = 1;
                adj(B,A) = 1;
                adj(A,C) = 1;
                adj(C,A) = 1;
                adj(A,D) = 1;
                adj(D,A) = 1;
            end
            if(i<M)
                B = M*i+j;  
                C = M*i+j+1;    %Node # for node below
                D = M*i+j;
                adj(A,B) = 1;       
                adj(B,A) = 1;
                adj(A,C) = 1;
                adj(C,A) = 1;
                adj(A,D) = 1;
                adj(D,A) = 1;
            end            
        end
    end    
end
ans =

     0     1     1     1     1     0     0     0     0     0
     1     0     1     1     1     1     0     0     0     0
     1     1     0     0     0     1     1     0     0     0
     1     1     0     0     1     1     1     1     0     0
     1     1     0     1     0     1     1     1     1     0
     0     1     1     1     1     0     0     0     1     1
     0     0     1     1     1     0     0     1     1     0
     0     0     0     1     1     0     1     0     1     1
     0     0     0     0     1     1     1     1     0     0
     0     0     0     0     0     1     0     1     0     0

How do i convert this to a two hop distance matrix.?

Can someone help?

[Ced]

What exactly do you mean by "two hop distance matrix"?

a) A logical matrix H(i,j) = 1 if the distance between i and j is two?

b) at the most two?

Something like this?

A =  [   ...
    0     1     1     1     1     0     0     0     0     0
    1     0     1     1     1     1     0     0     0     0
    1     1     0     0     0     1     1     0     0     0
    1     1     0     0     1     1     1     1     0     0
    1     1     0     1     0     1     1     1     1     0
    0     1     1     1     1     0     0     0     1     1
    0     0     1     1     1     0     0     1     1     0
    0     0     0     1     1     0     1     0     1     1
    0     0     0     0     1     1     1     1     0     0
    0     0     0     0     0     1     0     1     0     0 ];

MN = size(A,1);

TwoHopMat = false(MN,MN);

for i = 1:MN
    for j = 1:MN
        if ( A(i,j) ) % if we can reach this node
            % we can reach all it can reach too in two steps
            TwoHopMat(i,:) = (TwoHopMat(i,:) | A(:,j)');
        end
    end
end

% If it is "exactly two" and not "at the most two", 
% just remove the original adjacency matrix
% TwoHopMat = xor(TwoHopMat,A);

% If you want it as a double
TwoHopMat = double(TwoHopMat)

Or... shorter

A = logical(A);
TwoHopMatB = zeros(MN,MN);
for i = 1:MN
    TwoHopMatB(i,:) = any(A(A(i,:),:),1)
end

EDIT I was originally only checking the upper diagonal. However, with the loop as it is now, this will not work. E.g. A(3,2) == 1, and A(2,6) == 1, so in the end, TwoHopMat(3,6) should be 1. However, if neither 3 nor 6 checks their connection to 2 (upper diagonal), this will get lost.

[Christy Jackson]

I should be generating an adjacency/connectivity matrix like the one below

This connectivity matrix is identified for a network. Column represents nodes of the network and row represents the link existence between the nodes, i.e., the row one says about the connectivity information of node A,likewise for the remaining nodes. The matrix has the value 0 or 1, where 1 represents the existence of a link.

My hop matrix should look like the one below

Row value represents the one-hop and two-hop information between the nodes. The matrix takes the value 0 or 1, where 1 says low connectivity information for the node. Here one hop represents a communication between two elements (Node A to Node B) say (1,2) and (2,1) = 1. Whereas a two hop matrix is a communication between tow elements with a mediator in between (Node A to Node C and Node C to Node B). Lets Say if (1,3) and (3,1) =1 then (1,2) and (2,1) should also be 1

[Ced]

Thanks a lot for that explanation!

Only one question: why isn't the diagonal full of 1's? Since Node A can reach C, and therefore C can reach A, then A can go to C and back in two steps, no? =)

For correctness, here the adjusted code, using the CM above as A:

A = [ 0 1 1 0 0 0 0 0
     1 0 1 0 0 0 0 0 
     1 1 0 1 0 0 0 0
     0 0 1 0 1 1 0 0 
     0 0 0 1 0 0 1 0 
     0 0 0 1 0 0 1 0 
     0 0 0 0 1 1 0 1 
     0 0 0 0 0 0 1 0  ]; 

MN = size(A,1);

%%%%%%%%%%%%%%%%%%%%%%%%%%
%%Version 1: Looping through each element
A = logical(A);
TwoHopMat_1 = A;

for i = 1:MN
    for j = 1:MN
        if ( A(i,j) ) % if we can reach this node
            % we can reach all it can reach too
            TwoHopMat_1(i,:) = (TwoHopMat_1(i,:) | A(:,j)'); 
        end
    end
end

% we want the diagonal to be false
TwoHopMat_1 = xor(TwoHopMat_1,diag(true(MN,1)));

% If you want it as a double
TwoHopMat_1 = double(TwoHopMat_1)

%%%%%%%%%%%%%%%%%%%%%%%%%%
%%Version 2: Looking at each node once  
A = logical(A);

TwoHopMat_2 = zeros(MN,MN);
for i = 1:MN
    % This is everyone Node i can reach in a single hop
    single_hops = A(i,:);
    % now combine it with every node it can reach in two hops
    TwoHopMat_2(i,:) = any([ single_hops ; A(single_hops,:) ],1);
end

% we want the diagonal to be false
TwoHopMat_2 = xor(TwoHopMat_2,diag(true(MN,1)));

This returns

TwoHopMat_1 =

       0     1     1     1     0     0     0     0
       1     0     1     1     0     0     0     0
       1     1     0     1     1     1     0     0
       1     1     1     0     1     1     1     0
       0     0     1     1     0     1     1     1
       0     0     1     1     1     0     1     1
       0     0     0     1     1     1     0     1
       0     0     0     0     1     1     1     0

TwoHopMat_2 =

       0     1     1     1     0     0     0     0
       1     0     1     1     0     0     0     0
       1     1     0     1     1     1     0     0
       1     1     1     0     1     1     1     0
       0     0     1     1     0     1     1     1
       0     0     1     1     1     0     1     1
       0     0     0     1     1     1     0     1
       0     0     0     0     1     1     1     0

[Christy Jackson]

Thank you very much for your support. Appreciated. I have a certain condition in the network which allows the diagonals only to be zero. Thanks again, i ll come back with few more questions to you though.!

[Ced]

I see, thanks! I copied one of the solutions to the answer section so you can close the topic. Cheers

Answer 1

[Ced]

Possible solution, see comment section for details:

A = [ 0 1 1 0 0 0 0 0
     1 0 1 0 0 0 0 0 
     1 1 0 1 0 0 0 0
     0 0 1 0 1 1 0 0 
     0 0 0 1 0 0 1 0 
     0 0 0 1 0 0 1 0 
     0 0 0 0 1 1 0 1 
     0 0 0 0 0 0 1 0  ]; 

MN = size(A,1);

%%%%%%%%%%%%%%%%%%%%%%%%%%
%%Looking at each node once  
A = logical(A);

TwoHopMat_2 = zeros(MN,MN);
for i = 1:MN
    % This is everyone Node i can reach in a single hop
    single_hops = A(i,:);
    % now combine it with every node it can reach in two hops
    TwoHopMat_2(i,:) = any([ single_hops ; A(single_hops,:) ],1);
end

% we want the diagonal to be false
TwoHopMat_2 = xor(TwoHopMat_2,diag(true(MN,1)));

[Muhammad fawad]

How we find 3 and 4 hops. please help

Answer 2

[Christine Tobler]

An easier way to compute the two-hop matrix is through matrix multiplication, I think.

The adjacency matrix A is the one-hop matrix. The matrix A2 = A*A has a non-zero in A(i, j), if it is possible to go from node i to node j in exactly two steps. Use A + A*A to get non-zeros in A(i, j) if you can go from node i to node j in 2 or less steps.

[Rogier Noldus]

When we use A + A*A, then (A + A*A)_ij is the mathematical sum of A_ij and A*A_ij. Shouldn't we rather use A OR A*A? (A OR A*A)_ij will have a value 1 in position (i,j) when node j can be reached from node i in 1 hop or in 2 hops.

[Muhammad fawad]

how to find 4 or less than 4 hops using this method