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

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

根据你的内存有多大，你可以创建一个邻接矩阵作为 scipy.sparse.coo_matrix（即只要两个节点连接就具有 1 而在其他地方为零的矩阵），将其转换为另一种类型的稀疏矩阵然后走广场。该矩阵的条目恰好位于二阶连接存在的位置。条目的值甚至告诉您长度为二的节点之间存在多少条路径。

Answer 2

我写了一些代码来实现 obachtos and using 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-core/8 GB PC 上，执行时间为 4.1 分钟。 OP的问题还要大几个数量级。 dask distributed 包应该允许在一个足够大的集群上使用类似于运行的代码来完成任务。

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

Efficient algorithm to find 2-step neighbors for all vertices in a directed graph

algorithm

numpy

graph-algorithm