Create adjacency matrix from nearest neighbour search. (convert adjacency list to adjacency matrix) - Matlab

Question

I have a matrix 2000x5, in the first column the point number, and in columns 2-5 the 4 neighbours (0s if there isnt a neighbour). Is there an efficient way to create an adjacency matrix out of this ?

1   129 0   65  0
2   130 0   66  85
3   131 169 67  0
4   132 170 68  87
5   133 0   69  81
6   134 0   70  82
7   135 173 71  83
8   136 174 72  84
9   137 161 73  0
10  138 162 74  93
11  139 163 75  0
12  140 164 76  95
13  141 165 77  89
14  142 166 78  90
15  143 167 79  91
16  144 168 80  92
17  145 0   81  65
18  146 0   82  66
....

I found the following thread, where it is explained for just one neighbour, but I am not sure how to use it for multiple neighbours. matlab adjacency list to adjacency matrix

I would very much appreciate any help.

Answer 1

Firstly, I'm going to assume that the adjacency list is undirected. In any case, it's not that far of a stretch to go to multiple neighbours. What you need to do first is detect the total number of non-zero elements per row from columns 2 to 5. Once you do this, for the rows of the adjacency matrix, you would copy the point number for as many times as there are non-zero elements per that row. The function repelem is perfectly suitable to do that for you. The column indices would simply be the second to fifth columns removing all of the zero elements. How you can do this is first transpose the matrix resulting in indexing the second to fifth columns, then using a logical indexing matrix to remove out the zero entries. Doing this will unroll your vector in a column-major fashion, which is why transposing is required before doing this operation. Once you do this, you can create row and column access indices so that these can be input into sparse much like that post you linked.

Supposing that your matrix was stored in A, you would do something like this. This also assumes that each of the weights connecting the nodes are 1:

% Find total number of non-zero elements per row, skipping first column
non_zero = sum(A(:,2:end) ~= 0, 2);

% Create row indices
rows = repelem(A(:,1), non_zero);

% Create column indices
cols = A(:,2:end).';    
cols = cols(cols ~= 0);

% Create adjacency matrix
adj = sparse([rows; cols],[cols; rows], 1);

The above representation is in sparse. If you want the full numeric version, cast the output using full:

adj = full(adj);

---

If your graph is directed

If you have a directed graph instead of an undirected graph, the above call to sparse duplicates edges so that you are creating links to and from each of the neighbours. If your graph is actually directed, then you simply have to only use the row and column indices once instead of twice as seen in the above code:

% Create adjacency matrix
adj = sparse(rows, cols , 1);

---

Test Case

Here's a small test case to show you that this works. Supposing my adjacency list looked like the following:

>> A = [1 0 2 3; 2 4 0 0; 3 0 0 4]

A =

     1     0     2     3
     2     4     0     0
     3     0     0     4

The adjacency matrix is now:

>> full(adj)

ans =

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

Taking a look at the list above and how the matrix is populated, we can verify that this is correct.

---

Note about repelem

repelem assumes you have MATLAB R2015a or later. If you don't have this, you can consult this answer by user Divakar on a custom implementation of repelem here: Repeat copies of array elements: Run-length decoding in MATLAB

Answer 2

A quick and simple technique:

adjMat = zeros(size(A,1));
for ind = 1:size(A,1)
    % Flag 1 on each row 'ind' at the indices mentioned in col 2-5
    adjMat(ind, nonzeros(A(ind,2:end))) = 1;
end

Since you have mentioned using the nearest neighbour search, it is likely that the adjacency list should be completely filled to result in a undirected graph, in the sense that if row 1 has 20 as a neighbour, row 20 very likely has 1 as a neighbour.

However technically speaking, this will produce an adjacency matrix exactly equivalent to the adjacency list, assuming nothing by itself.

Example:

For an adjacency list

A = [1 2 3; 2 0 1; 3 1 4; 4 5 3; 5 4 0]

A =

 1     2     3
 2     0     1
 3     1     4
 4     5     3
 5     4     0

The result is:

adjMat =

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

---

P.S. To force undirected-ness, you can simply add another statement in the for loop body:

adjMat(nonzeros(A(ind,2:end)),ind) = 1;

This will ensure that the adjacency matrix will be symmetric, which is a characteristic of undirected graphs.