1

I am storing graph with two types of relationships using sparse lil_matrix format. This is how I am doing:

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

I would like to prune the network containing 50% of the nodes only. The way I am approaching this by:

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

This is not very efficient way in the case if the original matrix (X) is huge. Is there any fastest or smartest way to prune this ?

Mohan Timilsina
  • 490
  • 6
  • 25
  • On a quick read it is hard to visualize what your pruning is doing. But I can imagine two ways to improve this. 1) figure out how to do this with dense arrays and whole array operations. 2) explore structures with less overhead. For example a `dok` matrix, or even a plain dictionary with `(i,j)` tuple keys. You aren't using any special sparse matrix capabilities. – hpaulj Sep 19 '17 at 19:18

1 Answers1

1

Focusing on just on matrix:

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

This is the same as selecting rows and columns with 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]])

This indexing is faster with dense arrays:

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)

The dense array approach may run into memory errors. But sparse indexing can also have memory problems.

Sparse matrix slicing memory error

hpaulj
  • 221,503
  • 14
  • 230
  • 353