加速图中的采样

Question

我最近在 Python 中使用图形采样。我的工作示例如下：

for enx, wlen in enumerate(wlen_dist):
    for j in range(wlen):
        node_container = queue.Queue(maxsize=200000000)
        node_container.put(node_name)
        tmp_walk = [] # [node_name]
        while not node_container.empty():
            nod = node_container.get()
            neighs = list(network.neighbors(nod))
            tar = random.choice(neighs)
            node_container.put(tar)
            if len(tmp_walk) > enx+1:
                break
            tmp_walk.append(tar)
       some_container.append(tmp_walk)

其中 wlen 是长度为 enx 的路径的样本数，我只是将步数保存到 some_container（这里并不重要）。 wlen_dist 例如：

[1000,500,100]

在这里，获得了 1000 个长度为 2 的步行样本、500 个长度为 3 的样本和 100 个长度为 4 的样本。 networkx 是一个 networkX 图。我想知道，如何加速这样的代码（我是这部分的新手）。

我的想法：

使用 Numba 并将单独的 walks 包装到一个方法中
以某种方式使用 Cython
用C++全部重写并以某种方式调用它

我很乐意提供任何想法和反馈，谢谢！

Answer 1

图形嵌入中经常使用的一个想法是重用部分随机游走的想法：

如果您有一个访问节点 a_1, a_2, a_3 的随机游走，您可以将其视为一个长度为 3 的随机游走和 2 个长度为 2 的随机游走（a_1, a_2 和 a_2, a_3 ).

这可以推广到更长的游走，因此您的长度为 4 的随机游走包含 2 个长度为 3 的随机游走和 3 个长度为 2 的随机游走。

加速图中的采样

Speeding up sampling in a graph

python

graph

networkx

numba