Python Computing Vertex Degree Matrix

Question

I am currently working on trying to write code to calculate the degree matrix, so that I may compute the Laplacian L = D - A, where D=degree matrix, A=adjacency matrix.

This will be later used in my spectral clustering algorithm. I am using Python. So for this toy example, I am having trouble doing it. Can anyone provide an efficient way of doing this, or if there is an API for calculating the degree matrix? My question is simply, what is an efficient way of calculating the degree of connectivity matrix, or is there a python module for that?

Example:

import numpy as np
matrix = np.matrix('1, 1, 1, 1; 1, 0, 0, 0; 0, 0, 1, 1')

matrix =

 1     1     1     1
 1     0     0     0
 0     1     0     1
 0     0     1     1

How can I compute the degree(matrix) that gives me 5 3 4 4, which represent the degree of connectivity for each node? Thank you.

Vulpine

err, you want to encode graph-theoretic objects using numerical methods on a computer, and you got as far as declaring a matrix. Here is another SO question / answer on adjacency matrices (there are other, similar questions and answers that you should read through first rather than ask yet another version), here is one of many write-ups on the internet on how to do what you are asking , here is theory. – Underwood

Simply asking how to compute the degree matrix efficiently. I know how to do the rest. – Vulpine

Answer 1

Well I figured it out, but I don't know if this is the most efficient way of doing this. However, here was the answer I found.

#### Example of Computing Degree Matrix
import numpy as np
matrix = np.matrix('1, 1, 1, 1;'
                   '1, 0, 0, 0;'
                   '0, 1, 0, 1;'
                   '0, 0, 1, 1')

degree = np.zeros(len(matrix)) # initialize list to hold values of degree

# calculate the sums along rows and sum along columns
colsum = matrix.sum(axis=0)
rowsum = matrix.sum(axis=1)

# loop through matrix and add up all degree connections
for j in range(0, len(matrix)):
    degree[j] = colsum[0,j] + rowsum[j,0]

# get the diagonal entries to correct the for loop oversumming
A = matrix.diagonal()
d = A.flat
diagMat = list(d)

# print the degree of connectivity matrix 
print np.diag(degree - diagMat)

[[ 5.  0.  0.  0.]
 [ 0.  3.  0.  0.]
 [ 0.  0.  4.  0.]
 [ 0.  0.  0.  4.]]

Vulpine

Answer 2

There is a special package for graphs networkx:

import networkx as nx
import numpy as np

m = np.matrix('1, 1, 1, 1;'
              '1, 0, 0, 0;'
              '0, 1, 0, 1;'
              '0, 0, 1, 1')
G = nx.from_numpy_matrix(m)
nx.laplacian_matrix(G).toarray()

Result:

array([[ 3, -1, -1, -1],
       [-1,  2, -1,  0],
       [-1, -1,  3, -1],
       [-1,  0, -1,  2]], dtype=int64)

Fixity

Answer 3

You can use sum and diag of numpy Just instead of matrix use array

import numpy as np
matrix = np.array([[1, 1, 1, 1],[1, 0, 0, 0],[ 0 ,1 ,0 ,1 ],[0, 0, 1, 1]])    
degree = np.diag(np.sum(matrix, axis=1))

Edmonson

Answer 4

To answer the question, how to get the degree matrix from an adjancency matrix:

It might not be faster than some other answers, but at least a tiny bit simpler and written i PyTorch (should be easily translated into numpy as other answers has used)

import torch
A = torch.Tensor([[1, 1, 1, 1],
                  [1, 0, 0, 0],
                  [0, 1, 0, 1],
                  [0, 0, 1, 1]])

out_degree = torch.sum(A, dim=0)
in_degree = torch.sum(A, dim=1)

identity = torch.eye(A.size()[0])

degree_matrix = diag*in_degree + diag*out_degree - torch.diagflat(torch.diagonal(A))

tensor([[5., 0., 0., 0.],
        [0., 3., 0., 0.],
        [0., 0., 4., 0.],
        [0., 0., 0., 4.]])

Pretty straight forward code, some explanations:

• torch.diagonal gets the diagonal element in a 1D array
• torch.diagflat takes an array and creates a 2D diagonal matrix

Pyroconductivity

Answer 5

For those of you who are dealing with an undirected graph, you can use the following method to create the diagonal degree matrix of the nodes:

def diagonal_degree_matrix(adj):
    diag = np.zeros([adj.shape[0], adj.shape[0]]) # basically dimensions of your graph
    rows, cols = adj.nonzero()
    for row, col in zip(rows, cols):
        diag[row, row] += 1
    return diag

Where adj is the adjecency matrix of type csr_matrix and np is the numpy library.

Spinks

Answer 6

Are you calculating the in-degree or out-degree?

I think a bit more efficient code would be: degree_size = np.size(Matrix, 0)

out_degree = np.zeros((degree_size,degree_size))
in_degree = np.zeros((degree_size,degree_size))

out_degree_sum = Matrix.sum(axis=0)
in_degree_sum = Matrix.sum(axis=1)

for i in range(0, degree_size):
    out_degree[i,i] = out_degree_sum[i]

for j in range(0, degree_size):
    in_degree[j,j] = in_degree_sum[j]

Ilbert