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

Question

Christy Jackson 2016-3-17

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/273980-adjacency-matrix-of-a-network-to-distance-matrix-two-hop

评论： Muhammad fawad 2021-9-9

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?

5 个评论
显示 3更早的评论隐藏 3更早的评论

Ced 2016-3-17

编辑：Ced 2016-3-17

在 MATLAB Online 中打开

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.

Ced 2016-3-18

编辑：Ced 2016-3-18

在 MATLAB Online 中打开

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 2016-3-19

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 2016-3-19

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

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Ced 2016-3-19

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/273980-adjacency-matrix-of-a-network-to-distance-matrix-two-hop#answer_214202

在 MATLAB Online 中打开

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)));

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Muhammad fawad 2021-9-9

How we find 3 and 4 hops. please help

请先登录，再进行评论。

Answer 2

Christine Tobler 2016-4-25

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/273980-adjacency-matrix-of-a-network-to-distance-matrix-two-hop#answer_219377

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.

2 个评论
显示无隐藏无

Rogier Noldus 2021-8-19

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 2021-9-9