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$
1
  • $\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, 2018 at 18:42

2 Answers 2

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$
2
  • $\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, 2018 at 5:08
  • $\begingroup$ Hmmm. What does matlab give you for the above example where each node has degree 2? $\endgroup$
    – BenP
    Jul 22, 2018 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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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