Python计算顶点度数矩阵

Question

我目前正在尝试编写代码来计算度矩阵，这样我就可以计算拉普拉斯 L = D - A，其中 D = 度矩阵，A = 邻接矩阵。

这将在我的谱聚类算法中使用。我正在使用 Python。所以对于这个玩具示例，我很难做到。任何人都可以提供一种有效的方法来执行此操作，或者是否有 API 用于计算度数矩阵？我的问题很简单，什么是计算连接度矩阵的有效方法，或者是否有一个 python 模块？

示例：

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

如何计算度数（矩阵）得到 5 3 4 4，它表示每个节点的连通度？谢谢。

Answer 1

好吧，我想通了，但我不知道这是否是最有效的方法。但是，这是我找到的答案。

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

Answer 2

你计算的是入度还是出度？

我认为更高效的代码是： degree_size = np.size(矩阵, 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]

Answer 3

回答问题，如何从邻接矩阵得到度矩阵：

它可能不会比其他一些答案快，但至少更简单一点，并且是用 PyTorch 编写的（应该很容易翻译成 numpy，因为其他答案已使用）

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

非常简单的代码，一些解释：

torch.diagonal获取一维数组中的对角线元素
torch.diagflat 接受一个数组并创建一个二维对角矩阵

Answer 4

有一个特殊的图表包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()

结果：

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

Answer 5

对于那些正在处理无向图的人，您可以使用以下方法创建节点的对角度矩阵：

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

其中 adj 是 csr_matrix 类型的邻接矩阵，np 是 numpy 库。

Answer 6

您可以使用 sum 和 diag 的 numpy 只是代替矩阵使用数组

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

Python计算顶点度数矩阵

Python Computing Vertex Degree Matrix

python

graph-theory

cluster-analysis

adjacency-matrix