Labeling hubs in a network

Question

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)?

Answer 1

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

Answer 2

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.