有效地使用图形工具

Question

经过深思熟虑，我最终决定post这个问题在这里。几天前，我开始使用 graph-tool 来做各种事情。在那之前我一直在使用Networkx。我已经看到了与它的特定方面相关的令人印象深刻的 performance comparision and thought that everything would be simple enough. However, I immediately ran into the speed issue and 。我得到了一个令我满意的快速答复。但是，现在这个速度问题时不时地困扰着我，我找不到任何与有效使用它相关的 graph-tool 文档。例如，从我上一个问题的答案中，我开始意识到最好将所有边加在一起而不是一条一条地添加，这是一个非常重要的注意点，但没有在任何地方提到过！我现在有两个类似的问题：

(1) 如何选择给定节点的随机邻居？我只能看到以下解决方案：

nbr = np.random.choice(list(v.all_neighbours()))

因为v.all_neighbours()是一个生成器，我必须把它转换成列表来选择一个随机元素。这会减慢代码速度，但我看不到更好的方法。

(2) 我想为图中的每个顶点分配一个一维向量（list 可以吗？），稍后我将以特定方式交换和修改它们。这只是一个属性地图，我想查看一些有关如何有效使用它的文档。但是，我找不到任何东西。

(3) 我正在尝试在某个本身随时间变化的网络中模拟 triadic closure。因此，在每个时间步，我都需要有关图中每个顶点的邻居的信息。同样，我必须创建一个列表（或 numpy 数组）：

nbrs = [w for w in v.neighbours()]

这大大降低了我的代码速度。这意味着我没有正确执行此操作，但我找不到任何文档可以告诉我如何在图形工具中有效地使用邻居。

我为相同任务编写的 Networkx 程序以某种方式完全胜过图形工具代码，我根本无法购买。

此列表可能会增加，因此如果有人能向我指出一些关于有效使用图形工具的文档，除了回答上述具体问题之外，我将非常高兴。

提前致谢。

Answer 1

我会尝试做出更多“graph-tool 特定”的回答：

1) 实际上这个与 python 有关，所以您可能想使用 this thread using random.shuffle 中的解决方案但是，如果您要重复执行此操作（并且如果您有足够的可用内存），我认为最好将邻接矩阵作为 scipy 稀疏矩阵然后使用该矩阵：

import graph_tool
from graph_tool.spectral import adjacency
import numpy as np

g = graph_tool.Graph()
g.add_vertex(100)
edges = np.random.randint(0, 100, (500,2))
g.add_edge_list(edges)

mat = adjacency(g).tolil()
rows = mat.rows.copy() # mat.rows = in-neighbours for each vertex
map(np.random.shuffle, rows)
rnd_neighbours = { i:row[0] for i, row in enumerate(rows) if row }

其中 rnd_neighbours 包含每个入度非零的顶点的一个随机邻居的索引。

2) 阅读 graph-tool documentation regarding PropertyMaps and the detailed version，list 被接受为 python::object 或简称 object。然后，您可以将它们作为 PropertyMap.

中的元素进行访问

3) 对于三元闭包，请查看邮件列表中的clustering module and at this thread。

编辑：顺便说一下，我忘了说了，但是你可以在 graph-tool。虽然无法在文档中找到它...但是这里是 the source.

Answer 2

您可以访问邻居和顶点作为数组，这将加速您的代码，如文档中所述：https://graph-tool.skewed.de/static/doc/quickstart.html#fast-iteration-over-vertices-and-edges

例如，而不是做：

nbr = np.random.choice(list(v.out_neighbours()))

你应该做的：

nbr = np.random.choice(g.get_out_neighbours(v))

这应该快得多，因为使用数组而不是列表。

有效地使用图形工具

Using a graph-tool efficiently

python

numpy

graph

networkx

graph-tool