如何在graph-tool中高效找到二阶邻居？

Question

我正在使用图形工具，想要找到节点的二阶邻居（不是节点本身或原始邻居的邻居的邻居）。我认为使用 graph-tool 的内置拓扑函数可能会更快，所以我尝试了

# Here g is the digraph, and node is the vertex whose neighbors we want
d = gt.topology.shortest_distance(g,g.vertex(node),max_dist=2)
f = gt.GraphView(g,vfilt=d.a == radius)
second_neighbors = f.vertices()

但是，即使在大型图上，这似乎也比直接迭代慢得多。对于大型网络，我怎样才能快速做到这一点？

Answer 1

使用 iter_out_neighbors 并收集 Python 集合中的节点确实应该比使用中间

GraphView

对象更快。这是一个例子：

import graph_tool.collection

g = graph_tool.collection.data['serengeti-foodweb']
start_node = g.vertex(22)

so_neighbors = set()
exclude = set()
exclude.add(start_node)
for n1 in g.vertex(start_node).out_neighbors():
    exclude.add(n1)
    for n2 in n1.out_neighbors():
        so_neighbors.add(n2)
so_neighbors.difference_update(exclude)

这是使用 Jupyter 笔记本中的网络可视化包 gravis 对结果进行的目视检查。起始节点 22 为绿色，二阶邻居为红色，我将鼠标悬停在一阶邻居 132 上以突出显示其直接周围环境。免责声明：我是 gravis 的作者。它可用于轻松创建来自 graph-tool、NetworkX、igraph 和 Python 中的一些其他网络包的图形的交互式可视化。