python - 使用 lil_matrix 分割多关系图

Question

我使用稀疏 lil_matrix 格式存储具有两种类型关系的图形。这就是我正在做的:

e=15
k= 2
X = [lil_matrix((e,e)) for i in range(k)]
#storing type 0 relation#
X[0][0,14] =1
X[0][0,8] =1
X[0][0,9] =1
X[0][0,10] =1
X[0][1,14] =1
X[0][1,6] =1
X[0][1,7] =1
X[0][2,8] =1
X[0][2,9] =1
X[0][2,10] =1
X[0][2,12] =1
X[0][3,6] =1
X[0][3,12] =1
X[0][3,11] =1
X[0][3,13] =1
X[0][4,11] =1
X[0][4,13] =1
X[0][5,13] =1
X[0][5,11] =1
X[0][5,10] =1
X[0][5,12] =1
#storing type 1 relation#
X[1][14,7] =1
X[1][14,6] =1
X[1][6,7] =1
X[1][6,8] =1
X[1][6,9] =1
X[1][10,9] =1
X[1][10,8] =1
X[1][10,11] =1
X[1][12,8] =1
X[1][12,10] =1
X[1][12,11] =1
X[1][12,13] =1
X[1][14,12] =1
X[1][11,9] =1
X[1][8,7] =1
X[1][8,9] =1

我想修剪仅包含 50% 节点的网络。我处理这个问题的方式是:

nodes_list = range(e)
total_nodes = len(nodes_list)
get_percentage_of_prune_nodes = np.int(total_nodes * 0.5)
new_nodes = sorted(random.sample(nodes_list,get_percentage_of_prune_nodes))
e_new= get_percentage_of_prune_nodes
k_new= 2
#Y is the pruned matrix#
Y = [lil_matrix((e_new,e_new)) for i in range(k_new)]     
for i in xrange(e):
    for j in xrange(e):
        for rel in xrange(k_new):
            if i in new_nodes and j in new_nodes:
                if X[rel][i,j]==1:
                    Y[rel][new_nodes.index(i),new_nodes.index(j)] = 1

在原始矩阵 (X) 很大的情况下，这不是非常有效的方法。有没有最快或最聪明的方法来修剪它？

Answer 1

仅关注矩阵:

In [318]: X=X[0].astype(int)
In [327]: X.A
Out[327]: 
array([[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1],
       [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1],
       [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0],
       [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])

In [331]: new_nodes=sorted(random.sample(np.arange(e).tolist(),7))
In [332]: new_nodes
Out[332]: [0, 1, 2, 5, 8, 12, 13]

In [333]: Y=sparse.lil_matrix((7,7),dtype=int)
In [334]: for i in range(15):
     ...:     for j in range(e):
     ...:         if i in new_nodes and j in new_nodes:
     ...:             if X[i,j]:
     ...:                 Y[new_nodes.index(i),new_nodes.index(j)]=1
     ...:                 
In [335]: Y
Out[335]: 
<7x7 sparse matrix of type '<class 'numpy.int32'>'
    with 5 stored elements in LInked List format>
In [336]: Y.A
Out[336]: 
array([[0, 0, 0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 1, 0],
       [0, 0, 0, 0, 0, 1, 1],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0]])

这与使用 new_nodes 选择行和列相同:

In [337]: X[np.ix_(new_nodes,new_nodes)]
Out[337]: 
<7x7 sparse matrix of type '<class 'numpy.int32'>'
    with 5 stored elements in LInked List format>
In [338]: _.A
Out[338]: 
array([[0, 0, 0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 1, 0],
       [0, 0, 0, 0, 0, 1, 1],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0]])

对于密集数组，这种索引速度更快:

In [341]: timeit X[np.ix_(new_nodes,new_nodes)]
188 µs ± 1.3 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
In [342]: timeit X[np.ix_(new_nodes,new_nodes)].A
222 µs ± 6.77 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
In [343]: timeit X.A[np.ix_(new_nodes,new_nodes)]
62 µs ± 654 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

密集数组方法可能会遇到内存错误。但稀疏索引也会带来内存问题。

Sparse matrix slicing memory error