根据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。组间：表示共享不同簇标签的节点之间的边，例如group 1和group 2，表示节点1节点3，节点1节点4，节点2节点3，节点2节点4的边之和. 组1和组2之间的答案是2。然后返回一个包含结果的二维对称数组，即[[1,2,1],[2,1,1],[1,1,0]]

Answer 1

您可以使用矩阵代数；

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)

Answer 2

这将返回一个数组，其元素[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，但我认为这可能更快。