根据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 matrixaux = np.identity(cluster.max(),int)[cluster-1]# we can now count by multiplyingout = aux.T@A@aux# fix diagonal (which was counted twice)np.einsum("ii->i",out)[...] //= 2out# 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，但我认为这可能更快。