Суммируйте край в матрице смежности в соответствии с меткой группы в массиве numpy

Question

Например, у меня есть матрица смежности symri c (без self-l oop), т.е.

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.

Между группами: означает границу между узлами, которые имеют разные метки кластера, например, группа 1 и группа 2, это означает, что суммируется край, узел 1, узел 3, узел 1, узел 4, узел 2, узел 3, узел 2, узел 4. Ответ 2 между группой 1 и группой 2.

затем вернуть 2d-симметричный c массив, содержащий результат, т.е.

* 1 016 *

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, но я думаю, что это, вероятно, быстрее.