0
$\begingroup$

Let's say we did some analysis on a network dataset. We have an adjacency matrix which we can use to construct a graph and we can find the nodes with the highest degree's. How would I go about giving a location of these nodes. Would it be okay to refer to the entries of the adjacency matrix (i,j)?

$\endgroup$
  • $\begingroup$ Welcome to the site! What are you trying to do? Why not refer to vertices by their rank according to degree? $\endgroup$ – Emre Jul 19 '18 at 18:42
2
$\begingroup$

Im not sure if I understand your question. But, you do not need to create a graph to work out node degree. Node degree can be obtained by taking the sum of the row or column in the adjacency matrix. E.g. in this 4 node graph where each node has degree $2$, and the row and column sums are also 2.

  0|1|2|3|              1----0
0|0|1|0|1|              ¦    ¦
1|1|0|1|0|              2----3
2|0|1|0|1|
3|1|0|1|0|

And so if we were to update the matrix to add a diagonal edge between nodes 1 and 3. (apologies for the rubbish graphic). Adding values to the diagonal creates a self-loop edge.

  0|1|2|3|              1----0
0|0|1|0|1|              ¦ \  ¦
1|1|0|1|1|              2----3
2|0|1|0|1|
3|1|1|1|0|

In relation to node location, yes refer to node locations using the indices of the adjacency matrix $(i,j)$.

In python this is done by:

import numpy as np


a = np.matrix([[0,1,0,1],
               [1,0,1,1],
               [0,1,0,1],
               [1,1,1,0]])

a.sum(axis=0) # row sum. aka Node Degree
a.sum(axis=1) # column sum. aka Node Degree
# form a tuple with the result of above 
# i.e. (a.sum(axis=1),a.sum(axis=1)) = (1,1)

a.sum(axis=0).argmax() # index of row with max sum (returns 1st index if multiple nodes have same degree)

d= 2 # return nodes with degree value d
np.where(a.sum(axis=0) > d)[1] # returns indeces of nodes with degree > d
$\endgroup$
  • $\begingroup$ Thanks for the code. Now i did this on matlab. It seems doing the sum of the rows and columns, gives me something very close to doing degree(graph(U)), here U is my adjacency matrix. Comparing the two answers they are off by one. $\endgroup$ – user96176 Jul 21 '18 at 5:08
  • $\begingroup$ Hmmm. What does matlab give you for the above example where each node has degree 2? $\endgroup$ – BenP Jul 22 '18 at 18:44
1
$\begingroup$

Sure not. Graph is a combinatorial object. There is no algebraic origin/coordinate. If you change names of nodes (labels) you get a new adjacency matrix. Its called Permutation.

If you can use geometric embedding of your graph you can define positions (e.g. their coordinate after spectral embedding or any other embedding method).

But a pretty interesting approach which is natively graph theoretic is to use some Landmarks. Read this paper and it gives you a pretty nice idea how to do it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.