4

各ノードがkタイプのいずれかになる無向ネットワークがあります。ノードiごとに、ノードiが持つ各タイプの隣接ノードの数を計算する必要があります。

現在、列がノードのインデックスであるエッジリストでエッジを表しています。ノードはnxk行列として表され、各列はノード タイプを表します。ノードがk型の場合、k番目の列の値は 1、それ以外の場合は 0 です。

これが私の現在のコードです。これは正しいですが、遅すぎます。

# 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]

この for ループを回避できる巧妙な numpy はありますか? これを行う最善の方法が隣接行列を使用する場合、それも許容されます。

4

2 に答える 2

2

私があなたの質問を正しく理解していれば、numpy_indexedパッケージ (免責事項: 私はその作成者です) には、これに対する迅速かつエレガントな解決策があります。

# 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])

一般に、グラフの操作、またはジャグ配列を含むアルゴリズムは、多くの場合、グループ化操作を使用して効率的かつエレガントに表現できます。

于 2016-10-01T11:22:43.500 に答える