0
$\begingroup$

I know that the computational cost of the adjacency matrix is n*n. Namely, this graph-theoretical structure contains value 0 or 1 for every pair of vertices if there the edge exists or not, so it needs n^2 space. I am interesting in the computational cost of the adjacency-based distance matrix in which each entry is the Euclidean distance between the rows of the adjacency matrix. This matrix is a pseudo-distance matrix since it can contain zero in off-diagonal places if two adjacency rows are identical. For instance, we have the graph with five nodes:

enter image description here

whose adjacency matrix has the form:

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

Then we are computing the distance matrix of the Euclidean distances between the rows of the above adjacency matrix. This distance matrix has the form:

  1    2    3    4    5
1 0.00 2.00 1.00 1.41 0.00
2 2.00 0.00 2.24 1.41 2.00
3 1.00 2.24 0.00 1.73 1.00
4 1.41 1.41 1.73 0.00 1.41
5 0.00 2.00 1.00 1.41 0.00

I am interesting in the computational cost of the distance matrix computation and in the computational cost of overall process.

$\endgroup$
  • $\begingroup$ An adjacency matrix will only give you information about relations of vertices, you cannot infer a geometric embedding from it (see here for more information). So without more information there is no way of determining such a matrix. $\endgroup$ – KVN Jan 28 at 17:28

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.