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.

err, you want to encode graph-theoretic objects using numerical methods on a computer, and you got as far as declaring a matrix. [Here](http://stackoverflow.com/questions/13547133/adjacency-list-and-adjacency-matrix-in-python) 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](http://www.python-course.eu/graphs_python.php) is one of many write-ups on the internet on how to do what you are asking , [here](https://en.wikipedia.org/wiki/Laplacian_matrix) is theory. — Shawn Mehan, Sep 03 '15 at 16:57
Simply asking how to compute the degree matrix efficiently. I know how to do the rest. — ajl123, Sep 03 '15 at 17:41

score 6 · Answer 1 · answered Mar 13 '19 at 01:22

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)

score 5 · Accepted Answer · answered Sep 03 '15 at 19:01

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.]]

score 5 · Answer 3 · answered Oct 25 '19 at 14:50

5

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

answered Oct 25 '19 at 14:50

Hadi Rasekh

2,622
2
20
28

score 3 · Answer 4 · answered Mar 13 '19 at 00:06

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

score 1 · Answer 5 · answered Jun 06 '19 at 04:10

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.

score 0 · Answer 6 · answered Feb 07 '18 at 19:31

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]

Python Computing Vertex Degree Matrix

6 Answers6