有效的算法来找到所有顶点两步骤邻居有向图

我具有CSV格式边缘的大向图（〜14GB）表示为以下列格式的整数：有效的算法来找到所有顶点两步骤邻居有向图

node1,node2 
3213741,23521361 
3213741,6532710 
3213741,12340611 
3213741,6457392 
3213741,9682135 
6567133,12956771 
6567133,2386

node1是边缘开始，node2是边缘结束的地方。边缘按node1分组（可按node2分组）。

我需要为所有节点生成两步邻居。这是按以下格式：

node1,node2,node3 
3213741,6532710,5347128

我的想法是让边缘的副本，并通过节点2排序，这样有两个表t1.node1,t1.node2和t2.node1,t2.node2，然后以某种方式连接这两个表时t1.node1 == t2.node1和t1.node1 != t2.node2。但是这看起来太慢了。有没有更好的算法或算法可以利用数据按node1分组的事实？我更喜欢Numpy。谢谢。

来源

2017-05-08 Fenwick

这在SQL中会相当简单。既然你已经在csv中拥有了它，你可以导入到关系数据库并对其运行查询。 – mba12

没有帮助实际的问题，但你可能想看看[h5py]（http://docs.h5py.org/en/latest/）来保存你的数据。这可以节省大量空间并大大加快加载/节省。 – obachtos

我写了一些代码，实现由obachtos提出的稀疏矩阵的方法，并使用dask并联在单个节点上运行：

import numpy as np 
import pandas as pd 
import dask 
import time 
from scipy.sparse import coo_matrix 

np.random.seed(1) 

# Fabricate some data 
elem = int(1e7) 
rng = int(1e5) 
gr = np.random.randint(0, rng, elem * 2, np.uint32) 
gr = gr.reshape((elem, 2)) 
gr = gr[np.argwhere(gr[:, 0] != gr[:, 1])] 
gr = gr.reshape(-1, 2) 
grdf = pd.DataFrame(data=gr) 
gr = grdf.drop_duplicates().values 

def coord2adjacency(coords, shp, order, chunksize): 
    grsp = coo_matrix((np.ones(gr.shape[0]), (gr[:, 0], gr[:, 1])), 
         shape=(shp, shp)) 
    grcsr = grsp.tocsr() 
    adj = grcsr**order 
    return adj 

adjspdel = dask.delayed(coord2adjacency, 
         pure=True, nout=1, traverse=False)(gr, shp=rng, 
                  order=2, 
                  chunksize=5000) 
print('Computing an adjacency matrix of order {ordr} from {n} coordinates.'\ 
     .format(ordr=2, n=gr.shape[0])) 
t0 = time.time() 
adjsp = adjspdel.compute() 
print('Execution time: {tm} minutes.'.format(tm=(time.time() - t0)/60))

在我的4核/ 8 GB PC，执行时间为4.1分钟。 OP的问题还有几个数量级的问题。 dask distributed程序包应允许与此类似的代码在足够大的任务集群上运行。

来源

2017-05-11 22:43:27 blueogive

取决于你的内存有多大，你可以创建一个邻接矩阵作为scipy.sparse.coo_matrix（即一个矩阵，每当有两个节点连接，其他地方有零时），将其转换为另一种稀疏矩阵，然后取平方。这个矩阵的条目正好在二阶连接存在的地方。条目的值甚至会告诉您在长度为2的节点之间存在多少路径。

来源

2017-05-09 10:19:28 obachtos

有效的算法来找到所有顶点两步骤邻居有向图

回答

相关问题