根据numpy数组中的组标签对邻接矩阵中的边求和

Question

比如我得到了对称邻接矩阵（无自环），即

A = 
[
[0, 1, 1, 0, 0],
[1, 0, 1, 0, 1],
[1, 1, 0, 1, 0],
[0, 0, 1, 0, 1],
[0, 1, 0, 1, 0]]

然后，我得到了一个与该图相关联的簇标签 i 的数组，即

cluster = [1,1,2,2,3]

表示节点1和节点2在同一组，节点3和节点4在同一组，节点5在独立组。

问题是如何得到组内和组间的边之和，

组内：表示共享相同簇标签的节点之间的边，例如节点1和节点2在同一组中，因此它们的和为1，节点3和节点相同4. 对于节点 5，其 0.

Between groups：表示共享不同簇标签的节点之间的边，例如group 1和group 2，表示节点1节点3，节点1节点4，节点2节点3的边之和，节点2节点4。组1和组2之间的答案是2。

然后 return 二维对称数组包含结果，即

[[1,2,1],
[2,1,1],
[1,1,0]]

Answer 1

这将 return 一个数组，其元素 [i,j] 对应簇 i 和 j 的边之和：

n = cluster.max()
degrees = np.zeros((n,n))
idx = [np.where(cluster==i)[0] for i in np.arange(n)+1]
for i in range(n):
  degrees[i,i] = A[np.ix_(idx[i],idx[i])].sum()/2
  for j in range(i):
    degrees[i,j] = degrees[j,i] = A[np.ix_(idx[i],idx[j])].sum()

输出：

[[1. 2. 1.]
 [2. 1. 1.]
 [1. 1. 0.]]

您也可以使用 itertools，但我认为这可能更快。

Answer 2

你可以使用矩阵代数；

cluster = np.array(cluster)
# create cluster-node adjacency matrix
aux = np.identity(cluster.max(),int)[cluster-1]
# we can now count by multiplying
out = aux.T@A@aux
# fix diagonal (which was counted twice)
np.einsum("ii->i",out)[...] //= 2
out
# array([[1, 2, 1],
#        [2, 1, 1],
#        [1, 1, 0]])

为了加快速度，我们可以将矩阵乘积替换为 (1) 如果节点按簇排序：

boundaries = np.diff(cluster,prepend=-1).nonzero()[0]
out =  np.add.reduceat(np.add.reduceat(A,boundaries,1),boundaries,0)

(2) 如果不是：

nc = cluster.max()
out = np.zeros((nc,nc),int)
np.add.at(out,(cluster[:,None]-1,cluster-1),A)

根据numpy数组中的组标签对邻接矩阵中的边求和

Sum the edge in adjacency matrix according to group label in numpy array

python

numpy

igraph

numpy-ndarray

adjacency-matrix