Accumuler les valeurs de "neigborhood" d'edgelist avec numpy

Question

J'ai un réseau non orienté où chaque nœud peut être l'un des types k. Pour chaque nœud i, j'ai besoin de calculer le nombre de voisins que le nœud i a de chaque type.

Actuellement je représente les bords avec un edgelist où les colonnes sont des index des noeuds. Les nœuds sont représentés sous la forme d'une matrice n x k, où chaque colonne représente un type de nœud. Si un nœud est de type k alors la valeur de la colonne k est 1, 0 sinon.

Voici mon code actuel, qui est correct, mais trop lent.

# example nodes and edges, both typically much longer 
nodes = np.array([[0, 0, 1], 
        [0, 1, 0],      
        [1, 0, 0]]) 
edges = np.array([[0, 1], 
        [1, 2]]) 

neighbors = np.zeros_like(nodes) 

for i, j in edges: 
    neighbors[i] += nodes[j] 
    neighbors[j] += nodes[i] 

Y a-t-il un chiffre astucieux qui me permettrait d'éviter cette boucle? Si la meilleure façon de le faire est avec une matrice d'adjacence, cela est également acceptable.

Answer 1

Vous pouvez simplement utiliser np.add.at -

out = np.zeros_like(nodes) 
np.add.at(out, edges[:,0],nodes[edges[:,1]]) 
np.add.at(out, edges[:,1],nodes[edges[:,0]]) 

Answer 2

Si je comprends bien votre question, le paquet numpy_indexed (disclaimer: Je suis son auteur) a une solution rapide et élégante à ceci:

# generate a random example graph 
n_edges = 50 
n_nodes = 10 
n_types = 3 
edges = np.random.randint(0, n_nodes, size=(n_edges, 2)) 
node_types = np.random.randint(0, 2, size=(n_nodes, n_types)).astype(np.bool) 

# Note; this is for a directed graph 
s, e = edges.T 
# for undirected, add reversed edges 
s, e = np.concatenate([edges, edges[:,::-1]], axis=0).T 
import numpy_indexed as npi 
node_idx, neighbor_type_count = npi.group_by(s).sum(node_types[e]) 

En général, les opérations sur les graphes, ou des algorithmes impliquant jagged- tableaux, peuvent souvent être exprimés efficacement et élégamment en utilisant des opérations de groupement.