algorithm - 为有向图中的所有顶点查找两步邻居的高效算法

Question

我有一个 csv 格式 (~14GB) 的大型有向图，其边表示为以下格式的整数:

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

node1 是边的起点，node2 是边的终点。边按 node1 分组(可以按 node2 分组)。

我需要为所有节点生成两步邻居。格式如下:

node1,node2,node3
3213741,6532710,5347128

我的想法是复制边并按node2排序，所以有两个表t1.node1,t1.node2和t2.node1,t2.node2，然后在 t1.node1 == t2.node1 和 t1.node1 != t2.node2 时以某种方式连接这两个表。但这看起来太慢了。是否有任何更好的算法或任何算法可以利用数据按 node1 分组的事实？我更喜欢 Numpy。谢谢。

Answer 1

我写了一些代码来实现 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包应允许与此类似的代码在足够大的集群上运行任务。