CODEWITHSUNDEEP
matlab
Thoth
Thoth

Reputation: 1041

Extending adjacency matrix neighbours

I have an adjacency matrix. For example, the following,

+---+-------------------------------+
|   |   1     2     3     4     5   |
+---+-------------------------------+
| 1 |   0     1     0     0     0   |
| 2 |   1     0     0     0     1   |
| 3 |   0     0     0     1     0   |
| 4 |   0     0     1     0     1   |
| 5 |   0     1     0     1     0   |
+---+-------------------------------+

how can we extract the following adjacency matrix, without for loops, where for each element (row or column) the neighbors of the already existed neighbors were added? For example, the element 3 has neighbor the element 4 so in the new adjacency matrix the element 3 will have neighbors the elements 4 and 5. 

+---+-------------------------------+
|   |   1     2     3     4     5   |
+---+-------------------------------+
| 1 |   0     1     0     0     1   |
| 2 |   1     0     0     1     1   |
| 3 |   0     0     0     1     1   |
| 4 |   0     1     1     0     1   |
| 5 |   1     1     1     1     0   |
+---+-------------------------------+

Best regards,

Thoth.

Upvotes: 1

Views: 394

Answers (1)

Simon M
Simon M

Reputation: 266

If A is your adjacency matrix, then the matrix you want is A2, where:

A2 = (A+A^2) > 0

This is because the square of an adjacency matrix has components s_ij, where s_ij is the number of paths of length two between i and j. (In fact (A^n)_ij is the number of paths from i to j of length n).

Therefore, if you add A (which contains all pairs joined by a path of length 1) to A^2 which contains all pairs linked by a path of length two, you'll get the number of paths of length 1 or 2. (And we only care if this is positive for this case). Paths of length two are paths to the neighbours of neighbours.

You might want to set the diagonal back to zero though

Upvotes: 2

Related Questions