Adjacency Matrix from Numpy array using Euclidean Distance

Question

Can someone help me please on how to generate a weighted adjacency matrix from a numpy array based on euclidean distance between all rows, i.e 0 and 1, 0 and 2,.. 1 and 2,...?

Given the following example with an input matrix(5, 4):

matrix = [[2,10,9,6],
          [5,1,4,7],
          [3,2,1,0], 
          [10, 20, 1, 4], 
          [17, 3, 5, 18]]

I would like to obtain a weighted adjacency matrix (5,5) containing the most minimal distance between nodes, i.e,

if dist(row0, row1)= 10,77 and dist(row0, row2)= 12,84, 

--> the output matrix will take the first distance as a column value.

I have already solved the first part for the generation of the adjacency matrix with the following code :

from scipy.spatial.distance import cdist
dist = cdist( matrix, matrix, metric='euclidean')

and I get the following result :

array([[ 0.        , 10.77032961, 12.84523258, 15.23154621, 20.83266666],
       [10.77032961,  0.        ,  7.93725393, 20.09975124, 16.43167673],
       [12.84523258,  7.93725393,  0.        , 19.72308292, 23.17326045],
       [15.23154621, 20.09975124, 19.72308292,  0.        , 23.4520788 ],
       [20.83266666, 16.43167673, 23.17326045, 23.4520788 ,  0.        ]])

But I don't know yet how to specify the number of neighbors for which we select for example 2 neighbors for each node. For example, we define the number of neighbors N = 2, then for each row, we choose only two neighbors with the two minimum distances and we get as a result :

[[ 0.        , 10.77032961, 12.84523258, 0, 0],
       [10.77032961,  0.        ,  7.93725393, 0, 0],
       [12.84523258,  7.93725393,  0.        , 0, 0],
       [15.23154621, 0, 19.72308292,  0.        , 0 ],
       [20.83266666, 16.43167673, 0, 0 ,  0.        ]]

Could you please elaborate on what you consider a node? is it a row? what is the desired adjacency matrix output for your example input? — Ehsan
– Ehsan, Commented Jan 19, 2021 at 9:09
Hello Ehsan, Thank you for your interest, yes i meant row by node. I have already updated the publication. — Refka
– Refka, Commented Jan 19, 2021 at 9:44
Thank you for clear explanation. Please check to see if suggested answer resolves your issue. — Ehsan
– Ehsan, Commented Jan 19, 2021 at 9:59

Akshay Sehgal · Accepted Answer · 2021-01-19 10:37:46Z

1

You can use this cleaner solution to get the smallest n from a matrix. Try the following -

The dist.argsort(1).argsort(1) creates a rank order (smallest is 0 and largest is 4) over axis=1 and the <= 2 decided the number of nsmallest values you need from the rank order. np.where filters it or replaces it with 0.

np.where(dist.argsort(1).argsort(1) <= 2, dist, 0)

array([[ 0.        , 10.77032961, 12.84523258,  0.        ,  0.        ],
       [10.77032961,  0.        ,  7.93725393,  0.        ,  0.        ],
       [12.84523258,  7.93725393,  0.        ,  0.        ,  0.        ],
       [15.23154621,  0.        , 19.72308292,  0.        ,  0.        ],
       [20.83266666, 16.43167673,  0.        ,  0.        ,  0.        ]])

This works for any axis or if you want nlargest or nsmallest from a matrix as well.

edited Jan 19, 2021 at 10:37

answered Jan 19, 2021 at 10:31

Akshay Sehgal

19.4k3 gold badges26 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Refka Over a year ago

Hello Akshay, i tried it and it worked, thank you for providing me with another solution with enough explanation.

Ehsan · Accepted Answer · 2021-01-19 09:59:13Z

1

Assuming a is your Euclidean distance matrix, you can use np.argpartition to choose n min/max values per row. Keep in mind the diagonal is always 0 and euclidean distances are non-negative, so to keep two closest point in each row, you need to keep three min per row (including 0s on diagonal). This does not hold if you want to do max however.

a[np.arange(a.shape[0])[:,None],np.argpartition(a, 3, axis=1)[:,3:]] = 0

output:

array([[ 0.        , 10.77032961, 12.84523258,  0.        ,  0.        ],
       [10.77032961,  0.        ,  7.93725393,  0.        ,  0.        ],
       [12.84523258,  7.93725393,  0.        ,  0.        ,  0.        ],
       [15.23154621,  0.        , 19.72308292,  0.        ,  0.        ],
       [20.83266666, 16.43167673,  0.        ,  0.        ,  0.        ]])

answered Jan 19, 2021 at 9:59

Ehsan

12.5k2 gold badges24 silver badges36 bronze badges

1 Comment

Refka Over a year ago

It works. Thank you, i really appreciate your help.

Collectives™ on Stack Overflow

Adjacency Matrix from Numpy array using Euclidean Distance

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related