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，这表示每个节点的连通度？谢谢。

- ajl123

---

你想使用计算机上的数值方法对图论对象进行编码，目前已经声明了一个矩阵。这里有一个关于邻接矩阵的SO问题/答案（还有其他类似的问题和答案，你应该先阅读它们而不是再问另一个版本），这里是互联网上关于如何做你所要求的事情的众多文章之一，这里是理论方面的拉普拉斯矩阵。 - Shawn Mehan

只是想问如何高效地计算度矩阵。我知道如何完成其余部分。 - ajl123

Answer 1

有一个专门用于图形的包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)

- Mykola Zotko

Answer 2

我已经理解了，但不确定这是否是做这件事最有效的方法。以下是我找到的答案。

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

- ajl123

Answer 3

你可以使用numpy中的sum和diag函数，只需将矩阵替换为数组即可。

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

- Hadi Rasekh

Answer 4

回答如何从邻接矩阵中获取度矩阵的问题：

这个方法可能不比其他答案更快，但至少要简单一点，并且使用 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 获取一个 1D 数组中对角线元素
• torch.diagflat 取一个数组并创建一个 2D 对角矩阵

- Andreas Klintberg

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 库。

- Pedram

Answer 6

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

我认为更高效的代码应该是： 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]

- Koen